（计算机应用技术专业论文）大型场景绘制过程中遮挡剔除算法的研究.pdf

摘要 摘要 随着计算机图形学、虚拟现实以及三维交互设计等技术的不断发展及广泛应 用，大规模复杂场景的快速绘制作为这些应用领域的支撑技术逐渐成为计算机图 形学的研究热点。实时绘制技术经过了几十年的发展，取得了长足的进步，但在 保持一定真实感的前提下实时绘制出复杂场景仍然是一个具有挑战性的研究课 题。 本文首先简单介绍了实时绘制技术，然后从软件和硬件两个方面对当前国内 外遮挡剔除的可见性技术做了综述。着重从基于视点和基于区域的角度对遮挡剔 除技术领域中的软件算法进行了分类总结，并分析了这些算法的特点及存在的问 题。本文结合具体实际项目交互绘制的应用需求，选择基于区域的遮挡剔除技术 作为主要研究内容。 本文重点研究了两种基于视点区域的剔除方法： ( 1 ) 区域相关的虚拟遮挡 物算法。在传统虚拟遮挡物算法的基础上进行改进，引入剔除区域的概念以及不 同的剔除区域中物体的分布数量对种子物体选取的影响。改进后的算法能够对分 布较多物体的区域起到良好的遮挡效果，提高场景的整体遮挡剔除率和绘制速 度。( 2 ) 区域采样的球面投影剔除算法。基于扩展投影算法本文提出了一种改 进的方法一球面投影剔除算法，采用一个球面投影面对视域周围物体统一处理降 低算法的复杂性。先通过极坐标投影算法验证极坐标在圆周上投影对于二维遮挡 剔除的有效性，然后把二维极坐标投影算法扩展到2 5 维的场景中对视域采样形 成待处理的视点集合，对每个视点分别采用球面投影算法在经度和纬度上分别投 影进行判断，最后形成整个视域的可见物体集合。该算法充分利用了物体的空问 连贯性，在投影过程中逐步融合形成较大的遮挡面，提高了算法可见性判别效率。 实验结果表明本文的算法能够实现对物体的遮挡剔除，有效降低场景的复杂 度，明显提高场景的绘制速度。 关键词：可见性判断；遮挡剔除；种子选取；极坐标投影；球面投影 b b t r a c t a b s tr a c t w i l ht h ew j d e s p r e a da p p | i c a t i o n so fc o m p u t e rg r 印h l c s ，v i r n 训r e a i i ha n d3 di n l e r a c t i v e d e s i g n ，r e a l t i m er e n d e r l n go f t h r e ed i m e n s i o n a lo b j e c t sa st h ee s s e m i a lc o r eo f t h e 印p l i c a t i o n s b e c o m e sm o f ea n dm o r ei m p o a n t a l t h o u g h 幽eg r e a tp r o g e s s e si nt h e 矗e 2 do fc o m p u ! 。f g r a p h i c sh a v eb e e na c h i e v e di nl a t e s td e c a d e s ，r e a l - t i m er e n d e f i n go fc o m p l e xs c e n e sr e m a i n so n e o f t h em o s tc h a i i e n g m gi s s u e si nt h e 行e l d l nt | l i st h e s i s ，t h ek e yt e c h n i q u e so fr e a l - t j m er e n d e r i n go fc o m p l e xs c e n e sa r eb r i e n y i n 仃d d u c e d ，f o rt h a tt h eo c c l u s i o nc u l l i n gt e c h n i q u e sa r es u r v e y e dr e s p e c t i v e l yb a s e do ns o r w a r e a n d h a r d w a r e ，l nt h es u r v e y ，m o r ea t t e n t j o na r ep a yt ot w ok i n d so fa l g o r i t h m st h a ta r et h e o c c l u s i o nc u l l i n gt e c h n i q u e sr e s p e c t i v e l yb a s e do nv i e wp o i n ta i l dv i e wr e g i o n c o m p a r i n gt h e p f o p e t i e sa n d 印p l j c a t o nr e g i o no ，m e s et o wk i n d so fa l g o r i t h m ss h o w sf h a tl kr e g j 彻b a s e d a l g o r i t h m sa r em o r es u i t a b l et ot h ed e m a n do ft h oa p p l i c a t i o n si n t e r a c t j v er e n d e r i n g a sar e s u l t ， t h ed e c i s i o no ft h a tt h st 1 1 e s i se m p l a s i z e so nt h er e g i o n b a s e do c c j u s i o nc u f l i n ga i g o f i t h m sa r e m a d e 1 v oo c c l u s i o nc u l l i n ga r ed i s c u s s e di nt h i su l e s i s ：( 1 ) v i r t u a lo c c l u d e ra l g o r i t 砷r e g i o n r e l a l e d t h 。p 印e rg o e sd e e pi n t ot h ea l g o r i t h m go fr e g i o nr e l a t e do c c l u s i o ns e e d ss e i e “e d ，a n d d e v e l o p sa ni m p r o v e dv i n u a lo c c i u s i o n 甜g o r n h mt h a ti sb a s e do no b j e c td e n s i t yi nv i e wr 。g i o n i n v a r i 。u sv e wr e g j o n st h eo b j e c td e n s j l yi sd i 匏r e n l ，a n d 王l so c c j u s j o ne 髓c tj sa j s od i 仟e r e n t ，t h e i m p m v e da l g o r i t h mc a ni n c r e a s em eo c c l u s i o nc u i l i n gr a t e ( 2 ) r e g i o n b a s e ds 啪p 1 1 n g8 p h e r i c a l p r o j e c t l o nc u i 【i n ga i g o r i t h m t h ed i s s e r c a t i o ni n d u c e sl h ei m p r o v e dc u i i i n ga i g o r f t h mn a m e d s p h e r i c a lp r o j e c t i o nb yc o n s t r u c t i n gs i n 目ep r o j e c t i o nf a c eb a s e do nb k t e n dp r o j e c t i o nt or e d u c e t h ea l g o r i t h mc o m p l e x f i r s tl h et h e s i sv a l i d a 把st h ep o i n t _ b a s e dp o l ec o o r d i n a i ep r o j e c t i o ni n2 d a n dt h e ne ) ( t e n d s ti n t or e 百o ns a m p l i n 哥b a s e ds p h e r i c a lp r o j e c t i o nt h a tc o n s t m c l ss i n g l e p r o j e c t i o nf 乱e t oe s t i m a t et h eo c c l u s i o ni no r d e rt of e d u c et h ea l g o r i t h mc o m p l e xi n2 5 d t h e s p h e r i c a ip r o j e c t i o na ! g o r j t h ms a m p l et h ev i e wr e g i o nj n t ov i e wp o i n ts e t 。a n dt h e ne m e 唱et h e v i s u a lo b j e c to b t a j n e db yc o m p u t i n gt h cd c c l u s i o nf m mt h el o n g i t u d ea 1 1 dt 1 1 el a l i t u d e sp r o j e c l i o n f o i f e a c hv i e wp o i n ti n l op v so f t h ev i e w 心g i o nt h ea 蟾o f i t h mm a k e su s eo f t h es p a c ec o h e r e n c e j 北京工业大学工学硕士学位论文 t og e t l a r g e ro c c l u s i o nm s i o nf 犯e d u r i n gm eo b j e c tb e i n gp r o j e c t e di no r d e rt oi m p r o v et h e o c c l u s i o nc u l l i n gr a t e e x p e r i m e m ss h o wm a tt h ea l g o r i t h m si nt h j st h e s i sc a l lr e a l i z eo c c l u s i o nc u l l i n go ro b j e c t s ， d e c r e a s et h ec o m p l e x i t yo f s c e n ea n di n c r e a s et h er e n d e r i n gs p e e d k e y w o r d s s i b i n t y ：o c c i u s i o nc u l l i n g ；s e e ds e l e c t i n g ；p o l a rc o o f d i n a t e sp r o j e c t i o n ； s p h e r i c a lp r o j e c t i o n - i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 躲王永尔日期 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名 五永者、导 1 1 研究背景 第l 章绪论 随着计算机图形学与虚拟现实技术的不断发展，在交互计算机图形学、 c a d c a m 等领域中所要处理的场景数据越来越庞大，使得可见性判断成为实时绘 制的关键技术。可见性判断的主要目的是对于给定的场景和观察视点，通过对视 点的约束和物体之间的遮挡关系进行快速判断，扔弃大量不需要绘制的图形对 象，降低场景的复杂程度，增加整个场景的真实感，最终实现实时绘制与网络传 输。 在上世纪7 0 年代，隐藏面消除算法( h s r ) 就用来剔除多边形中不可见的部 分【”。从隐藏面消除的这个角度，这个问题已经得到了基本解决。但是，随着三 维场景的规模与复杂度的增加，试图用传统的方法对场景进行实时操纵或者漫游 变得非常困难。比如，著名的大卫雕像有3 g b 的数据量，在绘制的时候计算量是 非常大，即使目前最好的图形硬件也很难满足要求。还有在城市漫游的应用中， 具有大量的建筑物群落，要实时漫游而且具有一定的真实感其数据量也是惊人 的。除网格简化等方法之外，可见性判断是一种行之有效的方法j ，因为在大规 模复杂场景中，虽然需要绘制的对象数量大幅度增加了，但是对观察者来说却未 必增加很多，往往可见实体的数目要远远小于输入实体的总和。例如，在遮挡稠 密的虚拟城市场景中，在当前视点我们只能看到城市非常小的角落。又如在一幢 建筑物内，由于墙壁及其他建筑结构的局限，当视点处于屋内或在建筑角落内时， 我们只看到一间屋子内的场景或附近的物体，在这些情况下，采用可见性剔除算 法可以在很大程度上加速绘制过程。 1 2 研究意义 可见性判断并不仅仅是一个简单的遮挡关系判断问题。由于场景规模的增大 产生了计算复杂度与稳定性问题，不仅需要考虑交互的实时性，而且还要考虑画 面的质量与稳定性，因此很多因素影响可见性判断所需要采取的策略。例如，视 面的质量与稳定性，因此很多因素影响可见性判断所需要采取的策略。例如，视 北京工业大学_ 学硕 j 学位论文 点的微小变化可能会引起可见物体的巨大变化。如果在场景中有运动的物体，那 么物体间的遮挡关系是时刻变化的，导致判断可见物体的复杂度也增大等等。所 以，可见性判断的重要性随着我们处理的数据的复杂度增大而增大。 同时，可见性技术和阴影生成、机器人技术等其他技术也有很大的相关性。 可见性剔除算法的目的就是要减少送到绘制管线的图元数量从而提高绘制速度。 这些算法通过判断场景中物体在空间中的相互位置关系剔除不可见物体。还有一 些算法在绘制过程中利用帧与帧之间的时间相关性减少重复绘制。由于我们的项 目大型场馆人员应急疏散计算机模拟研究及在奥运场馆中的应用是实时交互 绘制系统，同时在绘制场景中有主要的大型建筑物和其他附属建筑，数据量比较 庞大。如果我们不利用加速技术那么系统的绘制速度会非常低，达不到要求。所 以要利用可见性剔除技术等来减少绘制数据量，实现帧率比较高的绘制。 1 3 实时绘制技术概述 传统的真实感图形绘制算法追求的是图形的真实感和高质量，而对每一帧画 面的绘制速度并没有严格的限制。而虚拟现实、网络多媒体系统要求的实时绘制 技术本质上是一种限时计算技术，即要求算法必须在给定的时间内，完成对场景 的绘制，同时尽可能的保持场景的真实感【2 j 。 目前提高场景实时绘制能力的方法主要有两种，一种是基于硬件的方法，通 过采用具有更高处理速度计算机硬件的图形芯片来实现实时绘制【3 l 4 1 。另一种是 基于软件的方法，从图形的绘制算法入手，降低场景的复杂度，从而达到实时绘 制的目的。二者相比，图形硬件加速器的发展是更为本质的解决之道，事实上， 随着计算机硬件技术的长足进步，目前主流图形硬件的多边形处理能力已经达到 每秒钟百万量级甚至千万量级。然而，一方面，由于经济因素和图形芯片设计能 力的限制，妨碍硬件加速的实现：另一方面，随着计算机图形技术的实用化，需 要构造更逼真、更精细的场景，使得场景规模不断扩大，单纯依赖于硬件加速的 快速绘制技术，并不能满足实际应用对绘制速度的要求【5 1 。理论上说，场景的复 杂性是无限的，而任何硬件的单位时间内的处理能力总是有限的1 6 j 。因此有必要 从图形绘制算法入手，提高计算机的实时绘制能力。 目前的实时图形绘制算法主要从三个方面展开p j ： 第1 章绪论 ( 1 ) 细节层次【8 】【9 】【l o 】 细节层次( l e v e lo f d e 诅i l ) 的基本原理是，利用透视投影的特性距离当前 观察视点越远的物体，其在成像平面上的投影面积越小，那么对远处的物体在绘 制阶段可用较少的等效绘制元素来表现它。层次细节算法一般需要利用或借鉴简 化算法的手段将原模型组织成若干层次的具有不同复杂度、不同相似度模型。而 每一个层次通常是和模型距离视点位置的远近和绘制时间开销相联系的，往往越 简单的模型其相似度就越差。该技术在不影响画面视觉效果的条件下，降低了场 景的复杂度，从而提高了绘制效率。 ( 2 ) 基于图像的绘制技术【1 1 】 1 2 i i b r ( m a g eb a s e dr e n d e r i n 曲技术是计算机图形学和计算机视觉的一门交叉 科学，该技术基于一些预置的图像( 或环境映照) 来生成不同视点处的场景画面。 与传统的绘制技术相比，i b r 技术具有易于实现、效率高、漫游速度快、对计算 机的资源要求不高等特点。 ( 3 ) 可见性剔除技术 可见性剔除技术大致上有分为三类算法，一类是精确的可见性判断算法，如 目前广泛使用的消隐算法( h i d d e ns l l r f 如er e m o v a l ，缩写为h s r ) 【1 3 l ，这类算法 需逐个对绘制元素判断是否可见，它无法满足绘制大规模场景的需要。一类是不 可见性或可能可见性判断算法 1 4 】。这类算法虽不能严格地判断出绘制元素是否一 定可见，但可以确定哪些绘制元素一定不可见。利用这类算法，对给定的视点和 视线方向，可以方便地得到场景的可能可见集。从处理时间分配的观点来看，对 于肯定不可见的绘制元素，只分配了较少的处理时间用来做不可见性的判断。更 进一步，如果能够成批地淘汰掉不可见的绘制元素，可使花费于不可见性判断的 处理时间不随场景的规模增长而增长1 5 1 。还有一类是近似可见性判断算法，近似 求出视点的可见物体，在绘制精度要求不太高但又要求较高的绘制速度时，可能 把一些实际可见的物体丢掉【1 5 】。 针对本文应用背景一大规模场景的实时绘制系统开发，本文将从可见性剔除 技术方面展开对实时绘制技术的研究。 1 4 可见性剔除技术 北京工业大学工学硕i j 学位论文 快速确定三维场景中可见物体是实时绘制复杂场景的关键 1 4 j 。不可见面剔 除技术( v i s i b i l i t yc u l l i n g ) 是快速判断物体可见性的主要算法，其目的是通过预 先估计绘制物体的不可见性来快速地剔除那些不可见的物体，得到一个可能可见 集( p o t e n t i a l l y v i s i b l e s e t ，p v s ) ，绘制时只需调用这些信息即可实现场景的快速 绘制。 v 图1 1 可见性剔除技术【4 】 f i g r u e1 一lv i s i b i l 时c u l l i n g 【1 4 】 依据剔除的目的和适用范围，可见性剔除技术可分为：背面剔除( b a c k f a c e c u l l i n g ) 、视锥体剔除( v i e w f m s t u mc u l l i i l g ) 和遮挡剔除( o c c l u s i o nc u l l i n g ) ，如图 1 1 所示。 1 4 1 背面剔除 背面剔除( b a c k f k ec u l l i n 曲的目的是将不透明物体的所有背向多边形剔除 掉。背面剔除主要采用投影法和夹角法两种测试方法【1 6 】。投影法的原理是：对于 朝向一致的多边形，如果它的投影多边形在屏幕空间中是逆时针方向，那么该多 边形就是背向的，应该剔除掉。夹角法的原理是：计算多边形的法线和视线向量 ( 从多边形上任意一点到视点的向量) 的夹角，若夹角大于丌2 ，该多边形就是 背向的。文献旧提出了一种快速简洁的背面剔除算法，来减少表面法向量所占用 的存储空间。该算法用来准确的对物体空间的多边形进行精确的背面剔除，而所 占用的存储空间仅为通用表面法向量的一半。k 嘶a 一1 8 】提出了一种分层背面剔除 算法。基于多边形方向相似性和几何距离将输入模型划分成一个层次结构，视空 间也被划分成与模型几何层次相对应的层次结构。在每一帧图像绘制中将视点的 第1 章绪论 位置和输入模型的几何层次结构相比较，来拒绝大量的背面多边形。同时，该算 法也考虑了用帧间的相关性来加速背面剔除。即使这样这种算法对于大场景来 说，其计算量仍旧是| 凉人的。 1 4 2 视锥体剔除 视锥体是由视点和屏幕( 垂直于视线方向、位于视点前方的一投影矩形，其 中心点在视线上) 所组成的视域四棱锥。视锥体剔除算法剔除视锥体之外的对象。 该算法通常采用边界体层次结构或某一空间数据结构( 诸如k d t r e e 树、o c t r e e 八叉树或b s p 树) 来剔除多边形。通过将视锥体与层次结构进行比较，迅速将场 景中位于视锥体之外的多边形剔除掉。视锥体剔除算法首先建立一边界体树， 然后通过遍历树结构来测试视锥体是否与边界体相交。如果边界体不与视锥体相 交，则停止遍历树结构。因为，边界体的子树也位于视锥体之外。由于所绘制场 景中大部分多边形是静态的，因此，用来实现快速的视锥体剔除算法是通过一空 间数据结构来实现，如八叉树o c t t r e e 结构二叉树b s p 空间分割法【2 0 l 。 f u c h s 2 1 提出了一种视锥体可见性剔除算法，充分考虑了帧问图象的相关性。 它将场景中的对象集划分为三类：位于视锥体之外，位于视锥体之内，与视锥体 边界相交，并且考虑到当视点在场景中改变时，对象的可见性改变缓慢这一事实。 算法基于空间连贯性，提出了一种快速将场景中的对象进行分类的方法。对位于 视锥体之外的对象，依据其距离视点的远近划分为一些子集，并按照对象的可见 概率将其划分为不同的集合。算法通过b s p 树结构来实现。a s s a r s s o n 【2 2 1 提出了 一种新的视锥体剔除算法。它通过视锥体的收缩来判断物体上的点与视锥体的几 何关系，对多边形进行快速剔除。 1 4 3 遮挡剔除 视锥体剔除用来剔除视锥体之外的对象，但是对于视锥体之内的对象并不总 是可见的，一些物体可能被场景中的其它对象遮挡或隐藏起来，因此在场景绘制 前也没有必要输送到渲染管道进行绘制。而遮挡剔除( o c c l u s i o nc u l l i n g ) 即是一种 可用来确定视锥体内哪些场景多边形被其它对象遮挡而不需要绘制的算法。遮挡 剔除不同于其他两种剔除方式，它需要利用全局知识，即需要考虑同一场景中的 北京工业大学工学硕士学位论文 其他绘制元素( 组) 和当前绘制元素组之间的关系。所以，相对于背面剔除和视 锥剔除，在深度复杂的大规模场景中遮挡剔除技术可为提高绘制效率提供更多的 收益州。 针对不同的应用，不同的算法采用不同的技术实现对遮挡物的选择和遮挡关 系的判定。各种遮挡剔除算法的目的都是设法充分利用物体在空间中的位置关 系、帧与帧之间内容的相似性等因素来快速判断场景中存在的遮挡关系。下一章 分别介绍几种典型算法，并对算法的性能、遮挡物的选择和对视点区域的要求等 方面进行比较。 1 5 遮挡剔除算法的研究现状 科研工作者根据待绘制场景本身的建筑特点提出多种剔除算法。对于室内场 景根掘建筑物内部结构的特点提出来的c e l l 一p r o t a l 算法【2 3 】 2 4 】，将每个房问看作一 个单元，而将该房间与其外部的可见连接处看作入口，整个建筑物就可以看作众 多单元通过入口连接起来，当观察者处在一个单元内部的时候，他只能看到该单 元内部以及透过入口的相关物体，不用关心其他场景实体，从而大幅度降低了计 算与绘制负荷。与一般的可见性方法不同，它首先定义一个空的p v s ，然后根据 入口逐步加入一些可见对象，而对于室外场景一般的可见性方法则是从整个场景 中逐步去掉那些不可见的对象计算p v s ，两者是一个相反的过程。 2 0 0 0 年前，对于遮挡剔除的研究主要集中在实时的基于视点计算可见物体。 9 7 年c o o r g 等人提出大遮挡物剔除算法【2 5 】，利用场景中大物体的遮挡区域比较大 的特性实时计算对于视点的不可见物体。2 0 0 0 年f b e r n a r d i n i 等人【3 3 】提出在构 造场景的层次数据结构的基础上，然后用视点相关数据结构结点的多边形替代形 体复杂的物体作为遮挡物。这些基于视点的算法在大场景实时漫游过程中并不能 明显提升绘制速度。遮挡剔除算法逐渐发展为基于视域进行判断，通过计算出 个视点区域的p v s 代替多帧画面的计算来提高绘制速度。w o n k a 等人提出了遮挡 物收缩与视锥扩张算法【2 ”，使用基于点的遮挡算法计算基于区域的可见物体，通 过对场景中的所有遮挡物收缩一个阈值来扩展点可见物体。2 0 0 5 年b i 仰e r 等人i l “ 提出一种快速的基于区域的城市漫游可见性判断方法，城市漫游中主要物体是建 筑物采用线空间层次遮挡判断。另外由于图形硬件也逐渐提供对遮挡判断的支 第l 章绪论 持，主要是通过提高并行程序来提高计算速度。 国内许多科研工作者对遮挡剔除技术也作了相关研究。2 0 0 2 年，浙江大学 c a d & c g 国家重点实验室的华炜等人提出了全局遮挡图6 1 ，组位于空间各个 方向上的可见性临界面进行不可见性判断，凡是位于该临界面后的物体必是不可 见的。2 0 0 2 年中国科学院计算技术研究所c a d 开放实验室的孙红梅、刘慎权提出 一种适合室外复杂地景的快速可见性的剔除算法【2 8 】。它结合b s p 树和z b u 腩r 算法实现动态场景的快速更新，同时有效利用地形高程数据的规则性直接定位可 能可见的地形块集合，提高了可见性判断的速度。2 0 0 3 年哈尔滨工业大学的石振 锋等人对景物密集的复杂场景【2 9 1 ，提出了基于主要遮挡物的动态可见性算法。该 算法通过场景中预先定义的主要遮挡物动态地形成一个遮挡树，位于遮挡树遮挡 区域中的景物将被剔除。同时对主要遮挡物采用简化的遮挡物代理，对盒子类型 的遮挡物提出了一种有效的简化算法。2 0 0 4 年潘志庚等人【3 0 1 提出了一种适用于在 给定视点运动路径情况下，处理三维场景的可见性预处理算法。首先对所有可能 的视线方向所对应的立方体进行细分，然后对分割后的平面沿着运动路径移动所 形成的光束体进行可见性预处理，最后合并这些光束体得到对该运动路径的可能 可见面集合( p v s ) 。但是该算法为了避免视域剔除的复杂性只能在给定视点路 径的情况下进行，缺乏灵活性。 以上所述算法在实际应用中都有许多局限性，对场景有太多的约束条件。例 如要求待处理的场景是地形数据，或者要求在场景中选择主要的遮挡物，或者是 视点运动路径固定等等。因此怎么结合实际场景的数据特点，利用物体的空间位 置关系等因素减小选择种子物体( 主要遮挡物) 对遮挡剔除的影响，降低视域剔 除的复杂性是未来该领域的重点研究内容。 1 6 本文的工作 目前还没有通用的遮挡剔除算法对任意场景进行实时绘制，各种算法都有一 定的局限性。基于视点的遮挡剔除算法在视点移动过程中实时计算可见物体，这 种算法简单、容易实现，但是当场景规模比较大时很难满足交互绘制的要求。在 实时绘制方面基于区域的算法更具有优势，在预处理阶段计算出视点区域的可见 物体供多帧画面使用，而不必实时计算每帧画面。但是这些往往对场景有特殊要 北京t 业大学t 学顿十学位论文 求，例如要求有大的物体、物体不能相交等情况，而且要求选择种子遮挡物体， 种子物体往往又会对遮挡剔除造成影响。 为了满足复杂场景的实时绘制，本文在分析已有遮挡剔除算法的基础上，从 如下两个方面对现有的算法虚拟遮挡物算法和扩展投影算法分别作了适当改进： 1 、传统的虚拟遮挡物算法在选择种子物体时没有考虑物体分布的影响，本 文适当改进了种子物体的选择方法，考虑物体在视点区域周围分布数量对遮挡效 果的影响，在物体较多的区域选择较多的种子物体提高该区域的遮挡效果，提高 整体场景的剔除率。 2 、对于扩展投影算法，采用球形投影面改进传统的六个平面投影面的判断 方法，并结和视点采样对2 5 维场景中的视域用基于视点的剔除方法计算视域的 潜在可见集( p v s ) 。同时球面投影算法可以对视域周围的物体统一处理，不必考 虑物体与视点区域的相对方位，简化了算法的复杂性。 1 7 本文的内容安排与组织结构 本文由四章内容组成，各章内容如下： 第一章是绪论部分，先简单介绍了可见性判断技术的研究背景、研究意义。 总结了遮挡剔除算法的研究现状，引入了本文的重点研究问题和主要研究内容， 最后给出了本文的组织结构。 第二章分析了目前典型的几种遮挡剔除算法。从软件和硬件两个方面介绍遮 挡剔除技术对场景绘制的加速。重点对软件算法中基于视点和基于区域的算法进 行了分析总结。 第三章研究了区域相关的虚拟遮挡物剔除算法。提出了对传统虚拟遮挡物算 法的改进方法，包括种子物体选择、高度方向的遮挡判断两方面。 第四章研究了基于区域采样的球面投影剔除算法。先在二维空间验证基于视 点的极坐标投影算法在遮挡剔除上的有效性，然后扩展到2 5 维空间对视点区域 采样，再通过基于视点的方法计算基于区域的p v s 。通过试验结果验证了本文算 法是有效的。 本文的最后是结论与展望，对本文的主要工作进行了总结，并对今后的工作 进行了展望。 第2 章典型遮挡剔除算法分析 第2 章典型遮挡剔除算法分析 大场景中遮挡剔除技术发展至今各种算法层出不穷并取得了相当的成就。本 章首先介绍了遮挡剔除算法的一些相关概念，并从软件和硬件两个方面介绍遮挡 剔除技术对场景绘制的加速，同时重点对软件算法中基于视点和基于区域的算法 进行了分析总结。 2 1 2 5 维空间中的遮挡 在本节中给出我们在遮挡剔除算法中的一些约定。 2 1 1 视点区域与2 5 维空间 视点为空间中的一个点，绘制时用来作为观察点，进行计算可见的物体。我 们用q 表示，视点不能穿过场景中物体的表面。 如图2 1 所示，视截体用来表示绘制时能够被观察点看到的空间范围，位于 这个空间内的物体能够被绘制。此空间范围为一棱台，其所属的顶点为观察点( 视 点) ，由近截面和远截面组成。视截体由六个平面围成，其中的四个平面与场景 的边界相对应，分别被称为左右底顶视截面。另外两个平面称为近视截面和远视 截面，它们定义了最近和最远距离，对于场景中的物体，只有位于该距离范围内 的物体才能够被摄像机所看到。 图2 1 视截体 f i g l l r e2 1v i e wf h l s t u m 面 北京工业大学工学硕士学位论文 视点区域为视点所能到达的区域，它是一个单连通闭集，且与场景中任一面 片不交【l 引，我们以q 表示，需要说明的是在本文中视点区域和视域不同，视域是 视线或视线集合所看到的范围，如四棱锥视域。如果待处理场景中的物体由一些 凸形平面组成，并且这些面与其在地面上的垂直投影相连，面之间只有可能在其 边界处相交，由这样的物体组成的场景称为2 5 维场景。在2 5 维空间中视点区 域为垂直于地面的棱柱体，其地面垂直投影为一个凸多面体，与二维空间中的视 点区域类似【4 8 1 。视点区域的高度将直接影响可见性采样的结果，高度越高，在该 区域中看到的物体越多。如果高度超过了所有物体的高度，则变成了空中漫游， 遮挡剔除算法也就失去了意义。我们主要研究基于地面漫游的实时绘制技术，故 不妨设视点区域为凸多边形，其高度为h o ( 即人眼睛的高度的最大值，用户可 以根据实际情况调整) ，遮挡物的高度高于h o ，视点区域正上方没有物体。故 在遮挡判断时，我们可以设视线方向为前方或前上方，此时物体的遮挡关系判断 可以根据地面垂直投影和物体高度进行。 21 2 遮挡物与被遮挡物 在可见性算法中用来遮挡其他对象的物体称为遮挡物( o c c l u d c r ) ；被遮挡的 对象称为被遮挡物o c c l u d e e 【5 1 ，如图2 2 所示。为了便于处理，假设我们研究的 物体不存在相互交叉的情况( 目前绝大多数算法均没有考虑这种情况，即物体间 不相互贯穿) 。如果存在相互贯穿的物体，需要对物体进一步分解。 e 震 蒸9 图2 - 2 遮挡物和被遮挡物【5 】 f i g u r e2 2o c c l u d e ra n do c c l u d e e 【5 】 如图2 2 所示，物体a 、b 、c 、e 、f 处在视点的视线区域内，物体d 处在 外部。物体a 、c 对物体b 形成部分遮挡，所以b 可见。a 、b 、c 单个物体对 e 、f 没有完全遮挡，但是a 、b 、c 的整体遮挡效果，对e f 完全遮挡。所以a 、 b 、c 是遮挡物，e 、f 是被遮挡物。 2 2 两类典型的遮挡剔除算法 2 2 1 特点与分类 各种遮挡剔除算法研究的侧重点和出发点都有所不同，实现的方法也不一 样，其共同点都是设法充分利用各种因素来快速判断场景中存在的遮挡关系，避 免对不可见物体的绘制，通过剔除隐藏在物体的物体来减少数据量。这种算法大 部分是保守的，也就是说它寻找可见的和可能可见的物体进行绘制。从观察者的 角度出发，遮挡剔除算法可分为基于点的算法和基于区域的算法；从算法利用的 数据特性出发可分为基于图像空间和基于物体空间的算法；从被观察的物体的结 构出发，可分为针对室内场景( 单元，入口结构) 和一般室外场景的算法。 下面我们从观察者的角度出发分析目前主要的基于视点的遮挡剔除和基于视 点区域的遮挡剔除算法。 图2 3 基丁视点和基丁视点区域的遮挡剔除 1 4 】 f i g u r e2 3f m m p o i ma n df b m r e g i o nv i s b i l i t y 【h 如图2 3 所示，( a ) 表示基于视点的遮挡剔除，( b ) 表示基于视点区域的遮挡剔 除。基于视点的遮挡剔除与基于视点区域的遮挡剔除的主要区别在于，前者只针 对当前视点来判断场景中物体之间的遮挡关系，实时计算出视点的可见物体进行 绘制：后者需要可见性判断结果对于一个视点区域都有效，具有可见性预测能力， 北京- t 业大学工学硕士学位论文 可以提供连续多帧画面的绘制。通常计算出该视点区域的潜在可见物体集合，这 个集合中的物体对区域中任一视点都有效果。这种算法对于大规模的实时漫游以 及网络应用来说比较有效，但是却需要较多的预处理计算，在保存预先计算的可 见物体集也需要大量的存储资源。 2 2 2 基于视点的剔除算法 2 2 2 1 大的凸遮挡物剔除算法 c o o r g 等人 3 l 】旧提出利用大的凸体物体进行有效遮挡判断。这种方法利用 视点相对于大的凸体遮挡物和被遮挡物之间的支撑平面和分割平面的位置关系 来判断遮挡。分割平面是由一个凸多面体的边和另一个凸多面体的顶点形成，并 且这两个凸多面体处在这个平面不同的两侧。而支撑平面也是由一个物体的边和 另一个物体的顶点形成，但这个物体处在平面的同一侧面。算法的基本思想是如 果视点位于两个支撑平面和遮挡物a 形成的区域3 的话，那么物体t 是不可见 的；如果处在区域2 ，物体t 是部分可见；如果视点处在区域1 的话，物体t 则 是完全可见，见图2 4 。 图2 _ 4 大凸遮挡物算法示例川 f i g u r e2 4l a 唱eo c c l u d e rc u l l i n ga 1 9 0 r i t h m 【3 l 】 支撑平面和分割平面是通过遮挡物的边和被遮挡物的包围盒的顶点来形成 的。这样可以避免当被遮挡物体的形体比较复杂的情况下可见性判断复杂的情 况。同时，当视点运动时，算法把大遮挡物和遮挡关系存储下来，以各下一帧可 用利用，提高绘制效率。这种算法对场景中物体形体要求较高，预先要选择一些 大的凸体遮挡物，而且没有充分利用物体之间的遮挡融合。 2 2 2 ，2 方向离散遮挡物算法( 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 s ) 2 0 0 0 年f b e r n a r d i n i 等人【3 3 1 提出在构造场景的层次数据结构的基础上， 然后用视点相关数据结构结点的多边形替代形体复杂的物体作为遮挡物。这样就 形成了轴对称的遮挡物加速可见性测试，见图2 5 。这种方法在判断哪个物体被 多个物体遮挡的时候，也含有遮挡物融合的思想，对物体的表匿是曲面或近似曲 面的情况，效率更高。 图2 5 方向离散遮挡物算法示例 3 3 】 f i g u r e2 5d d oi l i u s t r a t i o n ( 3 钉 在构造场景数据结构时该算法利用d d o 验证算法来确定结点的哪个面可以 作为遮挡物，并把信息保存下来以备绘制过程中可见性查询时用。在绘制过程 中对给定视点和视线方向时，通过自顶向下，从前到后的方式递归遍历场景树对 每个结点判断其可见性。这种方法通过在预处理阶段简化遮挡物来提高绘制过程 中遮挡判断速度。同时预处理时间代价也不太大。但是该算法适用与中等规模的 c a d 模型，对于大型场景其效率比较低。 2 - 2 3 基于视域的剔除算法 上面介绍的是典型的基于视点的可见性剔除算法，这类算法实时计算视点的 可见物体，对于大规模的场景绘制很难满足交互绘制的要求。在实时绘制方面基 于区域的遮挡剔除算法更具有优势，它们预先计算每个视点区域的可能可见集 ( p o t e m i a lv i s i b m t ys e t ，p v s ) ，在漫游时只需绘制p v s 即可。这类算法的大概步 骤如下： 1 把场景分割为若干个区域。 2 计算每个区域的p v s 。 3 在绘制过程中绘制当前视点所在区域的p v s 。 北京t 业大学工学预l 学位论立 那么下面分析几种典型的基于区域的遮挡剔除算法。 2 2 3 1 虚拟遮挡物算法 k o l t 帆等人在2 0 0 0 年提出了2 5 d 场景的虚拟遮挡物算法【3 5 1 。对于给定一 个场景和视区，一个虚拟遮挡物是一个依赖于视点的凸物体。而且从视区的任何 一点看，场景的其他物体均被这个虚拟遮挡物遮挡。引入虚拟遮挡物是应用有效 的遮挡物简化加速对区域的遮挡剔除，计算视区内有效的潜在可见集。首先在预 处理阶段通过物体的实体角来选取种子物体，并在物体对于地面投影的二维空间 上对每个种子物体和它附近的一些遮挡物构建一个虚拟遮挡物代替这些种子物 体。开始只有一个遮挡物，然后逐步加入，执行过程中虚拟遮挡物放在最远的遮 挡物后边，见图2 6 。迭代的每一步保存一个虚拟遮挡物，逐步形成更大的遮挡 物，能更有效的遮挡。在高度遮挡判断中该算法分层调用二维的遮挡剔除算法实 现对2 5 d 场景的遮挡判断。在实时绘制视点区域的p v s 时只有视点进入该区域 时才计算遮挡关系并通过虚拟遮挡物进行判断。 图2 - 6 虚拟遮挡物示例 3 5 】 f i g u r e2 6v i n u a lo c c l u d e r 口如 该算法一个明显的问题实在物体分布不均匀时选择的种子物体不能形成有 效的虚拟遮挡物，明显降低了剔除物体的效率。 2 2 32 遮挡物收缩算法 在计算基于单元的可见性方法时其复杂性通常要比基于点的可见性判断要 高。w o n k a 等人在2 0 0 0 年提出一种称为遮挡物收缩的方法口刀，使用基于点的 遮挡算法来计算基于单元的可见性，通过对场景中的所用遮挡物收缩一个给定的 第2 章典型遮挡剔除算法分析 长度来计算点的可见性。这种方法的思想是基于一个区域的遮挡区域可以通过一 些区域中的离散点的遮挡区域结合而成。 假设可以从一个点出发计算出基于点的可见性，那么可以使用基于点的可见 性算法来计算遮挡物收缩给定长度( e ) 之后的可见性，这是一种对基于单元可 见性的保守近似见图2 7 。在实现过程中可以使用多面体的集合操作在一般三 维物体上计算收缩，如果使用规则的体数据结构来存储遮挡物时，可以得到更简 单的收缩操作。如果要确保基于单元的可见性方法有效，那么视单元必须足够 大，保证它可以用于多帧画面。通过一个较大的收缩长度来收缩物体的话，可能 会产生很少的遮挡甚至没有遮挡。因此w o n k a 等人又提出在视单元内的多个采 样点上使用遮挡收缩。 图2 - 7 遮挡物收缩示例口8 1 f t g u r e2 - 7o c c l u d e rs h r i n k i n g 【2 8 】 算法中收缩半径e 的选择依赖于场景的整体类型，应该保证半径为e 的球体 大小和遮挡物的平均大小相当。随着e 值的变小，需要更多的球体来覆盖视单元 的边界，从而导致可见性计算非常费时。 2 2 33 线空间遮挡判断法 b i t t l l e r v 等人在0 5 年提出了一种基于区域的快速剔除算法i ”j 。这种算法把物 体的遮挡性分解到水平方向和垂直方向进行判断。该方法采用了坐标空间变换的 思想，把物体从笛卡儿坐标系变换到另外一个判断复杂性比较小的线空间进行判 断。主要是水平方向上采用p m c k e r 坐标对线空间进行参数化，从视点单元发出的 视线与遮挡物相交形成b l o c k e rp l o g y o n ，如果a 物体的b l o c k e rp l o g y o n 覆盖b 物 体的b l o c k e rp l o g y o