三维场景管理之四叉树和八叉树

四叉树和八叉树概述

传统计算机图形应用--特别是的应用的需要一个实时，交互的方法来现实--通过处理一个发送到显卡的数据的最有效的图形数据子集的方法来决定图形数据的显示，而不是传送全部的数据，四叉树，八叉树，Bsp树，背面剔出，pvs集合很多其他方法都是针对这个目的而提出的。

流行的计算机图形卡近些年在处理能力和处理方法上程指数增长，当前的状态揭示出很多时候应该更好的和快速的找到一个好的数据集把它们送到显卡里，而不是把精力放在努力的找到一个最好的数据集。这样的数据集是一个近似的最好的数据集并且能经常发现它都有十分有效的算法，因此手头上的任务因此就变成了回顾已经存在的技术和算法并且尝试找到最快的选择，这对于找到最好的解决问题的方法并不是什么负担（翻译:宋晓宇）。

四叉树

四叉树用于点数据、区域、曲线、平面及立体方面。在每一层上可以分解成相等的部分。

区域四叉树是基于把图像数组不断细分到四个相同大小的象限中。如果这个数组不是完全由1或完全由0组成（也就是说这个区域没有覆盖整个数组），那么它将被细分到象限中、子象限中，依此类推，直到得到完全由1或完全由0组成的块为止 。

作为区域四叉树的一个例子，从图1.可以看出，区域内的像素用1表示，区域外的像素用0表示。由图1中数组所产生的块由图1.1c表示，这个过程由度数为4的树表示（即每一个非叶子结点有4个孩子结点）。

图1.1 举例

在树型表示中，根结点与整个数组相对应。一个结点的每一个子结点表示一个由这个结点所表示区域的一个象限（按西北、东北、西南、东南次序标记）。叶结点则与那些没有必要进一步细分的块相对应。 标记为黑的或白的，主要依据它的相应块是否完全在表示的区域内（仅包含1）或外（不含1）。所有的非叶子结点均被标记为灰色（也就是说，它的块同时包含0和1）。

八叉树

八叉树是基于将对象数组连续的细分成八分圆的基础上的。如果数组不完全由1或完全由0组成，则数组会被细分成八分、十六分、依此类推直到立方体（可能是单个的三维像素）只有1或0组成为止，也就是说，它们完全在区域内或完全与区域不相交。

这一细分过程可由一个度数为8的树来表示，在这个8度树中，根结点表示整个对象，叶子结点则表示那些没必要进一步细分的数组的立方体。叶子结点是黑色还是白色（满或者空），是根据与它们相应的立方体是完全在对象内还是完全在其外来决定的，所有的非叶子结点均为灰色。图1.4是一个简单的三维对象的例子,采用梯状的形式给出了它的八叉树的块的分解， 及它的树描述。

图1.4

区域四叉树

区域四叉树是一个以最大块集合为特征描述的类的成员。每一个最大块都包含一个给定的区域，同时它们的集合又是整个的区域。最简单的表示是步长代码。

区域四叉树要求最大块是不相交并且有标准的大小和位置。

将数据转换成了一个区域四叉树时判定图像是同类的标准：灰度级的标准偏差在给定极限之内。

利用这一准则，图像数组被连续细分成象限、子象限等等直到获得相似的块为止，这一过程会产生一个规则分解。如果一个块和每个叶子结点（它的块的平均灰度级）相联合，那么结果区域四叉树将会给图像完全的指定一个分段地近似值，其中每个同类块都用它的平均值来表示。

为了获得图像中最大类似区域，我们必须允许合并相邻的块（或块的集合），只要结果区域保持相类似。这是通过分割和合并的算法实现的，但是结果分块不用四叉树表示了。最终的表示是邻接图的形式。因此，区域四叉树被应用在分割过程的初始步骤中。分解步骤递归地分解不相同的块直到满足相同的标准或到达一个给定的层次。最后，归类步骤集合所有类似的四邻接黑色的块到一个区域内，八邻接白色的块类似的集合到白色区域中。

举例来说，图1.5b-d演示了四叉树应用的结果，在图1.5a中的初始图像分解中的操作依次是合并、分裂和归类。在这种情况下，图像初始被分解成16块大小相同的正方形块。接着，在合并步骤中，四个类似的兄弟块被递归地合并归类成更大的块。

图1.5 举例阐述“分解-合并”的过程
(a)开始；(b)合并；(c)分解；(d)组

对于区域四叉树表示，不规则的分解方法也是可选用的，这种方法在节省空间方面存在潜力。 缺点是，选择哪一个是最优的分割点将花费大量的计算时间。

最终选择哪一类似的标准来指导分割过程是依靠表示区域的数据的类型。

四叉树和八叉树的历史

四叉树

最初的递归分解原理作为所有四叉树的基础，研究中遇到很多困难。区域四叉树主要用于描述几何数据。

