确定点是否位于 3D 网格内部的算法

Question

用于确定点是否位于 3D 网格内部的快速算法是什么？为简单起见，您可以假设网格都是三角形并且没有孔。

到目前为止我所知道的是，确定光线是否穿过网格的一种流行方法是计算光线/三角形相交的数量。它必须很快，因为我正在使用它进行触觉医学模拟。所以我无法测试所有三角形的射线相交。我需要某种哈希或树数据结构来存储三角形，以帮助确定哪个三角形是相关的。

另外，我知道如果我有任意顶点的二维投影，则需要一个简单的点/三角形相交测试。但是，我仍然需要知道哪些三角形是相关的，此外，哪些三角形位于点前面，并且只测试这些三角形。

Answer 1

我解决了我自己的问题。基本上，我采用任意 2D 投影（扔掉其中一个坐标），并将三角形的 AABB（轴对齐边界框）散列到 2D 数组。 （titus 提到的一组 3D 立方体是多余的，因为它只能给你一个常数因子加速。）使用 2D 数组和你正在测试的点的 2D 投影来获得一小组三角形，你可以这样做3D 射线/三角形相交测试（请参阅相交3D 中的射线、线段、平面和三角形）并计算 z 坐标（抛出的坐标）大于点的 z 坐标的射线交点的三角形数量。偶数个交点意味着它在网格之外。奇数个交点意味着它在网格内部。这种方法不仅速度快，而且非常容易实现（这正是我所寻找的）。

Answer 2

仅当您有许多查询来证明构建数据结构的时间合理时，该算法才有效。

将空间分成大小相等的立方体（稍后我们会计算出大小）。对于每个立方体，知道哪些三角形至少有一个点。丢弃不含任何东西的立方体。按照维基百科上的介绍进行光线投射算法，但不是测试直线是否与每个三角形相交，而是获取与直线相交的所有立方体，然后仅对这些立方体中的三角形进行光线投射。注意不要多次测试同一个三角形，因为它存在于两个立方体中。
找到合适的立方体尺寸很棘手，它不应该太大或太小。它只能通过反复试验才能找到。
假设立方体数量为c，三角形数量为t。
立方体中三角形的平均数量为t/c
k 是与射线相交的立方体的平均数量
这些立方体中的线-立方体相交 + 线-三角形相交必须最小
c+k*t/c=minimal => c=sqrt(t*k)
您必须测试立方体大小的值，直到 c=sqrt(t*k) 为 true
对于立方体大小的一个很好的起始猜测是 sqrt(mesh width)
为了获得一些视角，对于 1M 个三角形，您将按 1k 个交叉点的顺序进行测试

Answer 3

我没有从 mesh_contains 得到结果
我使用从修剪网格获取交点
locations, index_ray, index_tri = Mesh.ray.intersects_location( ray_origins=ray_origins, ray_directions=ray_directions,multiple_hits=True)

和

for i in range(len(locations)):
print("location={0}",locations[i])
# locations[i] -=0.5
print("location={0}",locations[i])
print(Mesh.contains(locations[i].reshape(-1,3)))
print(mesh_contains(Mesh.triangles,locations[i].reshape(-1,3)))

mesh_contains 内网格内的检查点，点和三角形已缩放
我可以知道缩放的原因吗

self.scale = (resolution - 1) / (self.bounds[1] - self.bounds[0])
    self.translate = 0.5 - self.scale * self.bounds[0]
self._triangles = self.rescale(triangles)

Answer 4

就准确性而言，射线三角形交集似乎是一个很好的算法。 Wiki 还有更多算法。我将其链接到此处，但您可能已经看到了。

您能否即兴维护点和它们作为顶点的平面之间的关系矩阵？这个主题似乎是学术界研究的一个话题。不知道如何访问与此相关的更多讨论。