四面体网格中的点定位

Question

在四面体网格中，是否有任何已证实的数据结构来定位四面体，其中四面体都是不相交的，但正在“接触”对方？也就是说，大多数面都是两个四面体的面。

locationI的意思是，我想找出给定的四面体点中的哪一个，或者它是否位于任何四面体中。

到目前为止，我已经尝试过：

1. 一棵简单的KD树。这对于我的需要来说太慢了，因为树的平均深度很高，而且我在每片叶子上还有很多四面体需要测试。
2. 包含每个细胞所有相交四面体的网格。这似乎好得多，但仍然不够快。首先，网格包含了大量的空单元格，因为我的整体网格不是很“四边形”。其次，大多数实际上含有四面体的细胞都含有大量的四面体(10+)。我想这是因为很多四面体共享每个顶点，当一个顶点在一个单元中，它的所有相邻的四面体也都是。

关于输入数据的进一步信息:网格通常不是凸的，可能有孔或包含。虽然后两者有点不太可能，但我必须处理它们，这使得“步行”没有(昂贵和复杂？)预处理。

Answer 1

如果您正在处理由具有邻接信息的四面体组成的三维三角剖分，则只需使用步行即可。这是一个标准的点定位技术，并使用三维定位测试。

有关更多信息，请参阅Olivier等人的论文“在三角剖分中行走”()。(在谷歌上搜索它，你会发现它的PDF格式。)

Answer 2

一些快速思考:八叉树将类似于您的网格方法，但允许您快速忽略空网格，并细分太满的网格。

另外，你没有提到你是如何测试一个点是否在四面体内。我看过它已经有一段时间了，但是也许重心坐标可以加速你的四面体点测试？或扫描线算法快速排除基于四面体顶点的四面体顶点，这些顶点明显位于扫描线的错误一侧，包含点。

Answer 3

诚然，这是一次小小的头脑风暴。

也许是kdTree的一种习惯，它使用面对齐平面而不是轴对齐平面。

如果一个点在一个四面体的所有四个平面的“正确”边上，那么它必须在四面体内部。(对吧？)如果你在任何一个平面上都是错误的，那么你不仅可以排除当前的重音，还可以排除飞机那一侧的任何其他人。

看起来，您应该能够构建一棵树，其中每个节点都是一个平面，而叶节点意味着您在一个特定的单元中(假设tet从不相交)。树可能很深，但是由于每个测试只针对一个平面(而不是一个更昂贵的三角形测试)，而且由于叶节点给出的答案正好是一个，所以看起来应该是快速的。

有效地建造这棵树可能会很困难。