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

Question

给定一个带有点的 3d 实体框。给定一个用四面体网格化的盒子。两个盒子的尺寸相同。

我需要找到一种算法，将实体的点映射到网格中的相应四面体。

我使用了下一个算法:

1. 用八叉树优化实体
2. 迭代网格中的四面体并检查它是否与八叉树的分支或叶子相交。 (Ratschek 和 Rockne 的算法)
3. 如果相交，将八叉树中的点映射到四面体。

但是这个算法非常慢，而且我在检查一个盒子和一个四面体之间的交点时遇到了很大的问题。

我仍然可以坚持使用八叉树，但我绝对需要一些合理的东西来检查交叉点。任何评论将不胜感激。

更新:我有 200 万个实体点和 20 万个四面体

更新 2:我正在尝试实现三角剖分行走

Answer 1

一个标准的简化是首先使用轴对齐的边界框计算八叉树-四面体的近似交点。由此产生的交叉测试非常简单。

然后，一旦遍历到树的叶级，就可以使用精确测试来确定给定四面体中包含哪些点。

总结一下:

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 在网格 M 中分布良好，并且 (ii ) M 中的四面体具有合理的纵横比。

实现良好性能的关键是确保尽可能高效地实现树遍历步骤。

四面体中的点测试可以通过检查给定点 pi 是否位于四面体 4 个面的“内部”侧来完成。给定一个四面体 [i,j,k,l]，点 pi 位于面 [i,j,k] 的“内侧”侧 如果它与“相对”顶点 l 位于平面 [i,j,k] 的同一侧。

可以使用自适应精度算法稳健地执行这些方向测试。 Jonathan Shewchuk 提供了这样的实现 here .