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

中文摘要 随着计算机硬件技术的高速发展和计算机图形学研究的深入，光线跟踪渲染 技术越来越得到人们的关注并且成为实时渲染和离线渲染研究的热点问题。动态 场景的渲染及如何管理动态场景是一个关键技术问题，动态场景的空间加速结构 需要考虑构造代价，遍历代价及更新代价。 本论文的工作目的是：围绕着动态场景渲染这个话题，深入地对动态场景空 间加速结构的构造、遍历和更新算法进行探索性的研究。本论文的贡献和创新性 在于：1 ) 在p b n 渲染系统中引入s a h 代价模型，设计并实现了b v h - s a h 和b s p s a l l 两种空间加速结构；2 ) 创新性地提出并实现了b i h k d t r e e 和研d k d t r e e 两种空间 加速结构；3 ) 分析比较了b v h s a h 、b s p s a l l 、b i l l k d t r e e 、酊d k d t r e e 、k d 仃e e 、鲥d 和o c c 仃e e s a h 七种空间加速结构的各自特点和适用条件；4 ) 在p b n 渲染系统中 设计并实现了利用b v h s a h 渲染动态场景的两种更新策略的体系结构，对比了 b v h s a h 实时全更新策略和半更新延时更新策略。本论文结论为：1 ) b v h s a h 对 于空间稀疏的小规模模型场景与其他空间数据结构相比较构造时间比较低，对于 变形场景特别有效，空间层次包围体b v h s a h 的渲染时间要落后于空间细分的加 速结构，在部分动态场景中，b v h s a h 半更新延时策略是一种效率很高的更新策 略；2 ) k d t r e e 、b i h k d t r e e 、面d k d t r e e 相比较鲥d k d t r e e 是最有效的方法；3 ) b s p s a l l 与舒d 、o c c 仃e e s a h 相比较，b s p s a l l 是最有效的方法。 关键词：动态场景空间加速结构光线跟踪更新策略 a b s t r a c t w i lm ef a s t e rh a r d w a r ei r n p r 0 v e m e n ta n dl o n g t i l l l e i n d 印t hr e s e a r c ho n c o m p u t e rg r a p l l i c s ，r a yn a c i n gb e c o m et l l ef o c u so fr e s e a r c ho nb o t l lr e a l - t i i l l ea n d o 用i n er e n d e r i n gt e c 岫o l o g ys ot h a tal o to fp e o p l ep a ya n e n t i o nt oi t i 乇a yt r a c i l l g d y n a r n j cs c e i l e s 锄dh o wt oh a n d l i n gt h ed y n a l l l i cs c e n e si st h ek e yt e c l l i l o l o g ) ， a c c e l e r a t o rn e e dc o n s i d e r i n gt h ec o s to fc o n s t 九1 c t i o na i l dr a y 仃a v e r s a l ，a 1 1 du p d a t e s t r a t e g i e si sa l s oi m p o r t a n tt ob ec o n s i d e r e d t h ep u 巾o s eo ft h i sp a p e ri st h a tw ed od e 印r e s e a r c ho na l g o r i t h i l l sf o r c o i l s t l l j c t i o n a i l dm yt r a v e r s a lo fs p a c i a la c c e l e r a t o ro nm et o p i co fr a yn a c i i l g d y n a l l l i cs c e n e s ，a n dm a tw ea l s ot 巧s o m en e wu p d a t es t r a t e g i e s t h ec o n t r i b m i o n a 1 1 d 硫o v a t i o no ft l l i sp 印e ri st 1 1 a t ：1 ) w eu s es a hc o s tm n c t i o nt oc o n s 仃u c tb v h s a h a n db s p - s a hi nt l l ep b r t 瑚d e r i n gs y s t e m ；2 ) w eb 血培u pt 、) l ，on e wa c c e l e r a t o r s b i h k d t r e ea n d 莎i d - k d t r e e ；3 ) w ec o m p a r eo u rn e wa c c e l e r a t o r sb v h s a l l ，b s p s a l l ， b m - k d t r e ea n dg r i d k ( 1 订e et ok c l 仃e e ，g r i da n do c c t r e e s a ho nt h ep u 印o s eo ff - m d i i l g o u tt h e i ra d v a n t a g e sa n dd i s a d v a n t a g e s ；4 ) w em a k eu s eo fd y n a r n i cb v h s a hu p d a t e s t r a t e g i e st od e s i 印a n d 血l f i l lt h en e wr e n d e 血g 胁m e w o r kf o rd y n a i i l i cs c e i l e s 血t 1 1 e p b r tr e n d e 血gs y s t e ma n df m dd i 虢r e n c eb e t 、e e nt h e 觚ou p d a t es t r a t e g i e sm a ta r e a l l u p d a t es t r a t e g ya 1 1 dh a l f1 a z yu p d a t es 仃a t e g y - t h ec o n c l u s i o no ft h i sp a p e ri st h a t ： 1 ) m ec o s to fb v h s a hc o n s t m c t i o ni sv e 巧l o wf o rm es c e n e sw i ms m a us c a l e g e o m e t 巧p r i i n i t i v e sc o m p a r e dw i t l lo m e rs p a t i a la c c e l e r a t o r se s p e c i a l l y f o rt h e d e f o n n a b l es c e n e s ，b u tt h er e n d 耐n gp e 墒肌a n c eu s i n gb v h s a hl a gf a r 血e p e 怕n i l a n c eu s i i l gs p a c es u b d i v i s i o n ，a n di i lt h ep a r t l yd y n 锄i cs c e n e st h eb v h - s a h h a l fl a z ) ru p d a t es 位a t e g yi sv e d ，e 肫c t i v e ；2 ) 酣d - k d t r e ei sm em o s te 脏c t i v e a c c e l e r a t o rc o m p a r e dw i mk d t r e ea n db m - k d t r e e ；3 ) b s p s a hi sm em o s te f r e c t i v e a c c e l e r a t o rc o m p a r e dw i m g r i da n do c c t r e e s a h 1 娅yw o r d s ：d y n a r n i cs c e n e s ，s p a c i a la c c e l e r a t o r ，r a yt r a c 崦，u p d a t es t r a t e g y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 王日l l 签字日期：2 吣孑 年月6 日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘鲎有关保留、使用学位论文的规定。 特授权苤盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 王a 弋 导师签名： 张钦 签字日期：协g 年月6 日 签字日期：加3 年6 月厂日 第一章绪论 1 1 研究背景和意义 1 1 1 研究背景 第一章绪论 渲染技术一个最主要的部分是可视化方法。例如，产生一幅图像是非常必要 的去检测从视点来看那些表面是可见的和从光源出发那些表面是可见的，因此会 形成阴影。如果考虑全局光照，某些表面对于其他表面是不是可见也是要必须检 测的。对于可见检测两种最普遍的方法是光栅化方法和光线跟踪方法，其可视性 检测方法性能的优劣是图形学交互应用的关键。 基于光栅化的方法对于从同一源点出发的许多光线进行可视性检测会受到 一定的限制，通过所有物体进行循环检测。这种算法会被具有特殊功能的硬件图 形处理单元( g p u ) 有效的支持。随着硬件和软件的优化和发展，g p u 会达到 实时渲染的性能，对于从视点或从光源一点对复杂模型进行可视性检测。除此以 外，它还能够使用许多技术实时的产生一些复杂的图形学效果。因此，当前基于 g p u 的光栅化技术在实时可视化方面占据主导地位。 光线跟踪算法支持点到点的可视性查询和更高级的光源效果，这些都需要强 大的计算能力。离线的渲染由于某些原因【2 已经首选光线跟踪来代替光栅化技 术。至今，光线跟踪技术由于没有硬件的特殊支持还未达到实际应用的交互水平。 1 1 2 研究意义 随着c p u 硬件的发展和并行机制的可行性，并且算法和软件结构的同等优 化使光线跟踪技术已经到达一个不仅仅局限于离线渲染的阶段。最早的交互式光 线跟踪限制在简单的着色效应 3 】，许多交互式光线跟踪渲染系统解决一些复杂的 问题【4 】【5 】。 快速光线跟踪的关键是使用诸如k d t r e e 、网格、包围体的空间数据结构进而 减少每根光线与几何单元体求交的次数。很长一段时间，光线跟踪的研究集中在 数据结构的效率和光线遍历及求交算法的操作上。构造空间数据结构的时间被忽 略因为它对于离线渲染并不重要。但是，随着光线跟踪的研究进入交互领域，原 来的数据结构仅仅适用于穿过静态场景或有限的动态场景。 光线跟踪有潜在的可行性用于交互应用，例如游戏，但是它必须可以展示每 第一章绪论 一帧几何场景的重要变化。这个研究领域面临新挑战：数据结构的构造算法要足 够的快速和弹性来满足交互帧速的实现，还要考虑对渲染效果和效率的影响。因 此，以前许多被认为无效的并且被放弃的空间数据结构要被重新思考和改进，对 于用相对较少的采样对复杂场景批处理渲染的交互系统来说，这是一个挑战。 1 2 国内外现状 i n g ow a l d 【6 7 】等人对动态变形场景的空间数据结构进行了大量的研究，提出 了基于表面积的结构包围体。c a r s t e i l 和a l e x a i l d e r 削提出了b o u i l d i i l gi n t e a l h i e r a r c h y ，一种更有效空间加速结构。s v e n 和g e r d l 9 j 提出了b k d 仃e e ，一种基于 光线跟踪的硬件加速的空间加速结构。i n g o 和t l l i a g o 【l o 】等人提出了用一致性网 格遍历光线跟踪方法生成动态场景。h 猢】对光线跟踪方法的静态场景的空间 数据结构进行了深入的研究，得出结论k d 一骶e 对于静态场景效率最高。i i l g ow a l d 和h a v r 锄【1 2 】对于光线跟踪方法提出了一种快速的建立k d - t r e e 的方法。 实时的光线跟踪已经引起了图形学研究者的注意，不可避免的会带来支持这 种渲染方式的硬件出现。与z - b u 腩r 算法相比，实时的光线跟踪从视觉上更能引 起图形研究者和游戏开发者的注意，它将改变3 d 图形引擎的能力和a p i 【l 3 j i l 4 l 。 由i g a d 小h t v 开发的a r a l m a 【1 5 】光线跟踪渲染器，已经在游戏开发方面开始有 实际的应用。 袁伟杰【16 】对全局关照下动态场景的有效组织做了大量的研究工作，提出一种 把多帧场景创建在同一个i 树下的方法。课题组对基于蒙特卡罗全局光照的光 线跟踪算法和静态场景的渲染和空间数据结构开展了许多深入的研究工作。 1 3 论文工作和章节组织 本课题主要研究基于物理图象合成技术的动态场景的有效管理架构，结合 p b r t 渲染系统，对动态场景尤其是变形场景的空间加速结构完成从启发构思到 实现的工作，对空间加速结构的构造算法【7 j o ，1 2 ，17 1 ，光线遍历算法和层次结构的 终止条件【】8 j 进行启发式探索。 本论文第二章叙述光线跟踪技术和原始的空间数据结构及场景的分类，第三 章阐述了对b s p s a l l 、b v h s a l l 、b i h k d t r e e 和鲥d k d t r e e 四种新型的空间数据结构 的实现和分析，第四章阐述了对动态b v h s a l l 的动画渲染体系结构的实现和 b v h s a h 更新策略的研究。 第二章光线跟踪技术和空间加速结构 第二章光线跟踪技术和空间加速结构 2 1 光线跟踪技术 在自然界中，光源发出的光线向前传播，最后到达一个妨碍它继续传播的物 体表面，我们可以将“光线”看作在同样的路径传输的光子流，在完全真空中， 这条光线将是一条直线。但是在现实中，在光路上会受到三个因素的影响：吸收、 反射与折射。物体表面可能在一个或者多个方向反射全部或者部分光线，它也可 能吸收部分光线，使得反射或者折射的光线强度减弱。如果物体表面是透明的或 者半透明的，那么它就会将一部分光线按照不同的方向折射到物体内部，同时吸 收部分或者全部光谱或者改变光线的颜色。吸收、反射以及折射的光线都来自于 入射光线，而不会超出入射光线的强度。例如，一个物体表面不可能反射6 6 的 输入光线，然后再折射5 0 的输入光线，因为这二者相加将会达到1 1 6 。这样， 反射或者折射的光线可以到达其它的物体表面，同样，吸收、反射、折射的光线 重新根据入射光线进行计算。其中一部分光线通过这样的途径传播到我们的眼 睛，我们就能够看到最终的渲染图像及场景。 2 1 1p a mt r a c i n g 技术 光线跟踪是一种真实地显示物体的方法，该方法首先由a n h wa p p e l 【l9 】在 1 9 6 8 年作为渲染实心物体中解决隐藏表面问题而提出的。w m t t e d 【2 0 在1 9 8 0 提出 了递推的光线跟踪技术。光线跟踪方法沿着到达视点的光线的反方向跟踪，经过 屏幕上每一个象素，找出与视线相交的物体表面点p 0 ，并继续跟踪，找出影响 p o 点光强的所有光源，从而算出p 0 点上精确的光线强度。当光线碰到一个物体 表面的时候，可能产生三种新的类型的光线：反射、折射与阴影。光滑的物体表 面将光线按照镜像反射的方向反射出去，然后这个光线与场景中的物体相交，最 近的相交物体就是反射中看到的物体。在透明物质中传输的光线以类似的方式传 播，但是在进入或者离开一种物质的时候会发生折射。为了避免跟踪场景中的所 有光线，人们使用阴影光线来测试光线是否可以照射到物体表面。光线照射到物 体表面上的某些点上，如果这些点面向光线，那么就跟踪这段交点与光源之间的 光线。如果在表面与光源之间是不透明的物体，那么这个表面就位于阴影之中， 光线无法照射。最终，光线进入虚拟的摄像机底片中，图片被生成出来。由于该 第二章光线跟踪技术和空间加速结构 算法是成像系统的完全模拟，所以可以模拟生成十分复杂的图片。 光线跟踪的优点：光线跟踪的流行来源于它比其它渲染方法如扫描线渲染或 者光线投射更加能够现实地模拟光线，像反射和阴影这样一些对于其它的算法来 说都很难实现的效果，却是光线跟踪算法的一种自然结果。光线跟踪易于实现并 且视觉效果很好，所以它通常是图形编程中首次尝试的领域。 光线跟踪的缺点：光线跟踪的一个最大的缺点就是性能，扫描线算法以及其 它算法利用了数据的一致性从而在像素之间共享计算，但是光线跟踪通常是将每 条光线当作独立的光线，每次都要重新计算。但是，这种独立的做法也有一些其 它的优点，例如可以使用更多的光线以抗混叠现象，并且在需要的时候可以提高 图像质量。尽管它正确地处理了相互反射的现象以及折射等光学效果，但是传统 的光线跟踪并不一定是真实效果图像，只有在非常近似或者完全实现渲染方程的 时候才能实现真正的真实效果图像。由于渲染方程描述了每个光束的物理效果， 所以实现渲染方程可以得到真正的真实效果，但是，这需要的计算资源，对计算 机硬件的计算能力要求比较高。 2 1 2 双向路径跟踪技术 v e a c h 【2 1 】提出双向路径追踪方法，并在后续文章中 2 2 】 2 3 】中进行了更加完整的 阐述。该方法是多重重要性抽样方法在整体光照领域的运用。双向路径追踪方法 在采样时分别从光源和视点各发射一束射线，经过在场景中的若干反射后，将两 条路径的终点连接在一起，形成一条完整的光路。这里的逆向跟踪实际上就是传 统的光线跟踪，而从光源出发的正向光线跟踪则用来计算来自环境的镜面反射光 和规则透射光对漫射表面光亮度的贡献。显然，与逆向光线跟踪相反，正向光线 跟踪是一个与视点和视线方向无关的过程。 2 1 3 分布式光线跟踪技术 分布式光线跟踪( d i s t r i b u t e dr a ”m c i l l g ) 由c o o k 2 4 】【2 5 1 在1 9 8 4 年提出，它本身 有一个重大的意义，在于计算模糊的复杂性的物理现象，这包含了运动模糊与反 射模糊、折射模糊等。所谓散射光线跟踪与抖动的概念便是建立在m o m ec 矾o 【2 6 1 的演算法则上。 分布式光线跟踪算法在处理每一被跟踪的光线时，在光线与物体表面的交点 处不仅朝其镜面反射方向和规则透射方向发射光线，而且依据物体表面的光照性 质朝其镜面反射方向和规则透射方向附近立体角内亦发射采样光线，即“分布池” 进行光线跟踪。该算法的计算效率依赖于每一表面镜面反射分布函数和规则透射 分布函数以及采样光线的数目。 第二章光线跟踪技术和空间加速结构 对理想点光源，它所产生的阴影均为本影，照明区与阴影区之间没有任何 半影过渡区。但对具有一定大小的光源，如面、线等光源，它不仅产生本影，而 且还会生成半影。半影是由于光源发射至被照射点的部分光线受到景物的遮挡而 产生的，若对光源均匀地发射阴影测试光线，则计算非常费时。且当采样不足时， 在阴影区域内会产生严重的走样现象。分布式光线跟踪算法则根据光源亮度的分 布特性及光源对于可见点的立体角来决定光源上采样点分布的疏密。每一采样点 向当前可见点发射一条光线。若该光线被景物遮挡，则它对当前可见点的光亮度 贡献为零。累计各采样的光亮度贡献即为可见点处受该光源照射的局部光亮度。 景深和运动模糊效果的模拟是分布式光线跟踪算法的一大页献。由于摄像机 和人的眼睛均是具有有限孔径的透镜。因而，所接收到的图像往往具有景深效果； 根据几何光学原理，来自场景中的光线经过透镜的折射后会聚在图像平面上。依 据透镜的几何光学参数和景物离透镜的距离。场景中一点经由透镜折射后可能映 射到图像平面上的不同位置上形成一个混淆圆。这意味味着，图像平面上某一象 素的光亮度可能包含来自场景中不同点的光亮度贡献。为了模拟上述景深效果， c o o k 在图像平面前面放置一凸透镜。在每一象素中选取一定数量的采样点，作 为初始光线起点选取其中一点向透镜的中心发射一光线。根据给定透镜的焦距， 即可确定该象素点在透镜后的聚焦点，然后在透镜表面上分布式地选取相同数量 的采样点，并在该象素的采样点与透镜表面上的采样点间成对地连成一条条光 线。所有这些光线通过焦点后进入场景对它们进行前面介绍的分布式光线跟踪 后，取各条光线对视点的光亮度贡献的加权平均就可得到该象素的光亮度值。 运动模糊效果的模拟是计算机图形学的一大难题。一般来说，运动模糊是由 于物体和摄像机之间在曝光的瞬间有一相对运动而产生的。c o o k 将前述的分布 式采样原理应用于时间域中，其具体方法是在时间城内随机分布地通过某一象素 向场景发射光线并进行跟踪，并将在定时间间隔内各光线对视点的光亮度贡献 进行加权平均就可得到该象素的光亮度值。 2 1 4p a c k e t 光线跟踪技术 在光线跟踪过程中相邻光线在光能传播过程中往往具有大致相同的路径。这 一性质启示我们，相邻光线之间具有空间连贯性( c o h e r e n c e ) 。对每条光线单独 进行跟踪并不是一个好的主意。通过光束跟踪的方法来利用光线之间的连贯性， 从而有效地提高了光线跟踪算法法的效率。 考虑到经曲面反射或折射后，相邻光线会向四周散射，从而改变相邻光线在 空间传播的连贯性，将场景限制为多边形场景，类似于光线跟踪中的光线树，光 束跟踪过程也可以用一棵光束树来描述。光束树中的边来表示被跟踪的光束，结 第二章光线跟踪技术和空间加速结构 点表示光束和场景中多边形的交点。在光线跟踪过程中，光线与景物表面的相交 为一个点，而光束跟踪时，光束与场景中景物表面的相交为一个或多个多边形， 因此光束树中的结点为一多边形。 光束跟踪的关键是如何定义光束( 包括确定反射光束和折射光束) ，使得计算 光束和景物的相交简单方便。传统的有b e 锄r a yt r a c i l l g 、圆锥光线跟踪技术及 利用s i m d 的p a c k e t 光线技术。 b e 锄r a y s 【2 。7 】从视点出发的原始光束投向整个屏幕，形成一视域四棱锥，但 采用棱锥表示光束不容易确定光束和景物的交点。为了解决这个问题，可对场景 中的景物进行线性变换包括透视变换，将它们从景物坐标系变换到屏幕坐标中。 在屏幕坐标系中视域棱锥体己经变为一个往体，视点被变换至无穷远处。一般地， 我们可将光束定义为在光束坐标系x y 平面上的多边形( 称为光束多边形) 沿z 轴平扫形成的柱体，这里光束坐标系为每一光束的局部坐标系。显然初始光束的 光束坐标系即屏幕坐标系，初始光束结点( 即光束树根结点) 包含了屏幕上可见 的所有多边形。 a m a i l t n e s 【2 8 】提出圆锥跟踪算法来模拟表面模糊反射和半影效果。由于采用 圆锥光束取代每一条象素光线算法有效地克服了图形走样现象。在圆锥跟踪算 法中，采用正圆锥来表示一束光线，取代标准光线跟踪算法中的理想光线。每一 圆锥光束均由三个参数确定，它们是锥顶、中心轴线和锥角。算法首先以视点为 锥项，以一个象素宽度为半径构造初始圆锥光束，并跟踪进入场景，计算其圆锥 光束中心轴线的镜面反射方向和折射方向，以产生反射圆锥光束和折射圆锥光 束。如果一条光线遇到一表面，由于该表面不完全光滑，因而产生了一镜面反射 圆锥光束和规则透射圆锥光束。镜面反射圆锥光束交于场景中的景物，形成一个 交区域，该交区域中所有点的光亮度聚集起来，将对表面上交点处产生光亮度贡 献。这样表面上反射出景物的模糊镜像。显然，景物镜像的模糊度取决于圆锥光 束在景物上交区域的大小。因而，锥角的大小反映了景物表面的粗糙程度。如果 锥角大小保持不变，则表面与景物之间的距离越大，光束与物体的相交区域就越 大，故上述模糊度亦依赖于景物眉与表面之间的距离大小。在圆锥光束跟踪中， 除了要求出圆锥轴线与景物表面交点之外，还要计算圆锥与所有景物表面相交的 区域，并计算该区域对锥顶处的光亮度贡献。因而圆锥算法的关键是如何计算圆 锥与景物表面的交区域。对一般的参数曲面来说，该交区域酌计算是非常困难的。 为简单起见，可以将场景表面限定为球面和平面多边形。 s i m d 光线束跟踪尽可能的发掘光线跟踪算法的相关性。我们的主要方法是 发掘第一级光线和s h a d o wr a y s 的相关性，主要体现利用并行的光线包在遍历算 法、求交算法和着色算法。我们利用这种算法通过s i 加指令对多个光线进行并 第二章光线跟踪技术和空间加速结构 行来减少算法的计算时间，通过仅仅查询光线包的数据来减少内存的带宽，与此 同时提高高速缓存的命中率。一些现代的微处理器架构提供单指令多数据流的并 行机制，它允许扩展浮点数的指令对四个浮点数进行操作，可以产生重要的浮点 加速。这对于3 d 图形来说有着重要的应用，这样的扩展指令例如h n e ls s e 【2 9 】， p 山m3 d n o w 【3 0 】和i b m 胛v i o t o r o l aa l t i v e c 洲。利用光线包和s i m d 指令操作可以 加速光线跟踪器的内核速度，体现在三角形求交、光线遍历和着色等方面。 2 2 原始的空间加速结构 目前常用的空间数据结构为获得层次遍历以及能够实现基于物体空间和图 像空间的剔除，需要将场景信息按一空间数据结构组织。空间数据结构是数据的 一种表示形式，可以将几何体数据组织在三维空间中。这种数据结构可以用于判 断几何体相互关系的加速查询，如裁减算法、光线跟踪以及碰撞检测等。目前空 间数据结构的组织通常是采用层次结构的方法。这种结构具有嵌套和递归的特 点，可以有效提高查询速度，计算复杂度通常从简单提高到复杂。但大多空问数 据结构的构造和实时更新开销都比较大，通常还需要一个预处理过程，因此较适 用于静态场景。目前常用的场景数据表示方法有：b s p 树( b i n a 可s p a c e p a n i t i o 血n gt r e e s ) 、八叉树( o c 仃c e ) 、层次包围体( b o u n d i i l gv o l u m eh i e r a r c l l i e s ， 简称b s ) 以及空间网格( 西d ) 表示等方法。 2 2 1 空间二叉树 b s p 【3 2 】叫( b 渤拶s p a c ep a n i t i o n ) 空间二叉树算法，即把场景分成许多子空间， 每个父结点都有两个子结点。场景为最大父结点，场景下包含两个结点( 左右结 点) ，若左结点包含的几何单元体数目大于阀值，则把左结点分成上下两个子结 点，再看上下结点中的几何单元体数目，如此剖分直到子结点深度大于阀值。当 求交时只需把光线与左右结点求交，若左结点有交则只需把光线与上下结点求 交，最后把光线与确定的空间结点中的有限几何单元体求交。这样就可以节省大 量无用的求交。 对于虚拟场景的实时绘制而言，b s p 树的最大优点是可以构造较好的均衡 树，尤其是当场景中对象不均衡分布时，从而减少树的深度。这样实时渲染时， 可以快速遍历整个场景，加速场景绘制。然而，对于场景中的动态对象渲染需要 花费昂贵的树结构更新代价，每一次动态对象渲染时将其加入到静态树结构中绘 制，然后重新移去动态对象。 第二章光线跟踪技术和空间加速结构 2 。2 。2 空间八叉树 空间八叉树 3 3 】采用类似于二维的四叉树结构对场景进行空间细分，整个三维 空间被细分成小的立方体。这些立方体通过采用递归的方式组织成层次结构，以 便对每个区域所包含的对象进行细分直到满足所需的分辨率为止。场景的八叉树 层次结构在预处理阶段生成，实时绘制时依据视点变化对树结构进行自适应的修 改。树结构也可用于对场景进行视域体裁减计算和其它可见性计算以及虚拟场景 的碰撞检测等。对场景进行八叉树细分能很好的支持建筑场景空间几何剖分。 空间八叉树算法是一个空间非均匀网格化分算法。该算法将合有整个场景的 空间立方体按三个方向中剖面分割成八个子立方体网格，组织成一棵八又树。苦 某一子立方体网格中所含的景物面片数大于给定的闭值，则对该子立方体网格做 进一步细分。上述细分过程递归地进行直至八叉树中每一叶结点子空间所含景物 面计数均小于给定阂值为止。进行光线跟踪的算法从光线起始点出发，沿光线前 进方向依次确定光线穿越的八叉树叶结点网格，若当前叶结点网格为非空结点， 则光线与它所包含的景物进行求交测试。若求得光线与景物的第一个交点，则结 束对该条光线的跟踪；若没有相交或当前叶结点为主网格，则沿光线前进方向继 续进行搜索，进入与当前空间网格相邻的下一叶结点网格进行求交测试。与 3 d d d a 【3 4 】【3 5 算法相比，空间八又树算法的优点在于它可以根据景物在场景中的 实际分布，对场景空间做非均匀剖分。在一般情形下，对场景空间的八又树剖分 所生成的空间网格数总是比3 d d d a 均匀剖分生成的网格数少。因而空间八叉树 算法可适应复杂场景光线跟踪的需要。 2 2 3 空间网格 空间网格【3 6 这种加速结构将三维空间沿着轴线分成均匀等大小的立方体空 间，这些小空间叫做v o x e l s 。每一个v o x e l 纪录着占据这个子空间的几何单元体， 对于一根光线，按照顺序穿过每一个v o x c l 与其包含的几何单元体进行求交测试。 因为光线穿过的v o x e l 是从远到近的排列，如果光线与某物体相交测试退出遍历， 这个物体一定是最近的物体。 2 2 4 结构包围体 包围体就是包含一组物体的空间体，要比所包含的几何物体形状简单的多。 包围体形式主要有：球体、椭圆体、轴对齐包围盒( a 撕s a l i g n e db o l u l d i l l gb o x ， 简称丸蝠b ) 、有向包围盒( o r i e n t e db o u n d i l l gb o x ，简称o b b ) 等【3 7 1 ，可用于 场景的可见性计算和碰撞检测，从而加速场景的处理。 第二章光线跟踪技术和空间加速结构 简单包围盒技术的效率并不十分高，其原因在于被跟踪光线与场景中每一景 物的包围盒都必须进行求交测试以决定是否需与其中所含景物进行求交计算，算 法的复杂性为o m ) ，这里n 为场景中景物的数目。包围盒技术的一个重要改进 是引进了层次结构，其基本原理是根据景物的分布情况，将相距较近的景物组成 一组局部场景，各相邻组又可组成更大的组，整个场景就被组织成树状层次结构。 算法同时建立起各结点局部场景的包围盒，其根结点即为整个场景及其包围盒。 被跟踪的光线首先进入该层次结构的根结点，并从根结点开始从上至下与各 相关结点的包围盒进行求交测试。若某一结点的包围盒与光线相交，则光线将递 归地与其子结点进行求交测试；反之，则该结点所含的所有景物必不与光线相交， 因而对该结点及其子树无需继续作任何测试。显然，层次包围盒技术通过减少光 线与景物( 包围盒) 的求交测试次数来提高算法的效率。设n 为场景中的景物 个数，则采用层次包围盒技术后，光线与景物求交测试计算复杂度降o ( 1 0 9 n ) 。 2 2 5 场景图表示 b s p 树和八叉树等空间数据结构都使用某种类型的树作为基本的数据结构， 均以层次形式来保存几何物体：与树结构表示相反，场景图( s c e n eg r 印h ) 【弼j 表示方法企图用包围体将场景中的对象包围起来，场景图是一有向的、简单的连 接图。三维场景除了模型的几何数据，还有模型变换、层次细节、纹理材质和光 源等信息。基于场景图的图形编程接口库，提供了各个细节上的场景管理与操作 能力。例如，如何交互，如何进行可见性计算( 剔除) ，如何对当前绘制模型进 行有效的简化。对于大数据量场景来说，不可能将全部的数据一次读入到内存中， 而必须是根据场景的变换在外存、内存之间动态调度。根据漫游者观察视点的逐 步变化，把将要落入到可视区域内，同时内存中暂时没有的数据被读入到内存中， 同时由于内存容量有限，必须将暂时不用的数据所占用的内存空间释放掉。 在漫游过程之中，随着视点的移动，场景中活动结点所表示的数据块首先进 行可见性判定，如果该地形块位于视域之内且可见，并且该结点所包含的网格数 据不在内存之中，则把对该网格数据块的请求加入到数据块网格载入请求缓冲 区，等待负责i o 的线程进行处理。而那些虽然为活动结点，但是却不可见的地 形块数据，却并不需要载入内存，又由于每次装载的数据都是代表某一块的批数 据，因此可以减小数据调度粒度，节省系统资源的耗费。整个运行时刻采用双线 程的运行机制，主线程负责场景l o d 的计算，活动结点的可见性判定，并且将 最终需要绘制的模型数据送至g p u 去绘制；而i o 线程则专门负责数据请求的 处理和数据的读取和丢弃。在两个线程之间采用互斥机制的以达到同步运行，协 同工作的目的。 第二章光线跟踪技术和空间加速结构 2 3 动画场景的组织和分类 本论文主要研究利用光线跟踪技术渲染动画场景。动画场景还没有一个完整 明确的定义，动画场景范围宽泛，变化范围包括从单个移动的三角形面片到在一 个静态场景中到两个连续的帧之间没有相同的三角形面片。静态场景的定义是几 何体从一帧到另一帧没有变化；一个部分静态场景的定义是一定量的几何单元移 动，而且其他部分保持静止，例如，几个人物移动穿过静态的游戏环境，或者是 场景中的一小部分总是在移动。 通常几何单元的移动方式可以被分成层化的、半层化的和无层化的三种。层 化的运动是指如果一个场景的几何单元体可以被分成组，某一个组所包含的几何 单元体可以组成一个物体的线性或刚体的变形，每一个组可以看成一个物体。与 层化的运动相反的是无层化的运动，每一个几何单元体彼此间独立运动。半层化 的运动是指场景被分割成物体，物体对于几何单元体来说是有层化结构的，但物 体之间的运动是相互独立的，没有层化关系。 此外，对于单个几何体的移动，动画变化可以按照其影响场景的拓朴结构变 化进行分类。通常，一个物体被存储在三角形网中，动画表现为移动某些顶点但 是三角形网的链接性没有变化，我们定义这种变化为变形场景。当然任意的变化 都可以改变场景的拓朴结构，包括链接性的改变、增加或删除几何单元体。本论 文使用部分变型的场景，整个场景变型的模型会非常复杂。 实际上，不同的应用使用不同种类的动画。例如，一个设计的应用可能用静 态的场景或者半层化的场景去完成汽车或飞机的部分零件，随着时间会有增加或 删除物体的操作，但是不会有非层化的运动。事实上，游戏可以在同一时刻包含 各种运动。例如，飞行模拟游戏或者第一人称射击游戏，可能包含一些静态场景 和一些无层化的运动像爆炸。在游戏中，会有一些独立的物体具有层次化的运动， 像飞行器和野兽。许多物体本身可能存在无层化的运动，像物体的出现或消失。 除此以外，人物可能是蒙皮结构的，这是很好的半层化运动的例子。没有一项技 术可以完全管理所有种动画的运动场景。 第三章空间加速结构的设计、实现和分析 第三章空间加速结构的设计、实现和分析 本章主要提出了四种改进型的空间加速结构( b v h s a h 、b s p s a h 、b m k d 骶e 、 鲥d k d 仃e e ) 的设计与实现的具体过程，并且对四种空间加速结构进行了比较， 分析了其不同的适用条件和特点。最后，还分析了空间细分于物体层次架构的各 自特点。 3 1 具有代价模型的结构包围体( b v h s a l l ) 的设计与实现 3 1 1 基于s a h 的代价模型 场景树的建立会影响光线遍历的效率和效果，所以，构造一个高效的场景树 对光线跟踪器来说是是十分重要的工作。h a r v e n 【l l 】在分析k d t r e e 的构造算法中详 细的介绍了基于s a h 【3 9 】代价模型的慨念，这是一个基于表面积概率的贪心算法。 基于s a h 的代价模型用于优化b v h 的构造最早由g o l d s l l l i t h 和s a l m o n m 】进行过 初步的分析。 s a h 可以简单的描述为：如果一条任意的光线与根结点的包围体相交，那 么这条光线与几何体相交的概率为几何体的表面积除以包围体的表面积。整棵树 的全局代价模型可以表示为： 卜。象2 警朋一。邑挚乙3 钔 b = n o d e a r o o ib = l e n r o o t t 表示全局代价模型，a 表示表面积，t a a 明表示光线与包围盒的求交代价， k 表示光线与几何体的求交代价。一个近似的贪心策略可以用到b v h 的自顶向 下构造过程中，每一次递归过程分割集合s 成两个子集s l 和s 2 ，直到s 足够小 可以成为一个叶子结点。每步的分割过程可以由( 3 1 ) 式推导出二叉分割树 的代价模型为： t = 2 t 柑b b+ 器忡。几十等忡2 儿矧3 第三章空间加速结构的设计、实现和分析 其中s 表示整个集合，s l 和s 2 表示分割后的两个集合，n 表示集合中几何 单元体的数目。 3 1 2b v h s a h 的构造算法的设计与实现 将s a h 代价模型导入到b v h 的构造算法中，其流程图如下所示： 图3 1b v h s a l l 构造流程图 每次根结点所包含的几何单元体被分割到两个包围体中，两个包围体可能有 相交的区域，其中的几何单元体被记录在两个结点中。 。 3 1 3b v h s a h 的光线遍历算法的设计与实现 b v h 属于对象层次结构体，其光线遍历算法不同于空间细分光线遍历算法， 第三章空间加速结构的设计、实现和分析 其空间示意图如下： 图3 2b v h s a h 光线遍历图 y 光线与根结点包围盒的交点的沿轴距离为t i l l a x 和n 1 1 i n ，与两个子结点的包 围盒交点沿轴距离分别为t l i l l i n 、t l m a x 和t 黜i l i n 、t r m a x 。分别对两个子结点进 行查询，确定是否将两个子结点都放入待求交运算的栈中。算法的伪代码描述如 下： a x i s = n o d e - s p l i 沁i s ( ) ；确定分割轴 i f ( r a y o a x i s 】 s p l i t p o s ( ) ) 根据光线源点位置确定左右结点 f i l s t c k l d = n o d e + 1 ： s e c o n d c l l i l d = n o d e 一 a b o v e c l l i l d ；) e l s e f i r s t c l l i l d = n o d e 一 a b o v e c l l i l d ： s e c o n d c m l d = n o d e + 1 ；) i f ( ! s e c o n d c l l i l d 一 b v h b o x i n t e r s e c t p ( r a y ，& r 仃n j n ，& r t m a x ) ) n o d e = 伍s t c d ；选择左结点 e l s ei f ( ! f i r s t c h i l d 一 b v h b o x i n t e r s e c t p ( r a m & l 仃i l 氓& l n l l a x ) ) n o d e = s e c o n d c h j l d ：选择右结点 e l s ef 左右结点都进栈 t o d o t o d o p o s + + n o d e = s e c o n d c h i l d ； n o d e = f i r s t c h i l d ；) 第三章空间加速结构的设计、实现和分析 3 2 具有代价模型的空间二叉树( b s p s a h ) 的设计与实现 3 2 1b s p s a l l 构造算法的设计与实现 对于可视性检测，b s p 是使用非常广泛的空间数据结构。但是，原始的b s p 的在构造和遍历及内存高需求方面来看并不是一种好的数据结构【4 1 1 。将基于 s a h 的代价模型引入到b s p 的构造会提高b s p 的构造质量【4 2 】，进而提高光线遍 历b s p 的效率。其构造的流程图如下： 固 图3 3b s p s a h 构造流程图 三个轴向的中间分割面选择应用了代价模型，在最小代价的分割面上进行分 割，形成左右两个子空间，继续递归分割，直到空间中几何单元体的数量小于某 一值。 第三章空间加速结构的设计、实现和分析 3 2 2b s p s a h 光线遍历算法的设计与实现 b s p s a h 的遍历算法与传统的b s p 遍历算法有些类似，都是通过比较中间轴 的分割面到光线源点的轴向距离与光线和包围体的交点轴向距离的