本文由@浅墨_毛星云 出品，转载请注明出处。  
文章链接： 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个物体的简单场景，每个物体由一个包围的球体封闭起来，其中可以将包围球体归组为一个更大的包围球体，如此内推，直到所有的物体被最大的球体包围，右图所示为层次包围体（树），可以用来表示左图的物体层次、根节点的包围体包含场景中的所有物体。

 

 

图28 灰色区域表示的是基于滞后的LOD选取方法的滞后区域

 

8.2.4 其他LOD选取方法

 

基于距离和基于投影面积的LOD选取最常用。除了投影面积，Funkhouser等人《Adaptive Display Algorithm for Interactive Frame Rates During Visualization of Complex Virtual Environments》一文中还提出了使用物体的重要程度，运动，以及焦点等方法来作为LOD的选取方案。

观察者的注意力是一个重要的因素。例如，在一个体育游戏中，控制球的图像是用户最注意的地方，那么其他的部分就可以相对来说低的层次细节，具体可以参见论文《Never Let ’Em See You Pop — Issues in Geometric Level of Detail Selection,”》。

 另外，也可以使用整体的可见性，如通过密集的叶子看到的附近对象可以用较低的LOD呈现。以及限制整体高级别LOD的数量以控制渲染的三角形总数的开销。其他的一些LOD选取的因素有颜色、以及纹理等。此外，也可以使用感知尺度来选择LOD。

8.3 时间临界LOD渲染 | Time-Critical LOD Rendering

我们通常希望渲染系统有一个固定的帧率，实际上这就是通常所说的“硬实时（HardReal Time）”或者时间临界（Time-Critical）。通常给定这类系统一个特定时间段（如30ms），必须在这段时间内完成相应的任务（如图像渲染）；当时间到的时候，必须停止处理。如果场景中的物体用LOD来表示，则可以实现硬实时渲染算法。

Funkhouser等人在《Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments》一文中提出了一种启发式算法（heuristic algorithm），对于场景中的所有可见物体，可以自适应选取细节层次，从而满足固定帧率的要求。这个算法在场景中具有预测性，因为可见物体的LOD选取基于预期帧率和可见物体。这种启发式算法与对应的反应性算法（reactive algorithm）形成了鲜明对比，后者的LOD选取基于前一帧画面的渲染时间。

 

九、大型模型的渲染 | Large Model Rendering

人们一直都认为所渲染的模型是适合存放到计算机主内存中的，但通常的情况其实并非如此。一个简单的例子便是渲染一个地球模型。这是一个非常复杂的话题，《Real-Time Rendering 3rd》中也仅提了一下，然后列了一些相关文献，这里也仅简单说一下。

 为了简单起见，大型模型的渲染通常会使用多个嵌套的数据结构，使用一个四叉树形式的数据结构来覆盖地球表面。而在每个叶节点内部可以根据具体内容使用不同的数据结构。此外，为了保持合适的帧率，即将进入视野中的模型区域，在需要之前从磁盘中分页，而四叉树也可以在这里使用的。

 值得一提的是，在RTR3书中6.2.5节(对应本系列文章第五篇的5.4 节)讨论了裁剪图（clip-mapping）策略，便是管理大型纹理的一种技术。

 

将不同的加速算法进行结合是不容易的事情。Aliaga等人将几种算法结合起来，用于非常大型的场景，具体可以参考如下3篇文章：

[1] Akeley, K., and T. Jermoluk, “High-Performance Polygon Rendering,” Computer Graphics (SIGGRAPH ’88 Proceedings), pp. 239–246, August 1988. Cited on p.22
[2] Akeley, K., P. Haeberli, and D. Burns, tomesh.c, a C-program on the SGI Developer’s Toolbox CD, 1990. Cited on p. 543, 553, 554
[3] Akeley, Kurt, “RealityEngine Graphics,” Computer Graphics (SIGGRAPH 93 Proceedings), pp. 109–116, August 1993. Cited on p. 126

 

而关于大型模型的渲染，有兴趣的朋友可以近一步参考这篇SIGGRAPH笔记：

Manocha D, Aliaga D. Interactive walk throughs of largegeometric datasets[J]. SIGGRAPH 00 Course notes, 2000.

 

 

十、点渲染 | Point Rendering

 

在1985年，Levoy 和 Whitted写了一篇具有开创性的技术报告《The use of points asa display primitive》。在这篇报告中，他们提出点作为一种新的图元来进行渲染，基本思想是用一个大的点集来表示物体表面并予以渲染。在随后的通道中，使用高斯滤波来填充渲染点之间的间隙。而高斯滤波器的半径取决于表面上点的密度和屏幕上的投影密度。有兴趣的朋友可以进一步了解。PDF地址在这里：

https://www.cs.princeton.edu/courses/archive/spring01/cs598b/papers/levoy85.pdf

 

 

图29 根据点渲染的方法渲染出来的模型，使用原型油彩（circular splats）。左图为名为Lucy的天使模型，拥有10万个顶点。但在渲染中只用到了300万个油彩，中图、和右图是对左边图的放大。在渲染中，中间的图像使用4万个油彩，当视点停止移动时，就变成了右图，使用了60万个油彩（此图由Szymon Rusinkiewicz的QSPlat program产生，Lucy的模型来自斯坦福图形实验室）

Reference

[1] Bittner J, Wimmer M, Piringer H, et al.Coherent hierarchical culling: Hardware occlusion queries madeuseful[C]//Computer Graphics Forum. Blackwell Publishing, Inc, 2004, 23(3): 615-624.

[2] Zhang H, Manocha D, Hudson T, et al. Visibility cullingusing hierarchical occlusion maps[C]//Proceedings of the 24th annual conferenceon Computer graphics and interactive techniques. ACM Press/Addison-WesleyPublishing Co., 1997: 77-88.

[3] 实时计算机图形学第二版[J]. 2004.

[4] Wonka P, Wimmer M, Schmalstieg D. Visibility preprocessing with occluder fusion for urban walkthroughs[M]//RenderingTechniques 2000. Springer, Vienna, 2000: 71-82.

[5] http://thomasdiewald.com/blog/?p=1488

[6] http://blog.csdn.net/skybreaker/article/details/1828104

[7] https://en.wikipedia.org/wiki/Bounding_volume_hierarchy

[8] Wonka P, Wimmer M, Sillion F X. Instantvisibility[C]//Computer Graphics Forum. Blackwell Publishers Ltd, 2001, 20(3):411-421.

[9] Wonka, Peter, Occlusion Culling for Real-Time Renderingof Urban Environments,Ph.D. Thesis, The Institute of Computer Graphics andAlgorithms, Vienna University of Technology, June, 2001. Cited on p. 679

[10] http://insaneguy.me/attachments/spatial_ds--bsp_tree-octree-kd-tree.pdf

[11] http://book.51cto.com/art/201008/220506.htm

[12] http://blog.csdn.net/silangquan/article/details/17386353

[13] Akeley, K., and T. Jermoluk, “High-Performance Polygon Rendering,”Computer Graphics (SIGGRAPH ’88 Proceedings), pp. 239–246, August 1988. Cited on p.22

[14] Akeley, K., P. Haeberli, and D. Burns, tomesh.c, a C-program on the SGI Developer’s Toolbox CD, 1990.Cited on p. 543, 553, 554

[15] Akeley, Kurt, “Reality EngineGraphics,” Computer Graphics (SIGGRAPH 93 Proceedings),pp. 109–116, August 1993. Cited on p. 126

The end.