射线与三角形相交
如何测试交叉射线和三角形，如果存在如何获得从射线原点到交点的距离？ 如果在我的程序中我必须检查 1 条射线到 ~10000 个三角形，我可以使用什么优化？
How can I test intersesion ray and triangle, and if it exist how to get distance from ray origin to intersection point??
What optimization I can use, if in my program I've got to check 1 ray to ~10000 triangles ??
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
单个多边形射线相交测试很简单，只需确保射线至少穿过其一侧（单独检查它们）或穿过由其两侧之间的三角形定义的平面。优化不检查光线根本没有机会穿过的多边形。根据您工作的维度有多高、区域有多大以及您正在处理的多边形数量，最典型的优化是 四叉树、八叉树 和 kd-trees。这也大约是实现的难度顺序（尽管四叉树和八叉树非常相似）。
A single polygon-ray intersection test is trivial and just involves making sure that the ray crosses at least one side of it (check them individually) or across the plane defined by the triangle between the sides of it. The optimization comes into not checking against polygons that the ray has no chance at all of crossing. Depending on how high of a dimension you're working in, how big the area is, and how many polygons you're dealing with the most typical optimizations are quadtrees, octrees, and kd-trees. This is also approximately the order of difficulty of implementation (although quad and octtrees are very similar).
可能是我第一次需要实现它时，我查看了这些幻灯片，我发现它们非常有用。
http://www.cs.princeton。 edu/courses/archive/fall00/cs426/lectures/raycast/sld016.htm
首先确保您了解它是如何工作的，然后您可以进行许多不同的优化。例如：
我曾经做过的另一个想法是一旦找到光线和面的交点。我曾经在二维中检查三角形内的点，同时用法线的最大绝对值将轴归零......绝对值(Ny)> abs(Nz) 我将在 YZ 平面上进行检查。
我可以建议另一个简单的实现优化，找到外接圆的中心和半径（这取决于您是否需要经常这样做，您可以选择一个更容易的中心，例如质心）。现在这个点和半径定义了三角形周围的边界球体。现在您可以更快地进行光线球体剔除。
http://www.cs.princeton。 edu/courses/archive/fall00/cs426/lectures/raycast/sld012.htm
不要求解整个多项式，您不需要射线/球体的交点，只需检查现有的根。
您还可以进行许多其他优化，例如：如果您的顶点和法线可以排列在更 SSE 友好的结构中，您可以一次进行 4 项检查。大约可以快 2.5 倍左右。
Probably the first time I needed to implement it I looked at these slides, which I find very useful.
http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld016.htm
First make sure you understand how it works then you can do a lot of different optimizations. For example:
Another think I used to do is once I find the intersection point of the ray and the face. I used to do the check for point inside triangle in 2D while I was zeroing the axis with maximum absolute value of the normal... if abs(N.x) > abs(N.y) > abs(N.z) I'll do the check in YZ plane.
I can suggest another simple to implement optimization find the center and radius of the circumscribed circle (well depends if you need to do it often you can choose a easer center like center of mass). Now this point and radius define a bounding sphere around your triangle. Now you can do much faster ray sphere culling.
http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld012.htm
Don't solve the whole polynomial you don't need the intersection point of ray/sphere just check for existing roots.
There are many other optimizations you can do for example: If your vertices and normals can be arranged in more SSE friendly structure you can do 4 checks at a time. Which roughly can go to around 2.5 times faster.