intersection - 射线三角相交

Question

如何测试intersession ray和triangle，如果存在如何获得从射线原点到交点的距离？如果在我的程序中我必须检查 1 条射线到 ~10000 个三角形，我可以使用什么优化？

Answer 1

单个多边形光线相交测试很简单，只需确保光线至少穿过它的一侧（单独检查它们）或穿过由其两侧之间的三角形定义的平面。优化涉及不检查光线完全没有机会穿过的多边形。根据您正在处理的维度的高度、区域的大小以及您正在处理的多边形数量，最典型的优化是quadtrees、octrees和kd-trees。这也大致是实现难度的顺序（尽管四叉树和八叉树非常相似）。

Answer 2

可能是我第一次需要实现它时，我查看了这些幻灯片，我发现它们非常有用。

http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld016.htm

首先确保你了解它是如何工作的，然后你可以做很多不同的优化。例如：

if (dot(V, N) >= 0)     // no intersection - ray points away from the triangle face
if (dot(P0, N) + d < 0) // no intersection - ray origin is behind the triangle face

我曾经做过的另一个想法是，一旦我找到了光线和面部的交点。我曾经在 2D 中检查三角形内的点，而我正在用法线的最大绝对值将轴归零...如果 abs(Nx) > abs(Ny) > abs(Nz) 我会检查YZ平面。

我可以建议另一个简单的实现优化找到外接圆的中心和半径（这取决于你是否需要经常这样做，你可以选择一个更轻松的中心，比如质心）。现在这个点和半径在你的三角形周围定义了一个边界球。现在您可以进行更快的光线球体剔除。

http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld012.htm

不要求解整个多项式，您不需要射线/球体的交点，只需检查现有根即可。

您还可以进行许多其他优化，例如：如果您的顶点和法线可以安排在对 SSE 更友好的结构中，您可以一次进行 4 次检查。大致可以快2.5倍左右。