参考文章

http://www.cnblogs.com/kex1n/archive/2012/08/26/2657054.html 关于场景管理概述
http://www.cnblogs.com/wangchengfeng/p/3495954.html?utm_source=tuicool 常见三维场景管理
http://blog.csdn.net/zhanxinhang/article/details/6706217 四叉树和八叉树
http://blog.sina.com.cn/s/blog_6471e1bb010135w1.html bsp树种portal计数
http://www.cnblogs.com/eyeszjwang/articles/2429382.html k-d树原理
http://www.cnblogs.com/v-July-v/archive/2012/11/20/3125419.html k-d树详解

最近在游戏公司实习的过程中需要学习场景管理，这里就整理了下。

常见场景管理技术

对于一个有很多物体的3D场景来说，渲染这个场景最简单的方式就是用一个List将这些物体进行存储，并送入GPU进行渲染。当然，这种做法在效率上来说是相当低下的，因为真正需要渲染的物体应该是视椎体内的物体。除此之外，从裁剪算法和碰撞检测等算法的效率来说，使用这种数据结构也是相当低效的。比较好的方式是使用具有层次结构的空间数据结构存储待渲染的物体，如BVH（包围体层次结构）、BSP（二叉空间分割）树、四叉树、八叉树和模糊K-D树等，在进行空间查找或者剔除的时候将时间复杂度从O(n)降低到O(logn)。当然，对应的代价是每帧更新的时候，需要更新对应的空间数据结构。

常见场景管理方法

• 多层次包围盒（BVH）
• 四叉树
• 八叉树
• BSP树
• k-d树

某些游戏或引擎的场景管理方法

• quake3：BSP，代表游戏《雷神之锤》
• unreal engine4：BSP，代表游戏《天涯明月刀》《虚幻竞技场》
• cry engine3：室内BSP，室外不是很清楚，代表游戏《孤岛危机》
• RenderWare：模糊k-d树，代表游戏《侠盗猎车手》《仙剑5》
• GameBryo：包围球层次结构，代表游戏《上古卷轴：天际》《古剑奇谭》
• Angelica：室外四叉树，八叉树，室内不清楚，国产MMO基本都是地形一套管理机制，其他的一套管理机制，代表游戏《完美国际》《诛仙》《笑傲江湖》

BVH（bounding volume hierarchies，包围体层次结构）

BV（bounding volume，包围体）是包含一组物体的空间体，它要比所包含的几何物体形状简单得多，所以在使用包围体进行碰撞检测等操作的时候比使用物体本身更快。常见的包围体有AABB（axis-aligned bounding boxes，轴对齐包围盒），OBB（oriented bounding boxes，有向包围盒），以及k-DOP（discrete oriented polytope，离散定向多面体），详细解释见维基百科。

对于三维场景的实时渲染来说，BVH是最常使用的数据结构，例如，BVH经常用于视椎体裁剪。场景以层次树形结构进行组织，包含一个根节点、内部节点和叶子节点。最高节点是根，没有父节点；叶子节点保存着需要绘制的实际几何体（BVH只能存储几何体，实际渲染的物体除了几何属性还有其他属性，一般使用场景图表示，参看维基百科）。树中的每个节点，包括叶子节点，都有一个包围体，可以将其子树的所有几何体包围起来，这就是BVH（包围体层次结构）名字的来源，图1为BVH的示例。

在场景中的物体移动的时候，需要对BVH进行更新。如果物体移动以后仍然在原先的包围体内，则不需要更新；若不在，则删除这个物体所在节点，并重新计算其父节点的包围体，然后，从根节点开始，以递归形式将这个节点插入这棵树中。另一种方法则是以递归形式增大父节点的包围体，直到这个包围体可以包含这个子节点为止。无论使用哪种方法，随着编辑操作的增多，这棵树会变得越来越不平衡，效率也会越来越低。

BSP（binary space partitioning，二叉空间分割）树

BSP树在1969年由Shumacher首次提出，当时并未想到能成为开发娱乐产品的算法，但从90年代初BSP树就已经被用于游戏行业来改善性能，并使利用地图中更多细节成为可能。第一个使用该技术的游戏是Doom，由游戏行业中的两位传奇人物JohnCarmack和John Romero创立。

在计算机图形学中，BSP树有两种不同的形式：分别为轴对齐(axis-aligned)和多边形对齐(polygon-aligned)。要创建BSP树，首先用一个平面将空间一分为二，然后将几何体按类别划分到这两个空间中，随后以递归形式反复进行这个过程。这种树有一个非常有趣的特性，如果按照一定的方式对树进行遍历，那么会从某个视点将这棵树包含的几何体进行排序（对于轴对齐的方式来说，它是粗略的排序；对于多边形对齐方式来说，它的准确的排序）。在Z-Buffer问世之前，基于多边形对齐的BSP树成为3D游戏进行场景排序的最佳方案。

