（计算机软件与理论专业论文）基于视点区域的全局遮挡图及精确pvs算法研究.pdf

摘要 摘要 随着虚拟现实以及三维交互应用技术的不断发展，大型模型的实时显 示逐渐成为计算机图形学研究的热点。作为虚拟场景交互式漫游的主要加 速方法，遮挡剔除技术日益被众多科学家所关注。然而，由于虚拟场景规 模及复杂程度的不断提高，遮挡剔除技术要花费大量的预处理时间，如何 提高预处理速度是基于视点区域的遮挡剔除技术亟待解决的问题。 首先，改进了全局遮挡图算法。为了加速全局遮挡图构造过程，通过 研究相邻视点区域间可见面片的相关性，推导出了区域相关的计算全局遮 挡图的定理；并且，通过利用方向连接图表示视点区域间的相关性，设计 了基于区域相关的全局遮挡图构造方法。 其次，针对传统精确可能可见集算法，设计了基于保守遮挡剔除的精 确可能可见集的算法。从三个方面加速了精确可能可见集的计算过程：其 一，利用空间连贯性，引入基于虚拟遮挡物的保守遮挡剔除算法，快速的 判断出场景中大量不可见的物体；其二，利用光线投射的方法，快速确定 可见的面片；其三，对于可见性不确定的面片，采用遮挡物优化的方法， 对面片与面片间的可见性判断进行优化。 最后，对改进的全局遮挡图算法和基于虚拟遮挡物的精确可能可见集 算法进行实验验证。运用v c h 、o p e n g l 进行编程实现，对算法改进前后 进行性能比较以及实验分析。 通过对已有的全局遮挡图算法和精确可能可见集算法的改进，有效提 高了预处理的速度，从而增强了在场景实时绘制中算法的实用价值。 关键词可见性剔除：遮挡剔除；可能可见集；全局遮挡图；虚拟遮挡物 燕山大学工学硕士学位论文 a b s t r a c t w i t hc o n t i n u a ld e v e l o p m e n to ft e c h n o l o g ys u c ha sv i r t u a lr e a l i t ya n d3 d i n t e r a c t i v e a p p l i c a t i o n , l a r g e m o d e l sr e a l - t i m e r e n d e r i n g h a sb e c o m e r e s e a r c h i n gh o t s p o ti nc o m p u t e rg r a p h i c s a sm a i na c c e l e r a t i n gm e t h o df o r i n t e r a c t i v ew a l k t h r o u g hi nv i r t u a ls c e n e ，o c c l u s i o nc u l l i n gt e c h n o l o g yh a sb e e n i n c r e a s i n g l yc o n c e r n e d h o w e v e r , b e c a u s eo ft h es c a l ea n dc o m p l e x si n c r e a s e o fv i r t u a ls c e n e ，ag r e a tt i m eh a sb e e nu s e di np r e p r o c e s sp h a s e h o wt o i m p r o v et h ep r e p r o c e s ss p e e di nf r o m r e g i o no c c l u s i o nc u l l i n gt e c h n o l o g yh a s b e e nap r o b l e mw h i c hs h o u l db e e ns o l v e du r g e n t l y f i r s t l y ，t h ea l g o r i t h mo fg l o b a lo c c l u s i o nm 印w a si m p r o v e d f o r a c c e l e r a t i n gt h eg o m c o n s t r u c t e dp r o c e s s ，t h r o u g hr e s e a r c h i n gv i s i b l es e t s r e l a t i v i t yb e t w e e na d j a c e n tv i e wc e l l s ，t h ev i e wc e l l sd e p e n d e n tg o m t h e o r e mw a sd e d u c e d a n d ，t h eg o m c o n s t r u c t i n gm e t h o dw a sd e s i g n e db a s e d o nu s i n gd i r e c t e dj o i n tg r a p ht oe x p r e s st h ed e p e n d e n c eb e t w e e nv i e wc e l l s s e c o n d l y , t h ee x a c tp v sa l g o r i t h mb a s e do nc o n s e r v a t i v eo c c l u s i o n c u l l i n gm e t h o dw a sd e s i g n e dt oa i ma tt r a d i t i o n a le x a c tp v sa l g o r i t h m t h e r e i st h r e ea s p e c t sf o ra c c e l e r a t i n gt h ep v sc o m p u t i n gp r o c e s s ：a b o v ea l l ，b yu s e o ft h ef e a t u r eo fs p a c ec o n s i s t e n c y , c o n s e r v a t i v eo c c l u s i o nc u l l i n gm e t h o d b a s e do nv i r t u a lo c c l u d e r sw a su s e dt oq u i c k l ye s t i m a t em a s si n v i s i b l eo b j e c t s i ns c e n e ；n e x t , r a yc a s t i n gt e c h n i q u ew a su t i l i z e dt oc o n f i r mv i s i b l ep o l y g o n s ； a tl a s t ，o c c l u d e r sw a so p t i m i z e dt oi m p r o v ep o l y g o n - p o l y g o nv i s i b i l i t ym e t h o d f o rd i s t i n g u i s h i n gt h eu n c e r t a i np o l y g o n s f i n a l l y , t h ei m p r o v e dg o ma l g o r i t h ma n de x a c tp v sa l g o r i t h mb a s e do n v i r t u a lo c c l u d e r sw e r ev a l i d a t e dt h r o u g ht e s t s o p e n g la n d v c + + w a su s e dt o i m p l e m e n tt h ea l g o r i t h m s ，b u ta l s o ，p e r f o r m a n c e so ft h e t r a d i t i o n a la n d i m p r o v e da l g o r i t h mw a sc o m p a r e da n da n a l y z e d i t a b s t r a c t t h ep r e p r o c o s s i n g s p e e dw a se f f i c i e n t l y i n c r e a s e dt h r o u g hi m p r o v e d t r a d i t i o n a lg o ma l g o r i t h ma n de x a c tp v s a l g o r i t h m ，c o n s e q u e n t l y i t s p r a c t i c a lv a l u ew a se n h a n c e di ns c e n e sr e a l t i m er e n d e r i n g k e y w o r d sv i s i b i l i t yc u l l i n g ；o c c l u s i o nc u l l i n g ；p v s ；g l o b a lo c c l u s i o nm a p ； v i r t u a lo c c l u d e r s l i l 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于视点区域的全局遮 挡图及精确p v s 算法研究，是本人在导师指导下，在燕山大学攻读硕士学 位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部 分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要 贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完 全由本人承担。 作者签字乏寸融、 日期：k 月：归 燕山大学硕士学位论文使用授权书 基于视点区域的全局遮挡图及精确p v s 算法研究系本人在燕山大 学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成 果归燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关 人员。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校 保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。 本人授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以 公布论文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密d ( 请在以上相应方框内打“4 ”) 作者签名：罩撂寻、日期：h 9 年妨月1 t 日 名：乃雾隰彳年丫m 第1 章绪论 1 1 课题研究背景 第1 章绪论 虚拟场景的实时图形绘制技术是虚拟现实、实时仿真以及交互式三维 设计等许多重要应用的底层支撑技术，也是计算机图形学本身的一个基础 性研究课题。随着虚拟现实技术应用的深入，计算机所要绘制的场景规模 日益庞大复杂，人们对所绘制场景逼真度要求也越来越高。虽然高速发展 的c p u 技术和专用图形处理器使得现今的图形工作站和个人p c 机的性能 得到了很大的提高，但是虚拟现实系统中场景的规模和复杂度与交互实时 性要求的绘制速度之间的矛盾，仍是制约虚拟现实应用发展的瓶颈。 早期，传统的消隐算法( h i d d e ns u r f a c er e m o v a l ，缩写为h s r ) i i 是一类 精确的可见性计算算法，这类算法通常需要逐个判断面片是否可见，因此 其算法复杂度为o ( n 2 ) ( n 为场景中面片的数目) 。但是，随着三维场景的规 模与复杂度的增加，h s r 算法将难以满足实时绘制的要求。于是出现了另 一类可见性判断算法，即可见性剔除算法 2 1 ，该算法通过预先估计物体的 可见性来快速地剔除那些不可见的物体，得到一个可能可见集( p o t e n t i a l l y v i s i b l es e t s ，简称p v s ) ，绘制时只需调用这些信息即可实现场景的快速绘 制，降低了场景的复杂程度，最终实现低负荷绘制与网络传输。 1 2 遮挡剔除技术国内外研究现状 大规模场景中，通常可见的物体数要比总数少得多，例如，典型的城 市场景，只能看到城市的一角，这类场景称为稠密遮挡场景。其它如室内 场景，墙壁遮挡了大部分场景，实际上从房屋的任何视点，仅能看到该屋 内的场景及通过门廊的可见物，这是可见性剔除算法得到广泛应用的依据 和前提。可见性剔除算法包括背面剔除、视域剔除以及遮挡剔除嘲，其中 l 燕山大学工学硕士学位论文 遮挡剔除的主要思想是通过选择一些遮挡物，在绘制流水线的前期以较少 的计算代价来剔除被遮挡物所遮挡的物体，以减少绘制流水线后期的处理 负荷，相对于前两者，它更加复杂，但在深度复杂的场景中它可以为提高 绘制效率提供更多的收益。下面，将着重介绍遮挡剔除方法及其最新的技 术发展。 近年来遮挡剔除技术的研究取得了很大的进展，随着工业需求的不断 增强，遮挡剔除技术在理论研究和实践中都取得了很大的成果，其广泛应 用于军事和航空航天、建筑及汽车等制造业、模拟训练、娱乐等许多领域。 正是由于遮挡剔除技术有着巨大的应用前景，国内外有许多大学和研究机 构都致力于该技术的研究。 1 2 1 基于视点的遮挡剔除方法 一类基于视点的遮挡剔除方法是在景物空间进行遮挡剔除，在预处理 阶段选取某些物体作为遮挡物，而在运行阶段利用遮挡物形成的本影区域， 对其余物体进行遮挡检测。 1 9 9 7 年c o o r g 提出了利用大的凸遮挡物进行遮挡剔除的方法 4 1 ，将场 景组织成层次结构，并且维护了一个与视点有关的遮挡物集合，可见性检 测只需要考虑遮挡物的边所对应的支撑平面与分割平面以及待测试物体的 包围盒之间的遮挡性。该方法适用于存在较大遮挡物的场景。 h u d s o n 提出了一种动态挑选遮挡物并计算其阴影区域( s h a d o w f r u s t u m ) 的方法来计算遮挡剔斛5 1 ，将视点作为投影中心，对每一个选出来 的遮挡物的侧影轮廓线构成一个阴影区域，将整个场景的层次结构和这些 阴影区域做测试，如果结点完全被其中一个阴影区域包围，则该结点和其 子结点都不可见。1 9 9 8 年b i t t n e r 对上述方法进行了改进，将阴影区域组 织成一棵遮挡树嘲，由于充分利用了遮挡物的融合，该方法优于h u d s o n 的方法。 b e m a r d i n i 提出了一种生成与视点有关的方向性离散遮挡物的方法【饥， 这些遮挡物用来剔除场景八叉树的结点。在预处理阶段，场景被简化为一 棵八叉树，其中结点的每一个面被视为一个潜在的遮挡物，然后将这些潜 2 第1 章绪论 在遮挡物和一系列视点区域相关起来。在每一个视点区域内通过进一步的 判断，筛选相关的潜在遮挡物，使之成为真正的有效遮挡物。 另一类基于视点的遮挡剔除方法是在图像空间进行遮挡剔除。这种算 法的基本思想是根据视点位置挑选出遮挡物，在图像空间将这些遮挡物离 散化，并将其离散表示组织成层次结构，剔除时将场景中物体的层次包围 盒自顶向下地与遮挡物的层次离散表示作比较，迅速拒绝被遮挡物体。 1 9 9 3 年g r e e n e 提出了层次z b u f f e r 方、法【引，作者利用了物体空间的八 叉树和图像空间的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 。 1 9 9 7 年z h a n g 提出了一种能够充分利用图形硬件的类似于层次 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 ，简称h o m ) 算法n ，这 种方法将可见性测试分成覆盖测试和深度测试两部分，层次遮挡图类似于 层次z b u f f e r ，也是一种层次结构，存贮的是透明度信息，深度信息则存 贮在其它的数据结构中。 2 0 0 0 年k l o s o w s k i 等人提出了一种基于体可见性的近似遮挡剔除算 法一优先层投影算法( p r i o r i t i z e d - l a y e r e dp r o j e c t i o n ，简称p l p ) 1 1 0 l ，该方法在 预处理过程中将场景有效的组织成单元网格，并由一个网格中包含的绘制 元素多少来决定优先级，这种算法能保证足够的帧速进行实时漫游，但它 是一种不保守的算法。 2 0 0 1 年h e y 1 1 l 等人将图像空间组织成2 维的网格结构，网格中的每一 个单元中用布尔值记录遮挡状态标识，为零时表示已有物体进行了填充， 那么按照由前向后的顺序进行绘制时，通过检测物体所对应的单元中的标 识来判断是否被遮挡。 h a v r a n 等人在2 0 0 3 年提出射线重投影算法【1 2 1 ，这种算法可分为重投 影阶段和绘制阶段。在绘制第一帧时调用普通的光线投射算法确定遮挡关 系，形成画面，在后续帧的绘制过程中利用重投影来提高绘制速度。算法 3 燕山大学工学硕士学位论文 采用两个辅助数组p o s 和a l p ，这两个数组的维数和画面的维数一致。在 第i 帧中所有射线和物体的交点被保存在p o s i 中，a i p i 用来保存第i 帧的 重投影点。一个物体经过重投影后，它的投影膨胀一次，这样可以形成重 叠信息，物体重投影的重叠信息可以用来判断遮挡关系。 2 0 0 3 年n a g a 等人提出o c c l u s i o n s w i t c h e s 技术【1 3 】，该技术利用了g p u 中集成的遮挡剔除检测功能，其中o c c l u s i o n s w i t c h e s 由两个g p u 组成， 分别用来进行遮挡物的计算和当前视点不可见部分的剔除，同时为了减少 g p u 间的通信，每一帧时都转换两个g p u 的功能，然后由第3 个g p u 来 进行图形的绘制显示。 2 0 0 4 年t i m oa i l a 等人提出d p v s 算法，解决大规模动态场景的遮挡 剔除问题1 1 4 】。该算法集成了视域剔除【1 5 】、遮挡剔除【l e l 、贡献剔除【1 7 1 、入口 单元剔除【1 8 增算法和可能可见集技术。该算法的目标：构造一个多种可见 性判断算法联合使用的框架，以适用于各种平台，在简单的场景中有最小 的开销，对于大规模场景，即使内存不够，也能适用。但是该算法依旧未 能解决因不精确判断引起的对可能可见集的大量处理。 1 2 2 基于视点区域的遮挡剔除方法 早期，有关全局可见性的研究试图给出精确的计算方法，但往往因为 非常高的计算复杂性和存储量而不具有实际使用价值，因此发展出另一类 以p v s 为核心的算法，即不需要严格的可见信息，而只需知道可能可见的 物体集合。这种算法需要一个预处理阶段，将可能可见集和视点区域联系 起来，并且大多数方法是从景物空间着手，考虑由视点区域对遮挡物所造 成的本影，然后再根据其他物体与该本影区域的关系来进行遮挡剔除，进 而求得p v s 。 1 9 9 0 年a i r e y 首先提出了针对建筑物室内场景的c e l l - a n d - p o r t a l 可见 性评估技术，从此掀起了研究可见性算法的理论热潮。1 9 9 8 年w a n g 提出 了基于光束的可能可见集方法【1 9 l ，在预计算阶段对每一光束计算位于光束 内的p v s ，实时绘制时，根据当前视点查找预先计算的可见性信息，用以 加速绘制过程。 4 第1 章绪论 w o n k a 提出收缩遮挡物方法1 2 0 1 ，通过采样视点区域边界，将基于视点 区域的遮挡剔除方法转化为用基于视点的遮挡剔除方法来实现。2 0 0 1 年 w o n k a 提出了一个异步的多进程在线计算方案，称之为i n s t a n t v i s i b i l i t y 2 q 。 由一个可见性计算服务器进行遮挡物本景的计算，并将计算出对应的可能 可见集实时地传送给另一个负责绘制的进程。 2 0 0 3 年l e y v a n d 等人将光线空间分解为两个正交的予空间，并在子空 间中分别计算物体之间遮挡关系。该方法适合处理2 5 d 的场景，处理一般 三维场景则显得复杂【2 2 1 。 2 0 0 4 年b i t t n e r 等人提出一种平衡c p u 和g p u 处理负担的算法田】。 为了提高查询速度，利用了可见性的时空相关性，可以使目前的实时绘制 图形软件包支持遮挡查询。在处理过程中利用g i 哪强大的处理能力，通过 g p u 的内部并行操作来进行遮挡查询，因此这些算法对硬件的要求高。 2 0 0 5 年s a m u l il a i n e 等人利用视点区域之间的相关性，提出了一种无 需将场景进行分层结构的算法，其核心思想是某一视点区域的可能可见集 是由与它相关的其余视点区域的可能可见集相加而得到的【2 4 】。同时，作者 介绍了该方法在保守及精确可能可见集算法中的应用。 国内许多科研工作者对遮挡剔除技术也作了相关研究。2 0 0 2 年，浙江 大学c a d & c g 国家重点实验室的华炜等人提出了全局遮挡图( g l o b a l o c c l u s i o nm a p ，简称g o m ) 算法1 2 3 1 ，对一个视点区域，g o m 表示一组位 于空间各个方向上的可见性临界面，这些可见性临界面提供了一个不可见 性判断依据一一凡是位于该临界面后的物体必是不可见的。2 0 0 5 年，任重 等人对于全局遮挡图的算法进行了改进【2 6 1 ，相对提高了g o m 的构造速度。 2 0 0 2 年中国科学院计算技术研究所c a d 开放实验室的孙红梅、刘慎 权等人，提出一种适合室外复杂地景的快速可见性的剔除算法 2 7 1 。它结合 b s p 树和z - - b u f f e r 算法，实现动态场景的快速更新，同时有效利用了地 形高程数据的规则性特点，直接定位可能可见的地形块集合，有效提高了 可见性判断的速度。 2 0 0 3 年哈尔滨工业大学的石振锋等人提出了基于主要遮挡物的动态 可见性算法郾】。该算法通过场景中预先定义的主要遮挡物，动态地形成一 5 燕山大学工学硕士学位论文 个遮挡树，位于遮挡树遮挡区域中的景物将被剔除。当场景按照b s p 树组 织，并按从前向后的顺序绘制场景时，算法具有较高的效率。 2 0 0 4 年，潘志庚等人提出了一种适用于在给定视点运动路径情况下， 处理三维场景的可见性预处理算法 2 9 1 。首先对所有可能的视线方向所对应 的立方体进行细分，然后对分割后的平面沿着运动路径移动所形成的光束 体进行可见性预处理，最后合并这些光束体，得到对该运动路径的可能可 见面集合。2 0 0 6 年，针对现在的遮挡剔除算法对动态物体达不到真正的剔 除，季国红等人提出了一种剔除场景中动态物体的算法，即区间扫描线z 缓冲器算法【如1 。 基于视点区域遮挡剔除技术的另一种算法为精确的可能可见集算法。 该类算法得到的结果为精确的可见信息，即对于视点区域内所有视点求取 可见面片，这些面片的并集成为该视点区域的p v s 。 这类技术通常在对偶线性空间中建立一种结构直接得出可见性事件 ( v i s i b i l i t ye v e n t s ) ，可见性的拓扑结构改变时为一个可见性事件。具有代表 性的该类结构包括a s p e c tg r a p h 3 1 1 ，3 dv i s i b i l i t yc o m p l e x a 2 1 。由于非常高 的计算复杂性和存储量，这此算法不具有实际使用价值，如a s p e c tg r a p h 的计算复杂度为o ( n 6 ) ，3 dv i s i b i l i t yc o m p l e x 的计算复杂度为o ( n 5 ) 。 1 9 9 7 年d u r a n d 等人通过直接计算v i s i b i l i t yc o m p l e x 低维元素s k e l e t o n 结构建立可见性事件p 3 1 ，该方法具有很好的鲁棒性，且在大多数场合下的 效率较高，但理论上界依然是o ( n 5 ) 。 2 0 0 1 年k o l t u n 等人在对偶线性空间建立了线段问射线的表示方法m 】， 通过判断所有经过视点区域和被检测物体间的视线是否被遮挡来进行遮挡 剔除计算。为了达到算法的高效性，作者通过图形硬件的离散化得到近似 的2 d 精确可见性结果。同年，b i t t n e r 等人利用相似的原理，通过建立区 域遮挡树快速获得可见性信息p ”。 2 0 0 2 年n i r e n s t e i n 等人首次提出了可行的计算3 d 场景的精确遮挡剔 除方法1 3 “，该方法利用普吕克空间来判断空间中两条直线的相互关系，由 此建立空间中两面片问射线的集合，通过构建实体几何( c o n s t r u c t i v es o l i d g e o m e t r y ，简称c s g ) 来判断该面片是否可见。2 0 0 5 年m o r a 等人对 6 第1 章绪论 n i r c n s t e i n 的方法进行了改进 3 7 j ，通过判断遮挡物的有效性，来减少进行 c s g 的数量，加速了算法的执行速度；最后以历史树的结构来保存可见性 信息，增强算法的鲁棒性。 1 2 3 遮挡剔除技术的分析比较 基于视点的遮挡剔除方法：这种方法的特点是不需要对场景进行预处 理，同时可以处理动态场景，但在绘制过程中需要消耗一定的时间。同时， 该方法分为两类，一类是在景物空间进行遮挡剔除判断，一类是在是图像 空间进行遮挡剔除判断。 基于视点区域的遮挡剔除方法：特点是需要预处理阶段，可见性判断 结果对于一个视点邻近区域都有效，具有可见性预测能力，可以提供连续 多帧的绘制，对于实时漫游以及网络应用来说比较有效，其缺点是需要较 长时间的预处理计算与存储资源消耗，并且不适合处理动态场景。 基于上述遮挡剔除技术的综述及对现有方法的分析比较，本文选用基 于视点区域的遮挡剔除方法进行研究，对现存的问题进行改进，以弥补其 不足之处。 1 3 课题研究内容及预期目标 本文在广泛调研和对大量中外文献分析的基础上，针对本文的研究问 题，主要完成以下几个方面的研究工作及预期目标。 ( 1 ) 基于区域相关的全局遮挡图的算法改进全局遮挡图算法相比其 它基于视点区域的遮挡剔除算法，具有适用于动态场景、存储量小等优势， 但其预处理过程，即全局遮挡图的构造过程需要花费大量的时问，通过分 析各个相邻视点区域间g o m 值的关系，提出利用相关性构造g o m 的方 法，以有效缩短预处理计算全局遮挡图的时间。 ( 2 ) 提出一种基于保守遮挡剔除的精确p v s 方法精确p v s 的求取不仅 有利于图形的加速显示，同时也是评价保守遮挡剔除算法紧致度的重要指 标。传统的精确p v s 算法需要很高的时间复杂度，本文在对前人提出的虚 7 燕山大学工学硕士学位论文 拟遮挡物遮挡剔除算法分析和研究基础上，提出了混和的精确p v s 算法。 ( 3 ) 改进算法的实验验证运用v c + + 及o p e n g l 为实验平台，对改进 后的算法编程实现，验证算法的有效性。 1 4 论文结构 全文共分5 章。各章结构及各章内容介绍如下。 第1 章为绪论，从遮挡剔除技术的现状分析直接引出课题研究工作的 出发点，对本文的研究内容进行了概述，最后给出论文的结构。 第2 章对遮挡剔除的基础技术进行深入剖析，分析了遮挡剔除的实现 步骤和方法，并进一步阐述了基于视点区域的遮挡剔除技术存在的问题。 第3 章为全局遮挡图算法的改进，针对视点区域间可见信息的空间相 关性，推导出区域相关性g o m 定理，并利用方向连接图表示视点区域间 的相关性，提出了基于区域相关的g o m 构造方法。 第4 章为精确可能可见集算法的研究，设计了将保守遮挡剔除与解析 方法相结合的框架结构，引入基于虚拟遮挡物的遮挡剔除判断方法，并对 面片与面片问可见性判断过程进行了光线投射及遮挡物优化等措施。 第5 章为算法的实验结果分析，利用2 5 d 及3 d 的虚拟场景，对本文 所提出的算法进行分析评价。 本文的最后是结论与展望，对本文的主要工作进行了总结，并对今后 的工作进行了展望。 8 第2 章基于视点区域的遮挡剔除技术基础 第2 章基于视点区域的遮挡剔除技术基础 遮挡剔除技术作为虚拟场景实时绘制的主要技术手段，自提出以来， 已经广泛应用到军事和航空航天、建筑及汽车等制造业、模拟训练、娱乐 等许多领域，并且取得了巨大的成功。目前，尽管在遮挡剔除方面进行了 深入、广泛的研究，取得了一定的研究成果，但由于虚拟场景的复杂性， 所取得的成就远不能满足科技工作者的要求，在预处理速度、动态场景及 基于g p u 的遮挡剔除等方面还有大量亟待解决的问题，更有效、更快速的 p v s 计算仍是一个重要的研究领域。本章对遮挡剔除的技术基础进行深入 剖析，为以后的研究打下基础。 2 i 遮挡剔除技术的基本步骤 通过对诸多遮挡剔除算法进行研究，可以总结出如图2 1 所示的基本 步骤1 3 8 l 。 耍缨螋 焦趟壅迥睑星- 绘制阶段 - - - - - - - - - - - - - + 图2 1 遮挡剔除技术的基本步骤 f i g 2 - ib a s i cs t e p so f o c c l u s i o nc u l l i n gt e c h n o l o g y 其中可以划分为三个基本阶段：预处理、遮挡查询和绘制阶段，预处 理阶段一般是脱机进行，其他两个阶段联机进行。如果要尽可能提高实时 9 燕山大学工学硕士学位论文 性，就要尽可能将需要大量计算的成分纳入预处理阶段，图中所示的虚线 部分表示可以纳入预处理阶段的计算成分。 ( 1 ) 遮挡物的选择遮挡剔除技术首先要选择一些物体作为遮挡物，否 则遮挡剔除也就无从谈起；另一方面，遮挡物的选择，直接影响着遮挡剔 除操作的效率及速度。通常，遮挡物选择分为静态及动态两种方法，前者 在预处理阶段指定部分物体作为遮挡物，而后者可以在运行阶段，从可能 的遮挡物集合中动态的选取其中的物体作为遮挡物。 ( 2 ) 遮挡关系表示它是遮挡剔除算法的核心内容，包含两种表示方 法：一是景物空间表示方法；二是图像空间表示方法，在图像空间，更容 易实现遮挡物的融合。是否能由遮挡物较快速的计算获得、以及是否在遮 挡测试过程中简单易行，是评价遮挡关系表示方法的标准。 ( 3 ) 可见实体计算该部分主要完成不可见物体的快速剔除。通常将场 景采用层次包围盒( 如八叉树1 3 9 1 、b s p 树m 等) 结构，根据不同的遮挡物表 示方法，进行相应的测试判断，快速剔除完全不可见的物体。 2 2 基于视点区域的遮挡剔除方法的关键技术 对于基于视点区域的遮挡剔除技术，要在预处理阶段完成以下工作： 将视点可以活动的区域划分成若干个子区域，每一个子区域称为视点区域， 同时，将场景以某种空间数据结构进行组织，选择合适的遮挡物，并利用 遮挡关系判断方法，计算该视点区域中的可能可见集，即p v s 。在场景漫 游过程中，根据当前视点所在的位置，确定所处的视点区域，将与该区域 相关的p v s 调入内存中，为了更进一步地提高场景的显示速度，多数漫游 系统都会用视域剔除算法来进行实时漫游。 下面，对于基于视点区域的遮挡剔除算法的关键技术，进行更进一步 地剖析介绍。 2 2 1 场景数据的组织 为了能够获得层次遍历以及能够实现基于物体空间和图像空间的遮挡 1 0 第2 章基于视点区域的遮挡剔除技术基础 剔除，需要将场景信息按一定的空间数据结构进行组织。空问数据结构是 数据的一种表示形式，可以将几何体数据组织在三维空间中。 目前空间数据结构的组织通常是采用层次结构的方法【4 ”。这种结构具 有嵌套和递归的特点，可以有效提高查询速度，计算复杂度通常从d ( n ) 提 高到d ( 1 0 9 n ) 。但大多数空间数据结构的构造和实时更新开销都比较大，通 常还需要一个预处理过程，因此较适用于静态场景的遮挡剔除算法中。目 前常用的场景数据表示方法有：四叉树、八叉树表示、b s p 树表示、层次 包围体以及场景图表示等方法。 2 2 1 1八叉树八叉树采用类似于二维的四叉树结构对场景进行空间细 分，整个三维空间被细分成小的立方体成为体素。体素通过用递归表的方 式组织成层次结构，以便对每个区域所包含的对象进行细分直到满足所需 的分辨率为止。 场景的八叉树层次结构在预处理阶段生成，该结构也可用于对场景进 行视域剔除计算以及虚拟场景的碰撞检测等。对场景进行八叉树体细分能 很好的支持建筑场景空间几何剖分，主要用于建筑场景实时绘制。 2 2 1 2 空间细分二叉树空间细分二叉树又称为b s p 树。b s p 树通过以 细分平面将空间细分为两个区域。树的叶节点表示空间体元，分枝节点表 示细分空间的分隔平面。 对于虚拟场景的实时绘制而言，b s p 树的最大优点是可以构造较好的 均衡树，尤其是当场景中对象不均衡分布时，从而减少树的深度。这样实 时渲染时，可以快速遍历整个场景树，加速场景绘制。 所有空间细分方法的缺陷是对于室外场景不能提供高性能的渲染绘制 能力，主要由于没有有效的算法对室外场景进行空间剖分。另外，对于场 景中的对象渲染需要花费昂贵的树结构更新代价，每一次动态对象渲染时 将其插入到静态树结构中绘制，然后重新移去动态对象。 2 2 1 3 层次包围体包围体就是包含一组物体的空间体，要比所包含的 几何物体形状简单的多。包围体形式主要有：球体、椭圆体、轴对齐包围 盒a a b b ( a x i s a l i g n e db o u n d i n gb o x ) 、有向包围盒o b b ( o r i e n t e db o u n d i n g b o x ) ，以及k - d o p 等。 1 1 燕山大学工学硕士学位论文 轴对齐包围盒( a a b b ) ：边界盒与坐标轴的方向一致，定义了两个极值 点，边界盒所包围的几何模型的坐标位于两个极值点之间。 有向包围盒( 0 b b ) ：边界盒的表面法向量两两正交，任意旋转后的轴 向边界盒即为有方向包围盒。 2 2 1 4 场景图表示八叉树、b s p 树和h b v 都使用某种类型的树作为基 本的数据结构，均以层次形式来保存几何物体；与树结构表示相反，场景 图表示企图用包围体将场景中的对象包围起来，场景图是一有向的、简单 的连接图。三维场景除了模型的几何数据，还有模型变换、层次细节、纹 理材质和光源等信息，对于这些要素可以用树来表示。 2 2 2 遮挡物的选择方法 在遮挡剔除算法中，用来遮挡其他对象的物体称为遮挡物( o c c l u d e r ) ； 被遮挡的对象称为被遮挡物( o c c l u d e e ) f 4 2 】。利用大的遮挡物体进行保守地 估计物体的可见性时，遮挡物的选择对于算法的运行速度以及剔除效率是 十分重要的。 遮挡物的选择标准包括：物体的大小，物体的体积越小，则其作为遮 挡物的可能性越小；物体离视点区域的距离，即物体离视点区域越近，则 其作为遮挡物的可能性越大；另外，可以根据其对遮挡程度的贡献大小进 行选择。遮挡程度通过物体的实体角( s o l i da n g l e ) 来衡量【4 3 1 ，记为q ，如图 2 2 所示，表示物体表面s 在单位圆上的投影。如果用p 表示方向向量夹 图2 - 2 实体角 f i g 2 - 2s o l i da n g l e 角，a 表示面片的大小，r 表示视点至面片的距离，则实体角为： 1 2 第2 章基丁二视点区域的遮挡剔除技术基础 q i a c o 。s o( 2 1 ) ， 在基于视点区域的遮挡剔除技术中，往往多个遮挡物体对某些被遮挡 物形成融合遮挡如图2 3 所示，其中图2 - 3 ( a ) 表示单个物体并没有对其它 物体形成遮挡，然而在这些遮挡物共同作用下，则遮挡了其它的物体如图 2 - 3 ( b ) 所示。如何解决融合遮挡的情况，是视点区域遮挡剔除中需要解决 的重点问题，因为在一般的场景中，由单个物体形成的遮挡是有限的。近 几年，分别有以下几种方法来处理融合遮挡的情况。 ( a ) 单个物体形成的遮挡( b ) 融合遮挡 ( a ) t h eo c c l u s i o nf o r m e db ys i n g l eo b j e c t( b ) o c c l u d e rf u s i o n 图2 - 3 物体形成的遮挡 f i g 2 - 3t h eo c c l u s i o nf o r m e db yo b j e c t ( 1 ) 扩展投影方法类似于基于视点的投影方法，将遮挡物和其他物体 投影到一个平面上，如果一个物体的投影完全被遮挡物的投影的并集所覆 盖，并且位于其后面，则该物体是被遮挡的，但不同于基于视点的投影， 这里投影是针对一个视点区域的。 扩展投影l 指的是相对于某一视点区域，物体在投影平面上的投影， 并且定义遮挡物的扩展投影相交时形成的融合，指的是所有扩展投影的交 集，而物体为被遮挡物时，扩展投影的融合是所有被遮挡物扩展投影的并 集。通过对遮挡物的低估计、被遮挡物的高估计，来保证算法的保守性。 剔除过程中通过比较遮挡物及被遮挡物的扩展投影、以及空间深度测试， 可以判断出遮挡关系。 1 3 燕山大学工学硕士学位论文 ( 2 ) 离散方法s c h a u f l e r 提出了一种保守的基于体可见性的遮挡剔除 的算法【4 5 l ，该算法将场景离散为一系列的体素，并将落于场景中物体内部 的体素标识成不透明。这些体素作为遮挡物，因为形状简单，很容易进行 遮挡物的融合。初始时，场景中的物体的表面首先被离散，那么被表面包 围的空间则由一系列不透明的体素所填充。对于每一个视点区域，首先将 相连的体素组织成大的b l o c k e r ，然后计算由视点区域和b l o c k e r 形成的阴 影区域，落于该阴影区域的体素被标识为“o c c l u d e d ”。并且进一步，寻找 落于这一阴影区域边界的其他b l o c k e r ，计算这些阴影区域，并将这些阴影 区域和原先阴影区域合并，就可以不断地扩大被遮挡空间。 ( 3 ) 虚拟遮挡物方法给定一个场景和一个视点区域，虚拟遮挡物1 4 6 是一个与视点区域有关的多边形，当然它并不是场景中一个真实存在的物 体。它是通过在物体空间中，不断地将遮挡物投影到相邻的其他遮挡物上， 然后进行合并而形成的。通过预先选取一系列的物体作为种子物体，根据 几何条件来选择一些物体来加入到相应的聚合体中，然后扩大各自的聚合 体的本影区域，以此来解决融合遮挡的问题。 2 2 3 遮挡关系判断方法 基于视点区域的遮挡剔除算法，大多是从景物空间着手，考虑由视点 区域对遮挡物所造成的本影，然后再根据其他物体与该本影区域的关系来 进行遮挡剔除，进而求得可能可见集。不同的算法往往采用不同的遮挡物 表示和不同的求取本影的方法。 想象一下现实生活中灯光下的影子，影子中部特别黑暗的部分称为本 影，是被遮挡物完全遮挡的区域，而四周灰暗的部分称为半影，是被遮挡 物部分遮挡的区域。 基于视点区域的遮挡剔除技术中，遮挡关系判断方法类似于在面光源 的作用下计算阴影区域的原理。如图2 - 4 所示，将面光源与遮挡物的顶点 分别相连，形成不同的直线；如果面光源与遮挡物位于该直线的同一侧， 则称此直线为支撑直线；如果不同侧，则称该直线为分割直线如图2 - 4 中 的虚线。支撑直线与分割直线将遮挡物的投影划分为本影区域与半影区域， 1 4 第2 章基于视点区域的遮挡剔除技术基础 处在本影区域的物体对于视点区域是完全不可见的，而处在半影区域中的 物体对于视点区域中的部分视点是可见的。因此，通过比较物体所处的位 置，可以判断出不可见的物体，得到视点区域的p v s 。 面 半影 奉影 半影 图2 4 本影与半影 f i g 2 - 4u m b r aa n dp e n u m b r a 2 2 4 可见信息的存储 预处理过程中将产生大量的可见信息，即可能可见集。一般情况下， p v s 组织成某种空间数据结构，对于复杂场景，可见数据可能很大。应用 中，这些结构信息需要读入内存中，或者通过网络进行传输。因此，为了 减少从硬盘中反复读取数据的次数，以及减少在网络传输中的负荷，产生 了另外的一个研究的热点领域，也就是p v s 数据的压缩【4 7 螂l ，并且已经取 得一定的研究成果。对于这些数据进行的压缩，分为两种形式，一种为有 损压缩，一种为无损压缩。 ( 1 ) 有损压缩所谓有损压缩，指通过增加可见结果的保守性来节省空 间。p a n n e 等人将相似的可见集合通过合并的方法，利用相邻视点区域的 p v s 在空间上的相关性，即多个相邻视点区域的可见集合用同一个大的集 合来代替。具体过程中用表的结构，来描述视点区域及物体间的布尔值， 当相邻区域间的p v s 相似度大于某一临界值时，合并这些p v s 为一个大 的可见集合。y a g e l 等人提出了一个相似的压缩方法，但是考虑了不相邻 视点区域的可见集进行压缩的情况。 ( 2 ) 无损压缩指在没有改变保守程度的情况下，减小存储空间。为了 实现这一目标，p a n n e 等人研究了列表之间的相关性。当一簇区域间有相 1 5 燕山大学工学硕士学位论文 似的可见信息时，其中相似的信息组织在一起，仅保存一次。相似的，如 果一簇多边形有相似的可见性时，同样组织在一起来保存。通过这样的方 法，对于相似的可见信息，仅保存了一次，因此减小了存储空间。 2 - 3 基于视点区域的遮挡剔除方法面临的问题及评价指标 尽管对遮挡剔除方面进行了深入、广泛的研究，取得了一定的研究成 果，但由于虚拟场景的复杂性，所取得的成就远不能满足科技工作者的要 求。下面，阐述一下基于视点区域的遮挡剔除方法面临的问题，并且指出 遮挡剔除方法的评价指标。 2 3 1基于视点区域的遮