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

Question

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

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

我使用了下一个算法：

1. 用八叉树提炼固体
2. 遍历网格中的四面体，并检查它是否与八叉树的分支或叶子相交。(Ratschek & Rockne的算法(
3. 如果它相交，则映射从八角树到四面体的点。

但是算法很慢，而且我在检查盒子和四面体之间的交集时遇到了巨大的问题。

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

更新：我有 200 万个实心点和 200k 四面体

更新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在这里提供了这样的实现。

Answer 2

假设你知道四面体的顶点，你可以检查一个点是否在四面体内，通过检查它是否位于每个平面的left或right侧，比如左边是沿法线指向的一侧。

确定点是在平面的左侧还是右侧的数学方法是直截了当的。

我

找到了另一种方法，但看起来像是我答案的变体。

当然，如果一个点在tet内部，它就会映射到tet。此方法可以作为顶点着色器或OpenCL/CUDA内核实现，这将使它高度并行。