轴对齐BSP树

轴对齐BSP树的创建方式如下：首先，将整个场景包围在一个AABB中，选取xyz其中一个轴，生成一个与之垂直的平面，将该AABB分为两个小AABB，然后以递归的方式继续对生成的AABB进行分割，直到树达到最大深度或AABB中包含的几何图元数量低于用户定义的某个阈值。轴对齐BSP树的结构如图2所示。

在分割的时候，有些物体会与分割平面相交，对这些物体有以下几种处理方法：1）存储在分割平面所在的节点中，如图2中的三角形也可以存储在1b中（图2采用的是第二种方法）；2）存储在多个叶子节点，如图2所示；3）将这个物体由这个平面分为两个物体。第一种方法效率比较低，比如物体比较小，但是恰好被平面分割，不得不将其存在较高的节点中，所以实际中很少采用这种做法；第二种方法会导致相同的物体被绘制多次，一般使用timestamping方法对其进行改进，即对绘制过的几何体做一个标记，绘制前对这个标记进行检查，若已经绘制过，则不再绘制，这种方法使用的比较多；第三种方法由于要对图元进行分割，所以计算量比较大，而且对于动态物体的渲染不太方便。

分割平面的选取也有多种方法：1）按照xyz-xyz……的顺序进行循环分割，如果每次都选择中间位置，则结果和八叉树一样。当然，也可以随意选定位置，BSP树相对于八叉树的优势之一就是平面的位置可以随意选择。2）对AABB的最长边进行分割。3）通过相关算法（geometric probablity theory）计算出近似最优的分割平面，该分割平面将尽可能少的与几何体相交。

轴对齐BSP树具有粗略排序的特征，对遮挡裁剪（occlusion culling）等算法具有较好的加速作用。在遮挡裁剪中，如果能够按照从前往后的顺序进行渲染，则可以减少像素着色器的负担。使用轴对齐BSP树，从根节点开始，先遍历靠近视点一侧的所有物体，再遍历远离视点的所有物体，对于每个子节点采用这种方式递归，则可以做到近似的从前往后进行渲染。由于它没有对叶子节点内的几何体进行排序，而且一个物体可能在多个叶子节点中，所以轴对齐BSP树只是粗略的排序。

多边形对齐BSP树

多边形对齐的BSP树采用多边形所在的平面进行空间分割，具体方法如下：在根节点处选取一个多边形，用这个多边形所在平面将场景中剩余的多边形分为两组。对于与分割平面相交的多边形，沿着相交线将这个多边形分为两个部分。接下来采用同样的方式对这些多边形进行递归分割，直到所有的多边形都在这棵BSP树中，如图3所示。

多边形对齐BSP树的创建非常耗时，适合静态场景，它的优点是对于给定视点，可以按照严格排序的顺序进行遍历，在没有Z-Buffer的DOS时代，这种方法是3D游戏制作中一种很好的方法，著名的FPS游戏Doom和Quake都使用了这种方法，并且quake里面还用了一个技巧，用一个二进制变量的不同位来存储子节点的索引，将对子节点索引的递归算法改进成了循环的算法，优化了空间复杂度。当然，现在已经不再使用了这种方法（它的好处被Z-Buffer取代，其缺点是只适用于静态场景，使用不便）。

PVS和portal技术

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

valve公司出品的《传送门》游戏就很有这种portal技术的味道呢 :)

一个portal引擎虽然能够提供许多非常好的特性，但是它的结构太复杂。当你使用portal技术来构建一个游戏引擎时你会发现它存在许多问题，最大的一个问题是在渲染场景的每一帧都需要进行可视性检测，这会产生大量的多边形剪切操作，在场景非常复杂的情况下，运算的费用会非常的高，因此需要寻找一种技术来对场景中可视性检测进行预计算而不是在运行期间进行计算。PVS（Potentially Visible Set）可视性集合，就是为了解决这个问题而出现的一项技术，可以通过对BSP中每一个叶节点设置一个PVS，这个PVS保存了从第一个叶节点开始看到的叶节点集合，它不仅可以用来帮助加速场景渲染，还可以用来加速场景中光照运算和进行网络优化。PVS是在场景进行预渲染时计算出来的，每一个BSP的叶节点都保存一个可视节点的集合，当对场景进行渲染时，摄象机所在的叶节点将被渲染，同时保持在PVS中的叶节点也将会被渲染出来，这里需要一些算法来避免场景重复渲染，由于今天硬件加速卡的发展，它所提供的硬件Z缓冲的大小已经可以方便的解决这个问题。

