（计算机软件与理论专业论文）大规模复杂场景的加速绘制方法研究与实现.pdf

摘要 摘要 大规模三维复杂场景的交互式绘制在很多领域都有广泛的应用前景，如三维 数字游戏、地理信息系统、科学计算可视化等。随着用户对图形绘制效果和速度 的要求不断提高，三维场景的规模和复杂度的增长速度远快于图形硬件绘制能力 的提高速度。在图形绘制软件上进行技术优化是加快大规模复杂场景绘制的有效 方法。大规模复杂场景的加速绘制方法是当前图形学中比较重要的研究方向。 室外城市场景是建筑物之间相互遮挡的大规模复杂场景，对于此类高度遮挡 场景，遮挡裁剪是最有效的加速绘制方法。本文研究和实现了基于g p u 遮挡查询 的连续层次化可见性计算方法。根据场景的内在结构特征对场景空间进行合理划 分，构建场景的空间层次结构，以便快速鉴别一组不可见几何体，这是场景可见 性计算的首要前提。在高遮挡场景中漫游时相邻帧之间视野变化范围较小，可以 充分利用可见性的时空连续性来减少层次节点可见性的判断次数，同时利用该特 征解决g p u 遮挡查询所存在的c p u 等待和g p u 空闲问题，实现c p u 与g p u 的 并行计算和负载平衡。实验证明，基于g p u 的连续层次化可见性计算方法可以有 效提高大规模复杂场景的绘制速度。 大规模复杂地形的实时绘制是图形学中的研究热点，是三维图形引擎中既基 础又重要的组成部分。由高度图构建的地形模型中的三角形面片数目巨大，交互 绘制地形模型的全部几何细节超出一般图形硬件的实时绘制能力。本文研究和实 现了大规模复杂地形的多层次化绘制方法，融合了视点相关的多分辨率层次细节 技术和基于地平线遮挡裁剪的层次化可见性计算方法，实现了对大规模复杂地形 的实时加速绘制。研究和改进了基于g e o m i p m a p s 的层次细节算法，对地形进行 合理的块分割，构建地形的空间层次结构，根据视觉重要性原则实时为各地形块 生成分辨率合适的细节模型。地形块层计细节的计算过程是简洁高效的，c p u 耗 费较低，获得的几何模型规模适中，使用三角形条带方式连接网格顶点，可充分 利用图形渲染管线的绘制能力。本文研究和实现了基于地平线遮挡裁剪的层次化 可见性计算方法，离线计算地形的全局层次化地平线遮挡图，在实时绘制时根据 该遮挡图判断层次节点的可见性。实验证明，融合多分辨率层次细节技术和地平 线遮挡裁剪技术的多层次化绘制方法可以实现对大规模复杂地形的实时加速绘 制。 摘要 本文最后对大规模复杂场景加速绘制技术的发展方向进行了一些展望，并提 出了一些在该领域值得进一步研究的方向。 关键词：场景空间层次结构，可见性时空连续性，地形块层次细节，地平线遮挡 裁剪 h a b s t r a c t a b s t r a c t t h e e x i s t i n gv i s i b i l i t yc u l l i n ga l g o r i t h ma n dl e v e lo fd e t a i la l g o r i t h m sa r eb a s e do n c p u r e q u i r e ds p e n d i n gm o r ec p u r e s o u r c e st oc a l c u l a t et h ep o t e n t i a lv i s i b l es e ta n dt h e l e v e lo fd e t a i lm o d e l ，i no r d e rt om a x i m i z et h er e d u c t i o ni nt h en u m b e ro ft r i a n g l ea n d g e tt h et i g h t e s tt r i a n g l es e t t h e i rd e f e c t sa r et h a tt h eo v e r h e a df o rs p e e d i n gu pi sm o r e t h a nt h ea d v a n t a g ef r o mr e d u c t i o no ft h en u m b e ro ft r i a n g l e s n o wh a r d w a r er e n d e r i n g h a sb e c a m et h ei n d u s t r y ss t a n d a r d ，a n di sa b l et op r o c e s sa n dr e n d e ral a r g ea m o u n to f t r i a n g l e sp e rf r a m e w ew i l li n t e g r a t ea n di m p r o v es o m eo ft h ee x i s t i n gs p e e d i n gu p r e n d e r i n ga l g o r i t h m w ew i l lr e d u c ec p uo v e r h e a da n di m p r o v eg p u u t i l i z a t i o nt o b a l a n c et h ec p ua n dg p uo v e r h e a d ，i no r d e rt or e n d e r i n g3 dc o m p l e xs c e n ei n i n t e r a c t i v ea n dr e a l t i m em o d e a no u t d o o ru r b a ns c e n ei st h et y p i c a ll a r g e - s c a l ea n dc o m p l e xs c e n ew h e r et h e r e a r el o t so fb u i l d i n g sa n dt h e s eb u i l d i n g sa r eh i g h l yo c c l u d e df o re a c ho t h e r f o rt h e h i g h l yo c c l u d e ds c e n e ，o c c l u s i o nc u l l i n gi st h em o s te f f e c t i v ew a yt os p e e du pt h e r e n d e r i n g w eh a v er e s e a r c h e da n di m p l e m e n t e dc o h e r e n ta n dh i e r a r c h i c a lv i s i b i l i t y c o m p u t i n gb a s e do ng p uo c c l u s i o nq u e r i e s w ed i v i d et h es c e n es p a c ea n db u i l d h i e r a r c h i c a ls p a c es t r u c t u r ea c c o r dt oi t si n h e r e n ts p a t i a lt o p o l o g y w ee x p l o i ts p a t i a l a n dt e m p o r a lc o h e r e n c eo fv i s i b i l i t yt om i n i m i z et h en u m b e ro fn o d e sf o rv i s i b i l i t yt e s t a n dt or e d u c et h ed e l a y sd u et ot h el a t e n c yo fq u e r yr e s u l t s o u re x p e r i m e n tp r o v e st h a t t h eo c c l u s i o nc u l l i n gm e t h o dc a l le f f e c t i v e l yi m p r o v et h el a r g e - s c a l ea n dc o m p l e xs c e n e r e n d e r i n gs p e e d t h en u m b e ro ft r i a n g l ef a c e si sv e r yl a r g ei nag e o m e t r ym o d e lb u i l to nt e r r a i n h i g hf i e l dm a pa n d i n t e r a c t i v er e n d e r i n gf u l lg e o m e t r yd e t a i l so ft e r r a i nm o d e li sb e y o n d t h er e n d e r i n gc a p a c i t yo fg e n e r a lg r a p h i c sh a r d w a r e w eh a v er e s e a r c h e da n d i m p l e m e n t e dm u l t i h i e r a r c h i e sr e n d e r i n go fl a r g e s c a l ec o m p l e xt e r r a i nw h i c hb l e n d i n g v i e w - d e p e n d e n tm u l t i - r e s o l u t i o n sl e da n dh i e r a r c h i c a lv i s i b i l i t yc o m p u t i n gb a s e do n h o r i z o no c c l u s i o nc u l l i n g w eh a v er e s e a r c h e da n di m p r o v e dt h el e da l g o r i t h mb a s e d o ng e o m i p m a p sw h i c hp a r t i t i o n st h ew h o l et e r r a i ni n t os o m eb l o c k st ob u i l dh i e r a r c h y s t r u c t u r eo ft e r r a i ns p a c ea n dg e n e r a t es u i t a b l er e s o l u t i o ng e o m e t r yd e t a i l sf o re a c h i i i b l o c ka c c o r d i n gt oi t sv i s u a li m p o r t a n c et oe y e s t h el o dc o m p u t i n gi ss i m p l ea n d e 伍c i e n t c o n s u m e sv e r yl i t t l ec p ur e s o u r c e s w ec a l c u l a t eh i e r a r c h i c a lh o r i z o n o c c l u s i o nd i a g r a mo ft h eo v e r a l lt e r r a i ni no f f - l i n et i m ea n du s et h i so c c l u s i o nd i a g r a m t od e t e r m i n et h en o d e o ft e r r a i nh i e r a r c h yi nr e a l - r e n d e r i n gt i m e o u re x p e r i m e n tp r o v e s t h a tt h em u l t i h i e r a r c h i e sr e n d e r i n gm e t h o dc o u l dr e n d e rl a r g e s c a l ec o m p l e xt e r r a i n s c e n ei ni n t e r a c t i v ea n dr e a l t i m em o d e k e yw o r d s ：h i e r a r c h i a ls t r u c t u r eo fs c e n es p a c e ，t e m p o r a la n ds p a t i a lc o h e r e n c eo f v i s i b i l i t y , l o do f t e r r a i nb l o c k ，h o r i z o no c c l u s i o nc u l l i n g i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 摊。一 嗍1 年月7 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：厶氕杞f 言耋了三二夕享毫痴芜 第一章绪论 1 1 研究目的和意义 第一章绪论 大规模三维复杂场景的交互式绘制在很多领域都有广泛的应用前景，如三维 数字游戏、地理信息系统、科学计算可视化等。随着用户对图形绘制效果和速度 的要求不断提高，使得三维场景规模和复杂度的增长速度远快于图形硬件绘制能 力的提高速度，在图形绘制软件上进行技术优化是加快大规模复杂场景绘制的有 效方法。大规模复杂场景的加速绘制方法是当前图形学中比较重要的研究方向。 在典型的三维图形技术应用领域用中，需要实时绘制具有真实感和交互式的 三维虚拟场景。所谓场景的真实感是指计算机图形系统绘制的画面图像应该具有 照片级的效果，这就需要精细的几何模型和高分辨率的纹理去描述场景，需要符 合物理规律的光照计算去模拟自然界的光照，甚至需要模拟一些特殊效果，如水 波、烟雾、气浪、尾烟及爆炸等。所谓场景的可交互性是指图形系统对于用户的 交互性操作应该立即做出反应并绘制相应的场景，当用户的视点改变时，画面的 刷新应该相当光滑，而无闪烁感。场景的真实感和交互性是一对矛盾体，场景的 真实感愈高，规模和复杂度就愈大，需要更多的计算量和绘制时间；为使场景具 有良好的可交互性，就应该减少计算量和绘制时间，提高场景的绘制速度。现有 大规模复杂场景的加速绘制算法都是力图在场景真实感和可交互性上取得一个平 衡，在保证场景可交互的前提下，绘制适度规模和复杂度的场景。 图形硬件技术的发展日新月异，图形处理单元( g p u ) 的发展速度超过摩尔 定律。目前主流图形硬件的多边形处理能力已经达到每秒钟百万量级。但是随着 图形技术应用领域的不断加深和扩大，需要构造更精细更逼真的三维场景，场景 的规模和复杂度不断增加，仅仅依赖于图形硬件加速绘制技术，并不能满足实际 应用对场景绘制速度的要求。理论上说，场景的复杂性和规模是无限的，而任何 硬件的单位时间内的处理能力总是有限的。通过研究场景的内在结构和人类视觉 感知规律，设计和实现大规模复杂场景的加速绘制方法是必要的，也是图形学发 展的必然趋势。 电子科技大学硕士学位论文 1 2 国内外研究现状 在三维图形技术的应用系统中，三维场景交互式绘制一直都是非常重要的基 本组成部分。国内外研究主要集中于三维场景中几何体的真实感绘制以及实时交 互绘制方面。目前大规模复杂场景的加速绘制算法都是力图在场景的真实感和可 交互性上取得平衡，在保证场景可交互的前提下，绘制适度规模和复杂度的几何 对象集合。目前加速绘制技术的研究主要集中于可见性裁剪技术、层次细节技术、 基于图像的绘制技术和基于g p u 的加速绘制技术四个方面。 ( 1 ) 可见性裁剪技术( v i s i b i l i t yc u l l i n g ) ：硬件z b u f f e r 算法是目前最为常用 的可见性裁剪算法，尽管其线性复杂度为o f n ) ( n 为面片数) ，但其可见性裁剪在 图形渲染管线的末端进行，不可见面片已经过光照着色和纹理映像，所以效率不 高。对高度复杂的场景，硬件z b u f f e r 算法难以达到实时简化场景的目标。当前 可见性裁剪技术的常用方法是在几何面片进入图形渲染管线之前，快速保守地判 断并裁剪其中不可见部分，获得适度规模的潜在可见集。实现可见性裁剪基本而 有效的思想是：快速估计场景的潜在可见集；让硬件z b u f f e r 算法对潜在可见集 实现精确的隐藏面消隐。如何在充分利用可见性的时空连续性特征加速判断裁剪 过程、如何实现多个遮挡物的融合，以及如何降低潜在可见集的c p u 计算开销是 当前研究的热点问题。 ( 2 ) 层次细节技术( l e v e lo f d e t a i l ，l o d ) ：可见性裁剪技术对遮挡程度高的 场景比较高效。但当场景中的可见几何体数量巨大时，可见性裁剪算法就无法简化 场的规模和复杂度。层次细节技术就是为简化场景中可见几何体的多边形细节而 提出的一类加速算法。按照视觉重要性原则，距离视点越远的几何体在显示屏幕 上投影面积越小，对视觉感官的贡献越少，因此一个自然的加速绘制方法是对近 处几何体充分绘制详细的几何细节，而对远处的几何体则大幅度地进行简化，绘 制较为粗糙的几何细节，这就是层次细节技术的出发点。层次细节技术的主要难 点在于如何快速构建并选择几何体的多次层次细节模型，以及不同层次细节之间 的自然过渡。 ( 3 ) 基于图像的绘制( i m a g eb a s e dr e n d e r i n g ，i b r ) ：基于图像的绘制技术以 几何体的图像作为基本绘制元素，因此该技术的最大优点是场景的绘制速度独立 于场景的复杂度，而仅仅与图像分辨率有关。图像像素定义在屏幕空间中，且与 视点的位置方向有关，因此景物空间中几何体模型到屏幕空间中像素的映像必须 随着视点参数的变化而动态地完成，映像效率决定了场景的绘制速度。基于图像 2 第一章绪论 的绘制技术主要包括几何表面纹理映射技术、布告板与替代物技术等。 ( 4 ) 基于g p u 的加速绘制：图形处理单元( g r a p h i c sp r o c e s s i n gu n i t ，g p u ) 是图形硬件显卡的核心部件，经历从固定功能管线( f i x e d f u n c t i o np i p e l i n e ) 到可 编程管线( p r o g r a m m a b l ep i p e l i n e ) 的革命性演变。g p u 硬件实现并加速固定功能 管线的几何变换、光照计算、纹理映像等基本功能。可编程着色器是g p u 可编程 部分，包括顶点着色器、几何着色器、像素着色器，给予了程序员更灵活的设计 空间，既可加速场景的绘制速度又可实时构造特殊效果增强场景的真实感，如柔 体动画、即时光线追踪、粒子系统、多角色实例化、过程几何、位移映射等。g p u 的可编程着色器之间的关联度较小，g p u 具有内在强大并行计算能力，现代c p u 基于流处理器的统一渲染架构和c u d a 开发环境的发布，使得g p u 作为c p u 的 一个并行协处理器，用于通用计算( g e n e r a l p u r p o s ep r o g r a m m i n g ) ，如大规模矩 阵运算、物理仿真、大规模排序查找等。 传统的层次细节技术和可见性裁剪技术基本上都是以c p u 为核心，需要耗费 较多c p u 资源去计算获得潜在可见集和层次细节模型，目的是最大化的简化场景 的规模和复杂度。以c p u 为核心的加速绘制方法的缺陷是为了加速绘制而进行额 外计算所带来的开销，甚至超过了由于减少绘制面片数所带来的补偿。在现实系 统中c p u 除了绘制场景外还有很多重要的任务去做，如人工智能计算、物理仿真、 输入输出处理、网络通信等，c p u 有时成为影响场景绘制速度的瓶颈。现在图形 的硬件绘制已经成为工业界的标准，g p u 计算和绘制能力有了显著提高，可以处 理和绘制较大规模的几何面片集合。可以从两个方面利用现有图形硬件的较强绘 制能力： ( 1 ) 改进以c p u 为核心的加速绘制算法，使其更适合现代g p u 特点。例如， 可以使用视点相关的离散层次细节技术来简化场景，离散层次细节技术构建的几 何网格可以进行三角形条带化组织，有利于g p u 一次处理大批量的三角形面片。 虽然离散层次细节技术的简化效果没有连续层次细节技术那么好，而且需要绘制 的三角形面片数有所增加，但降低了c p u 的资源消耗，充分利用了g p u 的绘制 能力，有效提高了场景的绘制效率。 ( 2 ) 利用g p u 的可变编程着色器实现场景的加速绘制算法。例如，可以利用 g p u 的顶点着色器完成不同层次细节间几何渐变过程中的网格顶点插值计算。 3 电子科技大学硕士学位论文 1 3 主要工作与创新 传统的层次细节技术和可见性裁剪技术基本上都是以c p u 为核心，需要耗费 较多c p u 资源去最大化的减少几何模型的三角形面片数，以获得最紧致的三角形 面片集合。现在图形硬件绘制已经成为工业标准，g p u 计算能力已有显著的提高， 可以一次处理适度规模的多边形面片集合。针对当前以高速g p u 为核心的图形处 理框架，本文采取的策略是在g p u 能够处理和绘制多边形的能力范围内，将尽可 能多的几何数据送入图形渲染管线，充分发挥g p u 的性能，降低加速绘制算法对 c p u 的资源开销。本文根据场景空间的内在拓扑结构合理构建场景的空间层次结 构，在此基础上融合和改进现有的加速绘制算法，通过简洁高效的计算获得适度 规模的三角形面片集合送入图形渲染管线，减轻c p u 的负担和增加g p u 的利用 率，实现对大规模复杂场景的交互式和真实感绘制。 本文的主要工作如下： ( 1 ) 研究和实现了基于g p u 的连续层次化可见性计算方法 本文研究和实现了基于g p u 遮挡查询的连续层次化可见性计算方法。根据场 景的内在结构特征对场景空间进行合理划分，构建场景的空间层次结构，以便快 速鉴别一组不可见几何体，这是场景可见性计算的首要前提。在高遮挡场景中漫 游时相邻帧之间视野变化范围较小，可以充分利用可见性的时空连续性来减少层 次节点可见性的判断次数，同时利用该特征解决g p u 遮挡查询所存在的c p u 等 待和g p u 空闲问题，实现c p u 与g p u 的并行计算和负载平衡。实验证明，基于 g p u 的连续层次化可见性计算方法可以有效提高大规模复杂场景的绘制速度。 ( 2 ) 研究和实现了大规模复杂地形的多层次化绘制方法 本文融合了视点相关的多分辨率层次细节技术和基于地平线遮挡裁剪的层次 化可见性计算方法，实现了对大规模复杂地形的实时加速绘制。研究和改进了基 于g c o m i p m a p s 的层次细节算法，对地形进行合理的块分割，构建地形的空间层 次结构，根据视觉重要性原则实时为各地形块生成分辨率合适的细节模型。地形 块层计细节的计算过程是简洁高效的，c p u 耗费较低，获得的几何模型规模适中， 使用三角形条带方式连接网格顶点，可充分利用图形渲染管线的绘制能力。研究 和实现了基于地平线遮挡裁剪的层次化可见性计算方法，离线计算地形的全局层 次化地平线遮挡图，在实时绘制时根据该遮挡图判断层次节点的可见性。实验证 明，融合多分辨率层次细节技术和地平线遮挡裁剪技术的多层次化绘制方法可以 实现对大规模复杂地形的实时加速绘制。 4 第一章绪论 本文的主要创新点如下： ( 1 ) 混合使用视点相关的多分辨率层次细节技术和基于地平线遮挡裁剪的层 次化可见性计算方法实现对大规模复杂地形的实时交互式绘制，减轻c p u 的负担， 发掘现代g p u 较高的渲染能力。 ( 2 ) 在使用g p u 遮挡查询时，充分利用可见性的时空连续性来实现c p u 和 g p u 间的并行计算，达到c p u 与g p u 的负载平衡。 电子科技大学硕士学位论文 第二章大规模复杂场景加速绘制相关技术 2 1 图形硬件的发展 2 1 1g p u 的发展过程 尸芦 i7 ! 垄兰兰 2 0 0 32 0 0 42 0 0 52 0 0 6 囤2 - i g p u 与c p u 的g f i d p s 发展速度对比 g p u 是图形硬件显卡的核心部件，三维模型的绘制都需要经过的g p u 来进 行，g p u 的运算能力每6 个月就提升一倍，其架构每1 8 个月就经历一次改变，其 发展速度超过摩尔定律，甚至超过了c p u 的演变【“，图2 - l 展示了2 0 0 6 前g p u 与c p u 的兆浮点运算能力( 3 f l o p s ( g i g a f l o a t i n g p o i n t o p e n t i o n s ) 的发展速度。 ( 1 ) 几何变换与光照( t a n s f o r m a d o na n dl i 曲t i n g , t l ) ：在1 9 9 9 年以前。 几何变换( 世界变换、视图变换、投影变换) 和光照运算都要由c p u 来完成，n v i d i a 首先将在g p u 中实现了硬件几何变换与光照计算。硬件几何变换与光照计算减轻 了c p u 的负担，可以绘制更多的多边形，产生更加逼真的效果。但此时的g p u 仍然是不可编程的，光照计算必须使用基本的光照模型。 ( 2 ) 可编程着色器( s h a d e r s ) ：可编程着色器技术是从固定功能管线分离出可 编程的部分，给予程序员更多的设计灵活度，从程序员的角度着色器包括顶点着 拗 瑚 啪 m 如 o 第二章大规模复杂场景加速渲染的相关技术 色器( v e r t e xs h a d e r ) 、几何着色器( g e o m e t r ys h a d e r ) 和像素着色器( p i x e ls h a d e r ) 。 2 0 0 1 年的g p u 提供了顶点着色器，允许程序员编写汇编代码进行几何变换和光照 计算，提供更灵活的光照模型。2 0 0 2 年至2 0 0 3 年的g p u 提供了可编程的顶点着 色器和像素着色器，同时出现了几种g p u 编程高级语言，如d i r e c t x 的h l s l 、 n v l d i a 的c g 和o p e n g l 的g l s l 等。这代g p u 使得顶点的几何变换、光照计 算及像素着色操作完全从c p u 转移到g p u 中来执行。2 0 0 4 年至2 0 0 5 年的g p u 增加了大量新的特性，支持d i r e c t x9 的版本3 和s h a d e rm o d e l3 0 ，支持g p g p u 编程，支持在顶点着色器中的存取纹理，极大的方便了g p g p u 编程。2 0 0 6 年 n v l d i a 引入了几何着色器，允许在g p u 中创建新的数据，使得g p u 由只可处理 现有数据的处理器变成了可以快速处理和生成新数据的处理器，能够执行生成几 何模型和增减几何细节的操作。 ( 3 ) 统一渲染架构：2 0 0 6 以后的g p u 硬件支持d i r e c t x1 0 标准和s h a d e rm o d e l 4 0 ，摒弃了传统渲染管线结构，而是采用了全新的流处理器( s t r e a m i n gp o r c e s s o r s ， s p s ) 并联结构，即统一渲染架构。顶点、几何与像素的着色处理都映像为在流处 理器中进行的浮点数计算。在传统渲染架构中，当顶点着色引擎负荷满载时像素 着色引擎可能闲置，或者相反，造成各个着色器引擎间负载不均，降低系统效率。 现代g p u 的分遣控制逻辑可以动态的分配流处理器去执行顶点、几何和像素的着 色操作，开发者可以不用考虑着色器的分配，而是通过相关a p i 由g p u 自动控制。 具有统一渲染架构的g p u 可以更好的支持浮点数的并行计算，n v i d 发布类c 语 言的集成开发框架c u d a 3 】用以支持g p g p u 编程，使得g p u 的强大并行运算能 力用于普通非图形渲染程序。 2 1 2g p u 的结构特点 m e m o r yr e s o u r c e s ( b u f f e r , t e x t u r e ，c o n s t a n tb u f f e r ) 董 。v 譬蝌，m 、s l a g c ，。厂 图2 - 2 现代g p u 的概念性结构，圆角矩形表示的处理阶段是可编程的 7 电子科技大学硕士学位论文 支持d i r e c t x1 0 的可编程渲染管线为实时图形应用系统绘制高真实感的三维 图形而设计。图2 2 是g p u 的概念性结构，展示了图形数据流在可变编程管线各 个处理阶段的流入流出过程，所有处理阶段都可使用a p i 进行配置，圆角矩形表 示的处理阶段是可编程的。图形渲染过程本质上是一个并行任务，g p u 各处理阶 段的独立性高，无论顶点数据还是像素数据都用4 个浮点数表示，非常适合于并 行计算，现代g p u 具有超长的流水线和高性能的并行计算能力。g p u 每个处理阶 段的作用如下： ( 1 ) 输入装备阶段( i n p u t a s s e m b l e rs t a g e ) 负载为整个管线提供几何数据， 如三角形、线和点。 ( 2 ) 顶点着色阶段( v e r t e x s h a d e rs t a g e ) 负责处理顶点数据，典型的操作有 几何变换、光照计算、蒙皮计算等，顶点着色器每次总是输入、处理和输出一个 顶点数据。 ( 3 ) 几何着色阶段( v e r t e x s h a d e rs t a g e ) 改变了以往g p u 只能处理已有数据 而不能生成新数据的能力。在以前的图形系统中，实时动态增减几何体的数据时 就需要c p u 进行计算，而几何着色器可以增删几何体多边形网格的顶点，支持有 限的几何扩张、删减和变形。 ( 4 ) 流输出阶段( s t r e a m o u t p u ts t a g e ) 是为图形数据流在光栅化之前从渲染 管线再次流入显存而设计，使得数据可以流出管线或者送入光栅器。流出的数据 可以作为输入数据再次循环进入管线，或者被c p u 读回。 ( 5 ) 光栅化阶段( r a s t e r i z e rs t a g e ) 负载裁剪视域体内不可见元素，设置三角 形面片，对顶点数据进行插值，将三角形的每个顶点属性转换为每个像素属性， 为像素着色阶段准备绘制资料。 ( 6 ) 像素着色阶段( p i x e l s h a d e rs t a g e ) 接受插值后的顶点数据，对纹理图像 进行采样，最终合成每个像素的颜色值。 ( 7 ) 输出融合阶段( o u t p u t m e r g e rs t a g e ) 综合各个输出值( 像素着色器的值、 深度和模板信息) 、渲染目标的当前内容、深度和模板缓冲，合成最终的渲染结果。 2 2 空间的层次结构 在大规模复杂场景中，几何体模型是场景的基本组成单位，但描述几何体的 数据为多边形网格，这些数据不能体现场景中几何体的空间分布情况。将复杂问 题分而治之是解决复杂问题的有效方法，根据复杂场景空间的内在拓扑结构，对 第二章大规模复杂场景加速渲染的相关技术 场景空间进行分割，构建场景空间的层次结构，是实现和优化各种场景加速绘制 算法的基础。树是表现场景空间层次结构的有效数据结构，对场景分割的一般方 法是树的根节点表示整个场景空间，再按照某个划分原则将整个场景空间划分成 若干子空间，树的子节点分别表示这些子空间，再将这些子空间进行划分，如此 递归反复，直到满足一定的结束条件。本节将讨论常用的空间层次结构、分割方 法和适用的场景类型。 ( 1 ) 二叉树空间分割( b i n a r ys e p a r a t ep a r t i t i o n ，b s p ) 的主要分割方法是使 用几何体多边形面片所在平面将场景空间一分为二，递归分割完成后形成多层次 的凸体单元。使用二叉树空间分割，可以方便的确定视点位于哪一个凸体单元中， 而且与视点在某一划分平面同一侧的几何体将位于另一侧的任何几何体之前，从 而当前视点出发，遍历场景二叉树绘制几何体，可自动消除隐藏面。二叉树空间 分割适用于具有固定遮挡物的室内场景，墙壁是自然的分割平面。 ( 2 ) k d t r e e 主要分割方法是选取垂直于x 、y 、z 轴中某一轴的平面作为分 割平面将场景空间一分为二，构成两个子空间，递归分割这两个子空间，最后形 成多层次的轴向包围盒。k d t r e e 适用几何体密集，几何体间高度遮挡的场景，如 室外城市场景，分割平面的选择需要考虑景物问的相互关性。 ( 3 ) 八叉树( o c t r e e ) 主要分割方法使用平行于x z 面、y z 面和x y 面的平 面将场景空间等分八个子空间，递归分割这些子空间，最后形成多层次的规则立 方体网格。八叉树分割时没有考虑景物间的关系，因此适合使用于视野开阔、景 物间遮挡关系弱的野外场景。 ( 4 ) 四叉树( q u a d t r e e ) 主要分割方法是使用平行于y z 面和x y 面的平面 将场景空间等分成四个子空间，递归分割这些子空间，最后在x z 平面上的形成多 层次的规则正方形网格。四叉树适合适用于基于高度图的大规模复杂地形场景， 高度图地形模型正是建立在规则正方形网格上的。 9 电子科技大学硬士学位论文 2 3 可见性裁剪技术 幽2 - 3 拥有8 。0 0 0 , 0 0 0 个多边形模型的虚拟城市左上角显示典型的开放视点观察 图片中绿色部分为遮挡裁剪去除的几何体所在区域，裁剪率达到9 9 可见性裁剪技术是复杂场景实时绘制的一种重要加速方法。在室外城市场景 中，由于建筑物之间的高度遮挡，位于地面上的视点仅能看到整个场景的很小部 分，如图2 _ 3 。在复杂的室内场景中，位于某房间中视点也只能看到整个场景的很 小部分，而场景的大部分被墙壁遮挡住了。对于这种高度遮挡的大规模复杂场景， 场景可见部分总是占场景总体规模的较少部分。可见性裁剪技术是加速绘制这种 高度遮挡场景的最有效方法，在绘制元素送入图形渲染管线之前，快速保守的判 断并裁剪其中的不可见部分，可有效的降低场景规模和复杂度。 幽2 4 可见性裁剪技术的三种类型：背面裁剪、视景体裁剪、遮挡裁剪 第二章大规模复杂场景加速渲染的相关技术 如图2 4 所示，根据对绘制元素进行可见性判断的依据，可将可见性裁剪算 法分为三类： ( 1 ) 背面裁剪( b a c k f a c ec u l l i n g ) ：如果一个绘制元素的法线方向背离视点 观察方向，则该绘制元素必不可见，将其裁剪。 ( 2 ) 视景体裁剪( v i e w f i u s t u mc u l l i n g ) ：如果一个绘制元素位于视景体的之外， 则该绘制元素必不可见，将其裁剪。 ( 3 ) 遮挡裁剪( o c c l u s i o nc u l l i n g ) ：如果一个绘制元素被其它不透明绘制元 素所遮挡，则该绘制元素必不可见，将其裁剪。 其中，遮挡剔除需要利用场景全局知识，即需要考虑同一场景中的其它绘制元素 和当前绘制元素之间的关系，相对于前两者它更加复杂。但在高度遮挡的复杂场 景中，可以有效的提高场景的渲染效率，本章将着重介绍遮挡剔除算法及其最新 的发展。 2 3 1 基本概念术语 ( 1 ) 潜在可见集( p o t e n t i a l l yv i s i b l es e t ，p v s ) 可见性裁剪算法的目标是快速估计出场景的潜在可见集。所谓潜在可见集包 含了全部可见绘制元素和一些不可见的绘制元素。在判断绘制元素的可见性时， 可见性裁剪算法可能将不可见绘制元素评估为可见，但从不将绘制元素评估为不 可见，这样保证了潜在可见集的保守可见性( c o n s e r v a t i v ev i s i b i l i t y ) ，即包含了全 部可见元素，可以绘制具有真实感的场景。 可以用紧致性来衡量潜在可见集中所包含的不可见绘制元素的多少，即包含 的不可见绘制元素越少，则可能可见集越紧致。当前的可见性裁剪算法研究的焦 点集中在潜在可见集的快速估计方面。实现可见性裁剪基本而有效的思想是：快 速估计场景的潜在可见集；让硬件z b u f f e r 算法对潜在可见集合实现精确的隐藏 面消隐。 ( 2 ) 层次化可见性判断( h i e r a r c h i a lv i s i b i l i t y ) 可见性判断如果只能对单一的绘制元素来进行，则不能有效地提高渲染效率。 将场景组成树形层次结构，可以成组地对绘制元素的进行可见性判断，形成所谓 的层次化可见性【6 】【7 】【8 】。可见性裁剪算法自项向下对层次结构中的节点进行可见性 判断。如果某个节点不可见，则其子节点也不可见，可以直接将其裁剪。如果不 能确定某个节点可见，则需要进一步判断其子节点的可见性，直至最低层次的判 电子科技大学硕士学位论文 断。 ( 3 ) 可见性的时空连续性( t e m p o r a lc o h e r e n c e a n ds p a t i a lc o h e r e n c e ) 可见性的时空连续性【8 】【1 1 】【1 2 1 是指相邻帧之间场景可见部分的变化较小，可以 假定前一帧的可见物体在当前帧也是可见的。可见性裁剪算法可以利用可见性的 时空连续性来加速判断过程。与场景的层次结构相结合，可以在景物空间上利用 可见性的时空连续性，即可以假定上一帧的可见节点在当前帧也是可见的。也可 以在图像空间上利用可见性的时空连续性，即利用前一帧渲染的景物图像对即将 渲染的景物可见性做出判断。 ( 4 ) 遮挡物的融合( o c c l u d e rf u s i o n ) 图2 5 遮挡物的融合 在很多情况下，场景中的物体被遮挡，并不是某一个遮挡物造成的，而往往 是由于多个遮挡物对其遮挡的结果。如图2 5 所示，虽然物体a 和物体b 都无法 单独全部遮挡物体c ，但是两者却共同对物体c 实现了完全遮挡。因此较好的遮 挡裁剪算法应该对所有的遮挡物进行融合，否则需要根据视点的位置和方向对场 景中的物体从前往后进行排序，然后按照从前往后的顺序逐一进行遮挡关系的判 断。 2 3 2 相关算法研究 ( 1 ) 单元与入口技术( c e l la n dp o r t a l ) v e i l e d 5 1 基于建筑c a d 的特点，以建筑模型中不透明遮挡面为划分面，将室 内场景划分为以房间为基本单元( c e l l ) 的二叉树空间层次结构。在此基础上，根 据单元之间共有的入口( p o r t a l ) ，如门、窗等，建立起单元与单元之间的邻接图， 然后通过深度遍历建立单元与单元的可见入口序列( p o r t a ls e q u e n c e s ) ，从而得到 1 2 第二章大规模复杂场景加速渲染的相关技术 单元对单元( c e l l c e l l ) 的潜在可见集、单元对几何对象( c e l l o b j e c t ) 的潜在可 见集。在实时漫游时，通过视景体裁剪，从上述两个潜在可见集中获得视点对单 元( e y e c e l l ) 的潜在可见集，有效地加速了场景可见性的判断。该算法预处理较 为复杂，目前仅局限于轴向对齐的建筑模型漫游。l u e b k e 2 q 对单元与入口技术进 行了改进，无需预先计算单元的潜在可见集，而是深度优先地递归访问场景中入 口，并通过视点和入口构成的裁剪盒( c u l lb o x ) 实现实时遮挡剔除。算法首先确 定当前视点所在的单元，绘制所有属于该单元内的物体，然后找到位于当前视景 体内且属于当前单元的入口，获得和入口相邻的新单元，由视景体和入口构建裁 剪盒，使用裁剪盒裁剪新单元中的景物，递归地执行相似的裁剪过程，可有效的 提高场景的绘制效率。 ( 2 ) 层次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 , h z b ) 传统的硬件z b u f f e r 算法未能有效利用可见性的时空连续性特征。g r e e n e 1 提出层次z b u f f e r 算法，利用了两种层次结构场景空间的八叉树和图像空间的四 叉树来实现。算法将场景物空间组织成八叉树结构，若八叉树节点包围盒的六个 表面关于当前的z 缓存器是不可见的，则那么该节点所表示立方体内任何几何体 都是不可见的，直接将其裁剪，否则需要进一步判断该节点的子节点的可见性， 若该节点为可见叶节点，则该节点的所有几何体可逐一绘制。为提高节点包围盒 关于z 缓存器的可见性判断效率，算法将屏幕像素对应可见点按其深度值组织成 一四叉树结构，以便快速裁剪不可见节点。该结构类似于纹理映像中的m i p m a p 表结构，它是一个分层结构，其中后一级z b u f f e r 的分辨率是前一级z b u f f e r 的 1 4 ，其中每一层z b u f f e r 像素所存储的z 值为该像素在屏幕上所对应的正方块中 各像素所对应可见点的最大z 值。利用层次z b u f f e r 算法就可实现场景八叉树节 点与某一层次z b u f f e r 进行的重迭测试和深度比较，从