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

看到许多如Unreal4、klayge等诸多3D引擎里面都使用了八叉树来管理渲染物体,一直没明白它是如何完成八叉树的构建和实时的更新,求大神释疑。

八叉树(octree)是三维空间划分的数据结构之一,它用于加速空间查询,例如在游戏中:

  1. 加速用于可见性判断的视锥裁剪(view frustum culling)。
  2. 加速射线投射(ray casting) ,如用作视线判断或枪击判定。
  3. 邻近查询(proximity query),如查询玩家角色某半径范围内的敌方NPC。
  4. 碰撞检测的粗略阶段(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.

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

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

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

要解决这个问题,可以考虑到在相交测试中,扩大包围盒总是保守的(这里的保守是指近似化不会做成错误结果)。如果把四叉/八叉树的正方/立方空间当作包围盒,那么扩大这些包围盒以容纳刚好在边界上相交的物体也是保守的。这就是松散四/八叉树(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

1 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部