虚拟场景的限时绘制技术
任利锋  张明敏  潘志庚
（浙江大学CAD&CG国家重点实验室，杭州  310027 ）

摘  要： 本文介绍静态场景的限时绘制技术。文章先简单分析一下绘制的流水线。然后介绍在流水线各个阶段采取的加速算法：可见性裁剪、细节层次、图象缓存。其中可见性裁剪就是找出不可见物体，把它们尽早地排除在流水线外。而细节层次技术是在合适的时候忽略一些次要的细节细节，减少通过流水线的负载量。纹理缓存技术则是把前面帧的绘制结果存成容易绘制的图像表示，用在后续帧中替代费时的坐标转换和光照计算。文章最后介绍了限时绘制框架，该框架为场景中的物体选择合适的绘制方法，使得绘制的结果最优。
关键词： 实时绘制；可见性裁剪；细节层次；图象缓存；限时绘制
Abstract: We reviewed some representive techniques of rendering of static scenes. First we gave a brief analysis of the rendering pipeline. Followed by accelerating techniques tackling each stage of the pipeline, namely visibility culling, level of details and image caching. The core of visibility culling is to find invisible objects and exclude them from the pipeline. And by ignoring less important details when possible, the level of details technique successfully reduce the workload of the pipeline. Image caching technique stores the result of time-consuming rendering in previous frames, then simply wrap this cached result in subsequent frames. At the end of this article, we introduced a framework named time-critical rendering, which keep multiple rendering skemes for every object in it, and choose the skeme that maximize a benefit function, of which time is import factor, as the best solution.
key words:  Real-time rendering; Visibility culling; LOD; Image caching; Time-critical rendering

0 引言
    在图形学发展的早期，研究者追求的是提高计算机生成的图象的真实感。随着场景的日渐复杂和各种复杂的光照明技术的广泛应用，计算机生成的图象越来越逼真，但绘制需要的计算量也越来越大。近年来，三维交互图形学和虚拟现实等应用的兴起，人们更加注重的是身临其境的感受。而相关的研究表明，系统具有和实际行为相似的动态特性远比逼真的静态图象更重要。真实的动态特性的关键有两个方面：图象的更新要及时，即延时短；图象更新的频率高并且稳定。
    单靠主机和图形加速卡的性能提高远远不能满足这些应用的计算要求。为了缓解计算量和绘制时间的矛盾，出现了几种代表性的加速技术，如可见性裁剪（Visibility Culling）、细节层次（LOD）、图象缓存（Image Caching）等[1]。另外，研究人员还提出了一种迥然不同的计算机制——限时绘制机制（Time-Critical Rendering）。可见性裁剪着眼于在绘制开始以前确定景物的可见性，剔除在最终图象中不可见的几何元素，只绘制可见部分。细节层次着
    眼于省略不能分辨清楚的细节，在物体的的几何细节超过显示设备的表达能力时，采用粗略的几何表示。图象缓存的出发点则是利用帧间的连贯性，把已有的绘制结果稍作调整应用到后续帧的绘制过程中，达到节省重复计算的目的。最后，限时绘制机制是一个综合考虑系统的计算能力以及绘制的时间和质量要求，必要时降低绘制结果的质量保证绘制在指定时间内完成的算法框架。
本文将首先简要回顾一下主流图形卡的绘制流水线，然后介绍几种加速技术的最新进展，分析其节省绘制时间的原理，并在每节的最后指出该技术的优缺点和适用领域。
1 绘制过程
    为了更加清楚地认识各种加速技术的原理和优缺点，我们需要站在整体的高度来看待这些技术。为此，先来回顾一下时下主流图形硬件的绘制流水线。在省略了一些具体的细节以后，绘制流水线可以划分为顶点操作，光栅化和位(fragment)操作三个阶段。
    第一个阶段对每个顶点进行操作。先把每个顶点转换到视点坐标系，并对它们进行光照计算。然后把这些初步处理过的顶点组装成点线面等图元。本阶段的最后一步是视域裁剪和背面剔除。第二个阶段是把点线面进行扫描转换和插值，将其转换成位，每一位对于帧缓冲区中的一个象素。第三阶段包括纹理计算雾化操作等，并进行深度比较。通过深度比较的位将参与该象素的混合(blend)操作。
 
