游戏开发中的渲染加速算法总结（一）

本文由@浅墨_毛星云 出品，转载请注明出处。
文章链接： http://blog.csdn.net/poem_qianmo/article/details/78884513

导读

这是一篇1万3千余字的文章，通过阅读，你将对游戏开发与实时渲染中加速渲染算法的以下要点有所了解：

常用空间数据结构（Spatial Data Structures）

• 层次包围盒（BVH ,Bounding Volume Hierarchies）
• BSP树（BSP Trees）
• 八叉树（Octrees）
• 场景图（Scene Graphs）

各种裁剪技术（Culling Techniques）

• 背面裁剪（Backface Culling）
• 视锥裁剪（View Frustum Culling）
• 遮挡剔除（Occlusion Culling）
• 层次视锥裁剪（Hierarchical View Frustum Culling）
• 入口裁剪（Portal Culling）
• 细节裁剪（Detail Culling）

各种层次细节（LOD，Level of Detail）技术

• 几种LOD切换技术（Discrete Geometry LODs、Blend LODs、Alpha LODs、CLODs and Geomorph LODs）
• 几种LOD的选取技术（Range-Based、Projected Area-Based、Hysteresis）

大型模型的渲染（Large Model Rendering）

点渲染（Point Rendering）

引言

《Real-Time Rendering 3rd》书中提到，实时渲染领域有四大目标，激励着游戏开发者们不断进步，它们是：

• 更高的每秒帧数
• 更高的分辨率
• 渲染更多的物体与更具真实感的场景
• 实现更高的复杂度

 
而要不断地追逐这四大目标，需要持续不断的优化算法，进行技术革新和硬件的升级。其中，加速渲染相关的算法一直是追逐这四大目标的重要一环。

这篇文章将基于《Real-Time Rendering 3rd》第十四章“Acceleration Algorithms”的内容，介绍计算机图形学和游戏开发中常用的对渲染进行加速的算法，尤其是对大量几何体的渲染，而很多这类算法的核心都是基于空间数据结构（Spatial Data Structures）。所以，本文将先介绍一些游戏开发中常用的空间数据结构，再进行各种加速算法，不同种类的裁剪算法，LOD相关的介绍。

一、空间数据结构 | Spatial Data Structures

空间数据结构（Spatial Data Structures）是将几何体组织在N维空间中的一系列数据结构，而且我们可以很容易地将二维和三维的一些概念扩展到高维之中。这些空间数据结构可以用于很多实时渲染相关操作的加速查询中，如场景管理，裁减算法、相交测试、光线追踪、以及碰撞检测等。

空间数据结构的组织通常是层次结构的。宽泛地说，即最顶层包含它之下的层次，后者又包含更下层的层次，以此类推。因此，这种结构具有嵌套和递归的特点。用层次结构的实现方式对访问速度的提升很有帮助，复杂度可以从O(n)提升到O(log n)。但同时，使用了层次结构的大多数空间数据结构的构造开销都比较大，虽然也可以在实时过程中进行渐进更新，但是通常需要作为一个预处理的过程来完成。

一些常见的空间数据结构包括：

• 层次包围盒（Bounding Volume Hierachy，BVH）
• 二元空间分割树（Binary Space Partitioning，BSP）
• 四叉树
• kd树
• 八叉树（Octree）
• 场景图 （Scene Graphs）

其中，BSP树和八叉树都是基于空间细分（Space Subdivision）的数据结构，这说明它们是对整个场景空间进行细分并编码到数据结构中的。例如，所有叶子节点的空间集合等同于整个场景空间，而且叶子节点不相互重叠。

BSP树的大多数变种形式都是不规则的，而松散地意味着空间可以被任意细分。

八叉树是规则的，意味着空间是以一种均匀的形式进行分割，虽然这种均匀性限制比较大，但这种均匀性常常是效率的源泉。另外值得注意的是，八叉树是四叉树的三维空间推广。

另一方面，层次包围盒不是空间细分结构，它仅将几何物体周围的空间包围起来，所以包围层次不需要包围所有的空间。

下文将对其中的层次包围盒、二元空间分割树、八叉树进行近一步介绍，并还将简单提到场景图(SceneGraph)，这是一种比较高层次的，相较渲染性能更关注模型关系的数据结构。

当然，限于篇幅原因，这里的每种数据结构都无法介绍得事无巨细，但已在每种数据结构介绍的最后备好了一些延伸的阅读材料，方便希望进一步了解的朋友们进行延伸阅读。

1.1 层次包围盒BVH | Bounding Volume Hierarchies