起初，很可能区域四分树被看作是在稀疏矩阵中聚集0块的一种方法。甚至Hoare指出是Dijkstra将一个矩阵的第一层分解成正方形块的。Morton作为索引的一种方式将其用在了地理数据库中（即空间索引）。

Warnock的一篇报告成了计算机图形学的里程碑，在报告中，他叙述了用图形的递归分解来实现隐藏线和面的排除算法。将图形重复地分解成矩形，这些矩形连续的变小，以便搜索区域时，可以足以简单的显示出来。

八叉树

经过许多研究员的独立研究，区域四叉树的三维变量--八叉树得到了发展。它经历了如下4个阶段

1. 八叉树是四叉树的自然延伸。
2. 八叉树是对立体对象的三种表示之一，就是将三维空间用垂直于x轴、y轴和z轴的平面分解成直平行六面体。.
3. 将对象分解成直平行六面体时不必按坐标轴排列。并且该平行六面体的大小和方向是任意的。每个平行六面体都被递归地分解成在该平行六面体所围成的空间内并排的行六面体。
4. 介于第二和第三种之间的方法是将空间递归分解成任意个直平行六面体，这种分解也是用垂直于三条坐标轴的平面来完成。

四叉树和八叉树常用于解释网的有限元素的分解。四叉树和八叉树适用于网的自动生成，其中三维立体用超二次曲面模型来表示，这已经被Kela、Voelcker和Goldak直接扩展到了网的边缘区域。这个方法比使用不连续的近似值要好。并且通过开发四叉树和八叉树性质的空间索引促进了对适应性分析的增强。

以上摘自：空间数据结构

3D游戏开发之场景管理

一、场景管理有很多种方法，如四叉树、八叉树、BSP、模糊K-D树、包围球层次结构等。

室内环境主要是BSP为主，从quake3一直延续到现在主流的引擎都是以BSP为基础，BSP使用并不难，关键是数据的生成，这就牵涉到场景编辑器。

Quake3、Unreal：BSP,有自己的编辑器。

FarCry：场景分为室内和室外两部分，室内场景使用BSP, 室外不清楚但应该跟地形有很大关系，同时为了支持超远距离视距使用了地形Occlusion Culling，另外也可以手动放置OcclusionArea。
RenderWare：模糊K-D树，内置了很多种K-D树切割方法，读者可以借鉴到自己的引擎，我自己试过把标准的RenderWare K-D树生成代码移植到Gamebryo，RW的切割还是很有技巧的。
GameBryo: 包围球层次结构，可以根据自己的需要进行修改。

二、基于地形、室外为主的MMO网游，个人认为还是用四叉树进行场景管理。

之前我们也尝试K-D树，问题是室外的实体太多了，而且实体非常密集，无论怎么切割，生成的K-D树深度都不能承受，毕竟实体不是点。八叉树也没必要，普通的一张512*512地图，实在没必要在Z轴上继续划分。提升效率的另外一个途径是Occlusion Culling，OC算法有很多。在场景编辑器或美术导出的时候指定PlanarOccluder，渲染之前进行遮挡检测。最明显的例子就是城墙，在城外打怪的时候望向城墙，城内的实体就不应该被渲染。目前有专门的OC中间件Umbra，Gamebryo集成了该插件。

三、目前我的做法，主要介绍下室外四叉树，室内及室内室外衔接做完了再做介绍。

场景元素：

1. 地形，由Tile组成。
2. 静态实体，指WorldBound固定不变的实体，如静止的房屋。
3. 动态实体，指WorldBound变化的实体，如烟雾特效、天生飞翔的老鹰。

场景层次结构：

1. 场景实体全部处于同一级；
2. 地形按四叉树组织
3. 地形四叉树的叶子节点Tile包含处于该TileAABB内的所有静态场景实体列表；一个静态实体有可能跨多个Tile。

场景更新：

静态物体：

1. 当添加实体的时候，根据实体的世界坐标及AABB，可确定实体处在哪些Tile，并更新相应Tile的实体列表索引。
2. 当删除实体的时候，遍历所有的地形Tile，更新实体列表索引。
3. 当移动、旋转、缩放即WorldBound变化的时候，马上更新相应Tile实体列表索引。编辑器、游戏内都一样。

对于动态物体，没有特殊处理，进行最简单也是低效的视椎体裁剪。

剔除及次序：

1. 地形四叉树剔除，确定可视VisTileList
2. 静态物体：遍历可视VisTileList，地形Tile的实体进行视椎体裁剪，获得VisEntityList
3. 动态物体：视椎体裁剪，添加到VisEntityList
4. 所有实体包括Tile跟PlaneOccluder进行OcclusionCull

场景渲染及次序：

1. 先绘制ui。
2. 绘制VisEntityList的非透明实体，被渲染的实体更新当前帧数避免重复渲染。
3. 绘制地形。
4. 绘制VisEntityList的透明实体，被渲染的实体更新当前帧数避免重复渲染。
5. 最后绘制天空盒