4

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

4

2 回答 2

3

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

除此之外，关于插入本身，基本上我会建议实施两步插入，在第一步中，您使用一些快速测试来查看三角形是否可能包含在某个立方体中，并且在第二阶段（以防万一第一个已经过去）你实际上做了一个正确的计算来看到这个。

一种这样的快速测试是获取三角形的边界框（从所有点的最小 x,y,z 到所有点的最大 x,y,z）并将该框与八叉树之一进行比较（如果同一轴上的三角形框的两个坐标都不在八叉树框定义的范围内，并且都在同一侧（都在下面或都在上面），那么它肯定在外面）。

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

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

于 2014-07-12T09:35:55.453 回答
2

如果你的粒子是统一大小的，而你的三角形不是，那往往需要一种非常不同的数据结构。对于大小均匀的粒子，您可以将它们视为点，并将一个粒子存储在树的一个叶节点中作为空间中的一个点（只要所有粒子都具有大半径/大小，则无关紧要）大小一致，因为您的搜索查询（只要它们按粒子大小扩展）将始终选取它们的中心点）。

对于三角形，它们的大小可以变化很大，并且可以与 8 个子八分圆中的多个相交。因此，您可以做几件我知道的事情：

  1. 只需在具有一些冗余的多个叶子中插入指向三角形的指针/索引，或者简单地在所有叶子中复制整个三角形数据（如果您在调整参数方面不小心，可能会在内存使用中爆炸）树对内容，但它可以使搜索更加缓存友好）。
  2. 分割三角形，这样如果它与两个或更多的八分圆相交，它就会变成两个或更多的分割三角形。这对于构建/更新来说往往有点昂贵，但如果您以缓存友好的方式将三角形数据直接存储在叶子中，则查询速度可能会很快。
  3. 使用松散的表示，例如松散的八叉树。在这种情况下，您只需在插入时将三角形视为单个点。但是，您将在插入过程中遍历的所有八叉树节点的 AABB 展开以包含三角形。

只要您将构建树所涉及的内存使用和处理降至最低，并设置一些合理的限制，例如八叉树的最大深度，以便它不想无限期地分裂，＃1 往往适合动态内容。

#2 往往非常适合静态内容，并且往往非常适合快速搜索，因为它可以产生比 #1 更浅且更平衡的树，因为您没有存储在叶子中的重叠数据，这将倾向于希望他们分裂得比理想情况下更多。如果您的数据是静态的，那么您可能只需要直接将一个副本存储在八叉树本身中，并且八叉树可以随意修改该数据以提供最快的搜索。

#3 往往非常适合动态内容，因为它可以很好地平衡构建/更新树和搜索树之间的开销。然而，松散的八叉树对搜索查询的性能造成了很大的打击，因为以前对中心点进行简单检查以确定要遍历哪些八分圆现在需要检查所有 8 个八分圆的 AABB 以确定哪些子在搜索过程中遍历。然而，它显着减少了构建和更新树的开销，使其在动态内容中得到很好的平衡，例如，网格在交互式实时上下文中对每一帧进行变形。

它有助于解决这些类型的问题，以准确地指定您的需求，例如您的网格是否是静态的，您是否需要快速更新/构建/搜索或平衡（您通常无法让所有这三件事都超快：使一个超快通常意味着使另一个变慢）。

例如，光线追踪器经常使用非常适合极端静态内容的代表，因为他们通常可以花一些额外的时间来构建结构，因为之后他们可能会针对它执行十亿次光线/三角形相交测试。光线追踪器花费一百毫秒来构建/更新其空间索引并不一定是什么大问题，因为它可能需要几秒钟，有时甚至几分钟或几小时才能以生产质量渲染整个场景。按照离线渲染标准，100 毫秒是微不足道的时间，按照实时标准，这是一个史诗般的时间。另一方面，最快的搜索时间对于光线追踪器来说非常重要，

然而，处理在实时上下文中移动的许多事物的碰撞检测的物理引擎需要一个非常不同的表示，适合动态内容。在完全交互式的实时上下文中处理静态和动态内容的广泛混合的游戏引擎可能会使用多种数据结构：每个数据结构都针对它们存储的内容类型量身定制。

如果您的粒子确实是大小均匀的，那么我建议使用不同的数据结构（例如，不同类型的八叉树）来存储三角形网格。如果您的粒子非常动态，而您的网格相当静态，则情况相同。在这种情况下，如果您正在搜索查看粒子是否与网格或粒子碰撞，您可能首先检查存储针对三角形优化的网格的八叉树。如果没有找到相交三角形，则搜索适合存储动态、大小均匀的粒子的另一个八叉树，以检查粒子与粒子之间的碰撞。您仍然可以将其抽象到看起来像单个数据结构的程度，但理想情况下，您应该为此使用两种不同的实现。

对于变换的网格，存储两个八叉树也很有用：整个网格的外部八叉树仅用于针对它们的 AABB 的粗略相交测试，例如，如果粗相交测试通过，则搜索每个网格存储的八叉树以查找哪个三角形(s) 相交。这使您可以避免在网格变换时更新存储三角形的八叉树（例如：当它们旋转时）。

于 2018-01-23T12:43:06.030 回答