确定一个点是否在 3D 网格内的快速算法是什么?为简单起见,您可以假设网格都是三角形并且没有孔。
目前我所知道的是,确定光线是否穿过网格的一种流行方法是计算光线/三角形相交的数量。它必须很快,因为我将它用于触觉医学模拟。所以我无法测试所有三角形的光线相交。我需要某种哈希或树数据结构来存储三角形,以帮助确定哪个三角形是相关的。
另外,我知道如果我有任何顶点的任意 2D 投影,一个简单的点/三角形相交测试都是必要的。但是,我仍然需要知道哪些三角形是相关的,此外,哪些三角形位于点的前面,并且只测试这些三角形。
最佳答案
我解决了我自己的问题。基本上,我采用任意 2D 投影(抛出其中一个坐标),并将三角形的 AABB(轴对齐边界框)散列到 2D 数组。 (提图斯提到的一组 3D 立方体是矫枉过正,因为它只会给你一个常数因子加速。)使用 2D 数组和你正在测试的点的 2D 投影来得到一小组三角形,你做一个3D 射线/三角形相交测试(参见 Intersections of Rays, Segments, Planes and Triangles in 3D )并计算 z 坐标(抛出的坐标)大于点的 z 坐标的射线相交的三角形数。偶数个交叉点意味着它在网格之外。奇数个交叉点意味着它在网格内部。这种方法不仅速度快,而且非常容易实现(这正是我一直在寻找的)。
关于确定一个点是否在 3D 网格内的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6554313/