algorithm - 实体框到四面体网格框的映射点

给一个有点的三维立体盒子。给了一个与四面体啮合的盒子。两个盒子的尺寸相同。
我需要找到一个算法，将实体的点映射到网格中相应的四面体。
我使用了下一个算法：
用八叉树优化实体
在网格中的四面体上迭代，检查它是否与八叉树的分支或叶相交。（Ratschek&Rockne算法）
如果相交，则将点从八叉树映射到四面体。
但是算法很慢，而且我在检查长方体和四面体的交集时遇到了很大的问题。
我仍然可以用八叉树，但我绝对需要一些合理的东西来检查交叉口。如有任何意见，将不胜感激。
更新：我有200万个实心点和20万个四面体
更新2：我正在尝试实现三角测量中的行走

最佳答案

一个标准的简化是首先使用轴对齐包围盒计算近似八叉树四面体交叉点。由此产生的交叉口测试非常简单。
然后，一旦遍历到树的叶级，就可以使用精确的测试来确定给定四面体中包含哪些点。
总结一下：

Form an octree T for your points X

for (all tetrahedrons ti in mesh M)

    Form a minimal axis-aligned bounding-box Bi for tetrahedron ti

    Traverse T from root, accumulating a list Li of all leaf nodes
    that overlap with box Bi

    for (all leaf nodes li in list L)
        for (all points pi in leaf node li)

            if (point pi is inside tetrahedron ti /*exact test*/ )
                Associate point pi with tetrahedron ti
            endif

        endfor
    endfor

endfor

该算法在以下条件下是有效的：(i)网格中的点均匀分布，并且X中的四面体具有合理的长宽比。
实现良好性能的关键是确保尽可能高效地实现树遍历步骤。
四面体测试中的一个点可以通过检查给定点是否位于四面体4个面的“内部”侧来完成。给定四面体M，如果点位于平面(ii)的同一侧，则点M位于面pi的“内部”侧，作为“相对”顶点[i,j,k,l]。
利用自适应精度算法可以可靠地进行这些定向测试。Jonathan Shewchuk提供了这样一个实现here。

关于algorithm - 实体框到四面体网格框的映射点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22382176/