写在前面

本专栏内容均为学堂在线慕课《3D游戏引擎架构设计基础》中的内容。个人将其转化成文字和图片的版本（个人更加喜欢文字版本的教程，阅读速度更快很多），方便查阅。原课程链接：3D游戏引擎架构设计基础。

场景管理

场景管理概述与BVH

为了提高场景管理的效率，场景对象的逻辑组织架构通常是树型的结构。举例：

游戏场景组织的架构包括：

场景图，多用于管理动态场景。
八叉树，多用于管理大型室外场景。
二叉空间分割，即BSP树，多用于管理室内场景。

BVH（Bouding Volume Hierarchies）包围体层次结构，用于快速判断场景对象之间的几何位置关系，其通过BVH方法为每个对象计算包围体。BVH就是节点有包围体信息的树状结构。举例：

其中包围体类型又包括：包围球，轴平行包围体，有向包围体，k-离散有向多面体。其计算复杂度是逐渐上升的。其中计算方法如下图所示：

场景组织结构：场景树，八叉树和BSP树

场景树

用层次结构表示场景中的对象
上层对象的操作影响其所有子树的对象
有向无环图

场景图的抽象描述如下：

八叉树

将空间分成八等份，如果被分的部分填满了场景内容，或被分的部分没有场景内容，则不再分割；否则，继续分割，直到满足终止条件。

八叉树的组织：

其缺点是叶子节点的指针空间都为空，浪费很多空间。其中一种改进的做法是：

线性八叉树节省了储存空间，场景运算也非常简便。

八叉树分割算法：

其中可以通过计算分割的立方体与几何包围体的包含关系来确定几何体与场景的几何关系是F（Full）还是E（Empty）。递归的分割算法实现非常简洁快速。

八叉树的构建思想决定了场景的有序性，当镜头位置和方向确定后，场景的遍历顺序就可以确定。八叉树的遍历方式可以从后向前遍历，或是从前向后遍历。其中前者被也称为画家算法，这种方式不需要计算遮挡关系，但是需要渲染每一个面，效率很低。后者是最近的面先渲染，再通过遮挡关系或深度缓存信息，决定像素的最终渲染结果。这种方法深度缓存需要在像空间执行，但是减少了很多渲染计算，效率较高。

八叉树的优点如下：

BSP树

是用空间超平面，递归地将空间分割为凸多面体集，用二叉树表示被分割的空间。

其中凸多面体的定义为：由若干平面多边形所圈成的封闭的立体叫做多面体，这些平面多边形称为多面体的面，这些多边形的边和顶点分别称为多面体的棱和顶点。如果多面体在它们每一面所决定的平面的同一侧，则称此多面体为凸多面体，或欧拉多面体。凸多面体的任何截面都是凸多边形，与凹多面体相反。

其分割思想为：其构建算法为：其中几个几何问题算法包括：

如何判断凸多面体：
如何判断两个面片的几何位置关系：
判断面片与顶点的几何位置关系：

解决了上述几个几何问题，继续讨论BSP树的构建。另外一个问题是，如何确定分割的超平面，选择步骤为：

剔除凸包面
计算NF、NB、NS
选择分割空间的超平面最后是BSP树完整的构建算法： BSP树的遍历算法（画家算法）：可以通过从前往后遍历，通过深度缓存进行计算进行优化。 BSP树的应用：最后对几种算法进行对比：

场景管理实例

OGRE场景管理

OGRE中场景类型分为：静态、动态、扩展的：

静态型：非常庞大、向四周不规则蔓延的、不可移动的、由三角形网格组成的物，包括地形、天空盒等，有以下的表示：SkyPlane, Skybox, SkyDome(SceneNode *)；World geometry, 通常是一个确定的SceneManager；Static geometry，通常SceneManager的树结构是确定的，如室内场景。
动态性：可在场景中移动的、离散的、相对较小的物体，主要包括实体（Entity）、粒子、摄像机等，用SceneNode类和MovableObject类表示。
扩展型：主要包括BSPSceneNode, OctreeNode, PCZSceneNode等。

OGRE场景管理部分类图：其中的主要类描述： SceneManger（场景管理单例）主要功能图： OGRE创建场景对象示例：