3D 引擎场景管理

茵为你值得

pstatus"> 本帖最后由 茵为你值得 于 2013-9-18 08:37 编辑

  我认为对于一个3D 引擎来说，最核心的部分应该算是场景组织（scene graph）了，如果这部分你都没有设计好， 那么就别指望开发一个成熟的3D 引擎了。为了开发3d 引擎，所以我首先就研究这方面的内容，对一个3D 的场景来说，又很多的物体，最简单的组织方法就是把他们用一个List 连接起来，然后在绘制没一帧的时候依次送入渲染器（render）进行处理。

  这显然不是一个很有效的方法，当处理一个普通的游戏场景都会显得非常慢的。实际上虽然一个场景中的物品很多，但是通常可见的指是以小部分，如何能够用很小的计算代价排除那些不可见的物品呢，这种方法叫做剔除隐藏面，减少绘制元（Hidden Surface Complexity Reduction）。为了实现这样的方法，牵涉到空间排序（Spatial Sorting），最基本的方法要算二叉空间分割树（BSP）了，DOOM 是第一个使用了二叉树的商业游戏。二叉树的构造简单地说就是对于要处理的一组对象，选择一个平面，将该组对象分成两组（如果由某个对象与该平面相交则用这个平面将这个对象分成两个对象）作为该结点的两个儿子，然后分别对两组对象用相同的方法，直到满足一个特定的条件（通常是到结点上只有一个对象）为止。

  二叉树确实是一种很有效的场景组织结构，因为，当给出视锥（view frustum）以后，在穿过（traverse）这棵树的时候，如果发现视锥（frustum）与结点所代表的平面不相交，那么这个结点上有一棵子树必然不可见,那么这个子树就不用送入渲染器了，当遇到Leaf 的时候，就可以获得所需的多边形数据，可以送入渲染器处理。虽然二叉树已经是非常有效的方法，但是仅仅依靠二叉树还是不能满足游戏的要求，因为现在的游戏的场景是在是很大很复杂，又很多的物品，按照二叉树的方法与viewfrustum 相交的Leaf 必然要送入渲染器，因为view frustum是很大的，所以会有很多的Leaf 与他相交，这就意味着渲染器还是要处理很多的数据，如果你确实能够看到这么多的物体，那也没有办法，但是通常，比如很多室内的场景，虽然在你的frustum 里面会由很多物体，但是你真正能够看到的还是很少的一部分，比如一个封闭的房间。因此被称为Portal 的技术被引入到游戏中来，之所以能够使用Portal 技术，那是因为很多室内场景自身的限制条件所致。我们引入region 的概念，一个region 就是一个相对封闭的空间，比如一个房间，region 与region 之间都是通过Portal（比如门或窗）相连接，因此，如果你处于一个region 当中，你就只能看到这个region 中的物体，如果你能够看到其他region 中的物体，那么你一定是通过Portal 看到的，所以处理的过程如下（考虑Portal 是单向的情况，如果两个region 可以通过一个门相互看到，我就是用两个单向的Portal）。

