（计算机应用技术专业论文）动态场景的光线跟踪加速结构研究.pdf

r e s e a r c ho fa c c e l e r a t i o ns t r u c t u r e sf o r d y n a m i c s c e n e sb a s e do nr a y t r a c i n g at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t f o rt h em s d e g r e ei nc o m p u t e ra p p l i c a t i o nt e c h n o l o g y b y l i a n gy a n p o s t g r a d u a t ep r o g r a m c o m p u t e r s c i e n c ed e p ar t m e n t c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：j i nh a n j u n a c a d e m i ct i t l e ：p r o f e s s o r 一 s l g n a t u r e a p p r o v e d m a y , 2 0 1 1 帅i i | | | 6 8 1 硕士学位论文 m a s t e r s f h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：禾杪日期：州年月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中师范 大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 作松名：槊抱孙警今蚴 日期：汐年占月j 日日期吉b ，年b 月j 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人 的学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程 中的规定享受相关权益。圃童途塞握变卮澄盾；旦圭生；旦二生；旦三生蕉查! 作者签名：霖桫 日期7 年5 月7 日 导师 日期 盛 l 硕士学位论文 m a s t e r st h e s i s 摘要 光线跟踪算法是一种原理简单、实现方便且能生成高真实感图像的主要渲染算 法，已在非实时渲染领域得到了广泛的应用。随着计算机硬件条件的发展和新算法 的研究，光线跟踪算法应用于交互系统和动态场景中已取得了较好的渲染效果。但 对于动态复杂场景，由于场景物体的复杂性和场景动态更新特性，光线跟踪的实时 渲染仍然是研究的热点和难点。 针对此问题，本文对动态复杂场景中涉及的多种不同运动类型的物体，依据物 体的运动特性，将物体划分为三类：静态物体，局部运动物体，运动物体。为每类 物体分别构建合适的加速结构。用全局八叉树来构建场景静态几何的加速结构，并 以八叉树的最大深度值来决策终止划分；对局部运动物体构建局部八叉树，其构建 可以通过增加全局八叉树深度来实现；对动态几何构建两层层次包围盒结构以有效 支持其在场景中的规则运动。 本文对动态场景的三种加速结构，引入三层组织方式来进行管理。顶层是组织 整个静态场景的全局八又树；中间层一个是存储局部运动物体的局部八叉树，另一 个是存储运动物体的b v h ，这两个加速结构信息都存储于全局八叉树结构之上；最 底层，是懒惰构建的b v h ，此层不显著构建，只有当光线穿过全局八叉树某子空间 网格，又进一步穿过运动物体b v h 时才构建。 最后，利用b a r t ( a b e n c h m a r kf o r a n i m a t e dr a yt r a c i n g ) 动态光线跟踪基准 提供的动态光线跟踪基准场景数据及其代码框架，进行具体的实验，着重对测试场 景k i t c h e n 、r o b o t 进行了测试，并与两层组织方式的b v h + b v h 、b v h + k d t r e e 树 的实现结果进行了比较。 分析实验结果数据，得出结论：对动态场景中的物体分类并分别构建恰当的加 速结构，用三层组织方式管理三种加速结构，对物体运动类型符合分类标准的动态 场景可以取得较好的全局渲染效果，一定程度上解决了动态场景的实时渲染问题。 关键词：光线跟踪；加速结构；八叉树；层次包围体；场景组织 d ，矗 硕士学位论炙 m a s t e r st h e s i s a b s t r a c t r a yt r a c i n ga l g o r i t h mi sam a j o rr e n d e r i n ga l g o r i t h m st h a tc a ng e n e r a t el l i 曲r e a l i t y i m a g e s ，h a sb e e nw i d e l yu s e di na r e a so fs t a t i cr e n d e r i n ga p p l i c a t i o n sb e c a u s eo fi t s s i m p l ec o n c e p t i o na n de a s i l yi m p l e m e n t a t i o n w i t ht h e d e v e l o p m e n to fc o m p u t e r h a r d w a r ea n dt h er e s e a r c ho fn e w a l g o r i t h m ，r a yt r a c i n ga l g o r i t h mh a sb e e nm a d eag o o d r e n d e r i n gp e r f o r m a n c ei nt h ei n t e r a c t i v es y s t e ma n dd y n a m i cs c e n e s h o w e v e r , i nt h e d y n a m i ca n dc o m p l e xs c e n e s ，d u et ot h ec o m p l e x i t yo fo b j e c t si ns c e n e sa n dd y n a m i c u p d a t ef e a t u r e so fs c e n e s ，t h er e a l t i m er e n d i n go fr a yt r a c i n gi ss t i l lac e n t r a li s s u ea n d d i f f i c u l t y t os o l v et h i sp r o b l e m ，t h ep a p e rr e l yo nt h ep r o p e r t i e s o fo b j e c t sw h i c hh a v e d i f f e r e n tt y p e so fm o v e m e n t t h r e ec l a s s e so fo b j e c t sa r ed i s t i n g u i s h e d ：s t a t i co b j e c t s ， l o c a ld y n a m i co b j e c t s ，d y n a m i co b j e c t s t oc o n s t r u c ta p r o p e ra c c e l e r a t i o ns t r u c t u r ef o r e a c hc l a s sb a s e do nt h ec h a r a c t e r i s t i c so ft h r e et y p e so fo b j e c t s g l o b a lo c 打e ea r et h e a c c e l e r a t i o ns t r u c t u r eo fc h o i c ef o rs t a t i cg e o m e t r yo fs c e n e sa n da r ec o m m o n l yb u i l tb y e m p l o y i n gt h em a xd e p t ho fo c t r e et od e t e r m i n et h et e r m i n a t i o no fs l i p p i n g f o rl o c a l d y n a m i cg e o m e t r y , t oc o n s t r u c tal o c a lo c t r e ea n di t sc o n s t r u c t i o nc a l lb er e a l i z e db y i n c r e a s i n gt h ed e p t ho fg l o b a lo c t r e e f o rd y n a m i cg e o m e t r y , at w o - l e v e lb o u n d i n g v o l u m eh i e r a r c h y ( b v h ) i si n t r o d u c e dt h a te f f i c i e n t l ys u p p o r t si t s r i g i d l ya n i m a t i o ni n s c e n e s t h ep a p e rp r o d u c e sat h r e e l e v e lh i e r a r c h yo r g a n i z a t i o n p a t t e r nt oo r g a n i z et h e m u l t i a c c e l e r a t i o ns t r u c t u r e so f d y n a m i cs c e n e s t h et o p 1 e v e li sg l o b a lo c t r e e a c c e l e r a t i o ns t r u c t u r e st oo r g a n i z ea l ls t a t i cs c e n e s t h em i d d l e 1 e v e li s1 0 c a lo c t r e ef o r l o c a ld y n a m i co b j e c t sa n db v hf o rd y n a m i co b j e c t s b o t ht w oa c c e l e r a t i o ns t r u c t u r e s r e l yo nt h eg l o b a lo c t r e e t h eb o t t o m l e v e li sl a z yb u i l db v h t h e s eh i e r a r c h i e sa r en o t b u i l tu p f r o n tb u ta r ec o n s t r u c t e dl a z i l yw h e nar a yt r a v e r s e st h e m i nm el a s t p a r t so ft h e s i s ，w eu s eb a r t ( ab e n c h m a r kf o ra n i m a t e dr a y t r a c i n g ) w h i c hp r o v i d e sa s e to fd a t e sa n dc o d ef r a m e st om a k e 0 1 1 1 e x p e r i m e n t s w ep a y c l o s ea t t e n t i o n st ot h et w ot e s t s c e n e s ( k i t c h e na n dr o b o t ) a n dt h e nw em a d ea l l c o m p a r i s o nw i t ht h eo t h e rt w oa l g o r i t h m s ( b v h + b v h 、b v h + k d t r e e ) w h i c ha r eb o t h o r g a n i z e di nt w o 1 e v e l 弋 a c c o r d i n g t ot h er e s u l td a t e s ，w ec a nc o m et ot h ec o n c l u s i o nt h a tt h ew a yt oc l a s s i f y t h eo b j e c t si nd y n a m i cs c e n e sa n dt oc o n s t r u c tap r o p e ra c c e l e r a t i o ns t r u c t u r ef o re a c h c l a s sa n dt h e nu s et h r e e - l e v e lh i e r a r c h i e so r g a n i z a t i o np a t t e r nt om a n a g e t h r e e a c c e l e r a t i o ns t r u c t u r e s ，c a ng e tab e t t e rg l o b a lr e n d e n n gp e r f o r m a n c ef o rd y n a m i cs c e n e s c o n t a i m n go b j e c t sw h i c hm o t i o nt y p e sm e e tt h ec l a s s i f i c a t i o nc r i t e r i a m e a n w h i l e ，s o l v e t h er e a l t i m er e n d e r i n gp r o b l e m so fd y n a m i cs c e n e si ns o m ee x t e n t k e yw o r d s ：r a yt r a c i n g ；a c c e l e r a t i o ns t r u c t u r e s ；o c t r e e ；b o u n d i n gv o l u m eh i e r a r c h y ； o r g a n i z a t i o no fs c e n e 硕士学位论文 m a s t e r + st h e s i s 目录 摘要i a b s t r a c t i i 第l 章绪论。1 1 1 研究背景和意义1 1 2 国内外研究现状2 1 3 论文所作的工作4 1 4 论文的组织结构4 第2 章光线跟踪相关技术分析。6 2 1 光线跟踪技术6 2 2 加速结构研究8 2 2 ，挟遴褶捌试8 2 2 2 加送缮梅。一9 2 3 静态几何的光线跟踪加速结构1l 2 3 1 空间二叉树1 1 2 3 2k d 树1 3 2 3 3 八叉树1 4 2 4 动态几何的光线跟踪技术1 6 2 4 1 运动类型16 2 4 2 动态几何的光线跟踪加速结构1 7 2 4 3 动态场景加速结构的层次组织18 第3 章加速结构的设计方案2 0 3 1 难点及解决方案分析2 0 3 2 关键技术及创新2 0 3 2 1 场景物体划分一2 0 3 2 2 加速结构选择2 1 3 2 3 场景多层加速结构的组织方式2 2 第4 章加速结构详细设计和实现。2 4 4 1 八叉树2 4 4 1 1 八叉树的构建2 6 4 1 2 光线穿过八叉树2 8 4 2b v h 3 0 4 2 1 构建b v h 3 1 4 2 2 光线穿过b v h - 3 2 4 2 3 更新b v h 3 4 硕士学位论更 m a s t e r st h e s i s 4 2 4 懒惰构建b v h 3 6 4 3 建立多层加速结构的组织3 7 第5 章实验结果及分析4 0 5 1 测试场景k i t c h e n 4 0 5 2 测试场景r o b o t s 4 1 5 3 结果分析4 2 第6 章总结及以后的工作4 5 6 1 总结4 5 6 2 以后的工作4 5 6 3 展望4 6 参考文献4 8 硕士期间发表的论文和参与科研项目5 2 至定谢5 3 硕士学位论文 m a s t e r st h e s i s 1 1 研究背景和意义 第1 章绪论 近年来，光线跟踪技术在图形图像处理各个领域得到了广泛的应用。随着计算 机硬件性能的提高及g p u 技术的发展，光线跟踪在交互场景、实时动态场景、大 规模场景等不同应用角度的高真实感实时渲染的研究成为热点。 相对于传统的光栅算法，光线跟踪技术有以下优点：( 1 ) 光线跟踪技术原理简 单、易于实现，3 d 效果及物体间关系直观，而光栅算法效果不明显、难以实现；( 2 ) 光栅算法只支持三角面片数较少的场景，而光线跟踪支持多面片( 且支持各种面片 类型，如球形、曲面、不规则表面等) 复杂场景的渲染及各种光照效果；( 3 ) 光栅 算法按帧构建场景三角面片和线性插值的特性都受硬件制约，难以实现并行化，而 光线跟踪技术具有可并行、可显示对数级三角面片的特性。基于以上优势，光线跟 踪技术被广泛应用于图形图像处理的各个领域。 光线跟踪技术也有自身固有的一些局限性。它是一种高计算代价的递归算法， 由于对每一条光线的跟踪及频繁的光线与景物的相交测试带来巨大计算量，要求并 行处理，这对目前已经发展良好的计算机硬件仍旧是一个挑战。由此，若想在桌面 级硬件条件下，实现真实感动态场景的实时渲染，则要求对光线跟踪的软件加速技 术做进一步研究。 真实感动态场景的实时渲染，具备以下特点和实现挑战。( 1 ) 首先，从场景渲 染的真实感出发，光线跟踪技术使用光线来判断各种元素的可见性，重点是进行光 线直接与真实曲面和其他没有简化的场景图元的求交计算，求交计算的数据量庞 大，是生成高度真实感图像的一个巨大挑战，而简化物体几何复杂度、忽略二次衍 生光线计算可减少计算量但又会降低场景渲染的精度，不利于图像真实感效果的实 现；( 2 ) 从场景的动态特性出发，动态场景中包含各种运动特性的物体，为了保持 运动几何每帧加速结构的质量，须部分重建或完全重建加速结构，而重建开销及部 分重建判断开销即使在中等规模的场景中涉及的数据量仍然是非常庞大的；( 3 ) 从 实时渲染角度出发，光线跟踪技术是对经由整个场景的光线进行实时分配的，而光 线跟踪相交测试、图元细分等环节数据集频繁更新都将引起渲染速度缓慢的问题， 必须利用光线跟踪加速技术满足动态场景渲染的实时性要求。 通过以上分析，可以看出，对于真实感动态场景的实时渲染的挑战均来自于光 线跟踪技术处理过程的大数据量问题，因此，使用渲染加速技术是必须的。而在普 硕士学位论文 m a s t e r st h e s i s 通硬件计算机上，使用加速结构成为主要的加速技术，而构建加速结构势必会带来 额外的内存和时间开销，构建加速结构的开销和由此获得的整个渲染过程中光线跟 踪效率的折中问题成为研究的焦点。使整个动态场景每帧的渲染时间最小化、针对 动态场景不同物体的运动特性对其构建适当的加速结构并取得好的光线跟踪效率， 是本论文研究的重点。 对此，本论文采取如下研究思路：首先，根据物体运动特性对场景所包含的物 体进行分类，分为静态物体、局部运动物体、运动物体三类；然后对各类物体，根 据其运动特性，分别构建加速结构；最后合理分层组织多种加速结构，自上而下的 组织整个动态场景数据。 关于“动态场景的光线跟踪加速结构研究 的研究课题，是立足于解决光线跟 踪技术的难题而展开的，对于解决构建加速结构开销和取得高效光线跟踪执行效率 之间的矛盾、完善光线跟踪技术在动态场景实时渲染应用领域的研究，具有重要意 义。 1 2 国内外研究现状 图形图像的真实感效果包括光照( 反射和折射) 、阴影和半阴影等效果，运用 光线跟踪技术可以同时实现多种真实感效果，是图形学中的主要渲染方法。但由于 各种真实感效果的实现都涉及大量光线与物体的求交测试，因此，处理复杂动态场 景所需的计算量十分庞大。 多年来，国内外广大学者对光线跟踪技术进行了大量的研列u 】。研究工作主要 集中在光线跟踪的各种加速技术上，其加速技术的研究角度大致可分为三类：构 建加速结构。运用适当的加速结构，高效组织场景空间及物体，以减少光线与面片 几何相交测试次数和相交测试时间，快速重建场景加速结构以实现实时渲染，常用 的加速结构有均匀网格( u n i f o mg r i d ) 1 3 1 、层次包围体( b o u n d i n gv o l u m e h i e r a r c h i e s ，b v h ) 【4 】、八叉树( o c t r e e ) 【5 1 、k d 树【7 ，9 ，1 0 1 、二元空间分割( b i n a r ys p a c e p a r t i t i o n i n g ，b s p ) 树；减少光线处理。通过控制树的构建深度及对光线的跟踪 深度来减少光线几何求交次数；利用光线传播方向的一致性快速定位相交点和相交 几何；利用光线的空间连续性对相邻光线进行“光线束”的处理方式以避免对每一 条光线都进行处理。将该技术与k d 树、空间网格等多种加速结构结合【6 ，7 ，8 】应用于各 种交互式光线跟踪系统中，取得较好效果；基于硬件的加速技术。将光线跟踪的 加速结构映射到图像处理器( g r a p h i c sp r o c e s s i n gu n i t s ，g p u ) 已经取得好的研究 效果。如基于g p u 的均匀网格【1 2 , 1 3 , 1 4 】，f o l e y 和s u g e r m a n 等【1 7 】提出将k d t r e e 加速 2 嚣、 ： 硕士学位论文 m a s t e r st h e s i s 结构映射到g p u 上；而t h r a n e 和s i m o n s e n 等【1 8 】提出在g p u 上实现b v h ，将数据 结构映射到g p u 硬件上，利用g p u 的并行处理特性取得较好的渲染效率。 以上对光线跟踪的加速技术的分析可以看出，在普通计算机硬件条件下，运用 恰当的加速结构并利用光线特性减少对光线的处理，可以有效解决构建加速结构的 开销和光线跟踪渲染效率的折中。本文重点研究对动态场景不同运动特性的物体分 别构建适合的加速结构，并保持加速结构在光线跟踪渲染过程中相交测试的高效 性、动态渲染过程中加速结构快速重建的有效性。 研究动态场景渲染的效率，一般从两个角度进行处理。一方面，研究利用g p u 硬件特性的动态场景处理，基于g p u 的光线跟踪研究已经取得好的效果。p u r c e l l 等【1 5 】将所有的光线跟踪内核都建立在g p u 上从而实现了基于g p u 的光线跟踪算法 框架；c a r r 等【1 2 】提出将c p u 与g p u 结合，g p u 仅负责光线跟踪的求交，以此加速 求交计算并提高g p u 的使用率；也有很多学者将光线跟踪的加速结构引入到g p u 中以实现更快的执行速度。而本文着重研究基于普通硬件条件的动态场景渲染，所 以不利用g p u 进行处理。 另一方面，研究动态场景中运动几何加速结构的高效重建的方法。研究工作主 要从三个角度出发：降低重建开销上7 1 ，如更新层次性包围体【2 0 1 和更新均匀网 格【8 】o 建立重建计划。如果不加区分的完全重建每帧加速结构，无疑将带来庞大 的计算量和执行开销，因此，进行加速结构重建计划的研究是很有必要的。文献 2 2 】 根据运动特性对场景物体划分为静态几何、局部运动几何、变形几何、全动态几何 四类。变形几何和规则运动几何由于运动范围有限，选择部分重建加速结构；而对 于无逻辑运动几何，判断重建哪部分加速结构的开销会更大，则选择完全重建加速 结构。多层加速结构的构建。对于动态几何光线跟踪，一般采用两层加速结构， 顶层加速结构存储整个静态场景信息以便对场景中的运动物体实现快速定位，底层 加速结构存储局部物体信息以便对运动、变形等部位的加速结构快速更新。如文献 2 3 1 用顶层b s p 底层b s p 两层结构实现的交互动态场景光线跟踪，取得了好的应用 效果。 以上对光线跟踪加速技术、动态场景渲染处理方法的国内外研究现状的回顾与 分析，表明了利用光线跟踪技术对动态场景进行渲染，根据动态场景物体运动特性 的不同构建不同的加速结构、同时合理分层组织各加速结构，以提高整个场景的全 局渲染效率的研究工作是有必要且可行的。 硕士学位论文 m a s t e r st h e s i s 1 3 论文所作的工作 本论文主要针对动态场景光线跟踪渲染的实时性难题，运用构建加速结构的加 速技术，在构建加速结构之前，对场景物体进行分类，并针对每类物体的运动特性 构建适合的加速结构。进一步，对多加速结构的场景进行合理的组织，以实现高效 的光线跟踪渲染效率。本论文的工作主要有以下三点： ( 1 ) 场景物体分类。为解决构建加速结构开销和全局光线跟踪执行效率之间 的矛盾，在预处理工作中，首先对动态场景中所有物体的特性进行分析，划分为三 类：静态物体( 整个场景) 、局部运动物体、运动物体。这样，在构建加速结构之 前，就可以针对三类物体的特性来分别构建合适的加速结构，静态物体可在预处理 环节构建加速结构，而具有动态特性的物体，其加速结构在光线跟踪渲染过程中根 据需要选择构建和更新。 ( 2 ) 对各类物体分别构建加速结构。用全局八叉树加速结构组织整个场景， 并将场景中的局部运动物体和运动物体结点信息存储在全局八叉树结构上，便于对 其实现快速定位和快速相交测试；局部运动物体由于其运动范围有限，对其构建局 部八叉树结构，可通过增加全局八叉树的深度值来实现；运动物体变化频繁，加速 结构需每帧更新，则构建两层层次包围体结构，顶层b v h 中包含所有各自分离的 运动物体集合，底层b v h 是只包含一个物体的b v h 。顶层b v h 保存运动物体集 合中各物体之间位置关系信息，当物体运动，位置关系发生变化时，更新顶层b v h 。 当某物体运动时，可仅仅重建此运动物体的b v h 或物体运动部分的b v h ，降低了 完全重建b v h 的代价。 ( 3 ) 组织场景的多个加速结构。用三个层次来组织整个场景的多个加速结构， 顶层是组织整个场景的全局八叉树；中间层一个是存储局部运动物体的局部八叉 树，另一个是存储运动物体集合的b v h ，这两个加速结构信息都存储于全局八叉树 结构上；底层是懒惰构建的单个运动物体b v h ，当光线穿过全局八叉树某子空间立 方体，又将进一步穿过存储于其中的单个运动物体的包围体时，构建此运动物体的 b v h ，并分析光线与其中三角形面片的相交关系。 1 4 论文的组织结构 本论文各章节的主要内容如下： 第l 章，介绍本论文的研究背景、意义和国内外研究现状。通过对光线跟踪技 术的优缺点及将其应用于真实感动态场景的实时渲染所面临的挑战进行分析，引出 4 硕士学位论炙 m a s t e r st h e s i s 本论文的研究内容及研究思路；通过对光线跟踪加速技术、动态场景渲染处理方式 的国内外研究现状的回顾，证实本论文的研究课题是有意义且可行的； 第2 章，对动态场景渲染相关的各项关键技术进行分析，包括光线跟踪技术原 理、加速结构研究以及静态几何光线跟踪和动态几何光线跟踪的技术分析；其中关 于静态几何和动态几何光线跟踪技术的研究是重点，包括各自的特性、适合的加速 结构等；从而分析得出，动态几何光线跟踪渲染是在静态几何加速结构的基础上， 选择多种加速结构并进行合理组织实现的； 第3 章，主要分析论文的难点和可行的解决方案，并对设计的关键技术场 景物体的划分，动、静态加速结构选择和场景多加速结构的组织方式进行了分析； 第4 章，分析本论文采用的关键加速结构的实现细节，包括加速结构的构建、 更新等内容，最后重点对场景多加速结构的三层组织方式进行分析； 第5 章，用动态场景光线跟踪基准提供的测试场景数据及其代码框架，进行具 体的实验，对测试场景进行测试，并与两种两层组织方式的实现结果进行了比较， 分析实验结果数据并得出结论； 第6 章，对论文所做工作的结果进行总结，针对不足提出以后工作的改进思路 和研究角度，最后，展望此研究内容的发展空间和广泛的应用前景。 硕士学位论文 m a s t e r st h e s i s 第2 章光线跟踪相关技术分析 光线跟踪( r a yt r a c i n g ) 技术是一项概念简单但功能齐全的技术，它可以模拟 光源和入射光在物体表面产生的反射和折射、阴影绘制和隐藏面消隐等，已成功应 用于非实时渲染应用领域。但由于涉及大量的光线与几何面片的求交计算，用该技 术实现实时的动态场景渲染，仍然是难题。针对此问题，本章节对光线跟踪的基础 算法以及各种加速结构进行分析，作为本论文研究的理论基础和依据。 2 1 光线跟踪技术 光线跟踪是一种来自几何光学的逼真显示物体的通用技术。该算法最初用于研 究隐藏面消隐，由a p p e l l 2 l 】在1 9 6 8 年提出并给出算法描述；后来，在1 9 8 0 年t u r n e r w h i t t e d 1 9 l 综合考虑光的折射、反射、投射和阴影等影响因素，提出第一个整体光照 w h i t t e d 模型，并基于此将光线投射算法扩展为递归算法，给出了完整的光线跟踪 算法描述。从此，光线跟踪算法得到了广泛的研究。 下面对光线跟踪算法的理论基础及成像原理进行分析。 光线跟踪算法的思想，来自于光线经过物体表面时产生的各种物理光学现象。 光线在物体之间传播时，光线到达物体表面后，产生各种光学现象( 反射、折射和 透射等) ，部分光线改变传播方向继续前进，遇到另一个物体后，又发生二次反射、 折射和透射，最后部分光线到达我们的眼睛，到达我们眼睛的光线为最后看到的物 体。所以，逆向跟踪光照明物理过程可实现整个绘制过程。光线跟踪图像生成的基 本原理图，如图2 1 所示。首先确定眼睛的位置和视线的方向，经过屏幕像素点， 视线与像素点连接形成一条射线，从而计算从眼睛出发通过每个像素中心的光线方 程，再计算光线与场景的最近交点和法向，最后将交点处的颜色值填入相应像素中。 图2 1 光线跟踪图像生成的基本原理图 6 、： 硕士学位论文 m a s t e r st h e s i s 基于图2 1 给出的简单成像原理图，我们结合图2 2 进一步分析光线跟踪算法 基本过程。在此图中，场景中有点光源、两个透明球、一个非透明球组成，分别用 l ，o l 和0 2 ，0 3 表示，涉及四种光线( 视线，阴影测试线，折射光线，反射光线) 。 整个光线跟踪算法的详细描述如下：从视点出发，经过视屏像素点( 视点与像 素点之间形成视线e ) ，到达透明物体o l ，光线在其表面作用产生反射光线r l 和折 射光线t l ；t 1 继续向前传播，到达物体o i 的另- n 表面且交点为p 2 ，形成折射光 线t 2 和反射光线r 2 ；t 2 继续传播，到达不透明物体0 3 且交点p 3 ，由于其不透明特 性不形成折射光线，而只形成反射光线r 3 ；r 3 继续传播，到达物体0 2 表面且交点 为p 4 ，形成折射光线t 4 和反射光线r 4 ：t 4 在透明物体0 2 中继续传播，与其另一个 表面相交于点p 5 ，产生折射光线t 5 和反射光线r 5 光线在某点处产生的总光强，有直接光照光强和间接光照光强两种，由三部分 组成：直接光照光强是光源产生的直接光照光强，为局部光强；间接光强是反射方 向上其他物体引起的光照光强和折射方向上其他物体引起的光照光强。据此，我们 可以计算得到视屏上每个像素点的光强，即相应的颜色值( 在此过程中，我们做出 阴影测试线来判断交点的可见性) 。在交点p l 处，p l 和光源l 的连线s l ，中间没 有其他遮挡物，该点为此视点的可见点，则用局部光照明模型计算光源l 在p l 点 形成的局部光强；反射光线r l ，不再与其他物体相交，则反射方向上的光强为零； 折射光线t l ，在物体o l 内部传播，产生的交点p 2 在o l 内部，则折射方向上的光 强为零。交点p 2 在o l 内部，局部光强为零，反射光线r 2 仍然在o l 内部传播则 不再继续跟踪，继续跟踪折射光线t 2 方向上的光强。t 2 与物体0 3 的交点p 3 处， 做交点p 3 与光源l 的阴影测试线s 3 ，也没有遮挡物，计算局部光强，此物体是非 透明的忽略折射光线，继续跟踪反射光线r 3 方向上的光强，结合局部光强，得到 p 3 处的光强。交点p 4 处的光强计算与前面的过程相同，此算法递归进行下去。 图2 2 光线跟踪算法的过程 7 在此过程中，场景的光线是从光源出发射向各个方向，在到达某个物体表面后， 部分被吸收，部分被反射、折射而改变方向继续前进，直到遇到新的物体表面。理 想情况，这个过程可以无限次执行下去。当然，光线在传播过程中会由于被吸收而 衰减，也会由于某些光线的传播方向对生成图像无贡献，也可能由于达到一定递归 深度时用庞大的计算量换取细微渲染效果得不偿失。因此，常用的递归结束条件： ( 1 ) 光亮度值，光线经多次反射和折射后衰减，光亮度对渲染贡献很小时，忽略 不计，停止递归；( 2 ) 光线未到达任何物体表面或已经射出场景；( 3 ) 递归深度， 在此跟踪深度( 反射或折射次数) 下，场景渲染效果已经达到预期要求。 对光线跟踪技术的分类研究，主要从以下两个角度：( 1 ) 从光线跟踪技术和硬 件的结合性来看，分为基于c p u 的光线跟踪、基于g p u 的光线跟踪和基于c p u g p u 的光线跟踪。( 2 ) 从对光线跟踪加速的主要处理技术角度，分为双路径跟踪技术p 2 、 分布式光线跟踪技术【l l 】和p a c k e t 光线跟踪技术；( 3 ) 从光线跟踪技术的应用角度， 分为基于静态几何的光线跟踪和基于动态几何的光线跟踪。 本文，重点从光线跟踪有效应用于动态场景实时渲染的角度出发，研究静态几 何和动态几何光线跟踪相关的加速技术，对动态场景不同运动特性的物体分别构建 适当的加速结构，并以恰当的层次方式将两类加速结构组织起来。 以下内容，是与此研究目标相关的一些关键技术，同时也是本文研究的技术重 点。 2 2 加速结构研究 在详细讨论光线跟踪加速结构之前，先对相交测试技术进行分析。光线跟踪是 跟踪每一条光线，每帧都需要重新计算光线与场景几何面片的相交情况，才能得到 正确的渲染结果。加速结构的建立，不仅仅为了快速定位场景物体，还需为光线求 交、快速相交测试做出贡献。 2 2 1 快速相交测试 测试光线与场景几何面片的相交情况、准确定位交点是光线跟踪技术的核心研 究内容。在进行渲染之前，进行快速而简单的相交测试，是为了减少全局渲染时间， 同时也为下一帧渲染存储相关信息，如此帧交点坐标信息、光线法向等。 已存在的各种算法，能够快速求解光线与各种几何面片( 如平面，球面，隐藏 面，自由曲面等) 的相交测试。而三角面片是最常用、最简单，能够代表各种几何 体的元素，既可以支持多数模型的应用，也可以通过“拼接、组合 等形式形成任 8 硕士学位论文 m a s t e r + st h e s i s 意表面的近似。 各种相交测试技术，都是为了有效减少光线与三角面片相交测试的计算量，而 交点是否存在的判断，w a c h t e r l 2 4 】对几种相交测试算法的速度、精度进行了比较分 析，得出用重心坐标测试方法效果较好。算法的基本步骤是：首先计算光线与三角 形的三个顶点所确定的平面的相交情况；然后判断计算出的击中点是否在三角面片 所在的平面上；最后验证交点的有效性，如果与重心坐标描述的点为同一个，则有 效。此外，k e n s l e r 和s h i r e l y l 2 9 1 提出了采用遗传算法自动搜索相交点的思想，在每 一代中基于运行时间筛选出最佳方法，通过在每一代中引入新的计算因子，反复选 择而得出结果。 、 2 2 2 加速结构 用光线跟踪技术渲染图像，即使在中等规模的场景中涉及的数据量都是很庞大 的光线数、构成复杂场景物体的面片数、动态变化引起的频繁更新数据等。通 常减少光线跟踪运行时间，常用的加速技术是构建加速结构，可以将运行时间复杂 度从吼刀j 降低到d 【l o g 疗j 。 使用加速结构是为了将每一帧渲染时间最小化，从而达到加速结构的构建开销 和获得的光线跟踪执行效率之间的折中。渲染静态场景时，加速结构仅在图像生成 前执行一次，渲染时间取决于加速结构能否有助于减少光线与三角面片相交测试次 数；当处理动态场景时，每帧几何面片的变化使原有的加速结构失效，所以几乎在 渲染每帧场景前都需要重新构建。因此，选择适当加速结构的原则是构建、更新加 速结构的开销要小于所获得的光线跟踪渲染效率。 ( 1 ) 光线跟踪加速结构分类 光线跟踪的加速结构有不同的分类标准，进而划分为不同的类型：根据所依 据的划分对象的不同，分为基于空间细分的加速结构和基于物体细分的加速结构； 基于划分方式的分类，分为自适应划分的加速结构和规范化划分的加速结构。 基于空间细分的加速结构是将整个场景剖分为子空间并将子空间单元以一定 的层次结构组织起来。由于是以空间为主要划分依据，因而，同一个几何单元可能 被划分到两个子细分空间。当进行求交计算时，光线穿过场景，同时也穿过包含物 体的子空间单元，只与包含物体的子空间进行光线物体求交测试( 忽略空子空间) 。 用多种空间细分方法构建的加速结构，如八叉树( o c t r e e ) 1 5 】用三个相互垂直的平 面递归地把空间分割为八份；二元空间划分( b i n a r ys p a c ep a r t i t i o n i n g ，b s p ) 哗1 树 用任意朝向、任意位置的分割平面，递归地把空间划分为两个子空间；k d 树【3 0 】类 9 硕士学位论文 m a s t e r st h e s i s 似于b s p 树，只是