c++ - 三角形网格和粒子的八叉树实现

Question

我目前正在研究一个高效的计算引擎，用于在 CPU 和 GPU 中进行粒子模拟。我最近一直在八叉树方面工作，我设法为空间中的粒子编写了八叉树的工作版本，并且还有效地处理了它们的碰撞。现在我必须在我的八叉树中插入三角形网格(STL 对象)，这样我也可以处理对象的粒子和三角形之间的碰撞。我很困惑如何以有效的方式将三角形插入到我已经创建的八叉树中？请提出实现这一目标的方法。如果这有帮助，我正在使用 C++。已经谢谢了。

Answer 1

将三角形插入现有八叉树与创建新八叉树并将它们插入其中应该没有太大区别。这里唯一重要的是确保您现有的八叉树覆盖一个保证包含所有三角形的 3D 空间。

除此之外，关于插入本身，基本上我会建议实现两步插入，在第一步中使用一些快速测试来查看三角形是否可能包含在某个立方体中，在第二阶段(如果第一个已经过去了)你实际上做了一个适当的计算来看到这一点。

其中一个快速测试是获取三角形的边界框(从所有点的最小 x、y、z 到所有点的最大值 x、y、z)并将该框与八叉树(如果同一轴上的三角形框的两个坐标都不在八叉树框定义的范围内，并且都在同一侧(都在下方或都在上方)，则肯定在外面)。

显然，一旦您发现三角形和八叉树框之间的交集，您应该对它的所有子框重复此测试。

算法中还有其他地方可以提高效率(例如按 x、y、z 对框和三角形进行排序，然后进行仅考虑相关框的检查)，但这取决于您所处的级别希望优化。