图1 绘制流水线示意图
Graph 1 Rendering Pipeline

    第一个阶段对每个顶点进行操作。先把每个顶点转换到视点坐标系，并对它们进行光照计算。然后把这些初步处理过的顶点组装成点线面等图元。本阶段的最后一步是视域裁剪和背面剔除。第二个阶段是把点线面进行扫描转换和插值，将其转换成位，每一位对于帧缓冲区中的一个象素。第三阶段包括纹理计算雾化操作等，并进行深度比较。通过深度比较的位将参与该象素的混合(blend)操作。
2 可见性裁剪
2.1基本分类
    对不可见景物进行坐标转换和光照计算，扫描转换以及位操作对提高绘制质量没有任何贡献，纯粹是浪费时间。找出不可锾澹阉蔷≡绲嘏懦诨嬷屏魉咄獾墓叹褪强杉圆眉簟０凑毡徊玫舻亩韵螅杉圆眉艏际醴治佑虿眉?View Frustum Culling)、背面剔除(Back Face Culling)、基于贡献的消除(Contribution Culling) 和遮挡消隐(Occlusion Culling)四类，分别剔除位于视野之外的、背朝视点的、在屏幕上投影面积太小的和被其他物体遮挡的物体或多边形集合[2]。
    景物是否能够通过前三种可见性裁剪，仅取决于本身的大小以及它相对于视点的位置和方向，场景中的其它物体对此没有影响。由于它们思想直观、算法简单，现有的图形卡上都集成了这些算法[3]。而遮挡消隐比较复杂，在下一节中单独介绍。
2.2遮挡消隐的代表算法
    Teller等人把室内场景划分成单元格和通道，在预处理阶段一次性地计算当视点位于各单元格中时位于视域内的物体集，大大加快了绘制的速度[4]。但是一般场景很难划分成格子和通道，限制了该算法的广泛应用。
    Greene的层次深度缓冲(Hierarchical z-buffer)算法用对象空间的八叉树和图象空间的深度金字塔来加速可见性裁剪过程[5]。算法的关键是快速的z-query测试，即不通过扫描转换确定物体是否被遮挡的手段。算法的缺点是主流图形硬件不支持z-query，用硬件实现时速度慢，Greene提到可以利用可见性的帧与帧之间的连贯性稍加弥补。
    层次遮挡图(Hierarchical Occlusion Map)算法[6]和Greene的方法类似，但前一种方法把遮挡问题分解为相互独立的两个子问题：物体的投影是否完全处于遮挡物的投影中，物体是否比遮挡物远。同时满足这两个条件的物体必然被遮挡。问题分解后方便于利用现有的硬件条件。另外，该算法选择遮挡作用大的那部分物体作为遮挡物，生成遮挡表示，遮挡表示在一次绘制的过程中只更新一次。相对于层次深度缓冲区方法的把全部景物做为潜在的遮挡物，并且随时更新遮挡表示来说，层次遮挡图算法常常会快一些。
    可见性裁剪通常利用各种层次结构加速剔除不可见物体的过程，其核心思想是包围体和分而治之：
不可见包围体中的所有景物必然不可见；采用层次结构，如果某节点不可见，则其所有子节点必然不可见。确定高层次节点为不可见可以排除大量物体，极大地加速了可见性裁剪过程。
    更多的细节可以一篇参考关于可见性裁剪的的专门论述[26]。可见性裁剪特别适用于室内场景等遮挡严重的场合。另外裁剪本身也有相当的计算量，以至于在一些情况下为了得到实在的加速必须采用多个图形卡[27][28]。
    另外还有一类算法不直接判别物体是否可见，而是按照可见的可能性从高到低的顺序绘制，直到屏幕基本被占满或绘制的几何元素达到预先指定的上限为止[7]。在[8]中可见性裁剪和场景简化结合起来，按照物体可见的可能性从小到大简化场景，直到达到预先设定的几何体素上限为止。
