（应用数学专业论文）大规模场景快速绘制技术.pdf

浙江大学博士学位论文 大规模场景的快速绘制技术的研究 摘要 p 7 8 ； 0 ( 大规模场景的快速绘制技术是虚拟现实、实时仿真以及交互三维设计等许 多重要应用的底层支撑技术，也是计算机图形学本身的一个基础性研究课题。尹 本文首先指出实现大规模场景快速绘制的关键在于设计一整套与场景规模基本 不相关或弱相关的绘制算法，并讨论了三条提高绘制效率的途径：与场景规模 弱相关的隐藏面剔除，层次细节表示以及基于图象绘制技术。r 本文所做的研究工作集中在三个方面： 1 利用全局可见性计算进行快速的遮挡剔除。提出了一种崭新的面向遮挡 剔除的全局可见性的表示方法一一全局遮挡图( g l o b a lo c c l u s i o nm a p 。 g o m ) 。这种表示方法有利于进行压缩存储和进行快速的遮挡剔除。 讨论了计算全局遮挡图中的视点区域采样问题。指出了在方向空间已被离 散的情况下，通过采样视点区域，只要满足一定的采样精度要求，是可以得到 保守的全局遮挡图的，并定量地给出了一个保守的视点区域采样精度。l ， 提出了一个自适应地计算g o m 的方法，该算法利用了图象空间进行场景 的可见性采样，同时以物体空间精度进行方向遮挡的判断。在g o m 应用方 面，讨论了利用g o m 进行遮挡剔除的算法。 lg o m 是一套完整的利用全局可见性进行遮挡剔除的解决方案，与过去的方 法相比，我们的方案：适用于更一般的场景；在不需任何特别处理的情况下， 对动态的物体( o c c l u d e c ) 进行遮挡剔除；可以采用图象压缩的方式进行压缩存 贮。上一 2 快速的整体镜面反射计算和绘制算法。提出了利用全局可见性来快速计 算镜面整体反射分量的算法。【借助于全局可见性，将整体镜面反射的计算和场 景预消隐计算联系起来，将整体镜面反射计算转化为一个计算入射光束的可能 可见集的问题，并构造一个相应的映射g 。在漫游阶段，则通过执行g 映射并 浙江大学博士学位论文大规模场景的快速绘制技术的研究 调用其他的光亮度计算过程，实时合成整体镜面反射分量。寸 3 基于层次表面采样的绘制技术。对于高度复杂的几何体提出了一种新的 f 简洁的动态层次细节表示层次表面采样。( 表面采样是指对于物体表面进行 ，- 。+ 。1 。一- 采样而得到的不规则表面块。将基于多边形表示的复杂几何模型通过景物空间 的采样转化为表面采样模型，再根据表面采样的大小、法向将表面采样组织成 层次细节结构，构成层次表面采样模型。在层次表面采样模型中，表面采样之 间不存在拓扑关系，因此对于表面复杂度极高的几何体来说，该表示十分精 简。7 我们提出了一个基于层次表面采样模型的绘制框架，其中采用了投影模板 技术来加速表面采样的光栅化，并使用了一种新的缓冲区来进行反走样。将表 面采样的屏幕投影面积作为层次细节的选择判据，使层次细节之间的过渡在视 觉表现上更加平滑。f 层次表面采样技术实质上融合层次细节和基于图象绘制技 术，在处理高度复杂的几何体显示了巨大的应用潜力。、j 关键词：大规模场景卜绘制采 瑟全局可见性i 遮挡剔除；层次细节i 基于 图象的绘芦基于点的绘杈 浙江大学博士学位论文大规模场景的快速绘制技术的研究 f a s t r e n d e r i n gt e c h n i q u e s f o r l a r g e - s c a l e c o m p l e x s c e n e a b s t r a c t t h ef a s tr e n d e r i n gf o rl a r g e s c a l ec o m p l e xs c e n ei st h et e c h n i c a lb a s i sf o rm a n y i m p o r t a n ta p p l i c a t i o n ss u c ha sv i r t u a lr e a l i t y , r e a l t i m es i m u l a t i o n ，i n t e r a c t i v e3 d m o d e ld e s i g n a n ds oo n m o r e o v e r , i th a sb e e naf i i n d a m e n t a lr e s e a r c hf i e l di n c o m p u t e rg r a p h i c sf o rd e c a d e s i nt h i st h e s i s ，i ti su n v e i l e dt h a tt h en a t u r eo ft h ef a s t r e n d e r i n gf o rl a r g e - s c a l ec o m p l e xs c e n ei st of i n do u ts u c hr e n d e r i n ga l g o r i t h m st h a t h a v en oo rl i t t l ed e p e n d e n c yw i t ht h en u m b e ro ft h ep r i m i t i v e si ns c e n e m e a n w h i l e ，i t i s p o i n t e d o u tt h a tt h e r ea r et h r e ep r o v e ds o l u t i o n st oa c c e l e r a t e 也e r e n d e r i n g p r o c e d u r e a sv i s i b i l i t yc u l l i n g ，l e v e l - o f - d e t a i la n di m a g e - b a s e d r e n d e r i n g t h em a i nw o r ks t a t e di nt h i st h e s i sf o c u s e si nt h e f o l l o w i n ga s p e c t s 1 f a s t v i s i b i l i t yc u l l i n gb yg l o b a lv i s i b i l i t y a n i n n o v a t i v e r e p r e s e n t a t i o n f o r o c c l u s i o n - o r i e n t e d g l o b a lv i s i b i l i t y , g l o b a l o c c l u s i o nm a p ( g o m ) ，i sp r e s e n t e d ， p r o v e d 试t ha d v a n t a g e s o fb o u n d e d s t o r a g e a n df a s to c c l u s i o n c u l l i n g t h ev i e w e r - r e g l s a m p l i n gp r o b l e mi ng o m c o m p u t a t i o ni sd i s c u s s e di nd e p t h i t h a sb e e ns h o w nt h a ti ti sf e a s i b l et oo b t a i ng o m c o n s e r v a t i v e l yb ym e a n so f s a m p l i n gv i e w e r - r e g i o n u n d e rac e r t a i n s p a t i a ls a m p l i n g r a t ei ft h ed i r e c t i o n a l s a m p l i n gi se n g a g e ds i m u l t a n e o u s l y af o r m u l at od e t e r m i n et h ec o n s e r v a t i v es p a t i a l s a m p l i n g r a t ei sg i v e n a na d a p t i v ea p p r o a c hf o rg o m c o m p u t a t i o ni si n t e r p r e t e di nd e t a i l t h ev i s i b i l i t y i n f o r m a t i o ni s s a m p l e da n dc o l l e c t e d i n i m a g es p a c ew h i l et h ed e t e r m i n a t i o nf o r d i r e c t i o n a lo c c l u s i o ni sm a d ew i t h o b j e c t s p a c e p r e c i s i o n t h e r e a r es e v e r a l a l g o r i t h m sf o ro c c l u s i o nc u l l i n gb yg o m d i s c u s s e d i ng e n e r a l ，g o mi sac o m p l e t es o l u t i o nt oe x p l o i tg l o b a lv i s i b i l i t yt op e r f o r mt h e o c c l u s i o n c u l l i n gf r o m a v i e w e r - r e g i o n c o m p a r i n g t ot h ep r e v i o u ss o l u t i o n s ，g o mi s a b l et oh a n d l em o r e g e n e r a lm o d e l s ，t o o c c l u d ed y n a m i co b j e c t sw i t h o u t a n y a d d i t i o n a lp r o c e s s i n g ，t ob e c o m p r e s s e db y t h ei m a g e c o m p r e s s i o n m e t h o d s 2 f a s tc o m p u t a t i o no fg l o b a ls p e c u l a rr e t i e c t i o n a na l g o r i t h mt of a s tc a l c u l a t e g l o b a ls p e c u l a r r e f i e c t i o n u s i n g2 l o b a lv i s i b i l i t y i s p r e s e n t e d b a s e d o ng l o b a l v i s i b i l i t y , t h ec o m p u t a t i o no fg l o b a ls p e c u l a rr e f i e c t i o na s s o c i a t e d 诵t ht h eh i d d e n s u r f a c e - r e m o v a lp r e p r o c e s si sh a n d l e db yc o n s t r u c t i n gas p e c i f i c m a p p i n gga n d c a l c u l a t i n gp o t e n t i a l l yv i s i b l es e t s ( p v s ) o f t h ei n c i d e n tb e a m so f s p e c u l a rs u r f a c e s i nt b er e n d e r i n gs t a g e t h eg l o b a ls p e c u l a rr e f l e c t i v ec o m p o n e n to fv i s i b l ep i x e l so n s p e c u l a rs u r f a c ei ss y n t h e s i z e di nr e a l t i m eb ye x e c u t i n gt h em a p p i n ggt o g e t h e rw i t h t h eo t h e r l i g h tc o m p o n e n tc a l c u l a t i o n 3 r e n d e r i n gt e c h n i q u e sb a s e do nh i e r a r c h i c a ls u r f a c ef r a g m e n t s ( h s f ) a i m i n g 浙江大学博士学位论文 大规模场景的快速绘制技术的研究 t od e a lw i t hh i g h l yc o m p l e xm o d e l s ，an o v e lc o n c i s er e p r e s e n t a t i o nw i t hd y n a m i c a l l e v e lo fd e t a i la sw e l la st h ec o r r e s p o n d i n gr e n d e r i n ga l g o r i t h mi s p r e s e n t e d a s u r f a c ef r a g m e n ti sa ni r r e g u l a rs a m p l e ds u r f a c er e g i o n ah s fm o d e li sc o m p r i s e do f a 盯e a tn u m b e ro fs u r f a c ef r a g m e n t s ，w h i c ha g eo r g a n i z e di nah i e r a r c h i c a ls t m c t u r e b ys c a l e w ep r o p o s eaf r a m e w o r kf o rr e n d e r i n gh s fm o d e l ，w h e r eas c r e e nt i l e t e c h n i q u e i s p r o p o s e dt os p e e du pt h er e n d e r i n go fs u r f a c ef r a g m e n t s s i n c ea n a p p r o x i m a t ez b u f f e ra l g o r i t h mi se m p l o y e dt or e m o v et h eh i d d e ns u r f a c ef r a g m e n t s s o m ea l i a si si n t r o d u c e di n e v i t a b l y an e wk i n do fb u 自c c rc a l l e dz d e l t a b u f f e ri s d e s i g n a t e dt oa l l e v i a t et h ev i s u a la r t i f a c t sc a u s e db y t h ea l i a s t h er e n d e f i n gt e c h n i q u e b a s e do nh s ft a k e st h ea d v a n t a g eo fi m a g e - b a s e dr e n d e r i n ga n dt h el e v e l o f - d e t a i l r e l a t e d a p p r o a c h e s ，p a r t i c u l a r l y s h o w nw i t hg r e a t p o t e n t i a l i n v i s u a l i z i n gh i g h l y c o m p l e xg e o m e t r i c m o d e i s k e y w o r d s ：l a r g e - s c a l ec o m p l e xs c e n e ，r e n d e r i n g , s a m p l i n g , g l o b a lv i s i b i l i t y , o c c l u s i o n c u l l i n g , l e v e l - e f - d e t a i l ，i m a g e - b a s e dr e n d e r i n g , p o i n t - b a s e dr e n d e r i n g 浙江大学博上学位论文大规模场景的快速绘制技术的研究 1 1 背景 第一章引言 三维图形绘制技术，是计算机图形学的一个重要的研究领域，它旨在根据给 定的视点和视线方向，快速和逼真地生成三维场景的二维图像。长期以来，对绘 制技术的研究一直围绕着绘制速度和真实感这二个方面展开。绘制图像的真实感 决定于场景模型的真实性和绘制算法的保真性。前者指的是场景中模型的几何形 状描述、表面材质设置、场景中光源分布的合理性；后者指的是如何按照人类视 觉感知规律和物理规律，对模型进行光影渲染，达到如同照片一般的真实感。总 的来说，图像的真实感愈高，需要的计算量和计算时间就愈多，其绘制的速度也 将降低。相反，如果减少绘制时间，则绘制结果的真实感亦将相应地降低。 在实际应用中，通常将绘铝4 技术分成实时绘制技术和离线绘制技术二类。前 者侧重于绘制的速度，即在尽可能保证绘制速度的前提下来完成绘制任务，其中 画面质量允许降低：后者则研究如何尽可能地保证绘制结果的高度真实感，对于 绘制时间一般没有特别的要求。从应用背景的角度来看，前者主要应用于各种需 要用户交互的场合，如交互式的c a d 建模软件、互动娱乐、仿真器、三维地理 信息系统等。后者主要用于生成高品质的影视作品，如影视数字特技合成、动画 制作等等。近年来随着“虚拟现实”技术的广泛应用，面向用户交互的三维图形 快速绘制技术受到了更多的关注。本文主要考虑大规模复杂场景的快速绘制技 术。 一般说来，场景是由一系列具有不同材质的造型元素( 通常是多边形) 和不 同形式的光源组成。在本文中，如果没有特别所指，造型元素即指多边形。目前 主流的快速绘制算法的速度均与景物空间复杂度相关，即生成一幅场景画面，需 要遍历并处理场景中的每一个造型元素，至少具有o ( d 的计算复杂度，( 为场 景中造型元素的个数) 。由于这类算法易于硬件实现和软件封装，现已广泛地为 浙江大学博士学位论文大规模场景的快速绘制技术的研究 各种图形绘制硬件和三维图形软件包( 如o p e n g l ，d i r e c t 3 d ) 所采用。随着计 算机硬件技术的长足进步，目前主流图形硬件的多边形处理能力已经达到每秒钟 百万量级甚至千万量级。然而，随着计算机图形技术的实用化，需要构造更逼真、 更精细的场景，使得场景规模不断扩大，单纯依赖于硬件加速的快速绘制技术， 并不能满足实际应用对绘制速度的要求。理论上说，场景的复杂性是无限的，而 任何硬件的单位时间内的处理能力总是有限的。所以，通过研究场景复杂性和人 类视觉感知规律等相关因素的内部联系，设计出与场景规模基本不相关或弱相关 的快速绘制算法是必要的，也是必然的趋势。 2 浙江大学博士学位论文 大规模场景的快速绘制技术的研究 1 2 大规模场景快速绘制的途径 在这里，先定义绘制元素的概念。所谓绘制元素是指绘制系统需要对其进行 显示的元素。即送入绘制流水线的元素。在经典的绘制系统中，绘制元素等同于 造型元素加上相应的材质信息，两者的数目是相同的。鉴于场景的规模的任意性 以及图形硬件处理能力的有限性，在实时绘制系统中，如果按统一的方式处理每 一个绘制元素，则用于个绘制元素的处理时间将随着绘制元素数目的增加而减 小。也就是说，对于一个实时绘制系统而言，存在一个使它失效的绘制元素数目， 称之为系统容量。 研究大规模场景快速绘制的目标是设计一个系统或算法，使得在满足绘制速 度的前提下，尽可能的提高系统容量和真实感。这里的真实感主要指的是绘制算 法的保真性，即光影渲染效果的真实感。 那么就前面的讨论可知， 1 ) 如果按照统一方式处理每一个绘制元素； 2 ) 如果绘制元素的数目随场景规模增加而增加； 3 ) 如果存在一个最低的绘制真实感要求： 那么只要给定绘制速度，系统容量理论上是确定的。所以，若要提高系统容量， 只能从上述条件入手。需要说明的是，条件3 是自然存在的人类对一个物体 的感知总存在一个最低的真实感要求，故只能从改变条件1 和条件2 着手。 从改变条件1 出发，如果不是按照统一的方式来处理绘制元素，而根据绘制 元素对最终绘制出的图像的贡献大小来决定处理方式和分配处理时间，则可以降 低整个绘制过程的时间。理论上说，对最终画面贡献小的绘制元素，相对于贡献 大的绘制元素，应该给予较少的处理时间。值得注意的是，用于评估绘制元素贡 献的时间开销应远远小于其获得的利益。 从改变条件2 出发，需要考虑绘制元素和造型元素之间的关系，即不将绘制 元素和造型元素直接等价起来，而是通过某种间接的映射关系将两者联系起来， 并且保证绘制元素不会随着造型元素的增加而增加，或者以指数( 或更低阶) 规 3 浙江大学博士学位论文 大规模场景的快速绘制技术的研究 律增加。 围绕如何改变上述条件，目前大规模场景快速绘制的途径主要有下列三条： 可见性判断。目前广泛使用的消隐算法( h i d d e n s u r f a c e r e m o v a l ，缩写为h s r ) 即是一类精确的可见性判断算法。然而，这类算法需逐个绘制元素判断是否 可见，即其算法复杂度至少为o a v ) 。显然，它无法满足绘制大规模场景的需 要。于是出现了另一类可见性判断算法，即不可见性或可能可见性判断算法。 这类算法虽不能严格地判断出绘制元素是否一定可见，但可以确定哪些绘制 元素一定不可见。利用这类算法，对给定的视点和视线方向，可以方便地得 到场景的可能可见集。从处理时间分配的观点来看，对于肯定不可见的绘制 元素，只分配了较少的处理时间用来做不可见性的判断。更进一步，如果能 够成批地淘汰掉不可见的绘制元素，可使花费于不可见性判断的处理时间不 随场景的规模而线性增长。 层次细节( l e v e lo f d e t a i l ，缩写为l o d ) 。层次细节的基本原理是，利用透 视投影的特性距离当前观察视点越远的物体，其在成像平面上的投影面 积越小，那么对远处的物体在绘制阶段可用较少的等效绘制元素来表现它。 这里提到的所谓“物体”是指具有一定逻辑意义的绘制元素组，而“等效” 是指两者的透视投影基本相同或差异很小。 基于图像的绘制( i m a g e b a s e d r e n d e r i n g ，缩写为i b r ) 。在i b r 方法中，绘 制元素指的是屏幕空间中的像素，而不是物体空间的造型元素。由于使用像 素作为绘制元素，绘制元素的数目并不随着场景的规模的变化而变化。但是， 由于绘制元素像素定义在屏幕空间中，是视点依赖的，因此造型元素到 绘制元素的映射必须随着视点的变化而动态地完成，这种映射的效率决定了 整个绘制的效率。 下面三节将分别介绍有关上述三条途径的相关工作。 4 z r 0 2 晶体结构示意图如图2 2 】。图中可以看出，立方相氧化锆为萤石结构( 空间群为 f m 3 m ) ：单斜相( 空间群p 2 1 c ) 和四方相氧化锆( 空间群p 4 2 n m c ) 是扭曲的萤石结构， 它们的结晶学参数洋见表2 - 1 1 “。从图2 2 和表2 i 可以看出：立方相氧化锆( c z r 0 2 ) ，z r 的配位数为8 ，形成z r 一0 四面体：四方相氧化锆( t z r 0 2 ) ，z r 的配位数仍为8 ，但八个0 原子分成两组，与z r 的间距不同；单斜相氧化锆( m z r 0 2 ) 中，z r 的配位数为7 ，由z r 一0 的三角形配位层和z 卜o 的四面体配位层构成。 2 - 2z lo z 晶体结构示意图 f i g 2 2t h es h e m a t i ed i a g r a mo fc r y s t a ls t r u c t u r eo fz r 0 2 表2 1z r o ：的晶体结构 t a b l e 2 一is t r u c t u r e so fp u r ez r 0 2p h a s e s f p h a s e s t a b i l i t y s p a c e c e 1p a r a m e t e r s ( a )a t o m i cp o s i t i o n s g r o u p r a n g e ( k )bba t o mxyz z r0 2 7 5 4 0 0 3 9 50 2 0 8 3 f”一zr。： 0 1 2 0 5p 2 ，c5 1 5 l5 2 0 35 3l 69 9 20 10 0 7 0 00 3 3 1 70 3 4 7 7 0 i f0 4 4 10 7 5 6 90 4 7 9 2 z r000 i 。一：r 。： 1 2 0 5 - 2 3 7 7p 4 z n m c5 0 7 45 0 7 45 1 8 89 0 00 2 50 2 5 0 2 0 4 4 z r000 c - z r o z 2 3 7 7 2 7l o f m 3 m 5 1 1 75 1 1 75 1 1 79 0 00 2 50 2 5 0 ，2 5 浙江大学博士学位论文 大规模场景的快速绘制技术的研究 遮挡剔除( o c c l u s i o nc u l l i n g ) 背面剔除利用下述事实来判断不可见性：如果一个绘制元素的法线方向背离 视点观察方向，则该绘制元素必不可见；视域剔除利用下述事实来判断不可见性： 如果一个绘制元素位于视域平头四棱锥之外，则该绘制元素必不可见；遮挡剔除 则利用下述事实来判断不可见性：如果一个绘制元素被其它不透明绘制元素( 组) 所遮挡，则该绘制元素必不可见。 如前所述如果可见性评估只能对单一的绘制元素来进行，则不能有效地提 高绘制的效率。此时需要将算法扩展为可以成组地对绘制元素进行可见性的评 估。那么，将场景组成层次结构，最底层的结点直接对应了一组绘制元素，而中 间结点则通过其子孙结点而间接地对应绘制元素组。不可见面剔除算法自顶向下 对层次结构中的结点进行可见性评估，实际上就是对其直接或间接对应的绘制元 素组进行评估。下文中所谓结点的可见性即指所对应的绘制元素组的可见 性。如果某个结点不可见，则其子结点也不可见，也就是说其间接对应的所有绘 制元素组都不可见；如果不能确定某个结点可见，则需要进一步对其子结点的可 见性进行评估，直至对低层次的结点。这样就可以迅速地成批拒绝不可见的绘制 元素。 对于背面剔除方法，从判断单一绘制元素是否为背面，扩展到判断一组绘制 元素是否都为背面，需要引入法向锥的概念 k u m a r l 9 9 9 。对于视域剔除和遮挡 剔除，通常采用绘制元素组的包围盒作为替代进行可见性评估 a s s a r s s o n 2 0 0 0 。 如果包围盒落于视域四棱锥外，或者被其他绘制元素所遮挡，则其包围的所有绘 制元素都不可见。 值得一提的是，遮挡剔除不同于其他两种剔除方式，它需要利用全局知识， 即需要考虑同一场景中的其他绘制元素( 组) 和当前绘制元素组之间的关系。所 以，相对于前两者，它更加复杂，但在深度复杂的场景中它可为提高绘制效率提 供更多的收益。所谓深度复杂度，指的是当用标准的z b u f f e r 算法来绘制场景时， 在像素上所进行的深度测试的平均次数。下面，我们将着重介绍遮挡剔除方法及 其最新的技术发展。 6 瑟漫大学游士学爱论文天蕊摸垠豢的捷逮绘裁技术麴磺究 1 3 2 遮挡剔除 酋先介绍有关遮挡剔除的两组概念。 蘩予魏蠢翡逮努爨滁骚基予程熹区域鹣遮挡爨豫。 冀中的主要区别税予，前者的遮挡剔除怒衙只针对当前视点位置，而后者的 计算结果对于一个视点邻近区域都是有效的。在漫游应用场合，凝于视点区域的 遮挡剔除的结果可以连续蛾提供给若干帧的绘制使尾。然两，蒸予视点区域的遮 整鬃狳逶港嚣要较长曩幸淡浆颈楚瑾，较多熬卷镰嚣镳，难臻赴蘧淤运动耱嚣嚣兔 遮挡体的情况。但秩另一方面来说，基于税点区域的遮挡剔除可以将绝大部分懿 计算鼹于预处理过程当中，而在真正绘制过稷中只需要极少的逡髀量。而基于视 点的遮挡剔除，通常需嚣谯绘制过程中耗费定的计算量，所以糟纯从提高绘制 效攀浆袁度瑟砉，基予筏煮嚣域斡遮挡剔除钱乎基于援点的遮搂掰涂。僵后者熬 优势在于不需要对扬豢穆预处理，并且胃戳簸瑷动态翡场景。 湖像精度的遮挡剔除和景物精度的遮挡剿除。 这一分类来自于消臆舞法中的图像空间消隐和景物空间消隐的概念。景物精 度熬慈搂剔除在景物空阉( o b j e c ts p a c e ) 审翔龋这整瞧。嚣黧缀蘩度熬速撞藏 除剿熬予绘割元素光穗能焉豹离散表示，程鲻像空蠲进行可见梭湃估。 1 3 2 。1 基于视点区域的c e l l - a n d p o r t a l 遮挡剁除 - , , j r c y a i r e y l 9 9 0 a i r e y l 9 9 1 首先提出了蒸予视点区域的c e l l a n d p o r t a l 可 凳经淫旗技术。莛类方法镑砖建筑麴戆室内缓爨，繇烬场景维织藏囊一系懿懿赛 阊( c d d 和将房间耦连的门、窗( p o r t a l s ) 构成的糟邻关系舀( a d j a c e n c y g r a p h ) 。 当视点位于一个房间内时，蒙观察到其他房间的任何物体就只能通过该房问的门 和窗。则每一个房间自然媳成为一个计算可能可见集的视点区域。a i r e y 提出了 一个绦窜静诗箕可鼹霹懿黎夔方法【a i f e y l 9 9 键，p 劐断蘸房霹中经一援煮透过一 个p o r t a l 可藐看觅鑫孽黼暴孛的多边形。该方法是一个伐舻) 箨法。在论文 【a i r e y l 9 9 1 中，作者提出了几个通过采样方法在指定精度下近似计算通过p o r t a l 可能盯见的多边形的方法，但这些方法不能保证求得的可能可见泉是保守的。 ， 浙江大学博士学位论文 大规模场景的快速绘制技术的研究 另一种基于视点区域的可见性评估技术是由t e l l e r 所提出 t e l l e r l 9 9 1 ，该方 法引入了c e l l t o c e l l 可见性的概念和相应的计算方法。通过测试一个c e l l 中的 一些关键位置对另一个c e l l 中的一些关键位置的可见性，来决定是否可以从一 个c e l l 观察到另一个c e l l 。该方法利用了如下事实：如果两个c e l l 之间是可见 的，则连接这些关键位置的线段至少有一条完全通过两个c e l l 之间的p o r t a l 序列。 在漫游过程中，动态地计算e y e t o c e l l 的可见性，并利用视域剔除进一步剔除 不位于视域四棱锥内的c e l l 。 1 3 3 2 基于视点的物体精度的遮挡剔除 基于视点的c e l l a n d p o r t a l s 的遮挡剔除 l u e b k e 等人提出了基于视点的c e l l a n d - p o r t a l s 的遮挡剔除技术 【l u e b k e l 9 9 5 】，该方法借鉴了a i r e y 和t e l l e r 的基于区域的遮挡剔除技术 a i r e y l 9 9 1 】。不同的是该方法无需预先计算针对视点区域( c e l l ) 的可能可见集， 而是深度优先地递归访问场景中p o r t a l ，并通过过估计( o v e r e s t i m a t e ) 它们的投 影来进行在线实时遮挡剔除。算法首先确定当前视点所在的c e l l ，绘制所有属于 该c e l l 的物体。然后找到位于当前视域且属于当前c e l l 的所有p o r t a l s ，用投影 后的p o r t a l 的顶点包围盒来替代其精确的投影，然后绘制出位于该投影内的物体 ( 只有这样的物体才是可能可见的) 。递归地找到通过这些p o r t a l s 相邻的其他 c e l l ，执行相同的过程，其中新找到的p o r t a l 需要用前面得到的p o r t a l s 的包围盒 来裁减。 凸体遮挡 在论3 之 c o o r 9 1 9 9 6 】【c o o r 9 1 9 9 7 q 1 ，作者提出了利用大的凸遮挡体进行遮挡 剔除的方法。这两种方法并没有真正地进行遮挡体的融合一即考虑多个遮挡体 的并集对其他物体的遮挡，但利用了可见性变化的帧与帧之间的连贯性。在论文 【c o o r 9 1 9 9 6 ，采用增量的方式来更新可能可见集。事实上，他们隐式地构造 了一个a s p e c tg r a p h 来有效地追踪可见性的变化视觉事件( v i s u a le v e n t s ) 。 他们通过考虑位于侧影轮廓线上的边、顶点来有效地减少视觉事件的数目。但这 种动态地追踪视觉事件的方法的代价是相当大的，并且难于实现。在论文 【c b n b l 9 9 7 】中，维护了一个与视点有关的遮挡物集合来剔除场景中其它物体。该 r 浙江大学博士学位论文大规模场景的快速绘制技术的研究 方法将场景组织成层次结构，遮挡剔除在遮挡物和层次结构结点的包围盒之间进 行。其中可见性评估只需要考虑遮挡物的边所对应的s e p a r a t i n gp l a n e 和 s u p p o r t i n gp l a n e 以及待测试物体的包围盒之间的遮挡性。如图1 3 1 所示。c o o r g 的方法适用于存在一些较大遮挡物的场景，在预处理过程中，用一个遮挡物对视 点所张的立体角来挑选较大的遮挡物。 ， 、 、 、s e p a r a t i n gp l a n e 图1 3 1 ：s u p p o r t i n gp l a n e 和s e p a r a t i n gp l a n e 基于s h a d o wf r u s t u m 的遮挡剔除 在论) h u d s o n l 9 9 7 ，作者提出了一种动态挑选遮挡物并计算其阴影区域 ( s h a d o w f r u s t u m ) 的方法来进行遮挡剔除。这种方法从另一个角度来看待物体 之间的遮挡性把视点看作是点光源，如果物体a 处于物体b 的阴影( 由“点 光源”造成的阴影) 中，则物体b 遮挡了物体a ，物体a 是不可见的。h u d s o n 用视点作为投影中心，对每一个选出来的遮挡物的侧影轮廓线构成一个s h a d o w f r u s t u m 。将整个场景的层次结构和这些s h a d o wf r u s t a 做测试，如果某结点完全 被其中一个s h a d o wf r u s t u m 所包围，则该结点和其子孙结点都不可见；如果某 结点与遮挡物侧影轮廓线所构成的任意一个s h a d o w f r u s t u m 都不相交，则结点和 其子孙结点不被选定的遮挡物所遮挡，它们将被送至绘制流水线进行绘制；如果 某结点和其中某一个s h a d o wf r u s t u m 相交，则递归地测试其子孙结点。 在 b i t t n e r l 9 9 8 中，作者提出了一个改进的方法。类似于s h a d o wv o l u m e b s pt r e e 方法 c h i n l 9 8 9 ，该方法将s h a d o wf r u s t u m 组织成一棵遮挡树，开始 时，遮挡树只有一个l i t 结点，然后将遮挡物逐一插入该树中。当一个遮挡物位 9 浙江大学博士学位论文大规模场景的快速绘制技术的研究 于一个l i t 结点中，则用该遮挡物的s h a d o wf r u s t u m 来调整此树。若遮挡物位 于一个s h a d o w e d 结点中，则该结点将直接被忽略掉。当遮挡树完成后，类似于 h u d s o n 的方法，逐层地执行遮挡剔除。该方法优于h u d s o n 的方法在于在较 好的情况下，对于一个场景层次结点的遮挡性测试的次数是o ( 1 0 9 ( n ) ) ，因为该 方法考虑了遮挡物的融合。 1 3 3 3 基于视点的图像精度的遮挡剔除 层次z _ b u f f e r 层次z - b u f f e r ( h i e r a r c h i c a lz - b u f f e r ) 是一种扩展的z - b u f f e r 消隐算法 【g r e e n e l 9 9 3 】。作者利用了两种层次结构：物体空间的八叉树和图像空间的 z - p y r a m i d 。所谓的z - p y r a m i d 是一组多分辨率深度缓存器。最精细分辨率上的深 度缓存器就是图形系统的z - b u f f e r ，上层深度缓存器的分辨率只有其下一层的一 半，其中每个元素值是对应下一层2 2 窗口中四个元素的最远的深度z 值。整 个z p y r a m i d 的构建是从低向上，最上层的唯一一个元素对应了整个z b u f f e r 中 最远的深度z 一值。 场景被组织成一个八叉树，并且以自顶向下、自前向后的方式遍历整个八叉 树，对每个结点进行遮挡测试。结点包围盒的每一个面的深度和当前的z - p y r a m i d 将一一比较从最顶层的深度缓存器开始，如果面的深度值大于包含其在屏幕 上投影区域的深度缓存器中的深度值，则该面被遮挡；反之，则递归至下一层深 度缓存器继续进行比较。若一个结点的所有面都被遮挡，则该结点内包含的所有 元素都无需被绘制；否则，对其子结点继续进行遮挡测试。若存在未被遮挡的绘 制元素时，z p y r a m i d 按自低向上的方式被同步更新。 该方法同时利用了帧与帧之间的连贯性，通过使用上一帧可见的绘制元素来 初始化z p y r a m i d ，即优先绘制这些绘制元素，然后用得到的z - b u f f e r 来构造 z p y r a m i d a 层次遮挡图 z h a n g 在论文 z h a n 9 1 9 9 7 】【z h a n 9 1 9 9 8 q h 提出了一种能够充分利用图形硬件 的类似于层次z b u f f e r 的方法，即所谓的层次遮挡图( h i e r a r c h i c a lo c c l u s i o nm a p ， l o 潺耩大学麟圭学位论文丈规摸场景静抉逮绘翻技术翦磺究 h o m ) 算法。这种方法将可见性测试分成粳盏测试和深度溺试两个部分。层次 遮挡网类似于层次z - b u f f e r ，也是一种层次结构，但不同的是，遮挡图存贮的是 透明度信息，深度信息则存贮在其它的数据结构中。 焱镁处理过程孛，滚摆一援遮挡谚：农绘裁建疆孛，对予德一羧，终溪颓走 选择的遮挡物建立h o m ，然后再孀h o m 剔豫场景中的其它物体。将预先选择 的遮耥物用黑白模式绘制后，从帧缓存器中读出作为最底层的h o m 中的缓存器。 然厝逐层建立层次结构，糨糙层的缓存器的镪一个像素是下一层中2 2 窗口中 像豢豹遴瞻度静平均毽。该建立过程可鞋蠲纹理浃射来完成。 猩餍h o m 剽除物体对，首先将物体的镪溺盒投影至g 屏幕上，弗找至n 在h o m 中最合适的层次该投影所占的像素个数小于4 个( 或一个用户自定义的值) 。 如果该投影所覆盖的像素熄半透明的，则该物体不能被剔除：如聚那些像素是完 全不透明鳃( 或是毫予髑户设置魏一个阑傻) ，朝逶过了覆盖测试，诧薄翥要进 行深魔测试来熬薮该秘体是否霄觅。在论文 z h a n 9 1 9 9 8 孛t 撵滋了强释深疫测 试的方法。最简单的测试用一个单一平面在所有的遮挡物急厮，所有通过覆 盖测试的物体都需要和谈平面进行比较。另一种方式时，使用一个深度估计缓存 器( d e p t he s t i m a t i o nb u f f e r ) ，其中屏幕被分割成一系列小块，繇一小块对应一 令鼙一平嚣弱予瀑痊灏试。 通过改变覆盖测试中的阀值，可以改变该方法的近似性从而以牺牲正确 性。并乏换取效率的提高。 方向饿离散遮挡物( d i r e c t i o n a ld i s c r e t i z e do e d u d e r ) 在 b e m a r d i n i 2 0 0 0 q b ，作者提密了一辩黧成与筏煮有关魏方秘往离散速拷秘 ( d i r e c t i o n a ld i s c r e t i z e do c c l u d e r ) 的方法，i 袅贱遮挡物可以用来剿除场景八叉树 的结点类似于h z b _ 和h o m 方法。在预处理阶段，场景教简化为一棵八叉 挝，蔟审结点的每一个聪视为一令潜在遮挡戆，然屡将这些潜在遮挡物程一系列 撬熹嚣域攘关起来。奁镲一令褪蠡区域蠹，遴避滋一步戆爨赣簿邃耀关瓣潜在遮 挡物，使之成为真正的脊效遮挡物。由于产擞的遮挡物都是与坐标轴平行的，可 以用较少的数据量来存贮这些遮挡物。 浙江大学博士学位论文