void CRegion：：Draw(LPRender lpRender_)
{
if (m_bVisited) return;      // 防止两个相邻的region 的Portal 形成死循环
m_bVisited = TRUE;
for (int i=0;i< m_NumOfPortals;i++)
{
if (m_aPortals.m_bOpen)
{
// 如果Portal 在view frustum 中
if (!lpRender->Cull(m_aPortals))
m_aPortals.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”的源代码，只看了场景组织的部分，我先把我的理解说一下。

Genesis3D 有如下几个概念：
Model
// Model[0]表示场景所有中不动的部分，
// Model(i>0)表示场景中的活动物体（比如：门，升降台）
// Model[0]对应一个二叉树
// Model 中还有FirstLeaf，NumOfLeafs 来记录对应的Leafs
// Model 结构中有一个int Area[2]的结构，
// 对于本身是活动门的Model，正好可以记录连通的两个Area

Cluster
// 不敢肯定，推测是一种区域的概念，比Area 要大
// 而且Cluster 之间没有动态的连通关系，只有临街关系。

Area
// 相当于我们上面所说的Region 的概念，
// Genesis3D 的一个场景中最多允许256 个Area，
// 这可以从它的world 结构中的AreaConnection[256][256]看出，
// 1 表示连通，0 表示不通
// Area 之间的连通性通过Model(i>0)来控制
// int VisFrame 表示Area 是否可见

Node
// BSP 上的结点
// int VisFrame 表示Node 是否可见

Leaf
// 划分世界的二叉树的叶子，
// 每个Leaf 上都有一个Area 的index
// 每个Leaf 上都有一个Cluster 的index
// 以及一个Polygon List 的指针

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 (int i=0;i< Model[0].NumOfLeafs;i++)
{
// 我就是根据这里的顺序，推测Cluster 是比Area 更大的区域
// 否则就应该先判断Area 了
if (Cluster[Leaf[E].ClusterIndex]与Cluster[Leaf.ClusterIndex ]不相通)
continue;
// 如果Leaf所在的Area 不可见，那么Leaf不可见
if (Area[Leaf.AreaIndex] != 可见)
continue;
Leaf.VisFrame = 可见
// 既然Leaf可见，那么i 的所有父结点都应该可见，
MarkVisibleParents(i);
// 下面的过程是将Leaf 所包含的所有surface 设定为可见
...
}
for (i = 1;i>NumOfModels;i++)
{
// 判断Model是否可见的方法是，
// 求Model的Axis-Aligned Bouding Box 的Center
// 遍历Model[0]的二叉树，找到Center 所在的Leaf
// 如果该Leaf 可见，那么该Model 可见
// 否则该Model 不可见
if (ModelVisible(Model))
Model.VisFrame = 可见
}
}
RenderWorldModel(...);      // 渲染场景不动的部分就是Model[0]
{
遍历Model[0]对应的二叉树，
除了一般用Frustum 来剪枝以外，
一旦发现Node.VisFrame 不可见，
那么该Node 代表的整个子树都被拣选（Cull）掉。
如果Leaf.VisFrame 不可见，
那么Leaf 中的所有Polygon 都被拣选（Cull）掉
}
RenderSubModels(...);      // 渲染场景中活动的部分
{
for (i = 1;i< NumOfModels;i++)
{
if (Model.VisFrame = 可见)
绘制Model
}
}
RenderActors(...);      // 渲染所有的人物
{
for (i=0;i>NumOfActors;i++)
{
Actor的AABB 的Center 所在的Leaf 如果可见
绘制Actor的PolygonList，否则不绘制。
}
}
  因为Actor 不会同时属于两个Area，所以只要找到Actor 的Center 所在的Leaf 是否可见就可以判断Actor 是否可见了。现在有些游戏使用其它的组织方法，比如Oni 中就使用了八叉空间分割树（Octtree），比起二叉树、Portal 技术由很大的优势，在2000 年游戏开发者年会中“Hidden Surface Reduction and Collision Detection Based on Oct Trees”一文（pease.doc）就比较详细的介绍了Bungie 公司的这个方法，我觉得很值得一试。

  我在看了peace.doc 以后决定采用oni 的做法，使用他们介绍的那种八叉树＋光线追踪（Raycasting）的组织结构。因为在思考二叉树＋Portal 的引擎时有很多问题难以解决，我觉得难点在于构造含有Portal 的二叉树结构，地图编辑器很难做，Genesis3D 的源代码并不包含地图编辑器的部分，所以你无法得知它是如何构造它的二叉树的。给出一个静止的场景部分，划分二叉树并不难，但是如果你希望能够构造含有Portal 的region 就比较麻烦了。
  1）首先，基本上不太会有一个Leaf 恰好等于一个region，实际划分可能出现一个Leaf 与若干region 相交，我最后的结论是可以用以下规则来划分，如果一个Leaf 属于某一个region，那么该Leaf 就不用再划分了，如果它与n 个(n>1)个region 相交，那么就要将该Leaf 继续划分下去。如此应该可以保证每个Leaf 一定属于某个region，那么在渲染的时候，只要找到照相机所在的Leaf 就可以通过该Leaf 上记录的region 索引，找到所需处理的region 了（Genesis3D里面的Leaf 结构就可以找到他所谓的Area）。如果是这种思路，那么下面问题就必须要解决。
  2）Region 如何识别或者划分，计算机自动（不太可能，这种region 的概念完全是人定的），手工识别（如何手工识别，在一个复杂的场景中选择一个个面，然后还必须构成封闭的空间才能定为region，这样恐怕也不现实）我还想过，所有的模型都有3ds max 来做，每次美工确保做一个Region（比如一个房间），我们自己做一个工具去识别包围该region的多面体，还必须能够手工加少数辅助对该region 进行Portal 的指定和识别，然后在地图编辑器中仅仅导入这样的结构，构造实际场景的时候只是设定一下region 的位置，然后对于每个Portal 设定他们指向的region 代号。 看似可行，但是实际上识别或者指定region 和portal 真的是很困难的，至少是非常复杂的事情。每当你想到一点做法，还会发现对其它的一些问题解决不方面，一直找不到关于划分region，设定Portal 的文章，所以我觉得做一个二叉树＋Portal的引擎，在地图编辑器方面就难以完成。

  在vanly 的ftp 上面有Quake 引擎的分析，他们的做法是将场景划分成二叉树以后，对于每个Leaf 都预先算好它的PVS。在渲染的时候，找到照相机所在Leaf，然后查表得到预先算好的该Leaf 的PVS，然后再绘制PVS 中的Leaf。这里它没有介绍如何计算这个PVS，而且它如何压缩使得巨大的PVS 表格只变成20K 也没有说。还有它并没有考虑会开关的Portal。所以我感觉还是没有什么进展。

  最后只有oni 的八叉树＋光线追踪还算有希望，他不需要将处于切分平面上的物体分割，而且不要指定region 和portal，对于美工建模来说限制很少，可以自由发挥，对于程序来说，地图编辑器因为不要什么识别功能，只要根据现有的数据划分出八叉树就可以了，负担也比较轻，只是它的消隐过程麻烦一些，也有些缺陷，但是感觉代价比二叉树＋Portal 要低，至少我们感觉基本可以实现，而二叉树＋Portal 的引擎还没什么好的解决方法。

myonkyo

不错啊，谢谢分享！