四面体网格中的点位置定位

Question

有没有已经证明有效的数据结构，可以用于在四面体网格中进行点定位，其中四面体都是不相交但“相互接触”的？即大多数面都是正好两个四面体的面。

通过“定位”，我指的是要找出给定点位于哪个四面体中，或者如果它不在任何四面体中，则确定它不在任何四面体中。

到目前为止，我尝试过：

1. 一个简单的KD-Tree。这对我的需求来说太慢了，因为平均树深度非常高，每个叶子节点仍然需要测试许多单独的四面体。

2. 包含每个单元格中所有相交四面体的网格。这似乎效果要好得多，但仍然不够快。首先，网格包含了很多空单元格，因为我的整个网格不是非常“盒状”。其次，大多数实际包含四面体的单元格，都包含了很多四面体（10+）。我想这是因为许多四面体共享每个顶点，一旦一个顶点在一个单元格中，它的所有相邻四面体也会在其中。

关于输入数据的一些进一步信息：该网格通常不是凸的，可能具有孔或包含物。虽然后两个情况不太可能发生，但我必须处理它们，这使得“行走”变得不可能（需要昂贵和复杂的预处理）。

- ltjax

---

你尝试过以下方法吗（找不到参考资料，所以我简要描述一下）？从任意一个四面体开始。确定一个面，相对于该点在四面体外（与第四个四面体顶点的另一侧）。走到该面的另一侧的四面体上。再次检查。如果没有这样的面，则该点在当前四面体中。该算法适用于凸网格。它是否符合您的需求？ - Nico Schertler

可能吧，虽然填补这些空缺可能会很困难。但如果你愿意的话，可以试一试。 - Nico Schertler

也许在你的情况下，区间树可以定位较少数量的四面体进行测试。深度可能类似于KD-Tree。 - Ante

我不知道你的应用程序是什么，以及你需要做出什么级别的保证，但有一些近似搜索技术可以非常快速地运行，并且有良好的实现可用。特别是，我会看一下FLANN，这是一个用于近似最近邻搜索的库，已经得到了相当多的优化和性能关注。这只会执行最近点搜索，但我认为这对于作为KD树的重大改进是值得指出的。 - Eric

基本上，这意味着您有机会找到第二近的点而不是最近的点。FLANN具有可调参数（目标精度），以控制速度/准确性平衡。如果您想要，还可以查看[ANN]（http://www.cs.umd.edu/~mount/ANN/）库，该库具有近似和精确最近邻搜索的有效实现。 - Eric

Answer 1

如果你正在处理一个由四面体相邻信息组成的三维三角剖分，你可以使用走路算法。这是一种用于点定位的标准技术，使用三维方向测试。

更多信息请参见Olivier Devillers等人的论文在三角剖分中行走。（在谷歌上搜索即可找到其PDF文件。）

- Ashwin Nanjappa

Answer 2

一些快速的想法：八叉树与您的网格方法类似，但允许您快速忽略空网格，并细分过于充实的网格。

此外，您没有提及如何测试点是否位于四面体内。虽然我已经有一段时间没有看过它了，但也许重心坐标可以加速您的点-四面体测试？或者使用扫描线算法，根据明显位于扫描线错误侧的四面体顶点来快速排除包含该点的四面体。

- River

---

我已经在使用重心坐标了。你会如何在这里应用扫描线算法呢？ - ltjax

一个简单的方法是按照点的x坐标进行排序。任何四面体，如果它的所有点的x坐标都小于你感兴趣的点的x坐标（同样地，都大于），那么它就不可能是你感兴趣的四面体。 - River

Answer 3

这可能有点头脑风暴的感觉。

也许可以使用面对齐平面而不是轴对齐平面的kdTree的自定义。

如果一个点在四面体的所有四个平面的“正确”一侧，那么它必须在四面体内部。 （对吗？）如果您在任何平面的错误一侧，那么您不仅可以排除当前的四面体，还可以排除该平面一侧的任何其他四面体。

似乎应该能够构建一棵树，其中每个节点都是单个平面，叶节点意味着您在一个特定的四面体中（假设四面体永远不会相交）。 树可能很深，但由于每个测试只针对一个平面（而不是更昂贵的三角形测试），并且由于叶节点给出了确切的答案，因此它似乎应该很快。

有效地构建树可能会证明很困难。

- Adrian McCarthy

---

那不就是普通的BSP树吗？需要进行大量的分割或复制。 - ltjax

@ltjax：不，这不是普通的BSP。使用普通的BSP树，您遍历到一个叶子节点，该节点会给出要测试的三角形列表。而使用我试图描述的方法，遍历树到达叶子节点会给出一个特定的三角形，该点位于其中，或者指示该点不在任何三角形中。它将分区与对三角形进行测试相结合。 - Adrian McCarthy

这还是相当普通的。我认为重复数量和平均树深度会使这变得不可行。请记住，如果您分割四面体，则可能最多会得到六个四面体。而且，除非使用更“正交”的东西（如KD-Tree或Octree），否则构建树时会出现许多精度问题。 - ltjax

我不确定我理解您关于分割四面体的评论。这些不会是任意平面，而是包含四面体侧面的相同平面。这里不涉及分割。每个向下的分支有效地排除了完全位于测试平面另一侧的四面体。无需分割。 - Adrian McCarthy

选择平面两侧的四面体怎么办？ - ltjax