1

给定一个带有点的 3d 实体框。给定一个用四面体网格划分的盒子。两个盒子的尺寸是一样的。

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

我使用了下一个算法：

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

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

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

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

更新 2：我正在尝试在三角测量中实现步行

4

2 回答 2

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][i,j,k]l

可以使用自适应精度算术稳健地执行这些定向测试。Jonathan Shewchuk在这里提供了这样的实现。

于 2014-03-13T19:40:51.400 回答
1

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

确定一个点是在平面的左边还是右边的数学是直截了当的。

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

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

于 2014-03-14T18:36:19.210 回答