射线三角形插入 [英] Ray-triangle intersetion

问题描述

如何测试相切射线和三角形，以及是否存在从射线原点到相交点的距离？
我可以使用什么优化方法，如果在我的程序中必须检查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 ??

推荐答案

单个多边形射线相交测试是微不足道的，仅涉及确保射线至少横穿其一侧（单独检查）或横穿其两侧之间的三角形所定义的平面。优化涉及到不检查多边形是否完全没有交叉的机会。 四叉树，八叉树和 kd树。这也大约是实现难度的顺序（尽管四叉树和八叉树非常相似）。

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).

这篇关于射线三角形插入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！