我目前正在研究一个高效的CPU和GPU粒子模拟计算引擎。我最近一直在研究八叉树，我设法为空间中的粒子写了一个八叉树的工作版本，并且有效地处理了它们的碰撞。现在我必须在我的八叉树中插入三角形网格(STL对象)，这样我就可以处理粒子和物体三角形之间的碰撞。我很困惑如何有效地将三角形插入到我已经创建的八叉树中?请建议实现这一目标的方法。如果这有帮助，我正在使用c++。谢谢了。
将三角形插入现有的八叉树与创建一个新的八叉树并将它们插入其中没有太大的不同。这里唯一重要的是确保你现有的八叉树覆盖一个3D空间，保证包含所有的三角形。
除此之外，关于插入本身，基本上我建议实现两步插入，在第一步中，您使用一些快速测试来查看三角形是否可能包含在某个立方体中，在第二阶段(如果第一个已经通过)，您实际上做一个适当的计算来查看。
一个这样的快速测试是获得三角形的边界框(从所有点的最小x,y,z到所有点的最大x,y,z)，并将该框与八叉树中的一个进行比较(如果三角形框在同一轴上的两个坐标都不在八叉树框定义的范围内，并且都在同一侧(都在下方或上方)，那么它肯定在外面)。
显然，一旦你发现了三角形和八叉树盒子之间的交集，你应该对它的所有子盒子重复这个测试。
算法中还有其他地方可以使此更有效(例如按x,y,z对盒子和三角形进行排序，然后只考虑相关盒子进行检查)，但这取决于您希望优化的级别。
如果你的粒子是均匀大小的，而你的三角形不是，这往往需要一种非常不同的数据结构。对于大小一致的粒子，你可以把它们当作点，只把一个粒子作为空间中的一个点存储在树的一个叶子节点上(只要所有的粒子大小一致，如果它有一个大的半径/大小并不重要，因为你的搜索查询，只要它们被粒子的大小扩展，就会总是拾取它们的中心点)。
对于三角形，它们的大小可以变化很大，并且可以与8个子八分位数中的多个相交。因此，你可以做我所知道的几件事:
- 简单地在多个叶子中插入一个指向三角形的指针/索引，并带有一些冗余，或者简单地在所有叶子中复制整个三角形数据(如果你不小心根据内容调整树的参数，可能会导致内存使用爆炸，但它可以使搜索更加缓存友好)。
- 分割三角形，这样如果它与两个或更多的八边形相交，它就会变成两个或更多的分割三角形。这对于构建/更新来说有点昂贵，但如果你以一种缓存友好的方式将三角形数据直接存储在叶子中，那么查询就会很快。
- 使用松散的表示，如松散的八叉树。在这种情况下，您只在插入时将三角形视为单个点。但是，您可以扩展在插入期间遍历的所有八叉树节点的aabb，以包含三角形。
#1对于动态内容来说是不错的，只要你最小化内存使用和构建树所涉及的处理，并设置一些合理的限制，比如八叉树的最大深度，这样它就不会无限期地分裂。
#2更适合于静态内容，更适合于快速搜索，因为它可以产生比#1更浅、更平衡的树，因为你没有在叶子中存储重叠的数据，这将倾向于让它们比理想情况下分裂得更多。如果您的数据是静态的，那么您可能只需要直接在八叉树中存储一个副本，并且八叉树可以自由地修改该数据，以提供最快的搜索。
#3对于动态内容来说非常好，因为它很好地平衡了构建/更新树和搜索树之间的开销。然而，松散八叉树对搜索查询的性能造成了很大的影响，因为以前只需简单地检查中心点来确定要遍历哪个八叉树，现在需要检查所有8个八叉树的AABB来确定在搜索期间要遍历哪些子节点。然而，它大大减少了构建和更新树的开销，使其在动态内容中保持良好的平衡，例如，在交互式实时上下文中，网格正在变形每一帧。
准确地说明你的需求有助于这些类型的问题，比如你的网格是否是静态的，你是否需要快速的更新/构建/搜索或平衡(你通常不能让这三件事都超级快:让一个超级快通常意味着让另一个变慢)。
例如，光线追踪器通常使用非常适合静态内容的代表，因为他们通常可以花费一些额外的时间来构建结构，因为他们可能会在之后对它执行十亿次光线/三角形相交测试。对于光线追踪器来说，花100毫秒来构建/更新其空间索引并不是什么大问题，因为它可能需要几秒钟甚至几分钟或几小时才能以生产质量渲染完整的场景。100ms在离线渲染标准下是极短的时间，而在实时标准下却是极长的时间。另一方面，对于光线追踪器来说，最快的搜索时间是非常非常重要的，所以松散的八叉树通常是一个糟糕的选择，大多数光线追踪器通常希望将交叉测试所需的数据深度复制到叶子中，这样他们就不需要零星的内存访问模式来访问存储在叶子中的数据。然而，处理在实时上下文中移动的许多物体的碰撞检测的物理引擎可能需要非常不同的表示来适合动态内容。在完全交互式的实时环境中处理静态和动态内容的游戏引擎可能会使用多种数据结构:每个数据结构都针对它们存储的内容类型进行定制。
如果你的粒子确实是均匀大小的，那么我建议使用不同的数据结构(例如不同类型的八叉树)来存储三角形网格。同样的情况，如果你的粒子是非常动态的，而你的网格是相当静态的。在这种情况下，如果你正在搜索粒子是否与网格或粒子碰撞，你可能首先检查存储针对三角形优化的网格的八叉树。如果你没有找到一个相交的三角形，然后搜索其他适合存储动态的、均匀大小的粒子的八叉树来检查粒子-粒子碰撞。您仍然可以将其抽象为看起来像单个数据结构的点，但理想情况下，您应该为此使用两个不同的实现。
对于变换的网格，存储两个八叉树也很有用:整个网格的外八叉树只是为了对它们的aabb进行粗相交测试，例如，如果粗相交测试通过，搜索每个网格存储的八叉树以找到哪个三角形相交。这允许你在网格变换时(例如:当它们旋转时)避免更新存储三角形的八叉树。