游戏引擎十大核心竞争力 之 （一）场景分割（alpha纯预览版、持续更新）

游戏引擎中最关键的问题之一，是场景管理技术；其中，最基础的部分，就是场景分割。场景分割要解决的几个问题如下：

游戏场景是一次载入还是需要实时的流载入
游戏场景场景过大而无法一次载入的时候，怎样一次载入一部分
一次载入一个部分，这个部分怎样定义，根据什么原则
对于已经分割的场景，动态物体在移动的时候，在各个分割之间移动是如何处理的（尤其类似碰撞检测的功能）
编辑器怎样创建一个场景，怎样动态的管理场景的大小，是否支持场景的合并和拼接
物理系统的场景需要怎么处理，是和图形场景一致的么？
本文的目的，就是讨论上面的几个问题，并给出我现在的理解。

描述世界
描述世界，就是定义游戏场景的层次。如果游戏场景很小，只是一次载入，只需要一个octree或者其他什么乱七八糟的【分割树】就可以了。我们先给这个方法定义一个名字，叫【白痴型-单场景-单分割树】。如果场景无法一次载入，也有不同的选择。选择1. 一个超大的场景，还是只用一个octree表示，只是octree的深度会根据场景的大小变得不同，在超大的场景中，这个深度会很恐怖，我们定义这个方法为【蛮力型-单场景-单分割树】。选择2. 就是对选择1的优化，对于octree的子结点，进行了压缩或者动态的分配，而不是一次分配一个极其恐怖的庞大的分割树，我们定义这个方法为【智力型-单场景-单分割树】。选择3.这个也是最常用的，场景分成多个子场景，也就是多个小的level，游戏进行中，就只是加载一部分的level，对于活动状态的level，也是加载其中的一部分，世界描述的逻辑定义，就是这样，至于碰撞检测、可见性分析等等，都是和单场景没有区别，所有的东西，都在一个树里面，我们把这个方法定义为【多场景-单分割树】。选择4.世界描述的逻辑定义和选择3一样，也是多个level，只是分割树也是多个的，而且分割树基本上都是和level一一对应的，我们定义这个方法为【多场景-多分割树】。选择5.有些比较蛋疼的方案，用了这样的中间过渡的方法，主要是针对室内和室外处理方法的不同，即使同一个区域内，也有可能出现两个不同的分割树，我们定义这个为【妖蛾子-单场景-多种分割树】。当然，不止这样几个方法，但是没有列举出来的方法，都是这些没有太大的区别的，已经列举的方法，基本上就是几种排列组合中最典型的。接下来就具体说明各种分割的方法：

【白痴型-单场景-单分割树】：动态物体的移动，只需要处理在【分割树】内部结点、层次结点之间的移动。编辑器的要求也会相对简单，创建场景的时候，就规定好整个场景的包围体，可以选择规定物体不会被允许移出这个包围体。

【蛮力型-单场景-单分割树】：动态物体的移动，同样只需要处理【分割树】内部的节点，层次结点之间的移动，但是当树的深度增大的时候，这个计算量是几何级数的增加，而且，这个几何级数的基数还不一定是2，有时候会是8，如果你是用octree的话。编辑器在控制场景大小的时候，也不好做，究竟支不支持动态的扩充呢，还是必须要固定大小呢？

【智力型-单场景-单分割树】：相对前者，针对一个庞大的树进行了优化的处理，一般就是【动态展开】的方法， 只在相机所在的地方，树的深度，才是最大化的，看不见得大结点，连子结点都不给分配；一个结点移出视线的时候，也释放他和他的子结点，保证树的整体空间最小。这样进行可见性判断、碰撞检测的时候，复杂度就低的多得多，复杂度就是BIG-Oh(n)，具体来说，n的多项式系数，就应该是树分支数k（八叉树就是8，kd-tree就是k），与一个和视距相关的常数c的乘积。编辑器方面的问题，和前者同样纠结。

【多场景-单分割树】：这种划分方法，好处就是，分割树只是一个容器，多场景系统不停地往里面拿东西和放东西，而树本身的任务很简单，就是可视性判断和碰撞检测。

【多场景-多分割树】：不一定必须是一种分割树，可以是多种分割树。所以分析算法复杂度就省了，这个情况比较复杂。这个方法美妙的地方就是，每棵树，都可以是完整的，所以，对于开发者来说，这个地方容易实现，不需要动态的展开树，或者进行线性化的压缩，而且，针对不同类型的子场景（室内和室外），可以选择最合适的树；对于复杂场景，可以选择更深的树，简单场景，就只需要稀疏的，层次很浅的树。当然，缺点也不少，最核心的一点，就是物体移动的问题，这个问题，不仅在编辑器内很难搞定，而且，在游戏运行时，还更纠结。比如，一个物体从一个子level移动到另一个子level，需要处理物体再分割树之间进行穿梭；如果物体同时处于两个场景的包围体中，怎么办，根据什么原则进行优先级的选择该放到哪个场景的分割树中？能够简单的归到上次所在的场景中这么简单么？有特殊情况么？在游戏运行时，如果一个物体运动到另一个场景中，然后，物体之前所在的场景被运行时归为非活跃关卡，紧接着，这个已经非活跃的关卡再次被加载的时候，会不会多出一个物体出来，就是那个不该在原地出现的物体？

