（计算机应用技术专业论文）基于遮挡裁减的实时绘制技术研究与实现.pdf

摘要 摘要 随着计算机图形学、虚拟现实以及三维交互设计等技术 的不断发展及广泛应 用，三维实时绘制技术逐渐成为计算机图形学的研究热点。虽然图形绘制技术经 过了几十年的发展，取得了长足的进步，但在保持一定真实感的前提下实时绘制 出复杂场景仍然是一个具有挑战性的研究课题。 本文针对大规模复杂场景实时绘制的关键技术开展研究，通过对可见性裁减 技术的分析并结合实际应用需求，选择基于光束体剖分的遮挡裁减技术作为研究 重点，分别探讨了基于点和基于区域的光束体剖分技术。 本文首先介绍了相关的基础知识，给出了基于光束体遮挡的可见性判断方 法，并介绍了基于光束体剖分进行遮挡裁减的原理。然后分别对基于视点和基于 视点区域的光束体剖分算法进行深入探讨，实现了效果明显改善的实时绘制算 法。具体地，在基于视点的光束体剖分算法中，充分利用了物体的空间连贯性， 提高了算法可见性判别效率；在基于区域的光束体剖分算法中，改进了原有的基 于光束体的可能可见集计算方法，将算法扩展为能够处理凸形视点区域，将视点 区域外侧包围盒扩展为整个场景包围盒，对于类似于城市漫游这样的环境采用 2 5 维处理，有效避免了物体与光束体各边界表面进行位置关系测试，减少了算 法计算量。在此基础上，考虑三维空间中物体高度对可见性的影响，引入了高度 遮挡因子将二维遮挡裁减算法扩充到了三维空间。 实验结果表明本文的算法能够实现对物体的遮挡裁减，有效降低场景的复杂 度，明显提高了场景的绘制速度。 关键词：实时绘制：可见性；遮挡裁减：光束体剖分；高度遮挡因子 a b s t i r a c t a b s t r a c t w i t ht h ew i d e s p r e a da p p l i c a t i o n so f c o m p u t e rg r a p h i c s ，v i r t u a lr e a l i t ya n d3 di n t e r a c t i v ed e s i g n ， r e a l - t i m er e n d e r i 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 n t i a lc o t eo f t h ea p p l i c a t i o n sb e c o m e sm o r e e n dm o r ei m p o r t a n ta l t h o u g ht h eg r e a tp r o g r e s s e si nt h ef i e l do fc o m p u t e rg r a p h i c si nl a t e s td e c a d e s ， r e a l - t i m er e n d e r i n go f c o m p l e xs c e n e sr e m a i n so n eo f 血em o s tc h a l l e n g i n gi s s u e si nt h ef i e l d i nt h i st h e s i s ，t h ek e yt e c h n i q u e so f r e a l - t i m er e n d e r i n go f c o m p l e xs c e n e sa r ed i s c u s s e d b a s e do n t h ea n a l y s i so fv i s i b i l i t yt e c h n o l o g ya n dt h ed e m a n d so fa p p l i c a t i o n s ，t h et h e s i sf o c u so no c c l u s i o n c u l l i n gb a s e do nb e a m s p a r t i t i o nt h a tc a l lb ed e p a r t e dt ot w op a r t s ：p o i n t - b a s e db e a m sp a r t i t i o na n d r e g i o n - b a s e db e a m sp a r t i t i o n 1 1 1t h eb e g i n n i n go ft h et h e s i s ，ab r i e fi n t r o d u c t i o no ft h eb a s i ck n o w l e d g er e l a t e dt or e a l - t i m e r e n d e r i n gi sg i v e n ，e s p e c i a l l yt h em e t h o d sa n dt h ep r i n c i p l e sf o ro c c l u s i o nc u l l i n gb a s e do nb e a m s t h e nt h ep a p e rg o e sd e e pi n t ot h ea l g o r i t h m so fb e a m sp a r t i t i o nb a s e do nv i e w p o i n ta n dv i e w p o i n t r e g i o nr e s p e c t i v e l y , a n dd e v e l o p sa ni m p r o v e dr e a l t i m er e n d e r i n ga l g o r i t h mt h a tc a na c c e l e r a t et h e s p e e do fr e n d e r i n go b v i o u s l y i nd e t a i l ，s p a c ec o h e r e n c ei sa p p l i e dt oi m p r o v et h ee f f i c i e n c y o f v i s i b i l i t yc u l l i n gi np o i n t b a s e db e a m sp a r t i t i o na l g o r i t h m ；i nr e g i o n - b a s e db e a m sp a r t i t i o na l g o r i t h m ， t h ec a l c u l a t i o no f p v sb a s e do nb e a m si si m p r o v e d f u r t h e r m o r e ，t h eo r i g i n a la l g o r i t h mi se x t e n d e dt o b ea v a i l a b l ew h e nt h ev i e w p o i n tr e g i o ni sc o n v e x o u t e rb o u n d i n gb o xo fv i e w p o i n tr e g i o ni sa l s o r e p l a c e db yt h eb o u n d i n gb o xo fw h o l es c e n et og e n e r a l i z et h ea l g o r i t h m - b ys i m u l a t i n g3 ds c e n e b e i n gr e n d e r e db y2 5 ds p a c e ，t h ec a l c u l a t i n go fl o c a t i o nr e l a t i o n s h i pb e t w e e nb u i l d i n g si ns c e n ea n d e v e r ys u r f a c eo f b e a m si sd r a m a t i c a l l yd e c r e a s e da n d a sar e s u l t ，t h ec o m p l e x i t yo f t h ea l g o r i t h mi sa l s o d e c r e a s e de f f e c t i v e l y t h ei n f l u e n c eo fh i g ho fb u i l d i n g so ni t sv i s i b i l i t yi sc o n s i d e r e da sw e l li nt h e s y s t e ma n daf a c t o r , h i g ho c c l u s i o nf a c t o r , i si n t r o d u c e dt oe x t e n dt h ea p p l i c a t i o no fo c c l u s i o nc u l l i n g a l g o r i t h mf r o m2 d t o3 d e x p e r i m e n t ss h o wt h a tt h ea l g o r i t h m si n t h i st h e s i sc a nr e a l i z eo c c l u s i o nc u l l i n go fo 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 ：r e a l t i m er e n d e r i n g ；v i s i b i l i t y ；o c c l u s i o nc u l l i n g ；b e a m sp a r t i t i o n ； h i g ho c c l u s i o nf a c t o r 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其它 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：至耋亟日期：2 1 堑6 ：1 2 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：垂垄塑导师签名：丝磋日期：2 选! ! 第1 牵绪论 第1 章绪论 三维实时绘制技术是目前计算机图形学中的重要研究领域，它麓在根据给定 麓粳点和褫线方两，快速翻逻真建生戏三维缓景雏二缎强像。夔麓嶷拨现实、实 时仿真以及三维交互设计等技术的应用，对实时绘制掇出了更高的要求：一方西， 计算机所绘制的物体、场景越来越复杂，如图1 一l 所示是维也纳的一个局部城市 模型，具套7 , 9 2 8 ，5 1 9 个多逑澎l ”，波蠢7 7 7 褪型静努黟数搀包含了数量超过5 0 0 兆的多边形数据f 1 2 1 。如栗以2 0 帧，秒的速度来绘制波膏7 7 7 飞机的话，那么就 需要每秒钟绘制l o o 亿个三角形面片，计算量非常大，即使使用目前最好的图 影疆终遴缀滚满足绘毒速发瓣要求；蠢冀一方瑟，鬟户要求绘割系绫掰生成弱殛 景具有良好的交互性和实时性。这就形成了场景模型的复杂性和绘制的实时陉之 间的矛盾。 图i - 1 局部城市模型【i i f i g u r e l 1ap a r to fac i t ym o d e l i l l ， 实时绘制技本撅述 实时绘制技术与传统的真实感图形绘制算法有联系但更有区别。传统的真实 感图形绘铡算法追求戆是图澎戆寞实感积裹囊量，恧对簿一梭画嚣瓣绘铡速度势 没有严格的限制。而虚拟现实、网络多媒体系统要求的实时绘制技术本质上是一 嚣衷工鼗天掌工学硬尘学证论文 种限时计算技术，即要求算法必须农绘定的时间内，宪成对场景的绘制，同时尽 可能的保持场景的真实感吼 强煎提衰场娥实时绘铡能力的方法主要霄两弛，种是綦于硬件的方法，邋 过采用具有更高处理速度计算机硬件的图形芯片来燕现实时绘制。该技术主要粲 中予用更少豹时闯绘制更多豹多边形 3 1 或增热一些离性毙的混合处理方法【4 。另 种是旗子软件的方法，从图形的绘带0 算法入手，降低场景的复杂度，从而达到 实黠绘剑的强的。二者提比，图形硬件加速器豹发震怒更为本质验解决之道，誉 实上，随着计算机硬件技术的长足谶步，目前主流图形硬件的多边形处理能力融 经达至每秒镑酉万量级甚麓予万量缀。然藤，一方露，由于经济嚣素靼图形芯片 设计能力的限制，妨碍硬件加速的宓现；另方面，随着计算机图形技术的实用 纯，震要搀造更邋奏、更精缨静场祭，健德场景援摸不断扩大，单纯婊赖于硬转 加速的快速绘制技术，并不能满足寅际应用对绘制速度的要求【3 9 l 。理论上说，场 豢熬复杂瞧是无羧弱，瑟经嚣硬謦豹单整瓣闼蠹鹣处理戆力憨是毒羧翳潮。因她 有必要从图形绘制算法入平，提高计算机的实时绘制能力。 嚣囊蓼戆安装嚣澎绘枣l 葵法主要扶三令方嚣震开瑚： ( 1 ) 场景简化技术 7 - 9 萁基零嚣理楚，裂矮透援投影懿特蛙距褰姿嚣鼹察褪点越远豹爨律，藕 在成像平面上的投影面积越小，那么对远处的物体在绘制阶段可用较少的等效绘 翻元素采袭瑗它。蒺次舞繁算法一般嚣要弱掰或餐鍪麓纯算法瓣手段将缀模型缀 织成若于层次的具有不同复杂度、不同相似度模型。而每一个层次通常是和模溅 距离褪煮位置静远近霸绘稍对鬻开镑稻联系弱，往往麓篱荦懿貘鍪冀耨 疆度裁熬 差。该技术在不影响画面视觉效果的条件下，降低了场景的簸杂度，从而提高了 绘锈效率。 ( 2 ) 基于图像的绘制技术( i m a g eb a s e dr e n d e r i n g ，简写为i b r ) b o a l 该菠术基予些预置静霉象( 或茚壤获黧) 来生藏不霞巍煮处静场聚藩覆。怒 传统绘制技术相比，i b r 熙有绘制独立于场景复杂 生，对计算机的资源要求不高 等特点。 ( 3 ) 可见性裁减技术 可觅性裁减技术大致上有分为两类算法，一类是精确的可觅性羚断算法，魏 第1 覃绪论 目前广泛使用的消隐算法( h i d d e ns u r f a c er e m o v a l ，缩写为h s r ) 【1 ”，这类算法 需逐个对绘制元素判断是否可见，它无法满足绘制大规模场景的需要。另一类是 不可见性或可能可见性判断算法i l ”。这类算法虽不能严格地判断出绘制元素是否 一定可见，但可以确定哪些绘制元素一定不可见。利用这类算法，对给定的视点 和视线方向，可以方便地得到场景的可能可见集。从处理时间分配的观点来看， 对于肯定不可见的绘制元素，只分配了较少的处理时间用来做不可见性的判断。 更进一步，如果能够成批地淘汰掉不可见的绘制元素，可使花费于不可见性判断 的处理时间不随场景的规模增长而增长 ”。 针对本文应用背景一大规模场景的实时绘制系统开发，本文将从可见性裁减 技术方面展开对实时绘制技术的研究。 1 2 可见性裁减技术 快速确定三维场景中可见物体是实时绘制复杂场景的关键1 3 】。不可见面裁 减技术( 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 yv i s i b l es e t ，p v s ) ，绘制时只需调用这些信息即可实现场景的快 速绘制。 v c u l l i n g 图1 2 可见性裁减技术1 1 3 】 f i g u r e1 - 2v i s i b i l i t yc u l l i n g 1 3 】 j b 京2 1 2 业大学工簪硕士学位论文 莰摇裁减弱曩魏窝逶弱蕊围，可冕黢蔑藏技本哥分为：蜚瑟裁减( b a c k - f a c e c u l l i n g ) 、视锥体裁减( v i e w f r u s t u mc u l l i n g ) 和遮挡裁减( o c c l u s i o nc u l l i n g ) ，如图 1 以所示。 1 2 1 背面裁减0 3 a c k - f a c ec u l l i n 酚 背面裁减的目的是将不媾明物体的所肖背向多边形裁减掉。背面裁减主要采 溺缎彩法窝夹麓法两释测试方法 搭i 。授彩法的原瑾是：对于赣囊一致静多迭彩， 如果它的投影多边形在屏幕空间中是逆时针方向，那么该多边形就鼹背向的，应 该裁减掉。夹角法的原理是：计算多边形的法线和视线向量( 从多边形上任意一 点潮褫点的向爨) 的夹角，整失角大予x 2 ，该多透形辘是背蠢貔。文献 1 鼋撵凄 了种快速简沽的背面裁减簿法，来减少表面法向量所占用的存储空间。该算法 周来准确的对物体空间的多边形进行精确纳鸳面裁减，褥所占用的存储空闻仅为 逶箱表面法向纛的一半。k u m ”提出了释分层背面裁减算法。基予多透形方向 相似性和几何距离将输入模烈划分成一个层次结构，视空间也被划分成与模型几 何层次相对应的层次结构。谯每一帧图像绘制中将视点麴位置和输入模型的几 掰层次结梅稻魄较，来拒绝大量的背面多边形。游时，该算法也考虑了孀帧瞬的 棚关性来加速背面裁减。 1 2 。2 视锥体裁减( v i e w f r u s t u mc u l l i n g ) 视锥体是幽视点和屏幕( 垂直于视线方向、位于视点前方的一投影矩形，其 中心点在视线上) 掰组成豹魏域疆棱锥。横锥体裁减算滚裁减视锥体之於静对象。 该算法通常采用边界体层次结构或某一窝闻数据结构( 诸如k d t r e e 树、o c t r e e 八叉树或b s p 树) 来裁减多边形。通过将视锥体与层次结构进行比较，迅速将场 豢中位予撬镶然之努魏多边影裁减掉擂】。援锥接载猿冀法营走建立一边赛葵秘， 然后通过遍历树结构来测试视锥体是否与边界体相交。如果边界体不与视锥体福 交，则停止遍历树结构。因为，边界体的子树也位于视锥体之外。幽于所绘制场 爨孛大邦分多迭形是静态戆，瑟瑟，磊亲实现涣速夔视镶镩裁减冀滚燕逶蓬一空 间数据结构来实现，如八叉树o c t t r e e 结构- - y 树b s p 空间分割法f 1 9 。 s l a t e r l 掇出了一种视锥体可见性裁减算法，充分考虑了帧间图象的相关 第l 苹绪论 性。它将场景中的对象集划分为三类：位于视锥体之外，位于视锥体之内，与视 锥体边界相交，并且考虑到当视点在场景中改变时，对象的可见性改变缓慢这一 事实。算法基于空间连贯性，提出了一种快速将场景中的对象进行分类的方法。 对位于视锥体之外的对象，依据其距离视点的远近划分为一些子集，并按照对象 的可见概率将其划分为不同的集合。算法通过一b s p 树结构来实现。a s s a r s s o n 2 1 】 提出了一种新的视锥体裁减算法。它通过视锥体的收缩来判断物体上的点与视锥 体的几何关系，对多边形进行快速裁减。 1 2 3 遮挡裁减( o c c l u s i o nc u l l i n g ) 视锥体裁减用来裁减视锥体之外的对象，但是对于视锥体之内的对象并不总 是可见的，一些物体可能被场景中的其它对象遮挡或隐藏起来，因此在场景绘制 前也没有必要输送到渲染管道进行绘制。而遮挡裁减即是一种可用来确定视锥体 内哪些场景多边形被其它对象遮挡而不需要绘制的算法。遮挡裁减不同于其他两 种裁减方式，它需要利用全局知识，即需要考虑同一场景中的其他绘制元素( 组) 和当前绘制元素组之间的关系。所以，相对于前两者，它更加复杂，但在深度复 杂的场景中它可为提高绘制效率提供更多的收益0 3 】。 针对不同的应用，不同的算法采用不同的技术实现对遮挡物的选择和遮挡关 系的判定。各种遮挡裁减算法的目的都是设法充分利用各种因素来快速判断场景 中存在的遮挡关系。本文以是否采用光束体剖分的方法进行遮挡裁减为标准将算 法分为两类，分别介绍几种典型算法，并对算法的性能、遮挡物的选择和对视点 区域的要求等方面进行比较。 1 2 3 1 非光束体剖分方法 ( 1 ) c e i i a n d p o r t a i 遮挡裁减 a i r e y 3 2 , 3 3 1 币 ：lt e l l e r 3 4 1 提出了基于视点区域的c e l l a n d - p o r t a l 可见性评估技 术。该裁减技术可有效的对建筑物的室内场景进行快速渲染，即将场景组织成由 一系列的房间( c e l l ) 和将房间相连的门、窗( p o r t a l s ) 构成的相邻关系图 ( a d j a c e n c yg r a p h ) 。当视点位于一个房间内时，要观察到其他房间的任何物体 就只能通过该房间的门和窗。则每一个房间自然地成为一个计算可能可见集的视 点区域。a i r e y 通过单元图( 如图i - 3 中间图所示，场景的俯视图) 构造了一b s p j b 京工业大学工掌醐士学位论文 榜 一耱场暴锯俸组织方式，瞽先教一令乎嚣涛空蠢一分为二，然嚣涛豆 莓莽按 炎别划分到达两个空间中，随后以递归形式反复这个过程。) 。b s p 树的剖分平面 沿蟹单元图的墒体，然后用点采样方法构造b s p 树的p v s ，即通过采样方法在 豢定穗度下近 黻诗篝逶遭p o r t a l 霉能霉麓豹多边形。该算法毂仅逶台萁鬻囱与 坐标轴方向一致的建筑物室内场景。 a d j a c e n c yg r a p h l 灏l o 据邻关系溺释b s p 越搿j f i g u r ei - 3a d j a c e n c yg r a p ha n db s p t r e e p 珂 ( 2 ) 层次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 l z - b u f f e r ) 是一攀孛扩震兹z - b u f f e r 溪隐葵浚。g r e e n e 【3 5 】 利用了两种层次结构：物体窀间的八叉树和图像空间的z - p y r a m i d 。利用场景空 间的相关性来判断每一八叉树结点的可见性。为提高可见性判断效率，还利用了 鬣像空闻静籀关经，瑷z - p y r a m i d 懿形式袭示，群将群纂象素翡毒舞点按葵深度 值组织成四叉树结构，后缀的分辨率是上一级的四分之一，其中每象素所存 储的值为该象豢所对应屏幕窝间可见结点的最大值。这榉，利用层次算法就可实 蕊荣耪a 叉秘绥赢帮当前羼臻象素可觅点集静抉速区域重叠嚣试窝深疫院较，簌 丽快速地判定结点和面片的w 见性。此外，层次z b u f f e r 算法利用了时间上的相 荚性加速可见性计算。虽然屡次z - b u f f e r 算法能高效的裁减不可见实体，当前的 阗形系统在硬佟上并不支掺z - p y r a m i d ，妥粥软件来模羧需要资源演耗相对较高， 逐无法做到实时绘制。 ( 3 ) 层次遮挡图 层次z - b u f f e r 算法中，溺屏幕上存在校少像素尚米被景物覆盖，程序不能。陡 德终止，尽管遮些像素的填充对最终画谳的影响极小z h a n g 3 6 1 注意到了这一缺 黧，提出了层次遮挡图( h i e r a r c h i c a lo c d u d i n gm a p ) 绪秘来解决这些阖题。投 + 6 - 辨 、翟 删甲人 l l ： 弟t 帮绪论 j i i i i i i i i i i i i ii 懋i 苎! ! ! ! ! 曼嬲燃曼! ! 曼! ! 嬲嬲 影区域被设爨麓不透骥，煲簦不透硬度定义为其中不逶鹾嚣域瑟积与整个方形区域 筒积之比。这样，在绘制道程中，算法不断更新与层次z b u f i e r 同分辨率的层次 遮挡图。若浆结点的不透明度大于给定的阈值，则说明该结点在屏幕上所对鹰 鼹基蠛象素爨麓本辏潢，无论还剩下多少景甥巍去绘翱，疆痔将绫寒对该嚣域雨 屏幕象素的绘制，剩余来填完的象素可简单地用背景或相奔象素颜色填上即可。 该算法严重依赖于初始遮挡面片的选取。 ( 4 ) 穗髂述整 在论文隰2 3 1 中，如图1 - 4 所示，作蒲提如了利用大的凸遮挡体进行遮挡裁减 的方法a 在预处理过程中，用一个遮挡物对视点所张的立体角来挑选较大的遮捎 携。这嚣静方法并没毒囊逶怒送行遥强髂瓣联合帮考虑多令遴攒俸静莠集对 其它物体的遮挡。c o o r g 2 2 】的方法适用于存在一些较大遮挡物的场景，由于采用 a s p e c t g r a p h 结构，算法复杂度较高( 在三维中复杂度为o ( n 9 ) ，n 为场景物体个 数) ，难良实瑗。蠹子凸体懑挡浚考实蠛涟搭兹兹融合，不适合遮糖锈俸较夺豹 场景 踅j - 4 ：努蘩线帮支撑线【2 2 】 f i g u r e1 - 4s e p a r a t i n ga n ds u p p o r t i n gl i n e s l 2 2 l ( 5 ) 戮影葵珐 物体2 _ n n n n 性可以看成把视点鬻作是点光源，如果物体a 处于物体b 的阴影( 由“点光源”造成的阴影) 中，则物体b 遮挡了物体a ，物体a 是不 可觅豹。h u d s o n 等天豳琵辩了一释健翔黼影锥( 鼹a 两w 融g 融撒) 逡行遮挡裁减麓 方法：给定一个视点，动态地选择一组遮挡物，对于每个遮挡物，用视点与之轮 嫁线建立弱影锥，阴影中黝所有实俸均被裁减。d r e t t a k i $ 积f i u m e 船珂尝试了通过 北京工业大学工学硕士学位论文 计算阴影边界来处理3 d 场景可见性问题，但是由于计算复杂度和稳定性问题很 难应厢子大糕模场景。b 讯n e f l 2 q 掇出了个改进的方法。该方法将s h a d o w f r u s t u m 组织成一摄遮挡撼，类似予h u d s o n 兹方法，逐墨撼撬行遮挡裁城。该方法忧予 h u d s o n 的方法在于在较好的情况下，对于一个场景屡次结点的遮挡性测试 的次数是o ( 1 0 9 ( n ) ) ，因为该方法考虑了遮挡物的融合。 ( 6 ) 基于体可见性的遮挡裁减 s c h a u f l e r 提出了基于体可见性的遮挡裁减。初始时，场景中的物体的表面 首先羧离散，那么被表嚣像围匏空阋则由一系残不遴硬静体素鬃壤充。瓣每一令 视点区域，酋先将相连的体素组织成大的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 ，计算这些强影区域，并涛这些鬻影 区域和原先阴影区域合并，就可以不鼹她扩大被遮挡空间。再根据体素和景物的 关系，判断出哪些景物是落于被遮挡空间的，所有不落于被遮挡空间的景物便构 成了该褫点嚣域掰对应的可麓可觅集。该方法有效静检测和表示被遮挡静空闯嚣 域，罄次提如了遮挡物可以与被遮挡的空白嚣域融合。该算法菲常适合视点区域 边界平行于嫩标轴的场景。 ( 7 ) 蒸手扩展投影戆遮按裁减 d u r a n d 【2 8 】提出了通过扩展綦于视点的投影来计算可能可见集的方法。算法原 理是：先根据一定原剐选择一些物体作为遮捎物，然后将遮挡物和被遮挡物投影 到嚣一平嚣，熟果被遮挡物戆投影嚣宠全被覆盖并鼹位于葵嚣嚣，裂被遮挡甥谗 为隐藏体，如图1 5 所示。但不同于基于视点的投影，这里投影是针对个视点 区域的。作者提出了一个e x t e n d e dp r o j e c t i o n 算子，他首先将凸视点送域变换 藏一个撬煮蠲边影，然嚣选择一个平行予程点疆边形懿投影乎瑟，对予每拿凸熬 遮挡物则通过连接顶点和对应视点区域顶点进行投影。为了保证不丢失可见面， 遮挡物的投影面保守估计。而被遮挡物的投影面需商估计，遮挡物和被遮挡物的 投影称为为扩震投影。扩袋投影靛象素表示称为扩袋深度鬻，多个遮挡锈静投影 乎丽可以融合，对酗体的扩展投影可以计算视区八个顶点处的投影面的交，这个 第1 章绪论 i i i i 虿躅蚕影褒傍鸯簸兹热速( 模蔽缓净嚣) 。投影乎嚣可以重赣投影裂瑟载投影平 瞄，以使前面累积的遮挡圈扩充到新的遮挡图。该簿法对遮挡物的选择很敏感。 图1 - 5 扩展投影【2 8 】 f i g u r e1 - 5e x t e n d e dp r o j e c t i o n 2 s 舀1 - 6 魔羧遮挡物冽 f i g u r e 卜6 v i r t u a lo c c l u d e r s l 2 9 1 ( 8 ) 纛擞遮挡椽( v i r t u a lo e c l u d e r s ) k o l t u n 2 9 提出了一个成拟遮挡物的概念并给出了一个2 5 维的嶷现。给定一 场景和程区，个虚拟遮撼物是个菝教予褪点的凸髂，被试为是从褫区豹任何 点均被完全遮挡，作为给怒褫区的一个旃效遮挡物。弓l 入虚拟遮挡物是应用有效 的区域对区域的消隐技术，计算视区内肖效的潜在可见集。论文提出了一种景物 j b 京工业大学工学硬士学位论文 空闺食成擎个逑整物，褒实辩交互漫游辩只震缀多黪纛羧貔来计算漤在可瑟瑟。 在预簸理阶段需要确定凡个裙幸搴标为萃孛予物体，对每个种予物体，联合鬻运 静一黧遮挡物椽建一个纛撅遮挡貔替代这些遮挡戆，开始只有一个遮拦物然爱逐 步鸯鞋入遮搂物，虚攘遮籀物放在最运瀚遮挡貔嚣覆，蘩蓬i - 6 爨示。迭代豹每一 步傈存一个虚锨遮挡耪，这魏更大的遮挡物能更有散酌遮搀，在实辩绘翻对裰煮 醒域静p v s 黛有在透入该嚣藏葬寸才诗算，罄次结杰遥i 遣蕊熬遮挡耱送行判戮。 该算法菲常适会实辩裁减。 ( 9 ) 收缩遮籀物 w o n k a 在转蠲提出了一种遘避采梯褫点区域边群采徐守施计葬整个褫点嚣域 对遮措裙造成的零彩区域的方法。翔聚一个物体被遮挡，充分条件怒它穗含在掰 裔网格内采样点的遮挡罐内。用离散采样的方法不避充分条件，可能会程采样点 之间的视点丢失一些可觅面。该文采用的方法是对簿个遥挡秘收缩，这样， 个收缩的遮挡物遮住，对应于原始遮挡物在范围肉静槭点在原褫点范围内的褫点 也被遮挡。利掰这个思想，考虑多个采样点，如果物体被视区内每个采样点的收 缩遮挡锥所遮挡，刚它在整个视区内也怒被遗挡的，遮挡融合就可执行。w o n k a 农p 1 中提出了一个辩步的多进稔在线计算方案，称之沟i n s t a n t v i s i b i t i t y 。由一个 可见性计算服务器进行上述的遮挡物本影的计算，并将计算出对应的可能可见集 实时她传送给弱一个负赏绘制的进程。 l 232 基于光束体割分的算法 ( 1 ) 基予光柬体的可能可见集 慕于光束体的可能可见集募法的基本恩想是：将从视点区域发出的所有光线 蠢成个五维光线空间，按定原则分割五缎光线空阃成若干予空间( 也称予光 柬髂) ，分别计葵每个子光慕体鸵p v s ，这些子光荣体p v s 的并蹙便为该视点区 域弱p v s 。不嗣的算法采用不月的分割原则嬲p v s 判别方法，下颓绘出与零文 璎完提关的薅釉算法，通过分恚曙其优缺点并缝合具体的应用环境提出我们的改进 设想。 w a n g t 3 n 撬遗了一秘将五缳浅线警阕是遭应邀分勰残必束抟豹可见牲颈懿理 方法。视患区域恐长方体，记为a ，对予褫感送域a ，确定一个包灏它的较大的 第1 章绪论 妖方钵，髂为壤域乡 铡包懑鑫劳辽荧转，嚣煮扶巍点长方薅a 起终发出豹光线 组成一个5 d 窄间，对这一5 d 空间分魔剖分成许多光束，记为c i ( 浮l 2 ，n ) ， 德一光束起源于视点区域的个子区域，并与视点区域外侧包围撤b 表面的 帮分槎交，对簿一c i 诗舅簇哥裴可是多迭影集合，褥羽p v s i ( 1 0 。嚣) 。熬 果某p v s i 中所包含的多边形数大于给定的闽值，则将对应的光束c 进一步细分， 该过程继续进行直到最终形成的光束所对应的p v s 中包含多边形的个数小于绘 建阙篷，或鬈撬域毽銎鑫袭瑟瑟褪点嚣域豢分裁到鬣缓为盘。蘩黧l 。7 酗瑟示， 通过剖分视点区域包围盒和视点区域，由视点区域发出的全部光线( 即五维光线 空间) 被分成若干光束体( 如图l ，7a ) ，r o 为视点矩形，r l 为包围它的外部矩形， a b 交这爨襄l 上一羧，掰鬟源予萎与a b 稿交黎搬线形残一令光束，它分为 两部分，前半部分由线段a b 、b d 、d c 和c a 组成，后半部分由线段a b 和射 线a f 、b e 组成) ，对每光束体计算像于光束体内的可能可见集( p v s ) 。 a ) _ = = 维空间的光束b ) 三缏空间的光束 图1 7 二绒和三维空间的光康【3 7 】 f i g u r e1 - 7t h eb e a m si n2 da n d3 d 3 7 1 在三维空间中，如图1 7b ) 所有元索为多边形，矩形区域变为长方体，每一 毙采由长方傣释筏城雹圈鑫躲上一个怒澎来定义。需簧疆据多速形与光束逮赛乎 面方程的位鼹关系判断多边形的可见性。 该算法要求视点区域为蠛形( 长方体) ，光束体的计算过于复杂( 如果取视域 外部矩形r l 梵整个缓景兹毽黼金，每个巍寐将只毒蘸警部分，将篱纯计算静复杂 度) 。对于一必特定场景( 如城市漫游) 如果转化为2 5 维处理，将省去繁琐的多j 妲 形与光束边界平短方程的位鬣关系判断，具有更高的效率。 北京m 业大学学硕士学位论文 ( 2 ) 基于视角剖分的可见性算法 和w a n g 的算法类似，潘志陡f 4 铘稳出了基于视角箭分的可见髋算法。该方法 是在绘定视点运动路经蟪提下，楚理三维场景瓣可照性预处理算浃。以视点戈中 心构逑一个立方体包围盒，对包围盒的6 个灏做二维分割，其3 d 示意图如图 l _ 8 所示。褫点与戗围盒袭面上的每一个方格形成一个光柬，光荣在给定视点路 径兹嚣点之溺遴行游动，形成一个必塞体( 魏图1 - 9 掰示) 。善先对疑鸯可能戆 视线方向所对应的立方体进行细分，然后对分割后的平面沿着运动路径移动所形 成的光束体嫩行可见性预处理，最后合并这砦光束体，得到对该逡动路径的可能 莓觅露集台( p v s ) 。这秘方法巷零适合绘定骆径静精琵，瓣变绽莲基较大豹鹾 点区域不太邈合。 塑1 - 8 褪熹与立方钵魏嚣鑫骢毙衷1 4 0 】 f i g u r e1 - 8 t h eb e a m sf o rv i e w p o i n t a n di t so u t e rb o u n d i n gb o x 4 0 】 j 气。 ， 。秘。骆。 |。| 蟾 菸琢 蛰1 - 9 路经巍索薅 4 。3 f i g u r e1 9 t h eb e a m sf o rp a t h d 0 叛上算法逶过党寨落潮薮兹俸懿霹鬼性，最终生成p v s 。毽楚，上述算法在 p v s 嬲计算过程中，视点区域的形状被限制为长方体，或限制在一条路径上，使 得算法的应用范围受到限制。 1 3 论文目的 本文的研究目的是：针对城市这样的复杂场景( 景物间遮挡比较明照，可以 转化为2 5 维处理) 实现实时漫游。 交于瑟嚣绘刳懿场暴烧模较大，将其全部辕入到绘刳警遵将严重影穗显示遴 第1 章绪论 度。实际上，由于景物间遮挡程度比较高，大部分景物由于被遮挡而不可见，因 此，利用遮挡裁减技术降低场景复杂度实现实时绘制即是必要的也是可能的。 为此，本文将对现有基于光束体的可能可见集算法进行如下改进，满足复杂 场景的实时绘制目的： 一将视点区域扩展为凸多边形或凸棱柱体，而不限于为矩形或长方体； 将视点区域外测包围盒扩展到整个场景区域； 一对三维场景采用2 5 维进行模拟，实现可见性计算。 此外，本文将在基于光束体剖分的光束体p v s 计算过程中充分利用空间连 贯性提高裁减效率。 在以上算法中，本文采取两种方法降低场景的复杂度。首先采用基于视点区 域的遮挡裁减技术，计算视点区域q 的可见物体集p v s q ，此时p v s q 仍有可能 比较大；然后在漫游中根据当前视点和视域采用基于视点的裁减技术进一步降低 p v s o 规模，这一步可以看成是视域裁减的进一步应用( 结合了遮挡裁减技术) 。 前者在预处理阶段完成，后者实时实现。 虽然在算法实现过程中，“基于区域的遮挡裁减算法”在预处理过程中先于 “基于点的遮挡裁减算法”出现，但为叙述方便起见，在后文中仍将先介绍基于 点的光束体剖分算法，然后再介绍基于区域的光束体剖分算法。 1 4 本文的内容安排与组织结构 本文分为以下几个部分：第一章主要介绍了实时绘制算法的研究背景、研究 意义，通过介绍相关的遮挡裁减算法引出我们所采用的方法，同时对本文的研究 目的做了说明，给出了我们的解决方案，根据该方案，我们对章节进行了如下划 分，第二章详细介绍遮挡裁减技术和光束体剖分技术基础知识，并对后面算法中 经常使用的一些基础技术进行了说明。第三章和第四章分别讨论了基于点和基于 区域的光束体剖分算法，通过分析相关问题，给出了剖分算法，通过试验结果验 证了本文算法是有效的。最后，总结本文所阐述的内容，并展望了本课题下一步 的工作。 第2 章相关知识 第2 章相关知识 这一章论述了本文工作的基础，首先描述了遮挡裁减的一些相关知识；然后 介绍了基于光束体剖分的一些基础知识，给出了了基于光束体的遮挡判断方法和 光束体剖分原理，最后介绍了后面章节算法中经常使用的基本技术：视域裁减， 视线和物体的相交测试。 2 1 遮挡裁减 在本节中我们介绍遮挡裁减中的一些相关基础知识，并给出我们在算法中的 一些约定。 2 1 1 二维和2 5 维场景空间 在= 维空间中，物体以线段l 。( i = l n ，n 为场景中的景物数) 的形式表示， 线段间除了有可能在端点处相交外没有其他交点，即线段间不存在相互穿透的情 况。 在城市漫游等三维环境中，大部分建筑物与地面相连，可以看成是由其地面 垂直投影垂直拉伸而成的，所以可以将它们看成是2 5 维场景【4 2 j 8 1 。场景中的物 体为一些凸形平面组成，记这些面为f 1 ，f 2 ，f n ，( n 为场景中的景物数) ， 这些面都垂直于地面，面之间只有可能在其边界处相交。设面f l ，f 2 ，f n 的 地面垂直投影分别为l 1 ，l 2 ，l n ( 由于绘图软件的限制，图中一般写成l l ， l 2 ，l n ) ，高度为h 1 ，h 2 ，h 。，为了便于处理，我们假设这些面均为垂 直于地面的矩形。如果不是矩形，可以用其最大矩形包围盒( 当该面作被检测物 体进行测试是否被遮挡时) 和最小矩形包围盒( 当该面作为遮挡物时) 代替。 2 1 2 视点和视点区域 视点为空间中的一个点，我们以q 表示，视点不能穿过场景中物体的表面。 视点区域为视点所能到达的区域，它是一个亏格为零的单连通闭集，且与场 北京工业大学工学硕士学位论文 景中任一面片不交【1 3 】，我们以q 表示，需要说明的是在本文中视点区域和视域不 同，褫域是视线或视线集合( 光荣体，也称光荣) 所看到的范围，如四棱锥视城。 在二维空阕中，援点逛域为涵多边形。2 。5 难空闼中，巍点区域为囊壹于憋 面的棱柱体，其地面垂直投影为一个凸多面体，与= 维空间中的视点区域类似。 视点区域的离度将麓接影响可见性采样的结果，高度越高，在该区域中看到的物 体越多。蟊鬈蠢度越过了掰有糁俸兹嵩发，测变成了空中漫游，遮挡裁减雾法墩 就失去了意义。我们主要研究基于地面漫游的实时绘制技术，故不妨设视域高腹 为h o ( 即人眼睛的高度的最大值，用户可以根据实际情况调整) ，遮挡物的高 度高予 b ，褪点区域歪主方没密耪体，敌在邃挡浏羝嚣，我餐霹鑫设程线方巍 为前方或前上方，此时物体的遮挡关系判断可以根据地面垂直投影和物体高度进 行。 2 1 3 闭塞体和闭塞对象 冀法中用来遮挡其他对象的物体称为闭塞体( o c c l u d e r ) ，即遮挡物；被遮挡 的对象称为闭塞对象o c c l u d e e ，酃被遮挡穆罄麓，细强2 - 1 掰示。为了馁予建瑗， 强设凌 j 硬究豹物终不存在撼亘遮挡的绩况( 譬兹缎大多数算法均没有考虑这糖 情况，即物体间不相互贯穿) 。如果存在相互贯穿的物体，需要对物体进一步分 解。 图2 - 1 遮挡物和被遮挡物【3 9 i f i g u r e2 1o c c l u d e r a n do e c l u d e e 【强 第2 章相关知识 图2 - 2 基于视点的遮挡裁减 1 3 】图2 - 3 基于视点区域的遮挡裁减 1 3 】 f i g u r e2 - 2f r o m 。p o i n tv i s i b i l i t y i l 3 1f i g u r e2 - 3f r o r e r e g i o nv i s i b i l i t y 1 3 】 如图2 - 2 ，2 - 3 所示，基于视点的遮挡裁减与基于视点区域的遮挡裁减的主 要区别在于，前者只针对当前视点来判断场景中物体之间的遮挡关系，后者需要 可见性判断结果对于一个视点区域都有效，具有可见性预测能力，可以提供连续 多帧的绘制，对于实时漫游以及网络应用来说比较有效，但是却需要较多的预处 理计算与存储资源消耗。 2 1 4 2 图像空间的遮挡裁减和景物空间的遮挡裁减 景物空间的遮挡裁减在景物空间( o b j e c ts p a c e ) 中判断遮挡性。图像空间 的遮挡裁减则基于绘制元素光栅化后的离散表示，在图像空间进行可