3 细节层次
    人眼对远处的景象分辨的比较模糊，相应地，绘制这些物体时可以忽略一些细节，从而减少通过绘制流水线的负载量。在LOD的方法里，场景有多个细致程度不同的表示，并根据一定的标准为绘制过程选取某个表示。细节层次技术分为造型和选择两部分。
3.1多细节层次造型
    文献[9]比较了一些常用的模型简化方法，并按照能否处理非流形网格、采用全局还是局部指标指导简化过程等标准分类，最后对算法的时间和空间要求和简化结果的误差进行比较。
就绘制的角度，这些算法的区别在于简化表示是静态生成还是动态生成。前一种方法是在预处理阶段生成所有层次的表示，并存储起来。显然，这样做需要大量的冗余空间，为了减少空间需求只能存储有限几个层次的表示。这又造成在不同的层次间切换时，图形有跳变，必须采用特殊的处理。
后一种方法虽然也在预处理阶段进行简化工作，但只是存储几何简化的过程（而非结果），而且物体是在绘制的同时动态地构造，选择代表物体的三角形和顶点。动态构造法只存储简化的过程，所以需要的额外空间比较小。其次动态构造法提供了密集的层次表示，相邻层次的几何信息的变化比较小，自然地避免了视觉上的突变。动态简化的例子包括累进网格[10][11]、多分辨率技术[12]、层次动态简化[13]。
    动态构造物体的几何表示降低了应用程序向图形子系统发送命令的速度。而在包含高端图形系统中，应用程序本来就已经是整个绘制的瓶颈，使用动态构造使系统效率大大降低。Gobbetti通过把累进网格中的顶点和三角形重新排序[14]，消除了遍历时间和原始网格几何复杂度的依赖关系，提高了抽取大型网格的简化表示的时间。
3.2选择绘制的层次
    最初的算法只是简单地根据物体的远近或在屏幕上的投影面积决定选择的细节[15]。其他影响选择的因素还包括图象的屏幕中心距、物体的运动速度、物体是否位于焦点位置以及物体本身的语义等等 [16]。在后面要提到的限时绘制框架里，选择还应考虑时间要求。
4图象缓存
    几何元素的绘制是非常耗时的过程——每个顶点都要经过坐标转换，光照计算等费时的处理——需要找到一个节省的方法。另一方面，离视点远的物体在相邻帧中的变化不显著，所以可以把它们存成图像表示，加速后续帧的绘制。
4.1 硬件支持
    首先介绍两种独特的硬件体系结构。Regan等人介绍了一种原本专门为头盔式虚拟现实系统设计的绘制结构[17]。这个绘制结构可以在不知道确切的视线方向的情况下开始绘制，等得到方向信息后再把得到的结果进行投影，调整到正确的位置。另外，硬件有多个存储区，分别容纳不同的物体（或物体的集合）的绘制结果，显示的图象由这些存储区里的内容叠加合成。值得特别指出的是，物体的更新是按自身需要进行的，而合成最终显示图象是按照帧速率进行的。
    Talisman[18] 模型和Regan的结构类似，物体（或其集合）独立地按照自身的更新速率绘制到不同的子画面（sprite），专用的仿射变形（affine warp）和合成器件按照显示速率把这些子画面合成为最终供显示用的图象。
    上述两种体系结构的公同特点是绘制图象和显示图象不再紧密耦合，而这也是不同物体能采用各自的更新速率的前提。这种体系结构完全符合绘制的要求，是有前途的发展方向。缺点是和主流硬件的体系结构差异太大，短期内只能停留在实验阶段。
4.2软件方案
    图象缓存技术就是把绘制的结果图象作为纹理，在误差允许的情况下，贴在简单的几何形体上用于后续帧的绘制，代替生成该图象的复杂几何体。不同图象缓存技术的区别在于用被纹理代替的几何的粒度和如何度量用纹理代替原有几何带来的误差。
