8

四面体网格中的点位置是否有任何经过验证的数据结构，其中四面体都是不相交但相互“接触”的？即大多数面是正好两个四面体的面。

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

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

  1. 一个简单的KD树。这对我的需求来说太慢了，因为平均树深度非常高，而且我仍然有很多单独的四面体要在每片叶子上进行测试。

  2. 一个网格，其中包含每个单元格的所有相交四面体。这似乎工作得更好，但仍然不够快。首先，网格包含很多空单元格，因为我的整体网格不是很“四四方方”。其次，实际上确实包含四面体的大多数细胞确实包含很多（10+）。我想这是因为很多四面体共享每个顶点，一旦一个顶点在一个单元格中，它的所有相邻四面体也是。

有关输入数据的一些进一步信息： 网格通常不是凸面的，可能有孔或夹杂物。尽管最后两个不太可能，但我必须处理它们，这使得如果没有（昂贵且复杂的？）预处理，“行走”是不可能的。

4

3 回答 3

6

如果您正在处理由具有邻接信息的四面体组成的 3D 三角剖分，则可以只使用walk。这是用于点定位的标准技术并使用 3D方向测试。

有关更多信息，请参阅Olivier Devlers 等人的论文《在三角测量中行走》。（谷歌它，你会找到它的PDF。）

于 2012-08-08T07:28:03.163 回答
1

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

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

于 2012-08-07T21:37:09.223 回答
0

诚然，这有点头脑风暴。

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

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

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

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

于 2012-08-07T20:06:29.540 回答