对于一个有很多物体的3D场景来说，渲染这个场景最简单的方式就是用一个List将这些物体进行存储，并送入GPU进行渲染。当然，这种做法在效率上来说是相当低下的，因为真正需要渲染的物体应该是视椎体内的物体。除此之外，从裁剪算法和碰撞检测等算法的效率来说，使用这种数据结构也是相当低效的。比较好的方式是使用具有层次结构的空间数据结构存储待渲染的物体，如BVH（包围体层次结构）、BSP（二叉空间分割）树、四叉树、八叉树和模糊K-D树等，在进行空间查找的时候将时间复杂度从O(n)降低到O(logn)。当然，对应的代价是每帧更新的时候，需要更新对应的空间数据结构。本文主要对BVH、BSP和八叉树进行介绍。
1、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的示例。
图1 BVH示例，左图为6个物体的简单场景，右图为对应的BVH
在场景中的物体移动的时候，需要对BVH进行更新。如果物体移动以后仍然在原先的包围体内，则不需要更新；若不在，则删除这个物体所在节点，并重新计算其父节点的包围体，然后，从根节点开始，以递归形式将这个节点插入这棵树中。另一种方法则是以递归形式增大父节点的包围体，直到这个包围体可以包含这个子节点为止。无论使用哪种方法，随着编辑操作的增多，这棵树会变得越来越不平衡，效率也会越来越低。
2、BSP（binary space partitioning，二叉空间分割）树
BSP树在1969年由Shumacher首次提出，当时并未想到能成为开发娱乐产品的算法，但从90年代初BSP树就已经被用于游戏行业来改善性能，并使利用地图中更多细节成为可能。第一个使用该技术的游戏是Doom，由游戏行业中的两位传奇人物JohnCarmack和John Romero创立。
在计算机图形学中，BSP树有两种不同的形式：分别为轴对齐(axis-aligned)和多边形对齐(polygon-aligned)。要创建BSP树，首先用一个平面将空间一分为二，然后将几何体按类别划分到这两个空间中，随后以递归形式反复进行这个过程。这种树有一个非常有趣的特性，如果按照一定的方式对树进行遍历，那么会从某个视点将这棵树包含的几何体进行排序（对于轴对齐的方式来说，它是粗略的排序；对于多边形对齐方式来说，它的准确的排序）。在Z-Buffer问世之前，基于多边形对齐的BSP树成为3D游戏进行场景排序的最佳方案。
2.1、轴对齐BSP树
轴对齐BSP树的创建方式如下：首先，将整个场景包围在一个AABB中，选取xyz其中一个轴，生成一个与之垂直的平面，将该AABB分为两个小AABB，然后以递归的方式继续对生成的AABB进行分割，直到树达到最大深度或AABB中包含的几何图元数量低于用户定义的某个阈值。轴对齐BSP树的结构如图2所示。
图2 BSP树结构
在分割的时候，有些物体会与分割平面相交，对这些物体有以下几种处理方法：1）存储在分割平面所在的节点中，如图2中的三角形也可以存储在1b中（图2采用的是第二种方法）；2）存储在多个叶子节点，如图2所示；3）将这个物体由这个平面分为两个物体。第一种方法效率比较低，比如物体比较小，但是恰好被平面分割，不得不将其存在较高的节点中，所以实际中很少采用这种做法；第二种方法会导致相同的物体被绘制多次，一般使用timestamping方法对其进行改进，即对绘制过的几何体做一个标记，绘制前对这个标记进行检查，若已经绘制过，则不再绘制，这种方法使用的比较多；第三种方法由于要对图元进行分割，所以计算量比较大，而且对于动态物体的渲染不太方便。
分割平面的选取也有多种方法：1）按照xyz-xyz……的顺序进行循环分割，如果每次都选择中间位置，则结果和八叉树一样。当然，也可以随意选定位置，BSP树相对于八叉树的优势之一就是平面的位置可以随意选择。2）对AABB的最长边进行分割。3）通过相关算法（geometric probablity theory）计算出近似最优的分割平面，该分割平面将尽可能少的与几何体相交。
轴对齐BSP树具有粗略排序的特征，对遮挡裁剪（occlusion culling）等算法具有较好的加速作用。在遮挡裁剪中，如果能够按照从前往后的顺序进行渲染，则可以减少像素着色器的负担。使用轴对齐BSP树，从根节点开始，先遍历靠近视点一侧的所有物体，再遍历远离视点的所有物体，对于每个子节点采用这种方式递归，则可以做到近似的从前往后进行渲染。由于它没有对叶子节点内的几何体进行排序，而且一个物体可能在多个叶子节点中，所以轴对齐BSP树只是粗略的排序。
2.2、多边形对齐BSP树
多边形对齐的BSP树采用多边形所在的平面进行空间分割，具体方法如下：在根节点处选取一个多边形，用这个多边形所在平面将场景中剩余的多边形分为两组。对于与分割平面相交的多边形，沿着相交线将这个多边形分为两个部分。接下来采用同样的方式对这些多边形进行递归分割，直到所有的多边形都在这棵BSP树中，如图3所示。
图3 多边形对齐BSP树示意图
多边形对齐BSP树的创建非常耗时，适合静态场景，它的优点是对于给定视点，可以按照严格排序的顺序进行遍历，在没有Z-Buffer的DOS时代，这种方法是3D游戏制作中一种很好的方法，著名的FPS游戏Doom和Quake都使用了这种方法。当然，现在已经不再使用了这种方法（它的好处被Z-Buffer取代，其缺点是只适用于静态场景，使用不便）。
3、八叉树
八叉树类似轴对齐BSP树。沿着轴对齐包围盒的三条轴对其进行分割，分割点必须位于包围盒的中心点，以这种方式生成8个新的包围盒。八叉树通过将整个场景包含在一个最小的轴对齐包围盒中进行构造，递归分割，直到达到最大递归层次或包围盒中包含的图元小于某个阈值，其分割过程如图4所示。八叉树的使用方式与轴对齐BSP树一样，可以处理同类型的查询，也可以用于遮挡裁剪算法中。由于八叉树是具有规则的结构，所以有些查询会比BSP树高效。
图4 八叉树分割过程
在八叉树的结构中，通常将物体保存在叶子节点中，其中有些物体必须保存在多个叶子节点中（2.1节第二段的第二种方法）。这种做法的一个最大弊端是增大数据量，而如果使用指针，则会导致八叉树的编辑变得更加困难。“松散的八叉树”算法对这个问题进行了改进。
4、空间结构的选取
目前为止，没有一种空间结构绝对的最优，根据不同场合选择不同的空间结构是一个明智的做法。八叉树和BSP树相比，由于其不需要存储分割平面的信息（因为每次都是在包围盒的中心点进行分割），所以要比BSP效率更高。但是这不是绝对的，例如在一个细长的走廊场景中，用BSP明显更合适，因为对沿着走廊的轴分割次数肯定要比另外两个轴来得多，如果使用八叉树，要么浪费另外两个轴的分割空间，要么沿着走廊的轴分割不够细。
一般来说，对于室内场景使用BSP树，因为1）室内场景遮挡比较严重，使用BSP树在特定的位置分割有助于提升效率；2）室内很可能朝某个方向延伸比较多，比如一条细长的走廊。对于大规模室外场景，使用八叉树比较好，因为场景中的物体比较分散，而且不会出现太多的遮挡，由于不用存储分割平面位置，使用八叉树这种规则的空间结构能够提高效率。当然，如果这个大规模室外场景的物体主要集中在地面，使用四叉树进行空间管理会比较好。
