如何高效地检测光线和网格的交点检测？

Question

我在OpenGL ES应用程序中为iPhone提供了几个3D模型，并且在某些时候我希望用户触摸屏幕并对其执行操作。问题是要识别屏幕上呈现的内容中的哪些被触摸。为了达到这个目的，我计算了OpenGL常见问题解答中提出的拾取光线，现在我想检测它是否与任何模型相交。

我抬头看看irrlicht源代码，发现我可以计算光线和每个单个模型三角形之间的交集（他们通过计算光线是否先与三角形平面相交，然后通过查看相交点落入三角形，但是如here所述，存在更有效的方式）。

我的问题是：我真的需要为每个模型的每个三角形做所有这些计算吗？没有更好的方法（可能不是那么精确）来达到类似的结果吗？

Answer 1

你很对，有更好的方法来通过树。一种方法是围绕对象构建一个octtree。然后，如果射线与8个线段中的一个相交，则可以检查它的8个子线中的哪一个相交，等等，直到剩下几个三角形进行相交测试为止。另一种方法是建立一个K-d tree。

有很多种方法可以有效地处理这个问题。在ray tracing acceleration structures上查找信息。