文档介绍：基于时空连贯性和几何简化技术的复杂场景快速消隐绘制算法
郑文庭鲍虎军彭群生
浙江大学CAD&CG国家重点实验室
摘要视觉信息是人类感知外部世界的主要渠道。随着虚拟现实技术应用的日益广泛,场景的规模越来越大,虚拟场景画面的实时显示成为整个虚拟现实系统成败的关键技术。在本文中,我们提出了一个结合层次遮挡图和图象缓存的快速消隐绘制算法,由于充分利用了空间连贯性和图象简化技术,本算法不仅在图形绘制速度和图象质量之间获得了一个很好的折衷,而且本算法可适合各种复杂度场景的快速绘制需要。如果把场景按离视点的远近分为近景、中景和远景三层,则本算法首先利用空间连贯性对场景实行快速保守的消隐,对可能可见的近景、中景使用几何绘制,对可能可见的远景实现了图象和几何混合的加速绘制。实验表明,几何上的快速消隐技术和基于图象的绘制加速技术的结合是一个良好的优势互补结合,本算法在实践中具有良好的效果。
关键词虚拟现实消隐基于图象的绘制方法
1 引言
硬件Z-buffer算法是目前最为常用的实时图形绘制算法。尽管其线性复杂度为O(N)(N为面片数),但该算法由于不考虑景物的空间连贯性,需逐一绘制景物面片而不管它是否隐藏,因而,对高度复杂的场景,硬件Z-buffer算法仍难以达到实时。解决这一个问题的关键是减少复杂场景中需实时绘制的景物面片数N。
目前,已有两类算法致力于减少视域中的待处理的景物面片。一类是基于空间连贯性的快速消隐算法[1][2][3][4][5],另一类是基于层次细节简化的图形绘制技术[6][7]。鉴于理想的绘制算法只需绘制当前视域中的可见景物面片,因而,以较少的代价剔除不可见面片无疑会极大地提高图形绘制效率。
第一类算法并不简化场景几何,而是充分利用景物空间、图象空间和时间域上的可见性和不可见性连贯性来快速剔除被遮挡(不可见)的景物面片。层次Z-buffer算法[1]和层次遮挡图算法[3]是这类算法的典型代表。这两个算法均将景物空间组织成层次结构,并把面片的可见性计算分解为深度排序和在屏幕上的重叠测试两个过程。算法引入深度Z锥来实现快速的保守排序,而图象锥则用来加速面片的重叠测试,这两个层次结构的引入使得快速剔除不可见面成为可能,从而极大地降低了后续硬件Z-buffer算法的绘制复杂度。更进一步,时间域上可见性连贯性的使用保证了Z锥和图象锥具有一个极好的初始条件,为快速绘制提供了重要保障。由于着眼于开发不可见景物的空间连贯性,这类算法对高遮挡率的场景非常有效,但对遮挡复杂性不高的复杂场景却毫无优势,仍无法达到实时。
第二类算法根据视觉特性,对离视点较远的景物进行几何简化,从而达到降低场景复杂性的目的[6][7][8][9][10][11][12]。但对高度复杂的场景,经几何简化后的场景可能仍非常复杂而无法实时绘制。九十年代中期发展起来的纹理简化技术较好地解决了这类问题。其典型代表是Shade的图象缓存(Image Cache)技术[13],该算法结合几何简化和基于图象的绘制技术的优点。算法首先将场景组织成一棵BSP树。漫游时,算法自动地决定 BSP树中各个结点中的景物是否满足纹理简化的误差要求,若满足,则取图象缓存中对应图象作为纹理,将其映射到一空间四边形表面上来取代结点中的几何来绘制画面;否则,直接采用几何来绘制。显然,这种动态图象简化技术大大减低了场景的复杂性,从而提高了图形的绘制效率。但由于该算法采用从后向前的绘制方式不能利用前述的空间不可见性连贯性来加速消隐过程。实验结果表明,该算法无法有效绘制高度遮挡复杂性的场景。
鉴于传统绘制算法均无法适合各种复杂场景的实时绘制需要,本章将给出一个结合层次遮挡图和图象缓存的快速图形绘制算法,由于充分利用了空间连贯性和图象简化技术,本算法不仅在图形绘制速度和图象质量之间获得了一个很好的折衷,而且本算法可适合各种复杂度场景的快速绘制需要。如果把场景按距离视点的远近分为近景、中景和远景三层,则本算法首先利用空间连贯性对场景实行快速保守的消隐,对可能可见的近景,中景使用几何绘制,对可能可见的远景实现了图象和几何混合的加速绘制。
2 相关工作

在介绍本算法之前,我们首先介绍前人提出的与本算法有关的一些算法、数据结构及其描述。
层次Z-buffer算法

层次Z-buffer算法由Greene等于1993年在SIGGRAPH会议上提出[1]。该算法首次对传统的硬件Z-buffer算法进行了改造,极大地提高了具复杂遮挡率场景的消隐过程。层次Z-buffer算法将场景中的景物组织成空间八叉树结构,并利用景物的空间连贯性来考察每一八叉树结点的可见性。若八叉树结点所对应的立方体的六个表面关于当前的Z缓存器不可见,则该立方体内上任何景物均不可见;否则,我们需要进一