Shade和Schaufler分别利用BSP树[19]和KD树剖分空间[20]，在合适的时机为每一块空间内的物体生成一个图像表示，用来加速后续帧的绘制。不论是BSP树还是KD树都会导致某些物体被分割成几个部分，在物体被分割的部位会出现裂缝和重叠。这是由图象缓存方法本身所决定的，因为创建图象缓存过程和利用该缓存作纹理的绘制过程都是离散的采样过程。
    频繁地更新图象缓存会降低效率，而提高纹理寿命的关键在于选择承载纹理的几何。Shade 和Schaufler把纹理简单的贴到平面的多边形上，原有深度信息的大量丢失限制了纹理的有效期。Sillion根据图象的特征提取出简单的三维几何体，用来承载纹理[21] ，延长了纹理的有效期限。但提取三维信息的过程很费时间，只能放在预处理阶段做。
Decoret[29]等人提出的集束告示牌（billboard clouds）比较好的解决了这个问题。告示牌    (billbord)在图形学领域特指一个始终朝向视点的矩形图像，最早用来作为路旁绿化树的简单表示。集束告示牌是一组带有普通颜色纹理和透明纹理的平面。
    图象缓存技术适用于远景，同时要求图形加速卡的纹理存储空间要足够大。
5限时绘制框架
    如前所述，在三维交互图形学和虚拟现实中，短延迟和高速稳定的帧速率比图象的真实感更重要[22]。但前几种技术都是“尽可能”减少一次绘制的时间，如果场景复杂，延迟就会增大，帧速率就会下降；如果相邻帧的场景时而简单时而复杂，帧的更新就会时慢时快。这些都大大影响了用户的沉浸感。找到保证绘制可以在预先确定的时间内完成的方法才能从根本上解决这个问题。
    Wloka提出了限时计算机制[23]。他指出当前绝大多数算法是批处理方式，得到结果的时间完全由计算的复杂度和硬件的处理能力决定，不能主动控制。对应地，他提出一种限时计算机制，在这种机制下，计算请求明确地指出计算必须完成的最后期限，系统综合考虑当前的资源状况和计算能力以及计算对时间和质量的要求，必要时降低对计算质量的的要求，采用简略的计算方法或数据，保证计算在指定时间内完成。绘制作为计算的一种特例，自然也能应用这个机制。
    文献[24]给出一种保证恒定帧速率的绘制框架。场景中的所有物体(object)都以多个细节层次表示，系统预测绘制每个表示需要的时间代价（cost）和得到的视觉收益（benefit），在保证绘制的总时间小于用户指定的时间的前提下为每个可见物体选择一个细节层次，使得绘制(rendering)这些物体得到的视觉收益是最大。实际上，这转化成一个优化问题。

    文献[16]考虑了计算视觉收益时涉及到诸多的因素，文献[14]对场景中所有物体采用连续的多分辨率几何表示，简化收益和时间代价的计算，提高了优化的收敛速度。
凡是能够提供时间代价不等的多种绘制方案（包括不同的绘制算法和模型的不同数据表示）的系统都能应用这个框架。限时绘制的框架是建立在加速算法上的，这一点清楚地体现在在文献[25]中，该文献提出的框架里几乎应用了上文提到的所有加速算法。
6 总结
    总之，各种加速绘制的方法的原理是：1）避免不必要的计算； 2）简化要绘制的物体；3）采用图像表示。而限时绘制就是充分考虑绘制所用时间的框架。这个框架利用到了所有可能的加速算法，在确保绘制时间大致满足设定要求的前提下，为场景中物体的选择合适的绘制方法，使得绘制的结果最优。

