游戏场景管理—四叉树

时间:2022-07-23 20:35:15

内容会持续更新,有错误的地方欢迎指正,谢谢!

场景管理:把不同的物体归属到不同类别里,而相似性的判断是根据物体的空间相干性。
把物体分类的目的:希望下次能快速找到所需的物体,所以更偏向于用四叉树来管理我们的场景,因为四叉树构建了这样的一个快速索引。

四叉树:设想一个二维平面,我们可以先把它按田字形划分为四份,如果这四份子空间中,存在不包含任何物体的子空间,那么我们就标记一下,然后在包含物体的子空间,继续划分为四个子空间,以此类推,这就是四叉树。转换到三维空间,我们可以把空间切分成八份,就是八叉树。

游戏场景管理—四叉树

上图中,每个节点对应一个平面区域,每一层的区域大小相同。

  1. 圆形代表该区域存在物体,且有四个子区域
  2. 白色正方形代表空间中存在物体,已经不需继续划分 或 已到最大深度。
  3. 黑色正方形代表空间中不存在物体。

四叉树的应用: 四叉树并不仅针对二维的游戏场景上,还可以:

  1. 广泛应用于三维室外场景管理(只考虑三维场景中的xy轴即可)
  2. 地形渲染剔除机制
  3. 根据四叉树只绘制玩家周围物体,或者,使用LOD技术
  4. 动态载入游戏对象

详细应用请见:http://blog.sina.com.cn/s/blog_89d90b7c0102wyfw.html

对于一个有很多物体的3D场景来说,渲染这个场景最简单的方式就是用一个List将这些物体进行存储,并送入GPU进行渲染。但这种做法在效率上来说是相当低下的,因为真正需要渲染的物体是视椎体内的物体。除此之外,从裁剪算法和碰撞检测等算法的效率来说,使用这种数据结构也是相当低效的。优秀的方式是使用具有层次结构的空间数据结构存储待渲染的物体,也就是场景管理还能用:

  1. BVH(包围体层次结构)
  2. BSP(二叉空间分割)树
  3. 四叉树
  4. 八叉树
  5. 模糊K-D树

在进行空间查找或者剔除的时候将时间复杂度从O(n)降低到O(logn)。当然,对应的代价是每帧更新的时候,需要更新对应的空间数据结构。

虚幻4用的BSP
《天涯明月刀》也用的BSP
国产MMO基本都是地形一套管理机制,室外四叉树、八叉树,代表游戏《诛仙》