【妖蛾子-单场景-多种分割树】：要处理室内和室外，是需要两棵树，这个是必须的，但是为什么不干脆把这个弄成两个子场景呢，做的时候也可以分开做，只需要在编辑器内进行一次导入，匹配好相对位置，甚至，可以学习cryengine的，分成layer，即使是同时出现在编辑器内，也是有一个严格的划分。所以，这样弄，只是一个过度的方案，完全可以继续做成【多场景-多分割树】，如果只是单场景，他就有所有单场景划分的缺点，和所有多分割树的缺点，这个方案，还能更奇葩一点么？不过的确使很多商业引擎还真这么弄了，只是现在的引擎，这样弄的越来越少了。

上面的讨论，我没有提到物理方面，这个问题，我还没有想明白，各种选择都和开发者的特殊需求相关；对于我来说，我使用第三方的物理引擎，havok和physX，两个引擎都倾向于让游戏对象管理-图形对象管理-物理对象管理，都是用同样的场景划分，所以，game world，分成多个level，每个level对应了一个graphics scene，一个physics scene(or physics island)，这样物体的物理坐标的描述和图形坐标的描述，可以很简单的统一，跨越level的时候，需要处理的问题，也是一致的，可以尽量保证改变在同一个地方发生。

具体的分割树算法细节
octree
 

