游戏场景管理的八叉树算法是怎样的？

八叉树（octree）是三维空间划分的数据结构之一，它用于加速空间查询，例如在游戏中：

• 加速用于可见性判断的视锥裁剪（view frustum culling）。
• 加速射线投射（ray casting） ，如用作视线判断或枪击判定。
• 邻近查询（proximity query），如查询玩家角色某半径范围内的敌方NPC。
• 碰撞检测的粗略阶段（broad phase），找出潜在可能碰撞的物体对。
  

总括而言，前3个应用都是加速一些形状（frustum、ray、proximity shape如球体）的相交测试（intersection test）。

简单来说，八叉树的空间划分方式是，把一个立方体分割为八个小立法体，然后递归地分割小立方体。

图片来源Wikipedia Octree

相似地，四叉树把一个正方形空间分割成四个小正方形。由于三维空间较难理解，之后本答案主要以四叉树作图示解释。

四／八叉树有多种变种，先谈一个简化的情况，就是假设所有物体是一个点，这样比较容易理解。

把每点放到正方形空间里，若该正方形含有超过一个点，就把该正方式分割，直至每个小正方形（叶节点）仅含有一个点，就可以得出以下的分割结果：

图片来源：CS267: Notes for Lecture 24, Apr 11 1996

这种做法是adaptive的，就是说按照一定的条件（叶节点只能有一个点）来进行分割。实际上，我们可以设置其他条件去决定是否分割一个叶节点，例如节点内的点超过10个，或是最多分割4层就不再分割等等。

在分割时，我们只需检查点是在每个轴的哪一方，就能知道该点应放置在哪个新的节点里。

建立了一个四／八叉树之后，我们可以得出一个重要特性：

如果一个形状S与节点A的空间（正方形／立方体）不相交，那么S与A子树下的所有点都不相交。

那么，在相交测试中，我们可以从根节点开始，遍历四／八叉树的节点，如节点相交就继续遍历，如不相交就放弃遍历该子树，最后在叶节点进行形状与点的相交测试。这样做，一般能剔除许多点，但注意最坏的情况是所有点集中在一起，那么就不起加速作用。

———————-
9月4日晚更新

当创建了一个四／八叉树之后，如问题所提及，有时候需要新增、删除物体（目前我们谈及的是点），以及更新物体（点）的位置。

更新位置的最简单实现，就是删去物体再重新安插。然而，显然的优化方法就是，检查旧位置和新位置是否位于同一个叶节点的正方／立方范围里，如果没超出范围，就不需要做删除再安插的工作。

但如果超出范围呢？除了简单地从根开始找合适的节点，也可以使用一些搜寻方法找到相邻的节点，如[1]。这里就不谈这些细节了。

了解最基本的四／八叉树后，可以把问题扩充至管理占面积／体积的物体。虽然我们可以每次比较场景物体和正方形／立方体是否相交，但为了性能，一般是使用物体的包围体（bounding volume）而不是物体本身。例如是使用包围球（bounding sphere）、轴对齐包围盒（axis-aligned bounding box, AABB）或定向包围体（oriented bounding box, OBB）。这个做法是保守的。

但无论是用物体的精确形状，还是使用包围体积，把它们放置在四／八叉树中会有一个问题：它们可能会与节点的边界相交。例如

图片来源：Akenine-Moller, Tomas, Eric Haines, and Naty Hoffman. Real-time rendering 3rd edition. p.655, AK, 2008.

在上图中，七角星最后处于两个叶节点。这时候至少有两个解决方法：

• 所有与物体相交的子节点都引用至该物物体。在此例子中，有两个叶节点都引用七角星物体。
• 令中间节点（非叶节点）也能放置物体。在此例子中，上一层的中间节点（就是右上的正方形）放置七角星物体。
  

第一种方法的范围比较精确，但如果物体的大小相差很大，大体积的物体便需要被大量小范围的叶节点引用，而且管理上也会很麻烦。第二种做法是较常用的方法。然而，第二种方法的范围可能非常大，例如物体刚好在场景的中心，即使是一个体积很小的物体，都只能放于根节点里。

要解决这个问题，可以考虑到在相交测试中，扩大包围盒总是保守的（这里的保守是指近似化不会做成错误结果）。如果把四叉／八叉树的正方／立方空间当作包围盒，那么扩大这些包围盒以容纳刚好在边界上相交的物体也是保守的。这就是松散四／八叉树（loose quadtree/octree）[2] 的思路。

图片来源：Akenine-Moller, Tomas, Eric Haines, and Naty Hoffman. Real-time rendering 3rd edition. p.656, AK, 2008.

以上所说的都是一些基本原理，在实现时要考虑具体的数据结构、内存布局等问题。现在一般认为，完全使用八叉树可能不利于缓存，用一些扁平的结构并利用SIMD可能更可提高性能，或是需要混合的方案，如八叉树只有两、三层，叶节点内使用扁平的方式储存各种包围体。

因此，除了传统的四／八叉树实现，也可以参考一些更新的技术，例如OpenVDB [3]中的一些思路。

[1] Frisken, Sarah F., and Ronald N. Perry. “Simple and efficient traversal methods for quadtrees and octrees.” Journal of Graphics Tools 7.3 (2002): 1-11.
[2] Ulrich, Thatcher. “Loose octrees.” Game Programming Gems 1 (2000): 434-442.
[3] K. Museth, “VDB: High-Resolution Sparse Volumes With Dynamic Topology”. ACM Transactions on Graphics, Volume 32, Issue 3, Pages 27:1-27:22, June 2013. http://www.museth.org/Ken/Publications_files/Museth_TOG13.pdf

作者：Milo Yip，游戏程序员、《游戏引擎架构》译者 vai：知乎