你好,游客 登录 注册 搜索
背景:
阅读新闻

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

[日期:2015-01-27] 来源:《游戏引擎架构》  作者:Milo Yip [字体: ]

  

剑网3

  八叉树(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:知乎

无觅相关文章插件,快速提升流量




收藏 推荐 打印 | 录入:Cstor | 阅读:
相关新闻       八叉树算法 
本文评论   查看全部评论 (4)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款