八叉树叶节点三角剖分的数据结构与算法

Question

我有一个应用程序，在这个应用程序中，我使用八叉树来存储轴对齐包围框(AABB)的卷网格。

给出一个水密流形三角形网格，我需要：

• 查找AABB是否与表面网格相交或完全位于表面网格内/外部，
• 用相交的AABB夹紧表面网格，生成完全位于每个AABB内的三角形。

三角剖分和包含AABB的八叉树都是动态的。八叉树中的叶节点数量很大。表面网格中的三角形数目要小得多(O(10^9 - 10^13)八叉树节点，而O(10^6)三角形)。

哪种数据结构和算法适合我的问题？

现在我：

• 将三角形存储在与卷网格相同的八叉树中，
• 将每个三角形存储在包含三角形的最小八叉树节点中，
• 用单个AABB裁剪三角形网格，方法是从该AABB遍历到根节点和它的叶，用AABB裁剪每个包含在节点中的三角形。

节点中的三角形在AABB中完全包含，不需要任何“裁剪”( AABB只包含这些三角形)，而从AABB到根的节点中包含的三角形需要裁剪。然而：

• 由于我存储三角形的方式(在包含三角形的最小八叉树节点中)，所以在每个单一八叉树节点内存储的最大三角形数中没有上限，因此在必须在单个AABB上测试的三角形数量中没有上限。
• 如果我只想测试AABB是否与三角形网格相交，我必须测试AABB和根节点之间的所有三角形，这可能很昂贵。理想情况下，我希望有一个非常快速的方法来测试，然后剪辑网格，如果测试是真实的。
• 目前，我没有快速确定节点是否在内部/外部/被网格交叉的方法。我可以构造一个有符号的距离场(这是昂贵的)，或者执行一些光线投射(这也是昂贵的)，也许有一个更好的解决方案，或者我只是需要预先计算一些东西来加快速度，每次我移动三角形网格。
• 移动三角形网格需要操作八叉树(我不知道这是否可以避免)。理想情况下，我希望为三角形网格生成一个八叉树，然后使用单个转换矩阵移动网格。但是，我需要在“包含三角形网格的八叉树”和“卷网格的八叉树”之间进行某种映射。也许这个映射是微不足道的，但我还没有弄清楚。当我移动网格时，这将使我免于操作八叉树，也许所需的坐标转换与裁剪的成本是可以忽略不计的。

Answer 1

与其让一个空间细分结构同时表示体素和三角形，我建议为网格创建一个单独的BVH。你可以在网上找到很多关于BVH构建算法的文章和论文。它可能比八叉树更有效地表示网格。

给定BVH，很容易通过从BVH根开始并遍历到与体素框相交的子节点来确定给定的体素是否可以与网格相交。取决于BVH的质量，即它与网格的匹配程度，许多体素(甚至更高级别的八叉树节点)可能只需几个检查就可以被消除。对于与网格曲面相交的体素，BVH遍历将到达叶子，在那里您可以将三角形累加到一个列表中进行裁剪。

如果BVH构建在网格的局部空间中，则网格可以很容易地移动或转换，而无需更新八叉树。(如果转换是唯一需要的转换，那么BVH节点将始终相对于体素对齐，这将将交集测试简化为AABB重叠测试；如果需要更一般的转换，则必须使用更通用的OBB和OBB测试。)

但是，请注意，BVH并不能很好地确定一个东西是在内部还是在一个水密网格之外。如果这对您很重要(我不清楚它是否重要)，那么您可能希望使用BSP树而不是BVH。BSP树可以用于类似于BVH的交集测试，但还可以表示网格的确切边界，从而可以用来确定点(或体素)在内部还是外部。BSP树的这一特性被广泛应用于碰撞检测。

另一种确定内部/外部性的方法是使用光线投射并计算与网格的交叉点数(偶数=外部，奇数=内部)。BVH也可以加速光线投射。