游戏开发中的渲染加速算法总结(三)

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

游戏开发中的渲染加速算法总结(一)
游戏开发中的渲染加速算法总结(二)

八、层次细节 | LOD,Level of Detail

细节层次(Level of Detail,LOD)的基本思想是当物体对渲染出图像贡献越少,使用越简单的形式来表达该物体。这是一个已经在各种游戏中广泛使用的基本优化技术。

例如,考虑一个包含1万个三角形的汽车,其中所包含的细节信息比较丰富。当视点靠近物体时,可以使用详细的细节表示,而当视点远离物体时,比如仅需覆盖200个像素,则完全无需渲染出1百万个三角形,相反,我可以使用诸如只有1000个三角形的简化模型。而由于距离的原因,简化后的模型与细节较丰富的模型看上去其实很接近。以这种方式,可以显著地提高渲染的性能开销。

图22 LOD图示

图23 LOD图示

图24 《古墓丽影:崛起》不同LOD的在线对比网站 @NVIDIA

通常情况下,雾效会与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
版权声明:本文为博主原创文章,转载请附上博文链接!

推荐阅读