algorithm - 找到射线和多边形之间交点的最快方法是什么？

Question

与问题所问的差不多。最好以伪代码形式回答并引用。正确答案应该重视速度而非简单性。

Answer 1

参见 Intersections of Rays, Segments, Planes and Triangles in 3D .您可以找到对多边形进行三角剖分的方法。

如果您真的需要射线/多边形相交，它位于 Real-Time Rendering 的 16.9| (第 2 版为 13.8)。

We first compute the intersection between the ray and [the plane of the ploygon] pie_p, which is easily done by replacing x by the ray.

 n_p DOT (o + td) + d_p = 0 <=> t = (-d_p - n_p DOT o) / (n_p DOT d)

If the denominator |n_p DOT d| < epsilon, where epsilon is very small number, then the ray is considered parallel to the polygon plane and no intersection occurs. Otherwise, the intersection point, p, of the ray and the polygon plane is computed: p = o + td. Thereafter, the problem of deciding whether p is inside the polygon is reduced from three to two dimentions...

有关详细信息，请参阅本书。