四面体网格中的点位置

Question

四面体网格中的点位置是否有任何经过验证的数据结构,其中四面体都是不相交的,但彼此"接触"？即大多数面孔都是正好两个四面体的面孔.

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

到目前为止,我尝试过:

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

2. 一个网格,包含每个单元格的所有交叉四面体.这似乎工作得更好,但仍然不够快.首先,网格包含许多空单元格,因为我的整体网格不是非常"四四方方".其次,大多数实际上含有四面体的细胞确实含有大量细胞(10+).我想这是因为很多四面体共享每个顶点,一旦顶点在一个单元格中,所有相邻的四面体也是如此.

关于输入数据的一些进一步信息:网格通常不是凸的并且可以具有孔或内含物.虽然最后两个有点不太可能,但我必须处理它们,如果没有(昂贵和复杂的？)预处理,这使得"行走"变得不可能.

Answer 1

如果您正在处理由具有邻接信息的四面体组成的3D三角测量,您可以使用步行.这是点位置的标准技术,并使用3D 定向测试.

有关更多信息,请参阅Olivier Devillers等人的三角剖分文章.(谷歌它,你会找到它的PDF.)

Answer 2

诚然，这有点动脑子。

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

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

看来您应该能够构建一棵树，其中每个节点都是单个平面，并且叶节点意味着您位于一个特定的四边形中（假设四边形从不相交）。树可能很深，但由于每个测试仅针对一个平面（而不是更昂贵的三角形测试），并且由于叶节点恰好为您提供了一个答案，因此看起来它应该很快。

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