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

Question

我正在尝试加载一个STL网格文件，并将它的三角形存储在八叉树数据结构中，以便进行一些科学分析(不是为了游戏)。

​

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

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

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

ps-我不想裁剪三角形。

Answer 1

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

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

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