是否应该每帧重建一个八叉树？

Question

当在游戏中使用octree进行碰撞检测时，是应该每帧重建一次树还是假设有一半的物体在一帧中移动？

Answer 1

如果场景随每一帧而变化，则必须重做树。

Answer 2

如果场景中有很多静态几何体，请考虑构建单独的八叉树。您还可以通过使用更复杂的叶节点来区分静态和非静态几何体来表达相同的想法。

底线：只重新生成你需要的东西。

Answer 3

如果你有非常动态的数据移动每一帧仍然需要加速碰撞检测，我实际上建议使用固定的3D网格。二维等价物：

它也可以作为一个空闲列表加倍，以允许恒定时间删除，就像这样（利用next索引作为同一网格单元格中下一个元素的索引或下一个自由元素从自由堆栈弹出，如果它已被删除）：

另一个例子：

现在有三个维度，这看起来似乎需要爆炸性记忆。然而，诀窍是让每个单元格将32位索引存储到一个数组中，并且基本上用作单链接索引列表。这将每个单元的大小减小到32位。现在，如果您存储100x100x100网格（100万个单元格），则需要不到4兆字节。

当元素移动时，您可以将它们从它们占据的单元格中移除，移动它们，然后将它们插入新单元格中。为了做到这一点，你所要做的就是操纵一些32位索引（没有内存分配/释放来将元素从一组单元转移到其他单元）。这都是恒定时间，并且不需要重新平衡树或分裂变得太拥挤或类似的八分圆。

您还可以使用网格层次结构（这可能听起来像八叉树但不同）。我的意思是你的场景中可能有一个粗网格用于整个网格对象。然后，每个网格对象可以为其每个部分存储粗网格，例如10x10x10。然后每个部分为每个多边形存储精细网格或八叉树。这允许非有机网格，例如刚刚与像机器人一样旋转的部分，以避免必须更新多边形的精细网格/八叉树，并且只更新其自身的粗网格部分和世界对象的粗网格。它开始旋转它的腿和手臂，例如只有有机模型在被骨骼变形时才需要更新它们的细网格，例如：

我将为你的完全静态元素/部分保留的八叉树，它永远不需要每帧更新，我会使用一个漂亮的八叉树，稀疏，可能有一些后处理缓存友好的内存访问。如果您可以假设八叉树在构建后永远不需要更新，那么您可以有更多时间来加速搜索并最大限度地减少内存使用。