参 考 文 献
[1]   刘学慧, 吴恩华， 虚拟现实的图形生成技术，中国图形图象学报，Vol.2, No.4, pp.205-212, Apr.1997.
[2]   Keith Cok, Developing Efficient Graphics Software: the Yin and Yang of Graphics, SIGGRAPH’99 Course,  pp.71-85, 1999.
[3]   Dirk Bartz, Michael Meibner, et.al., OpenGL-assisted Occlusion Culling for large Polygonal Models, EUROGRAPH’99 Tutorial 2, EUROGRAPH Association, Milano, September 1999.
[4]   S. Teller, C. Sequin, Visibility preprocessing for interactive walkthroughs, SIGGRAPH’91, pp.61-69, 1991.
[5]   Ned Greene and M. Kass, Hierarchical Z-buffer visibility, SIGGRAPH’93, pp. 231-240, 1993.
[6]   Hansong Zhang, Dinesh Manocha, et.al., Visibility culling using hierarchical occlusion maps, SIGGRAPH’97, pp.77-88, 1997.
[7]   James T. Klosowski, Claudio T. Silva, Rendering on a Budget: A Frame for Time-Critical Rendering, IEEE Visualization'99, San Francisco, Oct. 1999.
[8]   Mingmin Zhang, Pheng-Ann Heng, et.al., Time-Critical Rendering with Incorporation of LoD and Visibility Culling, Journal of Image and Graphics, Vol.5, Supplement, pp.482-485
[9]   P. Cignoni, C. Montani, et.al., A Comparison of Mesh Simplification Algorithms, Computers & Graphics, Vol. 22, No. 1, pp. 37-54, 1998.
[10]   Hoppe, H., Progressive meshes, SIGGRAPH'96, pp. 99-108, 1996.
[11]   Popovic, J. and Hoppe, H., Progressive simplicial complexes, SIGGRAPH’97, pp. 217-224, 1997.
[12]   Eck, M., DeRose, et.al., Multiresolution analysis of arbitrary meshes. SIGGRAPH’95, pp. 173-181, August 1995.
[13]   David Luebke, Carl Erikson，View-Dependent Simplification of Arbitrary Polygonal Enviroments, SIGGRAPH'97, pp. 199-208, 1997.
[14]   Enrico Gobbetti, Eric Bouvier, Time-critical multiresolution scene rendering, IEEE Visualization’99, pp. 123-130, October 1999.
[15]   Blake, Edwin H., A Metric for Computing Adaptive Detail in Animated Scenes using Object-Oriented Programming, EUROGRAPH'87, G. Marechal(Ed.), 1987
[16]   Toshikazu Oshima, Hiroyuki Yamamoto, et.al.,Gaze-Directed Adaptive Rendering for Interacting with Virtual Space, IEEE Proceedings of VRAIS '96.
[17]   Matthew Regan, Ronald Pose, Priority Rendering with a Virtual Reality Address Recalculation Pipeline, SIGGRAPH'94, pp.155-162, 1994.
 
[18]   Torborg J., Kajiya J., Talisman: Commodity Real-time 3D Graphics for the PC, SIGGRAPH'96, 353-364, 1996.
[19]   Jonathan Shade, Dani Lischinski, et.al., Hierarchical image caching for accelerated walkthroughs of complex environments, SIGGRAPH'96, pp. 75-82, 1996.
[20]   Gernot Schaufler, Wolfgang Stürzlinger, A three dimensional image cache for virtual reality, EUROGRAPH'96, pp. 227-236, 1996.
[21]   Francois X. Sillion, Fundamentals of image formation and re-use, SIGGRAPH'99 Course 39, pp. 16-29, 1999.
[22]   Gerda J.F., Kees J. Overbeeke, Trade-off Between Resolution and Interactivity in Spatial Task Performance, IEEE CG&A 1995, September 1995.
[23]   M.M. Wolka, Dissertation Proposal: Time-Critical Graphics, Brown University, cs-93-50, November 1993.
[24]   T.A. Funkhouser and C. H. Séquin, Adaptive display algorithm for interactive frame rate during visualization of complex virtual environments, Proc. SIGGRAPH'93,pp.247-254,August 1993.
[25]   Mingmin Zhang,Zhigeng Pan, Pheng-Ann Heng Time critical rendering algorithm with incoperation of LoD, visibility culling, The Journal of Visualization and Computer Animation, 2003.
[26]   Cohen-or, D., et.al., Visibility, problems, techniques and applications,  SIGGRAPH 2001 Course Notes, 2001.
[27]   Baxter, B., et.al., Gigawalk: Interactive walkthrough of complex 3d environments,. Proc. of Eurographics Workshop on Rendering 2002.
[28]   Govindaraju, N., et.al., Interactive visibility culling for complex environments using occlusion switches, ACM Symposium on Interactive 3D Graphics 2003.
[29]   Xavier D′ecoret, et.al, Billboard Clouds for Extreme Model Simplication, SIGGRAPH’03, pp. 689-696, 2003.