层次包围盒（Bounding Volume Hierarchies, BVH）方法的核心思想是用体积略大而几何特征简单的包围盒来近似地描述复杂的几何对象，从而只需对包围盒重叠的对象进行进一步的相交测试。此外，通过构造树状层次结构，可以越来越逼近对象的几何模型，直到几乎完全获得对象的几何特征。

对于三维场景的实时渲染来说，层次包围体（Bounding Volume Hierarchy，BVH）是最常使用的一种空间数据结构。例如，层次包围体经常用于层次视锥裁减。场景以层次树结构进行组织，包含一个根节点（root）、一些内部节点（internal nodes），以及一些叶子节点（leaves）。顶部的节点是根，其无父节点。叶子节点（leaf node）包含需渲染的实际几何体，且其没有子节点。

相比之下，内部节点包含指向它子节点的指针。因此，只要根节点不是这颗树唯一的一个节点，那么它就是一个内部节点。树中的每一个节点，包括叶子节点，都有一个包围体可以将其子树中的所有几何体包围起来，这就是包围体层次的命名来源，同时，也说明了根节点有一个包含整个场景的包围体。

图1 左图为一个包含6个物体的简单场景，每个物体由一个包围的球体封闭起来，其中可以将包围球体归组为一个更大的包围球体，如此内推，直到所有的物体被最大的球体包围，右图所示为层次包围体（树），可以用来表示左图的物体层次、根节点的包围体包含场景中的所有物体。

图2 层次包围盒的实现 @http://thomasdiewald.com/blog/?p=1488

图3 层次包围盒的实现 @http://thomasdiewald.com/blog/?p=1488

1.1.1 BVH的延伸阅读材料

[1] https://hal.inria.fr/inria-00537446/file/bounding_volume_hierarchies.pdf
[2] https://www.codeproject.com/Articles/832957/Dynamic-Bounding-Volume-Hiea...
[3] Wald I, Boulos S, Shirley P. Raytracing deformable scenes using dynamic bounding volume hierarchies[J]. ACM Transactions on Graphics (TOG), 2007, 26(1): 6.

1.2  BSP树 | BSP Trees

BSP树(二叉空间分割树，全称Binary Space Partitioning Tree)是一种常用于判别对象可见性的空间数据结构。类似于画家算法，BSP树可以方便地将表面由后往前地在屏幕上渲染出来，特别适用于场景中对象固定不变，仅视点移动的情况。

其中，BSP是Binary Space Partitioning（二叉空间划分法）的缩写。这种方法递归地将空间使用超平面划分为凸面体集合。而这种子划分引出了借助于称之为BSP树的树形数据结构的场景表示。

图4 一个BSP树的构造

BSP 树是一棵二叉树，每个节点表示一个有向超平面，其将当前空间划分为前向（front）和背向（back）两个子空间，分别对应当前节点的左子树和右子树。且BSP 树已经在游戏工业上应用了许多年（Doom是第一个使用BSP树的商业游戏）。尽管在现今BSP树已经没像过去那么受欢迎了，但使用依然广泛。

BSP树的一个有趣特性是，如果用一种特定的方式遍历，树的几何内容可以从任何角度进行前后排序。这个排序可以近似轴对齐，精确对齐多边形BSP。与BVH不同的是，BVH通常不包含任何形式的排序。

1.2.1 BSP树的构造
 
  •  从空树开始，每次选择一个面片作为节点插入树中

  •  每次插入一个新节点，从树的根节点开始遍历

• 如果新节点面片与当前结点片面相交，将新面片分割成两个面片
• 新节点在当前节点前向空间，插入左子树
• 新节点在当前节点背向空间，插入右子树
• 当前节点为空，直接插入新节点

  •  直到所有面片都被插入树中

简单来说，若要创建BSP树，需递归将一个平面空间一分为二，并将几何体归类到这两个空间中来完成。
 
1.2.2 BSP树的遍历

从根节点开始，判断输入位置与当前分割平面的“前”、“后”关系，

“前”则遍历左子树，“后”则遍历右子树，递归到叶子节点终止。

用平面方程 Ax + By + Cz + D = 0判断前后位置，可用 D(x0, y0, z0 ) = Ax0 + By0 +Cz0 +D 进行判别，

其中：

• D > 0：在平面前面
• D = 0：在平面上
• D < 0：在平面后面

 

这里贴出从后向前遍历BSP的示例代码：

