（计算机应用技术专业论文）真实感实时阴影绘制及其gpu加速.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 在现实生活中阴影为我们提供了大量的三维空间信息，虚拟场景中阴影不仅能 够增强场景的真实感，同时也能够帮助判断场景中物体的空间相对位置关系。阴影 绘制算法的真实感和实时性之间的矛盾，是计算机图形学和虚拟现实技术目前所要 解决的一个基本难题。在研究国内外众多论文的基础上，本文从真实感和实时性出 发，对经典的阴影绘制算法进行改进，主要研究和创新性体现在以下两个方面： 提出了基于四叉树结构的自适应阴影绘制算法，研究解决传统阴影绘制算法中 的走样问题。以l a l l c 宅w l l i 锄s 的经典阴影映射算法为基础，采用四叉树的层次结 构来自适应细分阴影图消除阴影映射算法的走样问题，运用非一致的分辨率来细分 阴影图，使之满足视点局部需要的纹理分辨率。借鉴传统的阴影绘制算法，研究解 决阴影映射算法的精度走样问题以及算法精度与算法效率之间矛盾，实验表明，该 算法大量的节约了纹理存储空间，同时提高了算法的真实感。 研究了基于四叉树的自适应阴影绘制算法的g p u 加速模型。本文从图形处理 硬件( g p u ) 流处理器的结构特点出发，建立基于四叉树的阴影绘制算法的g p u 加速模型，解决传统阴影映射算法的实时性难题，从而平衡精度与效率间矛盾。 关键词：阴影绘制；实时性；真实感；阴影映射；g p u 加速 硕士学位论文 m a s t e r st h e s i s a b s t r a c t s h a d o wp r o v i d e sal o to ft h r e e - d i m e n s i o n a ls p a c ei n f o r m a t i o ni no u rr e a ll i f e t h e s h a d o wo fv i r t u a ls c e n e sc 觚n o to n l ye n h a n c et h er e a l i s t i c ，b u ta l s oc a nh e l pt o d e t e r m i n et h er e l a t i o n s h i po ft h es p a c er e l a t i v ep o s i t i o no fo b j e c t s t h ec o n t r a d i c t i o n b e t w e e nt h er e a l i s t i ca n dr e a l - t i m eo ft h es h a d o wr e n d e r i n ga l g o r i t h mh a sb e e na f u n d a m e n t a la n dd i f f i c u l tp r o b l e mi nc o m p u t e rg r a p h i c sa n dv i r t u a lr e a l i t yt e c h n o l o g y o nt h eb a s i so fr e s e a r c h i n go nl a r g en u m b e ro f p a p e r s ，t h i sp a p e ri m p r o v e st h ec l a s s i c a l s h a d o wr e n d e r i n ga l g o r i t h mf r o mt h er e a l i s t i ca n dr e a l t i m e ，t h em a j o rw o r k sa n d i n n o v a t i o na l et w oa s p e c t s ： w ep u tf o r w a r da l g o r i t h mo ft h es h a d o wr e n d e r i n gb a s e do nq u a d - t r e ei no r d e rt o s o l v ea l i a s i n gi nt h et r a d i t i o n a ls h a d o wm a p p i n ga l g o r i t h m w ea d o p tar e a s o n a b l e q u a d t r e eh i e r a r c h i c a ls t r u c t u r e ，p a r t i t i o ns h a d o wm a pa c c o r d i n gt o t h ev i e wp o i n t , e m p l o yn o n - u n i f o r mr e s o l u t i o nt e x t u r em a p s ，m e e t i n gt h ev i e wp l a n en e e d so ft h el o c a l t e x t u r er e s o l u t i o n , t h e r e b yo v e r c o m et h ea l i a s i n gt oa c h i e v ea s i g n i f i c a n ti m p r o v e m e n t o v e rr e n d e r i n gr e a l i s t i cs h a d o wo nt h eb a s i so fl a n c ew i l l i a m s c l a s s i c a ls h a d o w m a p p i n ga l g o r i t h m u s i n gt h et r a d i t i o n a ls h a d o wa l g o r i t h mf o rr e f e r e n c e ，s o l v et h e a c c u r a c yo ft h es h a d o wm a p p i n ga l g o r i t h m , a sw e l la s t h ec o n t r a d i c t i o nb e t w e e n p r e c i s i o na n de f f i c i e n c y t h ee 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 ms a v e sal a r g es t o r a g e m e m o r yo ft e x t u r e , m e a n w h i l ei m p r o v i n gt h er e a l i s t i c w ed or e s e a r c ho fg p ua c c e l e r a t i o nm o d e lb a s e do nq u a d - t r e es h a d o wr e n d e r i n g a l g o r i t h m o nt h eb a s i so ft h ep a r a l l e lp r o c e s s i n gc a p a b i l i t ya n ds t r e a mp r o g r a m m i n g m o d e lo ft h eg r a p h i c sp r o c e s s i n gh a r d w a r e ，w ee s t a b l i s hg p ua c c e l e r a t i o nm o d e lb a s e d o nq u a d q r e es h a d o wr e n d e r i n ga l g o r i t h mt os o l v et h er e a l - t i m ep r o b l e m sw h i c ht h e t r a d i t i o n a ls h a d o wm a p p i n ga l g o r i t h mo f t e nm e e t sa n dt ob a l a n c ep r e c i s i o na n d e f f i c i e n c y k e y w o r d s ：s h a d o wr e n d e r i n g ；r e a l - t i m e ；r e a l i s t i c ；q u a d - t r e e ；g p ua c c e l e r a t i o n 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：眵杰林 日期：伽夕年月6 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名：务刍耨抽签名：铷钩 日期：加勺车艿月8 日日期：c ；乡年易月占日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的规 定享受相关权益。回意途塞握变后溢厦i 旦圭生i 旦二生；旦三生筮查! 作者签名秘崭 苫翥葛辩8 日日期：矽9 年6 月拶日 导师 日期 刚多 月目日 硕士学位论文 m a s t e r st h e s i $ 1 1 研究背景及意义 第一章绪论 在我们的生活的周围，三维几何物体的阴影为我们提供了大量的三维空间几何 信息。同样，在虚拟的三维场景中，三维几何物体阴影的作用一方面能够帮助观察 者判断场景中各个物体之间的空间相对位置关系，同时另一方面也能够提高虚拟场 景的真实感。虚拟现实强调的是对人的一种沉浸感受，这种沉浸感受是通过各种虚 拟现实技术手段，从观察者的视觉、听觉、触觉、嗅觉、味觉等方面提供一种与真 实世界中相似的感受。经验告诉我们，对于一个现实生活中的人，外界信息量的绝 大部分都是通过视觉获取的，这充分说明了真实的、实时的三维虚拟场景中的几何 物体的阴影在虚拟现实应用中的重要性。 三维几何对象的阴影是三维场景中的一种重要因素，它能够为三维的场景提供 很多至关重要的空间几何信息，因此，实时地生成真实感强的阴影效果，对于增强 三维虚拟场景对观察者的沉浸感受起着非常重要的作用。 阴影绘制的真实感和实时性之间的矛盾，是计算机图形学和虚拟现实技术目前 所要解决的难题之一。能否在国内外已有的研究工作基础之上，从真实感和实时性 两个方面出发，提高阴影绘制的效果己成为三维图形学和虚拟现实技术研究领域的 一个非常重要和热点的课题。 从阴影绘制的真实感考虑出发，图像的真实感是指三维场景中的几何物体对象 同光源之间相互作用，从而产生的与现实生活中亮度、明暗等的一致性程度，从一 致性的程度我们可以判断真实感是强还是弱。阴影生成绘制算法的真实感绘制集中 反应在一个问题匕锯齿状走样问题的反走样。针对具体问题，阴影的走样问题 是由于对阴影图的采样不够充分而导致的在阴影边界出现锯齿的现象。根据乃奎斯 特( n y q u i s d 理论，阴影图的分辨率( 有些学者也称精度) 不低于是视平面的分辨 率( 或精度) 的两倍才能比较有效地防止锯齿状走样的问题。锯齿状走样问题会随 着阴影图分辨率( 或精度) 的提高而减小，然而当前图形处理硬件( g p u ) 的显存 空间是非常有限的，因此，不加限制的提高阴影图的分辨率的是不现实的，并且代 价是很高的，而且在实时的动态场景的应用中，还会影响到实时的交互性能。因此， 硕士学位论文 m a s t e r st h e s i s 在传统的阴影生成算法理论框架下，阴影图分辨率同十分有限的纹理缓存空间 ( g p u 缓存) 具有不可调和的矛盾，并且高分辨率的阴影图又会使阴影计算的处理 时间急剧的增长，这对阴影绘制算法实时性能的提高十分不利。 从阴影绘制的实时性考虑出发，实时性则指：实时地计算与绘制，帧图像地更 新速率使眼睛观察不到明显闪烁的效果( 传统电影帧图像的更新速率为2 4 帧秒) ， 同时对用户的输入操作能够及时有效地做出反应，并产生相应的响应效果( 即要求 场景与时间的同步) 。在传统的阴影绘制方法中，无论是对象空间算法( 如：阴影 体算法) 还是图像空间算法( 如：阴影映射算法) ，都由c p u 而不是g p u 完成所 有的图形流水线的计算处理操作，极大的约束了算法的性能。近年来，由于可编程 图形硬件( g p u ) 的出现和计算性能的大大增强以及价格的大大下降，使一般的计算 机用户都可以使用以前只能在图形工作站上使用的图形处理器硬件( g p u ) 来进行 相关的计算处理，g p u 流式编程模型，为三维虚拟场景中实时地生成高真实感的阴 影提供了非常广阔的研究空间。 显然，必须寻找新的研究思路和新方法以适应提高阴影绘制算法中真实感、实 时性的迫切需求，包括算法的精度、算法的效率、利用g p u 的加速等，而这些内 容正是目前实时阴影绘制研究领域的热点问题。 本文立足于阴影绘制的两个关键问题，探索妥善解决算法真实感与算法实时性 之问矛盾的新思路，寻求实现真实感实时阴影绘制的新方法，从而有效地提高阴影 绘制算法的性能。 2 硕士学位论文 m a s t e r st h e s i $ 1 2 阴影相关理论 物 图1 1 阴影相关术语示意图 在此，我们首先大致介绍一下有关阴影的一些基本概念，如图1 1 所示。遮挡 物( o c c l u d e r ) 就是三维场景中遮挡光源从而会形成阴影的物体，接收物( r e c e i v e r ) 就是 接收遮挡物产生阴影的几何物体。对于点光源而言，形成的阴影我们称之为硬阴影 或清晰的阴影( h a r ds h a d o w ) ；对于面光源或者体光源而言，形成的阴影我们称之为 软阴影或模糊的阴影( s o f ts h a d o w ) 。软阴影区域由本影( u m b r a ) 和半影( p e n u m b r a ) 两部 分组成，图1 1 清晰的显示了这一点，其中本影是完全处于黑暗中的区域即完全没 有光线照到的区域：半影是被部分光源照亮的区域，一般表现为一个从暗到亮的渐 变过程。 ， 1 2 1 阴影的分类 阴影可以按生成阴影的光源性质可以分为两大类：硬阴影和软阴影。硬阴影如 图1 2 所示【2 】，在计算机图形和虚拟现实领域中经常采用这种阴影渲染方式，因为 它实现方法非常简单，而且在阴影渲染领域有句哲理的名言有总比没有好。软 阴影如图1 3 所示i z 】，根据生活的经验，我们容易知道，现实中的光源几乎都是面 光源或体光源的情形，形成的阴影区域通常有一个由暗到亮的渐变过程，即半影区， 这一部分仅仅由一部分光源照亮，并不是完全的处于无光的状态。硬阴影反映三维 虚拟场景的真实感效果一般比较差，软阴影反映三维虚拟场景的真实感效果一般比 3 较好，更接近于现实生活中的阴影效果，图1 _ 4 【2 1 所示的左右两幅图的比较反映了两 种阴影的效果。 ，一，日 囤1 - 2 硬阴影图1 3 软阴影 12 2 阴影的作用 图l _ 4 硬阴影和软阴影绘制效果比较 阴影在现实生活中给我们提供了许多重要的作用，例如：通过图1 5 口l 所示阴影 的对比观察，我们可以理解物体问的空间位置关系：通过图1 6 阁所示阴影的对比观 察，我们可以容易的得出投射阴影的遮挡物的形状特征：通过圈1 - 7 b l 所示阴影的对 比，我们可以了解接收阴影的接收物的几何特征。 图1 5 4 警客一番髫一 “ 尹歹 阴影作用i 酽霉 岛寒产 图1 6 阴影的作用i i 钐髫 1 3 国内外研究现状分析 图l 一7 阴影作用i i i 在三维虚拟场景中生成与现实中完全一样的阴影是一个非常复杂的过程。如何 生成真实感强的阴影，国内外研究学者已经发表了许多论文【l 耶】。其中的一些算法 能够渲染生成与现实中非常接近的阴影，如；光线跟踪技术n5 r “、辐射度技术1 7 一、 不连续同格化技术唧等方法。这些算法主要是对现实生活中的光照进行模拟计算， 但现实生活中的光照非常复杂，算法模拟的计算量必然相当大，因此，这些算法不 适用于实时性要求严格的三维动态虚拟场景。虽然也出现了一些改进的算法h “， 但是计算量依然很大，从而不能满足实时性的需求。 当前比较常用的实时阴影生成算法有两种；阴影映射 n l ( s h a d o w m a p s ，也成阴 影图算法) 和阴影体【i o l ( s h a d o wv o l u m e s ) 。阴影体算法是一种基于对象空间精确的阴 影生成算法，算法对场景中的物体有特别严格的限制条件，不能处理没有多边形结 构的物体的阴影计算，例如：烟、云、毛发等。同时，由于绘制阴影体需要很高的 填充率( f i l l r a t e ) ，因此该算法不适合于大规模动态场景的实时阴影绘制。阴影殃射 算法是一种基于图像空间采样技术的算法，算法对场景中的物体没有特殊的要求， 并且算法的执行效率与物体的几何复杂度无关。所以，该算法非常适用于大规模场 景的实时阴影绘制嘛1 3 1 4 。 阴影映射算法存在图像空间算法先天的缺点走样【l q ，具体可以分为三种形 5 瓢 鬟赫 项士学住论文 m a s t e r st h e s i s 式的走样，包括投影走样、深度精度走样和透视走样。投影走样跟光线方向与几何 模型表面的法线方向之间的关系有关，当光源和遮挡物的法向方向几乎平行的时 候，这种走样就会发生；深度精度走样是由于深度表( 也成阴影表、阴影图，其中 存储的就是深度值) 而导致的在物体表面的自阴影现象；透视走样是由于屏幕空间 像素和阴影图纹素( t o x e l ) 采样率不匹配引起的。s t a m m i n g e r 等( 2 0 0 2 ) t 1 6 j 提出了透 视阴影图算法，其核心思想是在标准设备空间中生成阴影图，从而极大的改善透视 走样的问题。b r a b e c 等( 2 0 0 2 ) u7 j 指出使用任意的透视变换，并不需要一定使用透视 投影变换矩阵。光源空间透视阴影图算法和梯形阴影图算法【1 9 , 2 0 等类似算法都是 基于这种思想产生的。这些技术改善了部分锯齿状走样，但没有消除所有的走样问 题，并且它们在实际应用中还存在某些情况难以处理【2 l 】。针对这些特殊情况，l l o y d 等( 2 0 0 5 ) 田谴过多个参数代替原来唯一的全局参数，解决了这个问题。基于透视走 样的改进不能彻底解决投影走样问题。 c h a r te 等( 2 0 0 4 ) t ：h 】提出了包括阴影图阴影体相结合的渲染算法，周国民等 ( 2 0 0 7 ) e 1 9 】和m a r t i n , t 等( 2 0 0 4 ) t ：2 0 】提出了梯形结构的阴影映射，s e n , p 等( 2 0 0 3 ) t ：h 2 5 1 提出了轮廓映射，这类算法都在物体轮廓边分析的基础上对阴影的查询应用一个非 线性的变形。f c m a n d o 等( 2 0 0 1 ) t ：2 6 】提出了自适应细分阴影图的算法，在此基础上出 现了一系列的改进，c h o n g 等( 2 0 0 4 ) 【2 7 j 需要一个单独的渲染遍为每个选定的平面。 a r v oj ( 2 0 0 4 ) 【冽在考虑深度的不连贯性、光源到视点的距离等因素的基础上，使用 一个的启发式的细分阴影图，该方法存在不一致阴影分辨率造成的走样问题。 d o n n e l l y 等( 2 0 0 6 ) t 2 9 j 的不一致阴影图算法，支持m i p m a p p i n g 解决缩小走样问题和支 持大区域过滤器，但该算法当需要额外的分辨率时没能解决放大走样的问题。l l o y d 等( 2 0 0 6 ) 【3 0 】结合光源视锥体、视点视锥体和透视的重参数化，对相对误差给出了深 入的分析。 另一类消除阴影图走样的思路是利用图形硬件。a i l at 等( 2 0 0 4 ) 口l j 和g r e g o r ys 等( 2 0 0 5 ) t3 2 】提出在新一代图形硬件条件下，根据当前摄像机视图中阴影坐标的要 求，在确切的位置上光栅化阴影数据的方法，该方法可以实现与光线跟踪一样的清 晰阴影。杨兵等( 2 0 0 5 ，2 0 0 6 ) 【3 3 蚓提出利用g p u 进行阴影算法的加速，然而半影区 的渲染需要迸一步的精确。刘力等( 2 0 0 8 ) f 3 5 】提出利用g p u 加速生成水底阴影的绘 制方法，然而当水底地形变化非常剧烈的时候，阴影会产生较大的像素误差。l o k o v i e 等( 2 0 0 3 ) 1 3 6 1 在p c f ( p e r c e n t a g e c l o s e rf i l t 砷f 3 7 1 的基础上提出了g p u 加速绘制算法， 来模拟现实的软阴影，该算法实时模拟了动态的软阴影，然而本质上这些阴影都是 6 硕士学位论文 m a s t e r st h e s i s 模拟的，并非真实准确的。 综上所述，近年来，国内外学者在克服阴影绘制走样问题和利用图形处理硬件 ( g p u ) 加速阴影绘制上都做了大量工作，并取得了较好的结果。通过对国内外阴 影绘制算法的研究现状分析揭示了反走样问题的解决与实时阴影算法真实感的提 高休戚相关。本论文关注的两个主要内容：真实感实时阴影绘制与图形处理器硬件 ( g p u ) 加速，涉及到真实感阴影绘制算法的研究与g p u 加速模型的研究。 1 4 本文工作及章节安排 1 4 1 论文的主要工作 本文研究内容涉及：图像渲染技术、可编程图形硬件( g p u ) 技术、阴影映射 ( s h a d o wm a p s ) 技术、阴影体( s h a d o wv o l u m e s ) 技术、基于对象空间阴影绘制 技术和基于图像空间的阴影绘制技术。基于四叉树的阴影绘制及其g p u 加速是我 们研究的重点。本文的主要工作体现以下两点： 提出了基于四叉树结构的自适应阴影绘制算法，研究解决传统的阴影映射绘 制算法中的锯齿状走样问题，探索解决算法精度与效率矛盾的新方法。以l a i l c , e w i l l i a m s 的经典阴影映射算法为基础，采用四叉树的层次结构来自适应细分阴影 图，从而消除阴影映射算法的走样问题。根据视点位置，递归的细分阴影图，生成 非一致的分辨率纹理阴影图，使之满足视点需要的局部纹理分辨率。 研究基于四叉树阴影绘制算法的g p u 加速模型。利用图形处理器硬件( g p u ) 的流处理器和并行处理等特性，建立算法的g p u 加速模型，解决传统阴影映射算 法的实时性难题。 1 4 2 论文的章节安排 全篇共分为五个部分，对真实感实时阴影绘制及其g p u 加速的相关技术进行 总结、研究和讨论。具体每章的安排如下： 第一章，介绍关于阴影绘制课题的来源和研究意义。介绍了阴影的概念和作用， 总结阴影绘制的主要方法手段和国内外的研究动态，指出了本论文的主要研究内容 和后面每章的具体安排。 7 硕士学位论文 m a s t e r st h e s i s 第二章，论述了实时阴影绘制算法的相关技术及g p u 加速技术。具体分析了 两种常见的实时阴影绘制算法一阴影体和阴影映射以及g p u 相关技术。 第三章，论述了基于四叉树的阴影绘制算法及其g p u 加速。在经典阴影映射 算法的基础上，提出了四叉树的自适应细分层次结构从而有效解决有限的纹理内存 处理真实感要求高的场景的走样问题；g p u 加速充分利用g p u 的并行处理能力及 流处理器特点以提高算法的实时性。 第四章，实现并分析基于四叉树的阴影绘制算法及其g p u 加速算法；证明该 算法在有效的解决阴影绘制中走样问题的同时大大提高了算法的效率。 第五章，总结本文的研究工作成果，分析本文中提出的基于四叉树的阴影绘制 及其g p u 加速的不足，并对今后的改进方向和将来进一步深入研究的方向进行了 分析和展望。 8 硕士学位论文 m a s t e r st h e s i s 第二章阴影绘制中的相关技术 实时地生成真实感强的阴影效果是一个非常复杂的过程，因此我们不能仅仅依 靠某一种技术来实现这种实时性和真实感都理想的效果，这个复杂的过程需要我们 通过对现实复杂的几何场景的不断观察分析，综合利用各种技术手段来绘制复杂的 现实世界在计算机上的虚拟场景的阴影效果。并且，阴影效果是光照作用产生的结 果，因此，精确地实时地渲染阴影的计算量将会是非常大的，处理计算的时间也会 很长，通常我们需要利用各种技术手段进行加速计算以满足实际情况的需求，如简 化模型技术、可编程图形硬件并行计算技术等等。本章将介绍两种最常见的实时阴 影绘制算法及g p u 加速相关技术。 2 1 可编程图形硬件 2 1 1 可编程图形硬件的发展 计算机用户都习惯于与上一代硬件产品相比较，通常，新一代的计算机硬件产 品不仅运行得更快，而且价格更便宜，更容易被广大计算机用户所接受。 计算机图形处理器( g r a p h i c sp r o c e s s o ru n i t , g p u ) 近二十年以来，一直以十分 惊人的速度快速发展，一方面，使得计算机图形处理器的速度和渲染图形的质量都 得到了极大的提高；另一方面，促使了图形相关应用领域的高速发展。目前普通用 户使用的图形处理器都已经达到了非常高的性能。在此比较n v i d i a 的三款旗舰 g p u ( g e f o r c e 6 8 0 0 g t 、g e f o r c e 7 8 0 0 g t 、g e f o r c e 8 8 0 0 g t ) ，如图2 一l 所示。 g e f o r c i e 6 8 0 0 g t 的显存带宽为3 5 2 g b s 、显存为2 5 6 m b ，g e f 0 r c e 7 8 0 0 g t 的显存 带宽为5 4 4 g b s 、显存为5 1 2 m b ，g e f o r c e 8 8 0 0 g t 的显存带宽为5 7 6 g b s 、显存 为5 1 2 m b 。如表2 1 所示。 表2 - 1n v i d i a 的三款旗舰g p u 对比 显存带宽( g b s )显存 g e f o r e e 6 8 0 0 g t3 5 2 g b s2 5 6 m b g e f o r c e 7 8 0 0 g t5 4 4 g b 内5 1 2 m b g e f o r c e 8 8 0 0 g t5 7 6 g b s5 1 2 m b 9 硕士学位论文 m a s t e r st h e s i s 鼍 o 镏 器 挂 蔼i 8 0 4 10 5 10 5 0 7 1 1 日期 图2 1 三款n v i d i ag p u 能力显存带宽比较 g p u 技术的不断高速发展，一方面促使了计算处理的速度大大的提高，另一方 面产生了许多新颖的图形硬件技术。令广大图形开发者和图形爱好者最为关注的就 是顶点可编程处理和片元可编程处理，从而，使得计算机用户在执行某种计算时， 可以通过程序的方式( 包括顶点着色程序和片元着色程序) 控制图形流水线的执行相 关的计算。因此，这种可编程性，极大的扩展了g p u 的计算处理能力和应用范围。 目前以n v i d i ag e f o r c e8 8 0 0 g t 为代表的通用可编程图形硬件已经具备了以下 功能： 第一、具备了可编程的特性，包括顶点级和片元级的可编程性。 第二、具备了高效的计算能力和高精度绘制的能力。 第三、支持诸如像齐次坐标、法向等4 元向量的数据格式，从而大大的方便了 程序的开发设计。 第四、具备了高显存带宽的纹理传输能力，如n v i d i ag e f o r c e 8 8 0 0 g t 的显存带 宽为5 7 6 g b s ，具有非常大的数据吞吐能力。 第五、具备了高效通信的机制，渲染到纹理( r e n d e r - t o - t e x t u r e ) 的功能有效的避 免了将中间处理的结果复制到纹硼_ ( c o p y - t o - t e x t u r e ) 这个非常耗时的处理过程。 1 0 硕士学位论文 m a s t e r st h e s i s 2 1 2 可编程图形流水线 具有可编程特性的图形流水线的流程图如图2 2 所示h 5 - 4 6 】。图2 2 的左边用实 线表示的是传统的固定功能图形流水线的流程，其具体细节如图2 3 所示。目前光 栅化这一操作还没有被引入可编程的操作特性，其他部分除了光栅化后的顶点的光 照计算、坐标变换等等操作都引入了可编程的操作特性，如图2 2 中的虚线部分， 其具体细节如图2 - 4 所示。 顶点数据【顶点法向颜色值纹理坐标】 ；一： 壹 片段数据 颜色值纹理坐标 图2 2 可编程图形流水线的总体框架 蜜率 一* 女m + + 片r- g 罔2 - 3 固定功能图形处理管线 l 蕊“豢l a 蓼一l 籍以* 测哆j 二型熟 隰一壁母二? 陵辫一厩j 一：豁 j 4 ；8 卜 二：嚣i ；c j 一+ 片元坟l ， 图2 _ 4 利用顶点和片元处理器的可编程管线 从图2 - 2 中实线与虚线的对比咀及图2 - 3 与2 _ 4 的对比可以看出，图形处理器 ( g p u ) 的可编程性有两个部分，分别是顶点处理嚣( v c r t c xp r o c e s s o r 简写v p ) 和片元处理器( f r a g m e n tp r o c e s s o r 简写f p ) 。顶点处理器所操作的对象是顶点值和 与顶点值有关联的一些数据。顶点处理器( v p ) 用来执行顶点变换、法线变换、法 线规格化、纹理坐标生成、纹理坐标变换、光照等传统的操作。片元处理器所操作 的对象一个片元值及与片元值有关联的数据。片元处理器用来执行访问纹理、应用 作 一然t i 猱t，蠢|卜。 l l m 镕 l 翟 h l 。一一 曩莲一 面要茎一 一 一一一 习一一一。一 堙 | | 、r_ * 编 翮竺 襄匿 甏 肼躐黼辫 k 鹜l _ 一帻i i 硕士学位论文 m a s t e r st h e s i s 纹理、雾化、颜色汇总等传统的图形操作。 要利用现代图形处理器硬件( g p u ) 的可编程性，开发人员需要编写在图形处 理器上( 包括顶点处理器和片元处理器) 运行的程序，人们把这种程序称之为着色 程序( s h a d e r ) ，可以分为两种，一种是顶点着色程序( v e r t e xs h a d e r ) ；另种是片 段着色程序( f r a g m e n ts h a d e r ) 。 可编程图形硬件( g p u ) 的广泛应用也促使了着色语言( s h a d e rl a n g u a g e ) 的 开发，当前，比较著名的有o p e n g l 着色语言( g l s l ) 、高级着色语言( h l s l ) 和c g 。 这三种是非常相似的，g l s l ( o p e n g l 着色语言) ，是一种高级着色语言，运 行在o p e n g l 平台上，它是o p e n g l2 0 规范的一部分。微软的h l s l ( h i g h - l e v e l s h a d e rl a n g u a g e ，高级着色语言) ，它是由微软定义的，与g l s l 一样，h l s l 提供 在顶点级别和像素级别上的可编程能力，h l s l 的顶点着色器对应于o p e n g l 的顶 点着色器，h l s l 的像素着色器则对应于o p e n g l 的片元着色器。h l s l 是微软( m s ) 专用的图形应用程序编程接口( a p i ) ，专门为d i r e c t x 而设计的。c g 是由著名显卡 制造商n v i d i a 定义的一种跨平台语言，既支持d i r e c t x 也支持o p e n g l 。 另外，h l s l 规范由微软控制的，c g 规范由n v i d i a 控制的，g l s l 是由o p e n g l a r b ( 由各个图形硬件和计算机制造商的代表共同组成的组织机构) 控制的。h l s l 用于微软的d i r e c t x 环境，g l s l 可用在各种操作系统中并且与o p e n g l 一起使用。 c g 则在d i r e c t x 和o p e n g l 两种环境均可使用。 2 2 实时阴影绘制算法 目前，绘制阴影的方法非常之多，当前流行的实时阴影生成算法有两种：阴影 体算法( s h a d o wv o l u m e s ) 和阴影映射算法( s h a d o wm a p s 或称阴影图算法) 。 2 2 1 阴影映射算法 阴影映射算法也称阴影图算法，首先是由l a n c ew i l l i a m s 在1 9 7 8 年他的论文中 提出来的【1 1 1 。该算法可分为两步，如图2 5 所示，在第一步中，以光源中心作为视 点即从光源所在的位置出发，渲染场景并渲染场景到z 缓存区( 也称深度缓存区即阴 影表或阴影图) 中。因为在这个步骤中不关心颜色缓存区的内容，只关注每个像素点 相对于光源的深度值，因此在这步操作中，我们可以关掉颜色缓冲区和纹理生成， 1 3 硕士学位论文 m a s t e r st h e s i s 只保存z 缓冲区，以加速这个计算过程。在第二步中，从真实视点角度出发，以常 规方式绘制场景，渲染每一个像素点之前要对它做阴影测试。对于每一个绘制的片 元，计算其在光源裁剪空间中的深度值z 。为此，我们首先需要将片元的坐标 ( ，z 咖) 从观察空间转换到光源空间( 锄，蜘，z 呐) ，并比较锄值与 ( 锄，) 位置上的深度值。如果片元的深度值大于阴影图中存储的深度值， 那就说明了点，从光源处看，有更靠近的光源的几何对象遮挡了它，所以这个片 元就位于阴影中。如果锄值等于阴影图中的深度值，那就是说，该片元能够光源 照亮。 光 视点 视点平面 图2 5s h a d o wm a p s 算法示意图 阴影映射算法有以下优点：第一，阴影映射算法( s h a d o wm a p s ) 实现简单， 只是进行了简单的深度值比较操作，因此阴影映射算法很容易被可编程图形硬件 ( g p u ) 实现；第二，该算法是在图像空间计算阴影，因此该算法的效率比较高。 同时，阴影映射算法由于算法本身特性图像空间算法，使其具有一定的局 限性锯齿状走样问题。锯齿状走样问题是一种由于在阴影映射的第一步操作 中，对阴影图的采样不充分而在阴影边界形出现锯齿的现象，如图2 - 6 左图所示。 根据乃奎斯特理论，阴影映射中阴影图的精度即纹理分辨率必须是视平面的两倍才 能防止走样。图2 6 显示了阴影走样问题，两张图显示了使用4 0 9 6 x 4 0 9 6 ， 3 2 7 6 8 x 3 2 7 6 8 不同的精确度阴影映射，可以看出走样问题会随着阴影图精度的提高 1 4 而减小。然而在实际应用中，这个代价是非常高的，尤其是在实时的动态场景中 图形硬件的纹理显存空间是非常有限的。 22 2 阴影体算法 图2 - 6 阴影走样问题 阴影体算法首先由f r a n k l i nc r o w 在1 9 7 7 年他的论文“中提出的【l o l 。阴影体算 法由两个部分组成：第一，在对象空间中构造阴影体具体来说就是从轮廓边缘构成 阴影体；第二，采用在阴影平面计数的方式以确定每个像素的阴影并把阴影体渲染 进模板缓冲区( s t e n c i l b u f f e r ) 中。对三维虚拟场景中的每个光源都重复以上两个步 骤，并把他们产生的结果叠加在一起，渲染成一幅最终的帧图像。阴影体算法的基 本原理，如图2 - 7 所示。 光源 砚亘。 隰。夕 图2 - 7 阴影体算法原理 硕士学位论文 m a s t e r st h e s i s 2 3 本章小结 本章对阴影绘制中的相关技术做了大致介绍，包括对当前主流的两种实时阴影 算法的介绍和g p u 相关介绍，对走样问题进行了详细阐述，这些内容是第三章改 进算法的基础。 1 6 硕士学位论文 m a s t e r st h e s i s 第三章基于四叉树的阴影绘制算法及其g p u 加速 总结国内外学者的研究成果，我们不难看到l a n c ew i l l i a m s 在1 9 7 8 提出来阴影 映射算法以及后来在此算法基础上出现的诸多针对锯齿状走样问题的改进算法，都 是在假设阴影图纹理可以一一对应地映射到场景中的三维几何体的基础上的，也就 是说，阴影图的纹理分辨率与场景中的三维几何体所需的纹理分辨率完全匹配，这 种假设意味着场景是均匀的而且基于纹理分辨率。然而，基于纹理分辨率的场景不 适合于空间频率可变的光源情形。通常情况下，我们希望在光变化快的区域中能够 渲染更多的像素点，如本文讨论的阴影边界就是典型的这种情况：在光变化慢的区 域希望能够渲染较少的像素。针对本文研究的重点阴影绘制的真实感和实时性 的研究，在总结前人研究成果的基础上，我们采用一种四叉树( q u a d - t r e e ) 的层次 结构，自适应地细分场景几何体阴影图，从而达到在阴影边界区域渲染更多的像素， 而在阴影之外的其他区域渲染较少的像素的目的。 3 1 基于四叉树的阴影绘制算法 3 1 1 四叉树相关理论 四叉树是一棵有根的树，其中每个节点要么有四个孩子，要么没有孩子，我们 称有孩子节点的节点为内部节点，没有孩子的节点称为叶子节点。在四叉树结构中， 每个节点对应于一个正方形区域。如果一个节点，有孩子，那么四个孩子就一一对 应于 ，所对应正方形区域的四个象限。换句话说，四个孩子节点对应的正方形区域 合在一起，就构成了对父节点所对应正方形区域的一个子区域细分，称之为四叉树 细分( q u a d - t r e es u b d i v i s i o n ) 。如图3 1 所示，我们给出了一棵四叉树及其对应的子区 域细分。根节点的四个孩子一一对应于四个象限，分别被记为n e 、n w 、s w 和s e ， 其中n e 表示东北象限，n w 表示西北象限，s w 表示西南象限，s e 表示东南象限。 1 7 n e s e 图3 1 四叉树及其对应的子区域细分 我们可以利用四叉树结构存储不同类型的数据。为了更好的理解四叉树的存储 结构及其相关理论，我们从利用四叉树结构细分平面上的一组点的实例来展开介 绍。对于利用四叉树的数据结构来细分一组点，只要某个正方形区域中包含的点多 于一个，就要不断地对其进行细分。因此对于一个正方形区域元中给定的一组点， 我们可以定义一棵四叉树如下。设允= 【屯，屯i x 耽，耽。】。 如果c o u n t ( p ) _ _ 1 ，那么分别设、如、如、如为旯的四个象限。 令= + x a ) 2 ，= ( 以+ 儿) 2 ，在此假设上定义下面四个集合： = p 尸i 见 矗埘，毋 ) ， = p p i 见，乃 虼讨 ， 岛= p p i 见王，。h ，, y y 划 ， = p p l 见 ，乃s ) 1 8 硕士学位论文 m a s t e r st h e s i s 入懈 2 i l n e l j 砧形一 九s e 了m d k 矗 图3 2 四叉树中某个内部节点及其细分后的四个孩子节点 如图3 2 所示，这棵四叉树的根节点1 ，中存放了五。在此，将存放于1 ，处的正方 形区域记作力( ，) ，四叉树中的每个节点，都对应着其相应的正方形五( v ) ，此外， 如果，有孩子，则有四个孩子，且分别为： n e 象限对应的孩子就是落在正方形区域中所有的点构成的一个集合 对应的一个比原来四叉树对应的正方形区域更小的正方形区域；n w 象限对应 的孩子就是落在正方形区域中所有的点构成的一个集合对应的一个比 原来四叉树对应的正方形区域更小的正方形区域：s w 象限对应的孩子就是落 在正方形区域岛中所有的点构成的一个集合对应的个比原来四叉树对应的 正方形区域更小的正方形区域；n e 象限对应的孩子就是落在正方形区域k 中 所有的点构成的一个集合对应的一个比原来四叉树对应的正方形区域更小的正 方形区域 根据上面四叉树的定义，我们可以得到一个递归的算法：将当前的正方形区域 细分为四个象限，同时也对正方形区域对应的点集进行细分：接着，在每个象限对 应的小正方形区域中分别对相应的点集构造四叉树。直到某个象限区域对应的点集 包含的点数小于2 时，递归就结束。 19 硕士学位论文 m a s t e r st h e s i s 在构造四叉树过程中，如果某个正方形区域包含多个点的，那么都会被分割为 四个更小的正方形区域。但是在某些情况下，点集本身不一定会被分割。四叉树的 深度与其中各点之间的最小距离以及初始状态下正方形区域的边长有关。下面的结 论清楚地说明了这一点： 。 结论1 如果对平