raw*_*der 6 c++ particles collision octree space-partitioning
我目前正在研究一个高效的计算引擎，用于 CPU 和 GPU 中的粒子模拟。我最近一直在研究八叉树，我成功地为空间中的粒子编写了八叉树的工作版本，并且还有效地处理了它们的碰撞。现在我必须在我的八叉树中插入三角形网格（STL 对象），以便我也可以处理粒子和对象三角形之间的碰撞。我很困惑如何以有效的方式将三角形插入到已经创建的八叉树中？请提出实现这一目标的方法。如果这有帮助，我正在使用 C++。已经谢谢了。
将三角形插入现有八叉树与创建新八叉树并将其插入其中应该没有太大区别。这里唯一重要的是确保现有八叉树覆盖 3D 空间，并保证包含所有三角形。
除此之外，关于插入本身，基本上我建议实现两步插入，在第一步中，您使用一些快速测试来查看三角形是否可以包含在某个立方体中，在第二阶段中（如果第一个已经过去了）你实际上做了适当的计算才能看到这一点。
其中一种快速测试是获取三角形的边界框（从所有点的最小 x,y,z 到所有点的最大 x,y,z）并将该框与八叉树之一进行比较（如果同一轴上的三角形盒子的两个坐标都不在八叉树盒子定义的范围内，并且都在同一侧（都在下面或都在上面），那么它肯定在外面）。
显然，一旦您发现三角形和八叉树框之间的交集，您应该对其所有子框重复此测试。
算法中还有其他地方可以提高效率（例如按 x、y、z 对框和三角形进行排序，然后进行仅考虑相关框的检查），但这取决于您希望优化的级别。