c++ - 在八叉树中存储具有共享边的三角形

Question

我正在尝试加载一个 STL 网格文件并将其三角形存储在八叉树数据结构中以用于某些科学分析(不是用于游戏)。

如图所示，三角形 1 存储在八叉树节点 NE、SE、SW 和 NW 中，而三角形 2 存储在八叉树节点 NW 和 SW 中。 (2d 表示，但在 3d 中是相同的故事)。

分割节点 NW 和 SW 是没有意义的，因为这两个三角形共享红色边缘。如果我有两个以上的三角形跨越多个单元格，这个问题就会变得更加麻烦。

那么，在八叉树中存储三角形的正确方法是什么？

ps- 我不想剪裁三角形。

Answer 1

我使用了两种最常用的方法:

• 在与三角形相交的每个叶节点中存储三角形；所以，一个三角形可能在多个叶子中；
• 将三角形存储在完全包围三角形的节点(分支或叶)中；没有重复。

第一种方法对于粗略的、轴对齐的、物体形状的估计是有用的——解决紧密堆积问题。基本上它是不均匀的体素化。第二种方法非常适合碰撞检测。每个三角形都需要与同一节点及其子节点中的其他三角形发生碰撞。第二种方法产生了相当轻量级的实现(您可以将链表 next-pointer 直接添加到三角形)。