本文由@浅墨_毛星云 出品，转载请注明出处。
文章链接： http://blog.csdn.net/poem_qianmo/article/details/78884513
游戏开发中的渲染加速算法总结（一）
游戏开发中的渲染加速算法总结（二）
八、层次细节 | LOD，Level of Detail
细节层次（Level of Detail,LOD）的基本思想是当物体对渲染出图像贡献越少，使用越简单的形式来表达该物体。这是一个已经在各种游戏中广泛使用的基本优化技术。
例如，考虑一个包含1万个三角形的汽车，其中所包含的细节信息比较丰富。当视点靠近物体时，可以使用详细的细节表示，而当视点远离物体时，比如仅需覆盖200个像素，则完全无需渲染出1百万个三角形，相反，我可以使用诸如只有1000个三角形的简化模型。而由于距离的原因，简化后的模型与细节较丰富的模型看上去其实很接近。以这种方式，可以显著地提高渲染的性能开销。
通常情况下，雾效会与LOD一起使用。这样我们可以完全跳过对一些物体的渲染，直接用不透明的雾来进行遮挡。另外，雾效的机制可以实现下文所介绍到的Time-Critical LOD Rendering。通过将元平面移近观察者，可以更早地剔除对象，并且可以实现更快速的渲染以保持帧速率。
一般情况下，完整的LOD算法包含3个主要部分：
• 生成Generation
• 选择Selection
• 切换Switching
其中，LOD的生成就是生成不同细节的模型表示。RTR3书中12.5节中讨论的简化方法可用于生成所需数量的LOD。另一种方法是手工制作具有不同数量的三角形模型。选择机制就是基于某种准则选取一个层次细节模型，比如屏幕上的评估面积。最后，我们还需要从一个细节层次转换到另一个细节层次，而这个过程便称为LOD切换。
下面对LOD的切换和选取相关的算法进一步说明。
8.1 LOD的切换 | LOD Switching
当从一个LOD切换到另一个LOD的时候，忽然的模型替换往往会引起观察者的注意。这种现象被称为突越（Poping）。
这里有几种不同的LOD切换方法，有着不同的特性：
• 离散几何LOD | Discrete Geometry LODs
• 混合LOD | Blend LODs
• 透明LOD | Alpha LODs
• 连续LOD和几何形变LOD | CLODs and Geomorph LODs
8.1.1 离散几何LOD | Discrete Geometry LODs
离散几何LOD是最简单的LOD算法，不同的表示是不同图元数量的同一模型，但这种方法突越现象严重。
8.1.2 混合LOD | Blend LODs
在概念上，完全可能存在一种直观的方法，从一个LOD切换到另一个LOD，只需要在较短的时间内在两个LOD之间执行一个线性混合，这种方法无疑可以得到一种比较平滑的切换，但是这种混合操作的代价较高。渲染两个LOD要比一个LOD需要更大开销，因此也就违背了LOD的初衷。但LOD切换通常发生在较短时间内容，在同一时间也不是对场景中所有物体进行切换，所以依然可以从中获益。
Giegl等人在《Unpopping: Solvingthe Image-Space Blend Problem for Smooth Discrete LOD Transition 》这篇文章中提出了一种方法，实际应用的效果较为出色。思路是在两个LOD之间有一个alpha值的过渡，有兴趣的朋友可以进一步了解。
8.1.3 透明LOD | Alpha LODs
完全避免突越现象的一种简单方法便是使用alpha LOD。其中并没有使用同一物体很多不同细节的实例，而且每个物体只有一个实例。
随着LOD选取度量值（如与物体之间的距离）的增大，物体整体透明度也随之增大（也就是alpha值减小），当完全透明时，物体最终就会消失。
这种方法的优点是，比离散几何LOD方法上感觉更连续一些，可以避免突跃现象。此外，由于物体最终会完全消失而不需要进行渲染，可以得到很好的加速效果。
图26 使用Alpha LOD对图中的圆锥体进行渲染，当距离圆锥体较远时，就提高它的透明度，直到最后消失。直线左边的图像是从同一距离处进行的观察，而直线右边的图像是左边图像不同尺寸的情形。
8.1.4 连续LOD和几何形变LOD | CLODs and Geomorph LODs
连续细节层次（Continuous Level of Detail , CLOD）的基本思想是基于LOD选取值来精确决定可见多边形的数量。在100m远处，模型包含1000个多边形，当移动的到101m的地方时，模型减少到998个多边形。
几何形变层次细节（Geomorph LODs）是基于简化生成的一组离散模型，且其中模型顶点之间的链接关系保持不变。而网格简化的过程可以从一个复杂的物体中创建各种不同的LOD模型，具体做法可以参见《Real-Time Rendering 3rd》12.5.1一节，一种方法就是创建一组离散的LOD，然后按照上文中提到的方法来使用。这里的边塌陷（Edge Collapse Methods）方法有一个有趣的性质，即允许在不同的LOD之间采用其他过渡方法。
图27 几何形变LOD的简化模型图示。左边和右边的图像所示分为为低细节层次和高细节层次的模型，中间的图像是在左右模型中间进行插值生成的几何变形模型。注意。中间的牛模型和右边的模型具有相同数量的顶点和三角形。
8.2 LOD的选取 | LOD Selection
给定一个物体不同细节层次，必须做一个选择，决定渲染或者混合其中的哪一个层次，这就是LOD选择（LOD selection）的任务。有几种不同的LOD选择方案，这些方案也可以用于遮挡裁剪算法。
常见的三种LOD选取技术是：
• 基于距离的LOD选取( Range-Based )
• 基于投影面积的LOD选取( Projected Area-Based )
• 基于滞后的LOD选取(Hysteresis)
依然是分别进行简要概述。
8.2.1 基于距离的LOD选取 |Range-Based
选取LOD的一种常用方法是将物体的不同LOD于不同距离联系起来。细节最丰富的LOD的距离从0到一个用户定义值r1之间，下次层次的LOD的距离位于r1~r2之间，以此类推，如下图：
图28 左图为基于距离的LOD的原理示例图。其中，LOD3是一个空物体，也就是表示当物体大于r3时，就不渲染任何物体，因为物体对图像的贡献度不够。右图为场景中的一个LOD节点，它只有一个子节点基于r。
8.2.2 基于投影面积的LOD选取 | Projected Area-Based
基于投影面积的LOD选取，顾名思义，即投影面积越大，就选取细节越丰富的LOD。
8.2.3 基于滞后的LOD选取 |Hysteresis
若用于确定LOD度量标准围绕某个值ri在画面之间是变化的，那么就会出现不必要的突跃现象，也就会在不同的LOD之间来回快速切换。对此，可以引入一个围绕ri值的滞后来解决这个问题。如下图，这是一个基于距离的LOD，可以应用于任何类型，当r增大时，使用上一行的LOD距离；当r减小时，使用下面一行的LOD距离。
图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/levo...
图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
来源：CSDN，作者：浅墨_毛星云
原文：https://blog.csdn.net/poem_qianmo/article/details/78884513
版权声明：本文为博主原创文章，转载请附上博文链接！
