确定一个点是否在 3D 网格内的快速算法是什么？为简单起见，您可以假设网格都是三角形并且没有孔。
到目前为止，我所知道的是，确定光线是否穿过网格的一种流行方法是计算光线/三角形相交的数量。它必须很快，因为我将它用于触觉医学模拟。所以我不能测试所有三角形的光线相交。我需要某种散列或树数据结构来存储三角形，以帮助确定哪个三角形是相关的。
另外，我知道如果我有任何顶点的任意二维投影，那么简单的点/三角形相交测试都是必要的。但是，我仍然需要知道哪些三角形是相关的，此外，哪些三角形位于点的前面并且只测试这些三角形。
我解决了我自己的问题。基本上，我采用任意二维投影（丢弃其中一个坐标），并将三角形的 AABB（轴对齐边界框）散列到二维数组中。（titus 提到的一组 3D 立方体是多余的，因为它只会给你一个常数因子加速。）使用 2D 数组和你正在测试的点的 2D 投影来获得一小组三角形，你可以这样做3D 射线/三角形相交测试（请参阅 3D中的射线、线段、平面和三角形的相交）) 并计算射线交点的三角形数量，其中 z 坐标（抛出的坐标）大于该点的 z 坐标。偶数个交叉点意味着它在网格之外。奇数个交叉点意味着它在网格内。这种方法不仅速度快，而且很容易实现（这正是我想要的）。
只有当您有许多查询来证明构建数据结构的时间是合理的时，这种算法才有效。
将空间分成大小相等的立方体（我们稍后会计算出大小）。对于每个立方体，知道哪些三角形中至少有一个点。丢弃不包含任何东西的立方体。执行维基百科上介绍的光线投射算法，而不是测试线是否与每个三角形相交，获取与线相交的所有立方体，然后仅对这些立方体中的三角形进行射线投射。注意不要多次测试同一个三角形，因为它存在于两个立方体中。
找到合适的立方体尺寸很棘手，它不应该太大或太小。它只能通过反复试验才能找到。比方说number of cubesisc和number of trianglesis t。
立方体中三角形的t/c
k平均数是与射线相交的立方体的平均数
这些立方体中的线立方体交点 + 线三角形交点必须是最小的
c+k*t/c=minimal=>c=sqrt(t*k)
您必须测试立方体大小的值，直到c=sqrt(t*k)为真立方体大小的
一个好的开始猜测是sqrt(mesh width)
要有一些透视图，对于 1M 个三角形，您将按 1k 个交叉点的顺序进行测试
就准确性而言，Ray Triangle Intersection 似乎是一个很好的算法。Wiki有更多算法。我在这里链接它，但你可能已经看过了。
您能否即兴发挥，保持点与它们构成顶点的平面之间的关系矩阵？这个话题似乎是学术界的一个研究课题。不知道如何访问与此相关的更多讨论。