traverse_tree(bsp_tree* tree,point eye)
{
	location = tree->find_location(eye);
 
	if(tree->empty())
		return;
 
	if(location > 0)      // if eyeinfront of location
	{
		traverse_tree(tree->back,eye);
		display(tree->polygon_list);
		traverse_tree(tree->front,eye);
	}
	else if(location < 0) // eye behind location
	{
		traverse_tree(tree->front,eye);
		display(tree->polygon_list);
		travers_tree(tree->back,eye);
	}
	else                  // eyecoincidental with partition hyperplane
	{
		traverse_tree(tree->front,eye);
		traverse_tree(tree->back,eye);
	}
}

1.2.3 BSP树的种类

在计算机图形学中，BSP树有两大类别，分别是为轴对齐（Axis-Aligned）BSP树和多边形对齐（Polygon-Aligned）BSP树。下面分别进行介绍。

1.2.4 轴对齐BSP树 | Axis-aligned BSP tree

轴对齐BSP树可以按如下方式来创建。首先，将整个场景包围在一个AABB（轴对齐包围盒，Axis-Aligned Bounding Box）中，然后以递归的方式将这个包围盒分为若干个更小的盒子。

现在，考虑一下任何递归层次的盒子。选取盒子的一个轴，生成一个与之垂直的平面，将盒子一分为二。有一些方法可以将这个分割平面固定，从而将这个盒子分为完全相同的两部分，而也有其他的一些方法，允许这个平面在位置上有一些变化。与分割平面相交的物体，要么存储在这个层次上，成为两个子集中的一员，要么被这个平面分割为两个不同的物体。经过这个过程，每个子集就处于一个比较小的盒子中，重复这个平面分割的过程，就可以对每个AABB进行递归细分，直到满足某个标准才终止这个分割过程。而这个标准，通常是用户定义的树最大深度，或者是盒子里面所包含的几何图元数量，需低于用户定义的某个值。

分割平面的轴线和位置对提高效率至关重要。一种分割包围盒的方法就是轴进行循环。即在根节点，沿着x轴对盒子进行分割，然后再沿着y轴对其子盒子进行分割，最后沿z轴对其孙盒子进行分割。这样，就完成了一个循环周期。使用这种分割策略的BSP树常被称为k-d树。而另一种常见策略是找到盒子的最长边，沿着这条边的方向对盒子进行分割。

下图展示了一种轴对齐BSP树的分割过程。

图5 轴对齐 BSP树。在这个示例中，允许空间分割位于轴上的任意位置，不一定必须在中点位置，形成的空间体分别用A~E来标志。右图所示的树是当前的BSP树数据结构，每个叶子节点表示一个区域，区域内容显示在下方。注意，黄色三角形在物体列表中含有C和E两个区域，因为它同时覆盖了这两个区域。

值得一提的是，从前到后的粗排序（Rough Front-to-Back Sorting）是轴对齐BSP树的一种应用示例，这种方法对于遮挡剔除算法非常有用。而在视点的另一侧进行遍历，可以得到从后向前的粗排序（Rough Fack-to-Gront Sorting）,这对于透明排序非常有用。且还可以用来测试射线和场景几何体相交的问题，只需将视点位置换为射线原点即可，另外还可以用于视锥裁剪。

1.2.5 多边形对齐BSP树 | Polygon-aligned BSP tree

多边形对齐BSP树（Polygon-alignedBSP tree）是BSP树的另一大类型，其中将多边形作为分隔物，对空间进行平分。也就是说，在根节点处，选取一个多边形，用这个多边形所在平面将场景中剩余多边形分为两组。对于与分割平面相交的多边形来说，沿着其中的交线将这个多边形分为两部分。然后，在分割平面的每个半空间中，选取另外一个多边形作为分隔物，只对这个分隔物所在平面的多边形进行继续分割，直到所有的多边形都在BSP树中为止。

需要注意，多边形对齐BSP树的创建是一个非常耗时的过程，这些树通常只需计算一次，可以存储起来进行重用。

下图是一个多边形对齐BSP树的图示。

图6 多边形对齐BSP树。左图中，多边形分别用A~G表示。首先，用多边形A对空间进行分割，生成的两个半空间分别由多边形B和C分割，由B形成的分割平面与左下角的多边形相交，将其分割为多边形D和E。最后形成的BSP书如右图所示。

因为完全不平衡树的效率非常低，所以多边形对齐BSP树分割时最好是形成平衡树，即每个叶子节点的深度相同或者相差一个层次的树。

多边形对齐BSP树的一个典型性质就是对于一个给定的视点来说，可以对该结构按照从后往前（或者从前往后）的顺序进行严格遍历，而轴对齐的BSP通常只能给出粗略的排序顺序。所以，基于多边形对齐BSP树的此性质，建立了严格的前后顺序，可以配合画家算法来绘制整个场景，而无需Z缓冲。

