3D引擎场景管理

3D引擎场景管理我认为对于一个3D引擎来说，昀核心的部分应该算是场景组织（scenegraph）了，如果这部分你都没有设计好，那么就别指望开发一个成熟的3D引擎了。为了开发3d引擎，所以我首先就研究这方面的内容，对一个3D的场景来说，又很多的物体，昀简单的组织方法就是把他们用一个List连接起来，然后在绘制没一帧的时候依次送入渲染器（render）进行处理。这显然不是一个很有效的方法，当处理一个普通的游戏场景都会显得非常慢的。实际上虽然一个场景中的物品很多，但是通常可见的指是以小部分，如何能够用很小的计算代价排除那些不可见的物品呢，这种方法叫做剔除隐藏面，减少绘制元素（HiddenSurfaceComplexityReduction）。为了实现这样的方法，牵涉到空间排序（SpatialSorting），昀基本的方法要算二叉空间分割树（BSP）了，DOOM是第一个使用了二叉树的商业游戏。二叉树的构造简单地说就是对于要处理的一组对象，选择一个平面，将该组对象分成两组（如果由某个对象与该平面相交则用这个平面将这个对象分成两个对象）作为该结点的两个儿子，然后分别对两组对象用相同的方法，直到满足一个特定的条件（通常是到结点上只有一个对象）为止。二叉树确实是一种很有效的场景组织结构，因为，当给出视锥（viewfrustum）以后，在穿过（traverse）这棵树的时候，如果发现视锥（frustum）与结点所代表的平面不相交，那么这个结点上有一棵子树必然不可见,那么这个子树就不用送入渲染器了，当遇到Leaf的时候，就可以获得所需的多边形数据，可以送入渲染器处理。虽然二叉树已经是非常有效的方法，但是仅仅依靠二叉树还是不能满足游戏的要求，因为现在的游戏的场景是在是很大很复杂，又很多的物品，按照二叉树的方法凡是与viewfrustum相交的Leaf必然要送入渲染器，因为viewfrustum是很大的，所以会有很多的Leaf与他相交，这就意味着渲染器还是要处理很多的数据，如果你确实能够看到这么多的物体，那也没有办法，但是通常，比如很多室内的场景，虽然在你的frustum里面会由很多物体，但是你真正能够看到的还是很少的一部分，比如一个封闭的房间。因此被称为Portal的技术被引入到游戏中来，之所以能够使用Portal技术，那是因为很多室内场景自身的限制条件所致。我们引入region的概念，一个region就是一个相对封闭的空间，比如一个房间，region与region之间都是通过Portal（比如门或窗）相连接，因此，如果你处于一个region当中，你就只能看到这个region中的物体，如果你能够看到其他region中的物体，那么你一定是通过Portal看到的，所以处理的过程如下（考虑Portal是单向的情况，如果两个region可以通过一个门相互看到，我就是用两个单向的Portal）。voidCRegion::Draw(LPRenderlpRender_){if(m_bVisited)return;//防止两个相邻的region的Portal形成死循环m_bVisited=TRUE;for(inti=0;im_NumOfPortals;i++){if(m_aPortals[i].m_bOpen){//如果Portal在viewfrustum中if(!lpRender-Cull(m_aPortals[i]))m_aPortals[i].m_pRegion-Draw(lpRender_);}m_apObjects-Draw(lpRender_);}m_bVisited=FALSE;}通常我们使用二叉树的方法来组织region，理想的情况下每个二叉树树的Leaf就是一个region，通过二叉树的遍历可以很容易的找到照相机（camera）所在的region。不过我觉得实际做场景的时候不会这么理想，因该是一个region可能被划分成了几个leaf，不过只要保证每个leaf一定属于某个region，我们就可以对每个leaf增加一个region的引索（index），同样可以很方便的找到所在的region。Portal引擎的一个不太好的地方就是，你必须手动设定许多Portal，设计场景的会有一些限制，否则得不到很好的效果。在了解了这些技术以后我又去看了“Genesis3D”的源代码，只看了场景组织的部分，我先把我的理解说一下。Trace.hTrace.cvis.hvis.cworld.hworld.cGenesis3D有如下几个概念：Model//Model[0]表示场景所有中不动的部分，//Model[i](i0)表示场景中的活动物体（比如：门，升降台）//Model[0]对应一个二叉树//Model中还有FirstLeaf，NumOfLeafs来记录对应的Leafs//Model结构中有一个intArea[2]的结构，//对于本身是活动门的Model，正好可以记录连通的两个AreaCluster//不敢肯定，推测是一种区域的概念，比Area要大//而且Cluster之间没有动态的连通关系，只有临街关系。Area//相当于我们上面所说的Region的概念，//Genesis3D的一个场景中昀多允许256个Area，//这可以从它的world结构中的AreaConnection[256][256]看出，//1表示连通，0表示不通//Area之间的连通性通过Model[i](i0)来控制//intVisFrame表示Area是否可见Node//BSP上的结点//intVisFrame表示Node是否可见Leaf//划分世界的二叉树的叶子，//每个Leaf上都有一个Area的index//每个Leaf上都有一个Cluster的index//以及一个PolygonList的指针Actor//活动的人因此我可以基本推断若干Leaf构成一个Area，若干Area又可以构成一个Cluster？（猜测）对于二叉树上的每个Node都设置了一个VisFrame，用于判断是该结点代表的子树是否可见。我们可以看到它的渲染过程：RenderScene(...){Vis_VisWorld(...);//检测并设定可见性RenderWorldModel(...);//Render场景不动的部分就是Model[0]RenderSubModels(...);//Render场景中活动的部分RenderActors(...);//Render所有的人物}下面我们来分析每个过程：Vis_VisWorld(...){将所有的结点设置为不可见//它用的方法很巧妙，这个留给读者自己去看了找到Camera所在的Leaf，假设为Leaf[E]Leaf[E].VisFrame=可见Area[Leaf[E].AreaIndex].VisFrame=可见//通过一下这个递归过程设定所有Area的可见性//通过AreaConnection[][]来判断，//凡是跟Area[Leaf[E].AreaIndex]能够连通的都设定为可见//具体方法比较简单，留给读者自己去看了Vis_Flood_r(Area[Leaf[E].AreaIndex])for(inti=0;iModel[0].NumOfLeafs;i++){//我就是根据这里的顺序，推测Cluster是比Area更大的区域//否则就应该先判断Area了if(Cluster[Leaf[E].ClusterIndex]与Cluster[Leaf[i].ClusterIndex]不相通)continue;//如果Leaf[i]所在的Area不可见，那么Leaf[i]不可见if(Area[Leaf[i].AreaIndex]!=可见)continue;Leaf[i].VisFrame=可见//既然Leaf[i]可见，那么i的所有父结点都应该可见，//这个方法也很简单，留给读者自己去看了MarkVisibleParents(i);//下面的过程是将Leaf所包含的所有surface设定为可见//我不清楚他为什么要做这一步...}for(i=1;iNumOfModels;i++){//判断Model[i]是否可见的方法是，//求Model[i]的Axis-AlignedBoudingBox的Center//遍历Model[0]的二叉树，找到Center所在的Leaf//如果该Leaf可见，那么该Model可见//否则该Model不可见if(ModelVisible(Model[i]))Model[i].VisFrame=可见}}RenderWorldModel(...);//渲染场景不动的部分就是Model[0]{遍历Model[0]对应的二叉树，除了一般用Frustum来剪枝以外，一旦发现Node.VisFrame不可见，那么该Node代表的整个子树都被拣选（Cull）掉。如果Leaf.VisFrame不可见，那么Leaf中的所有Polygon都被拣选（Cull）掉}RenderSubModels(...);//渲染场景中活动的部分{for(i=1;iNumOfModels;i++){if(Model[i].VisFrame=可见)绘制Model[i]}}RenderActors(...);//渲染所有的人物{for(i=0;iNumOfActors;i++){Actor[i]的AABB的Center所在的Leaf如果可见绘制Actor[i]的PolygonList，否则不绘制。}}因为Actor不会同时属于两个Area，所以只要找到Actor的Center所在的Leaf是否可见就可以判断Actor是否可见了。现在有些游戏使用其它的组织方法，比如Oni中就使用了八叉空间分割树（Octtree），比起二叉树、Portal技术由很大的优势，在2000年游戏开发者年会中“HiddenSurfaceReductionandCollisionDetectionBasedonOctTrees”一文（pease.doc）就比较详细的介绍了Bungie公司的这个方法，我觉得很值得一试。我在看了peace.doc以后决定采用oni的做法，使用他们介绍的那种八叉树＋光线追踪（Raycasting）的组织结构。因为在思考二叉树＋Portal的引擎时有很多问题难以解决，我觉得难点在于构造含有Portal的二叉树结构，地图编辑器很难做，Genesis3D的源代码并不包含地图编辑器的部分，所以你无法得知它是如何构造它的二叉树的。给出一个静止的场景部分，划分二叉树并不难，但是如果你希望能够构造含有Portal的region就比较麻烦了。1）首先，基本上不太会有一个Leaf恰好等于一个region，实际划分可能出现一个Leaf与若干region相交，我昀后的结论是可以用以下规则来划分，如果一个Leaf属于某一个region，那么该Leaf就不用再划分了，如果它与n个(n1)个region相交，那么就要将该Leaf继续划分下去。如此应该可以保证每个Leaf一定属于某个region，那么在渲染的时候，只要找到照相机所在的Leaf就可以通过该Leaf上记录的region索引，找到所需处理的region了（Genesis3D里面的Leaf结构就可以找到他所谓的Area）。如果是这种思路，那么下面问题就必须要解决。2）Region如何识别或者划分，计算机自动（不太可能，这种region的概念完全是人定的），手工识别（如何手工识别，在一个复杂的场景中选择一个个面，然后还必须构成封闭的空间才能定为region，这样恐怕也不现实）我还想过，所有的模型都有3DSMAX来做，每次美工确保做一个Region（比如一个房间），我们自己做一个工具去识别包围该region的多面体，还必须能够手工加少数辅助对该region进行Portal的指定和识别，然后在地图编辑器中仅仅导入这样的结构，构造实际场景的时候只是设定一下region的位置，然后对于每个Portal设定他们指向的region代号。