确定一个点是否在3D网格内的算法

Question

确定一个点是否在3D网格内的算法

26

什么是快速算法来确定一个点是否在3D网格内？为简单起见，您可以假设该网格全部由三角形组成，没有孔洞。目前我所知道的一种流行的方法是通过计算射线/三角形交点的数量来确定射线是否穿过网格。它必须是快速的，因为我要用它来进行触觉医学模拟。因此我不能测试所有三角形的射线相交。我需要某种散列或树数据结构来存储三角形，以帮助确定哪些三角形是相关的。此外，我知道如果我有任意的顶点的2D投影，则只需要进行简单的点/三角形相交测试。但是，我仍然需要知道哪些三角形是相关的，并且还需要知道哪些三角形在点的前面，并只测试这些三角形。

- Jeff Jenkins

Jeff，我看到了你检查一个点是否在网格内的方法。在获取每个三角形的AABB之后，如何按照你所说的进行哈希步骤呢？每个三角形的AABB是（xmin，xmax，ymin，ymax，zmin，zmax），那么得到的哈希值怎么样呢？ Chao - user1202740

3个回答

4

这个算法只有在你有很多查询来证明构建数据结构的时间是有效的情况下才有效。将空间分成相等大小的立方体（稍后我们会确定大小）。对于每个立方体，知道至少有一个点的三角形。丢弃不包含任何内容的立方体。按照维基百科上介绍的方式进行光线投射算法，但是不要测试线段是否与每个三角形相交，而是获取所有与线段相交的立方体，然后仅对这些立方体中的三角形进行光线投射。注意不要多次测试同一个三角形，因为它存在于两个立方体中。
找到适当的立方体大小很棘手，它既不能太大也不能太小。只能通过反复试验来找到。假设立方体数量是c，三角形数量是t。
一个立方体中三角形的平均数量是t/c
k是与光线相交的立方体的平均数量
线-立方体相交+其中三角形的线-三角形相交必须最小化
c+k*t/c=minimal => c=sqrt(t*k)
您需要测试立方体大小的值，直到c=sqrt(t*k)为真
立方体大小的一个很好的起点猜测是sqrt(mesh width)
为了有一些视角，对于100万个三角形，您将测试大约1k个交点

- titus

进行一次射线投射算法，朝哪个方向？ - rwols

@rwols：只要光线穿过奇数个三角形，它就在网格中，方向无所谓。 - Willem Van Onsem

-1

当涉及到准确性时，射线三角形相交似乎是一个很好的算法。维基上有一些更多的算法。我在这里链接它，但你可能已经看过了。

也许你可以通过维护点与构成它们的平面之间的关系矩阵来进行改进？这个主题似乎是学术界的研究课题。不确定如何获取更多相关讨论。

- vpit3833

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jeff Jenkins · Accepted Answer

我解决了自己的问题。基本上，我采用任意的2D投影（舍弃其中一个坐标），将三角形的AABB（轴对齐边界框）哈希到2D数组中。（如Titus所述的一组3D立方体过于浪费，因为它只能给你带来恒定的加速。）使用2D数组和正在测试的点的2D投影，得到一小组三角形，对其进行3D射线/三角形交集测试（参见3D射线、段、平面和三角形的相交），并计算射线与Z坐标（被舍弃的坐标）大于点的Z坐标的交点数。偶数次交点意味着它在网格外面。奇数次交点意味着它在网格内部。这种方法不仅快速，而且非常容易实现（这正是我要找的）。