多边形对齐BSP树的其他应用也包括相交测试和碰撞检测等。

1.2.6 BSP树的延伸阅读材料推荐
 
[1] http://web.cs.wpi.edu/~matt/courses/cs563/talks/bsp/bsp.html
[2] https://pdfs.semanticscholar.org/90e4/c4a65b4b04d9e2374e5753659c102de4c0...
[3] https://en.wikipedia.org/wiki/Binary_space_partitioning
[4] http://archive.gamedev.net/archive/reference/programming/features/bsptre...

1.3 八叉树 | Octrees

八叉树（octree），或称八元树，是一种用于描述三维空间的树状数据结构。八叉树的每个节点表示一个正方体的体积元素，每个节点有八个子节点，这八个子节点所表示的体积元素加在一起就等于父节点的体积。一般中心点作为节点的分叉中心。

简单来说，八叉树的空间划分方式很简单，即递归地进行规整地1分为8的操作。如下图，把一个立方体分割为八个同样大小的小立方体，然后递归地分割出更的小立方体。这个就是八叉树的命名来源。这种分割方式可以得到比较规则的结构，从而使得查询变得高效。

图7 八叉树的构成 @wiki

相似地，四叉树是把一个二维的正方形空间分割成四个小正方形。而八叉树是四叉树的三维空间推广。

图8 八叉树的实现 @http://thomasdiewald.com/blog/?p=1488
图9 八叉树的实现 @http://thomasdiewald.com/blog/?p=1488
图10 八叉树的实现 @http://thomasdiewald.com/blog/?p=1488

上述三幅图也均来自《Space Partitioning: Octree vs.BVH》http://thomasdiewald.com/blog/?p=1488 一文，这是一篇比较八叉树和BVH的有趣的文章，有兴趣的朋友可以阅读一下。

1.3.1 松散八叉树 Loose Octrees

松散八叉树的基本思想和普通八叉树一样，但是每个长方体的大小选中比较宽松。而如果一个普通长方体的边长为l，那么可以用kl来代替，其中 k>1，如下图所示。

图11  一个普通八叉树和松散八叉树的比较。图中黑色的原点表示长方形的中心点（第一次细分）。在左图中，星形物体刺穿了一个普通八叉树的一个分割平面。，这样，一种选择就是将这个星型物体放在最大的长方形中（根节点的长方体）。而右图所示为一个k=1.5的松散八叉树，也就是将长方体放大了50%，如果将这些长方体稍微移动，就可以保证区分出它们。这样，这个星型多边形就完全位于左上角的长方形之中。

1.3.2 八叉树延伸阅读材料

[1] http://web.cs.wpi.edu/~matt/courses/cs563/talks/color_quant/CQoctree.html
[2] https://en.wikipedia.org/wiki/Octree
[3] Losasso F, Gibou F, Fedkiw R.Simulating water and smoke with an octree data structure[C]//ACM Transactionson Graphics (TOG). ACM, 2004, 23(3): 457-462.

1.4 场景图 | Scene Graphs

BVH、BSP树和八叉树都是使用某种形式的树来作为基本的数据结构，它们的具体区别在于各自是如何进行空间分割和几何体的存储，且他们均是以层次的形式来保存几何物体。然而三维场景的绘制不仅仅是几何体。

然而，渲染三维场景不仅仅只是渲染出几何图形，对动画，可见性，以及其他元素的控制，往往需要通过场景图（Scene Graphs）来完成。

场景图被誉为“当今最优秀且最为可重用的数据结构之一。”Wiki中的对场景图的定义是“场景图（Scene Graph）是组织和管理三维虚拟场景的一种数据结构，是一个有向无环图（DirectedAcyclic Graph， DAG）。”

场景图是一个面向用户的树结构，可以通过纹理、变换、细节层次、渲染状态（例如材质属性）、光源以及其他任何合适的内容进行扩充。它由一棵以深度优先遍历来渲染整个场景的树来表示。

图12 通过创建场景图来表示对象

另外提一句，开源的场景图有Open Scene Graph和OpenSG等，有兴趣的朋友们可以进行进一步了解。

场景图的延伸阅读材料：
[1] http://www.openscenegraph.org/index.php/documentation/knowledge-base/36-...
[2] https://en.wikipedia.org/wiki/Scene_graph
[3] http://archive.gamedev.net/archive/reference/programming/features/sceneg...

未完待续......

来源：CSDN，作者：浅墨_毛星云
原文：https://blog.csdn.net/poem_qianmo/article/details/78884513
版权声明：本文为博主原创文章，转载请附上博文链接！