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

Question

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

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

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

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

ps-我不想剪辑三角形。

Answer 1

我使用了两种最常见的方法：

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

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