(图片来自http://www.gamasutra.com/features/19970801/octree.htm）

octree划分空间的平面，是和坐标轴正交的；对于每个结点，都是一个AABB(axis-aligned-bound-box)，每个结点内部，都有8个大小完全相等的子结点。

在这篇文章里面，我们只谈到了空间的分割，而没有讲可视性判断，所以，就空间分割而言，octree不是那么的有优势，而且，很多时候，空间的利用率不是很理想，尤其是场景的广度比较大（水平方向的），而深度（垂直方向的）比较浅的时候。具体谈空间相关的算法：

1. 静态物体、动态物体的添加：

添加一个静态的物体，首先计算这个物体最终的AABB，然后看这个AABB是否在octree的根节点内部，如果在，就继续判断这个AABB是不是在各个子结点中，如果在，则继续判断。。。

如果一个开始这个AABB就不在octree中呢，对于无法伸缩的octree，这个地方，就应该是一个错误，所以，编辑器在创建、移动静态物体（甚至动态物体）的时候，必须要保证这个物体不会移出根结点所在的范围。

添加静态物体的伪代码：

bool OctreeNode::AddObject( Object *object )

{

     if ( this->aabb.Contains(object->aabb) )    // 这个物体的aabb在当前结点的范围内吗？

     {

           for ( int i = 0; i < 8; i++ )  // 继续判断这个物体是不是在各个子结点内

           {

                if ( children[i]->AddObject( object ) )  // 如果某个子结点【接受】了这个物体，则任务完成

                {

                        return true;

                }

           }

           // 物体虽然在当前结点内，但是任何一个子结点都不能完全包含这个物体，那么就把它放在当前

           this->AddObjectImpl( object );

           return true;

     }

     return false;

}

 

2. 动态物体的移动，多简单。。。

void OctreeRoot::UpdateObject( Object *object )

{

       // 打开冰箱门

       rootNode->RemoveObject( object );

       // 把大象放进去

       bool result = rootNode->AddObject( object );

       // 关上冰箱门

       object->SetUpdateResult( result );

}

 

关于空间划分的，就只有这么一点东西，每个引擎在细节的部分会有一些不同，但是核心的思想就是这么简单的。

BSP
BSP的细节，放到quake3章节中详细讨论，这里就省略了。

kd-tree
kd-tree一般都是针对碰撞检测（和光线追踪）的优化进行划分，对于图形场景，很少有用kd-tree的。kd-tree，很多地方和bsp相近，有时候很难分辨具体是bsp还是kd-tree。实际上，也有一些工具是根据kd-tree的算法，生成bsp的场景的。

Case Study-Engine
Unreal Engine 3
unreal engine 3，从04年公布到今天，经历了很长的时间，算法的细节变化了很多。我主要分析04年的版本，这个版本可以从网上获得（悄悄的说，比如verycd），能不能编译我不清楚，但是肯定是没有办法运行的，因为没有04年那个时候的美术资源，用现在的ue3的游戏资源代替也不行。因为这样一些理由，分析的结果无法那么准确。

ue3的04年的版本，是使用的【蛮力型-单场景-单分割树】，但是从设计来看，已经考虑了以后扩展成【多场景-单分割树】的方案。04版ue3，一个关卡就是一个ULevel，从代码来看，一个游戏运行时只会有一个ULevel。ULevel中有一个FPrimitiveHashBase成员，这个就是Octree的马甲，FPrimitiveHashBase的一个子类，就是FPrimitiveOctree：

 

所有关于octree的具体操作，就在类FOctreeNode中完成：

 

其他引擎基于octree的实现方法，也是和这个一样一样的，每个OctreeNode中，有一个列表，存放在这个Node下的一组Object，然后是8个子结点。

核心函数AddPrimitive

 

先检查物体是不是在世界范围内，在游戏运行时，使用SingleNodeFilter进行添加物体

 

SingleNodeFilter中，首先看子结点能否完全包含该物体的，如果子结点无法包含物体，那么就【尝试】自己包含这个物体。如果子结点可以包含该物体的，则，继续递归对于子结点的SingleNodeFilter。

【尝试】自己包含这个物体，就是StoreActor，具体实现如下：

 

如果当前结点已经包含了过多的物体，同时，这个结点还没有子结点，（同时，这个结点比定义的最小粒度的结点要大），那么划分这个结点的空间，然后把当前已经包含的物体，以及新的物体，都尝试再放到当前结点一次（因为已经分配了子结点，所以，这个时候，很多物体，有可能放到子结点中了，而另一些物体，则再次放到这个结点）。

如果该结点的分配子结点的操作不符合要求，或者之前已经分配过，那么就直接把这个新添加的物体放到object list中，同时通知这个物体，Primitive->OctreeNode.AddItem(this)【你现在已经在我里面了】 :P 

以上就是04版ue3的场景分割相关的主要算法。

接下去看06版ue3和09版ue3的改进。

06年，Unreal Tournament 3开发接近尾声，Gears Of War的开发已经进行了相当长的一段时间。GOW最大的特点就是多场景系统。

在代码中，最醒目的地方，就是多了UnWorld：

 

FSceneInterface *scene，和可视性、sorting相关的场景管理，从Level中移到了UWorld中，场景分割的场景树，FPrimitiveHashBase *Hash也从Level中移到了UWorld中，Level里面，现在还剩什么呢？

 

Level中，还剩下BSP，主要用于室内Brush的碰撞检测、静态光照、渲染等等；以及Kismet可视化脚本的对象。其他的部分，已经不直接和场景管理、尤其是场景分割相关了。但是其中有一个成员，比较让我感兴趣：

 

这个地方，很明显应该就是Unreal怎么处理跨越边界的物体，尤其是那些动态的物体的；最关键的，"streaming a level in/out”，啊哈！注意看前面提到过的，【多场景-多分割树】的难点。我相信这里会是相当纠结的（后面具体分析）。

Level中唯一和游戏对象直接打交道的地方，就是Level的父类，LevelBase：

 

所以，我们可以得到06版Unreal的场景分割的大概方法，UWorld管理Level（主要是runtime streaming），以及一些其他的乱七八糟的事务（事务相当多而且类别各异，这是unreal设计策略的一个通病），level简单的作为游戏对象的提供（从streaming的结果中得到新的游戏对象）。

Unreal 06到09在这个方面变化不大。（ps：由于我一直没有找到一个可以调试的版本，unreal的进一步介绍可能要停一阵。不过可以肯定的，unreal是这个系列中的最重要的参考引擎。)

 

CryEngine
首先说说CryEngine。。。啊。。。CryEngine~~~~ 在这么多的引擎中，CryEngine的设计是我最喜欢的，恩，甚至超过了nebula device系列。21世纪游戏引擎什么最重要？模块设计！我理解的模块设计最重要的就是两点：分层和分块。CryEngine、C4、nebula device 3在分层方面都是做的相当好的。在分块方面，ND3就开始凌乱了；C4就不清楚了，手头连个sdk都没有。CE在分块方面的划分也是非常合理。我对CE设计的全部理解，来自Crysis Mod SDK，引擎部分的代码全部只有部分头文件，一般都是公用的接口，直接动态加载DLL可以使用的。就暴露的接口类而言，设计那是相当华丽！恩，废话不说了，大家自己去看。

在应用层的场景管理，就只有这么一点点的接口，是在是没有办法分析：

 

 

Quake 3 && Half Life
Ogre
Gamebryo
Gamebryo，在这个系列中多半是反面教材。在这一辑中，gb也没有什么好说的，压根就没有场景分割的说法。和场景相关的类都放到了core appFramework中，的entity system；而且没有场景分割，所有的东西看起来都像是他们已经被分割好放到了场景中；其他的工程中，好像也没有相关的实现。而且多半看起来，这个场景管理还是倾向scene graph的（在今天看来，scene graph就是主流中的非主流），的确是挺符合Gamebryo在人们心中的形象的。

Cube 2
Case Study-Editor
gtk-radiant
World Craft( my project )
Getic
Torque 3D

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/xjyhust/archive/2009/09/01/4509286.aspx