四叉树（QuadTree）和八叉树（Octree）

四叉树或四元树也被称为Q树（Q-Tree）。四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等，而八叉树（Octree）主要应用于3D图形处理。八叉树其实就是四叉树在z轴上的延伸，原理差不多，四叉树多用于地形管理，八叉树多用于空间管理。

完全四叉树

不完全四叉树

八叉树类似轴对齐BSP树。沿着轴对齐包围盒的三条轴对其进行分割，分割点必须位于包围盒的中心点，以这种方式生成8个新的包围盒。八叉树通过将整个场景包含在一个最小的轴对齐包围盒中进行构造，递归分割，直到达到最大递归层次或包围盒中包含的图元小于某个阈值，其分割过程如图4所示。八叉树的使用方式与轴对齐BSP树一样，可以处理同类型的查询，也可以用于遮挡裁剪算法中。由于八叉树是具有规则的结构，所以有些查询会比BSP树高效。

在八叉树的结构中，通常将物体保存在叶子节点中，其中有些物体必须保存在多个叶子节点中。这种做法的一个最大弊端是增大数据量，而如果使用指针，则会导致八叉树的编辑变得更加困难。“松散的八叉树”算法对这个问题进行了改进。

k-d树（k-d tree）

K-D树，即K-Dimensional Tree，是一种高维索引树型数据结构。常用于大规模高维数据空间的最邻近或者K邻近查找，例如图像检索中高维图像特征向量的K邻近匹配，对KNN算法的优化等。

K-D树实际上是一棵高维二叉搜索树，与普通二叉搜索树不同的是，树中存储的是一些K维数据

先以一个简单直观的实例来介绍k-d树算法。假设有6个二维数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间内（如图1中黑点所示）。k-d树算法就是要确定图1中这些分割空间的分割线（多维空间即为分割平面，一般为超平面）。

k-d树的构建是一个递归的过程。然后对左子空间和右子空间内的数据重复根节点的过程就可以得到下一级子节点（5,4）和（9,6）（也就是左右子空间的’根’节点），同时将空间和数据集进一步细分。如此反复直到空间中只包含一个数据点。

每次划分时，应该选择哪个维度？最简单的做法就是一个维度一个维度轮流着来，但是仔细想想，这种方法不能很好地解决问题。假设有这样一种情况：我们需要切一个豆腐条，长度要远远大于宽度，要想把它切成尽量相同的小块，显然是先按照长度来切，这样更合理，如果宽度比较窄，那么这种效果更明显。所以在K-D树中，每次选取属性跨度最大的那个来进行划分，而衡量这个跨度的标准是什么？ 无论是从数学上还是人的直观感受方面来说，如果某个属性的跨度越大，也就是说越分散，那么这组数据的方差就越大，所以在K-D树进行划分时，可以每次选择方差最大的属性来划分数据到左右子树。

总结

场景管理是3D游戏中很重要的环节，决定游戏性能和效果。想当年2005年《完美国际》刚出的时候，惊叹于那超大世界无缝地图，10年前的场景管理技术已经做的那么出色！现在主流的游戏引擎ue4，unity5，ce3等都自带了很好的场景管理技术，不过作为底层引擎研发还是要了解这些技术的。

这些场景管理技术实际上也经常用到遮挡渲染、碰撞检测、图像处理等多种领域当中。

目前为止，没有一种空间结构绝对的最优，根据不同场合选择不同的空间结构是一个明智的做法。八叉树和BSP树相比，由于其不需要存储分割平面的信息（因为每次都是在包围盒的中心点进行分割），所以要比BSP效率更高。但是这不是绝对的，例如在一个细长的走廊场景中，用BSP明显更合适，因为对沿着走廊的轴分割次数肯定要比另外两个轴来得多，如果使用八叉树，要么浪费另外两个轴的分割空间，要么沿着走廊的轴分割不够细。一般来说，对于室内场景使用BSP树，因为
1）室内场景遮挡比较严重，使用BSP树在特定的位置分割有助于提升效率；
2）室内很可能朝某个方向延伸比较多，比如一条细长的走廊。对于大规模室外场景，使用八叉树比较好，因为场景中的物体比较分散，而且不会出现太多的遮挡，由于不用存储分割平面位置，使用八叉树这种规则的空间结构能够提高效率。当然，如果这个大规模室外场景的物体主要集中在地面，使用四叉树进行空间管理会比较好。