（计算机科学与技术专业论文）基于gpu的光线跟踪算法研究与实现.pdf

基于g p u 的光线跟踪算法研究与实现 摘要 在游戏、c a d 、虚拟现实、电影电视特效等众多应用的推动下，光线跟踪算 法作为一种重要的真实感绘制技术被广泛地研究并得到了大力的发展。现代g p u 在通用计算方面的发展已经证明了它是一个适合加速光线跟踪任务的处理器。本 文着眼于g p u 上的光线跟踪算法，主要研究内容为：以流处理的方式在g p u 上 实现光线跟踪算法及其加速策略，具体工作如下： 首先，通过对g p u 流处理图形管线和b r o o k g p u 的研究，设计一个光线跟踪系 统的流处理模型，实现并验证该模型在g p u 上的流处理映射。 其次，提出基于g p u 的进入点搜索策略。该策略通过对光线进入场景的位置进 行预设，加速光线跟踪在g p u 上的遍历过程。进入点搜索不但可以有效地减少传统 的k d r e s t a r t 遍历算法所引入的冗余遍历步数，而且还具有越过空节点向下设置进 入点的能力，从而提高算法从k d 树结构获得加速的能力。算法使用短栈实现进入 点搜索，并利用掩码支持多光线的并行遍历，适合在g p u 的高数据并行结构上运行。 在b r o o k 平台下，对进入点搜索算法进行实验和分析的结果表明：采用进入点搜索 的算法在大多数情况下能有效地提高光线跟踪的绘制速度，在场景中物体遮挡关系 较为复杂时，进入点搜索可将光线遍历的速度提升1 0 以上。 最后，在进入点搜索算法的基础上，进一步提出层次化进入点搜索算法。该算 法支持对一束光线的遍历，能利用光线的空间相关性以减少平均遍历步数，并能缓 解进入点搜索算法因采用短栈而受到的限制，从而进一步提高绘制的速度。 关键词：光线跟踪；g p u 计算；流处理；k d 树；进入点搜索 i i 硕一l 二学位论文 a bs t r a c t w i t ht h ep u s h i n go fv a r i o u sa p p l i c a t i o n sr a n g i n gg a m e s ，c a d ，v i r t u a lr e a l i t y ， f i l ma n dt e l e v i s i o ns p e c i a le f f e c t s ，r a yt r a c i n ga sa ni m p o r t a n tr e a l i s t i cr e n d e r i n g t e c h n i q u eh a sb e e nw e l ls t u d i e da n dd e v e l o p e d m o d e r ng p u sh a v eb e e np r o v e nt ob e s u i t a b l ef o ra c c e l e r a t i n gr a yt r a c i n gt a s kt h r o u g ht h e i rg e n e r a lc o m p u t i n gp o w e r t h i s t h e s i sf o c u s e so ng p ub a s e dr a yt r a c i n g ，t h em a i nc o n t e n t sa r er e a l i z i n gr a yt r a c i n go n g p ua n da c c e l e r a t i n gg p ur a yt r a c e r t h em a i n w o r ki sa sf o l l o w s ： f i r s t l y ，t h r o u g hat h o r o u g hs t u d yo fg p ur e n d e r i n gp i p el i n ea n db r o o k g p u ，a s t r e a mp r o c e s s i n gm o d e lf o rr a yt r a c i n gi sp r o p o s e d t h em a p p i n go ft h i sm o d e lo n t o g p ui sr e a l i z e da n dv e r i f i e d s e c o n d l y ，ag p ub a s e de n t r yp o i n ts e a r c hs t r a t e g y i sp r o p o s e d t h i ss t r a t e g y a c c e l e r a t e st h et r a v e r s a ls t a g eo fr a yt r a c i n go ng p ub yp r e s e tt h ee n t r yp o i n to far a y i n t ot h es c e n e e n t r yp o i n ts e a r c hc a nn o to n l ys a v et h er e d u n d a n tt r a v e r s a ls t e p s i n t r o d u c e db yk d r e s t a r te f f e c t i v e l yb u ta l s oa l l o ws e t t i n ge n t r yp o i n tl o w e rb y s k i p p i n ge m p t yv o x e l s t h i se n h a n c e st h ea b i l i t yt h a tt r a v e r s a ls t a g eb e n e f i t sf r o ma w e l ld e s i g n e dk d t r e ec o n s t r u c t i o ns c h e m e s h o r ts t a c ki su s e dt or e a l i z et h ee n t r y p o i n ts e a r c h ，a n dm a s k i n gi su s e dt os u p p o r tp a c k e tt r a c i n g t h e r e f o r e ，t h ea lg o r i t h m c a nw o r ke f f i c i e n t l yo nt h ed a t a p a r a l l e ls t r u c t u r eo fg p u e x p e r i m e n t sa r ec a r r i e do u t u n d e rb r o o ke n v i r o n m e n t t h er e s u l t ss h o wt h a ti nm o s tc a s e s ，e n t r yp o i n ts e a r c hc a n i m p r o v et h er e n d e r i n gs p e e de f f e c t i v e l y i ns c e n e sw i t hh i g ho c c l u s i o n ，t h et r a v e r s a l t i m ec a nb es a v e db ym o r et h a n1o l a s t l y ，o nt h eb a s i so fe n t r yp o i n ts e a r c ha l g o r i t h m ，af u r t h e ro p t i m i z a t i o no f h i e r a r c h i c a l e n t r y p o i n ts e a r c ha l g o r i t h mi sp r o p o s e d t h i sa l g o r i t h ms u p p o r tr a y b u n d l et r a v e r s a l ，c a na d o p tt h er a yc o h e r e n c et os a v et r a v e r s a ls t e p sp e rr a y ，a n da l s o a l l e v i a t et h er e s t r i c t i o no ne n t r yp o i n ts e a r c hm a d eb ys h o r ts t a c k s oi ti se x p e c t e dt o f u r t h e ri m p r o v et h er e n d e r i n gs p e e d k e yw o r d s ：r a yt r a c i n g ；g p uc o m p u t i n g ；s t r e a mp r o c e s s i n g ；k d t r e e ； e n t r yp o i n ts e a r c h i i i 基于g p u 的光线跟踪算法研究j 实现究 插图索引 图2 1 光线跟踪原理5 图2 2 递归光线跟踪流程7 图2 3 层次包围盒示例1 1 图2 4 通过一致空间细分跟踪一条光线1 2 图2 5 一个k d 树的示例13 图3 1 非统一渲染管线1 5 图3 2 非统- n 统一渲染架构的趋势1 5 图3 3b r o o k 的系统架构17 图3 4 流处理模型1 8 图3 5b r o o k 的流声明方式1 8 图3 6b r o o k 的流操作函数1 9 图3 7 一个核函数定义的示例2 0 图3 8 纹理内存中存储场景网格2 2 图3 9 多通道方法实现核的连接2 3 图3 1 0 光线跟踪的流处理模型2 4 图3 1 1 光线三角形相交测试函数2 5 图4 1 一个k d 树遍历的示例2 8 图4 2 光线穿过体素的三种情况2 9 图4 3 通过更新光线有效段跳过已处理的体素3 0 图4 4 一个p u s h d o w n 策略的示例3 1 图4 5 进入点搜索算法伪码3 2 图4 6 使用短栈的进入点搜索算法伪码3 3 图4 7 将包中不活动光线a 屏蔽3 4 图4 8 进入点搜索算法流程3 5 图4 9 从o 点发出的光束只经过分割面的一侧3 6 图4 1 0 从o 点发出的光束跨越体素的分割面3 7 图4 1 1 平截头剔除算法的示意图3 7 图5 1 以初始光线对实验数据进行绘制的结果4 2 图5 2 使用不同的渲染核绘制的结果4 2 图5 3 进入点搜索算法的实验场景4 3 v i 硕j j 学位论文 附表索引 表4 1 在一些场景上进入点搜索算法对遍历步数的影响3 9 表5 1 对实验场景进行绘制的耗时4 2 表5 2 采用进入点搜索算法前后的绘制速度比较( 5 1 2 x 5 1 2 分辨率) 4 4 表5 3 采用进入点搜索算法前后的绘制速度比较( 1 0 2 4 1 0 2 4 分辨率) 4 4 v i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 堡素 日期：2 7 年6 月g 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 2 去 ； 赳 1 勺专 日期： 叩年占月君日 日期：呻年f 月吕e t 硕上学位论文 1 1 引言 第1 章绪论 绘制技术是计算机图形学的一个重要分支。绘制是指使用计算机程序将使用 某种特定语言或数据结构描述的三维场景模型在计算机屏幕上显示出来的过程。 以绘制结果是否贴近现实世界中的视觉效果为标准，绘制技术可以分为真实感绘 制和非真实感绘制。其中，真实感绘制力求逼真地模拟现实中的光学效果，从而 使绘制的结果产生如相片一般的视觉感受，所以有时它也被称为照片真实感绘制。 真实感绘制在生活中几乎随处可见。真实感绘制用于机械和建筑行业的辅助 设计，生成产品或建筑物的效果图不仅可以节省生产样品的开销，更重要的是能 够便于设计者进行交互式地调整修改，缩短设计难度和周期；依赖真实感绘制实 现的虚拟现实技术也在战斗训练、游戏开发、模拟验证等应用中大受欢迎；在如 今的电影电视拍摄、广告设计中，用计算机制作特效画面常用于代替无法实拍或 者成本过高的场面，其真实感已能让观众难辨真伪。随着各类产业和生活需求的 推动，各方面的应用不断地要求真实感绘制算法向更高的真实度、更快的绘制速 度上发展。 1 2 研究背景及意义 纵观当今常见的用于真实感图形的绘制技术，主要包括如下几种【卜3 l ： 1 光栅化。光栅化循环地访问场景中的各个图元，直接修改与该图元相应的 屏幕像素的值，从而将用图元描述的向量图转化为用像素描述的光栅图。 2 光线投射。光线投射将屏幕看作一个连通待绘制场景的窗户，从视点出发 通过屏幕上的像素向其后的场景中投射出的光线将进入到待绘制场景中。 当光线碰撞到物体时，利用光线和碰撞表面的属性计算对应像素点的颜色 值。 3 辐射度算法。辐射度算法利用有限元方法模拟光的散射现象，被直接光照 的表面也可作为间接光源对周围的表面产生光照。辐射度以物体间交互光 照的方式产生图形。这种算法能产生更真实的软阴影，更有效地表现如颜 色渗出等室内物体间的相互作用。 4 光线跟踪。光线跟踪的原理类似于光线投射，但是光线不在碰撞到第一个 物体后停止，而是可能从这一点上产生阴影、反射、折射等新的光线，算 法继续对这些光线进行跟踪，绘制光线路径上的其它碰撞点。 基于g p u 的光线跟踪算法研究与实现 这几种绘制技术各有其特点。光栅化的绘制速度最快，是目前大多数显卡所采 用的渲染方法，但是它仅仅是场景物体到屏幕平面的映射，并没有给定计算颜色的 方式，不能支持高级的光照效果；光线投射以像素为单位进行绘制，通常比以图元 为单位进行绘制的光栅化方法慢，但它可以结合光线属性、光强等信息决定像素颜 色，从而获得更逼真的效果；辐射度算法从光能分布的角度考虑物体间相互照射的 效果，其光照模型较其它算法更为准确，但辐射度算法一般仅用于纯漫反射的环境 而不能处理镜面或透明物体；光线跟踪可以模拟反射、折射、散射、色散等多种高 级光学效果，这些效果是其它绘制方法所难以达到的。 正是由于光线跟踪在直接光照效果体现中的独有优势，并且通过选择合适的方 法进行跟踪和渲染，光线跟踪还可以方便地融合如辐射度等算法支持的间接光照效 果【4 6 】，故而单从绘制结果的真实性来说，光线跟踪是目前最为理想的选择，光线 跟踪算法也因此成为目前真实感绘制技术的主要发展方向【7 1 。但是光线跟踪算法的 复杂度相当高，尤其是使用高级的渲染效果时。相对较慢的绘制速度使得算法的应 用受到极大的限制。所以和提高算法的真实度一样，加速光线跟踪算法的运行始终 是对光线跟踪算法的研究热点。 在进行光线跟踪时，提高绘制速度的代价往往是牺牲结果的真实度【8 】。为解 决这个问题，许多研究着眼于用硬件加速算法。由于g p u 是几乎每台p c 机都有 配置的图形设备，这使得g p u 光线跟踪可以几乎无成本地得到应用，因此近几年 利用g p u 加速光线跟踪任务成为了一个重要发展趋势。本文的工作正是在上述背 景的驱动下进行的。 1 3 本文的研究内容 在已有的同类工作基础上，本文主要从以下几个方面对基于g p u 的光线跟踪算 法进行了研究： 1 在g p u 并行加速方面，通过对流处理计算模型和b r o o k g p u 的研究，分析以 核和流的形式建模的光线跟踪系统。通过实验验证了该流处理模型在g p u 上的实现。 2 在加速光线跟踪算法方面，分析了现有k d 树遍历方法的不足。提出使用进 入点预设的改进方案，通过引入的进入点搜索算法，使光线能跳过不经过 的和空的体素从树的中间节点重新开始遍历，从而节省遍历步数，提高绘 制的速度。 3 在进入点搜索算法的基础上，进一步提出采用光束跟踪的方法实现层次化 进入点搜索。层次化进入点搜索可利用光线的空间相关性降低平均遍历步 数，并缓解算法因采用短栈而受到的进入点深度限制。 2 硕上学位论文 1 4 本文的组织结构 第一章概述了本文的研究背景、意义以及本文的主要工作和组织结构。 第二章详细介绍了基于光线跟踪的绘制技术，分析了各种绘制方法的优缺点， 并综述了加速光线跟踪算法的各种技术，为后文进行的研究打下理论基础。 第三章分析了g p u 的流水线结构和b r o o k 流处理计算的特点，给出了一个光线 跟踪算法的流处理模型。 第四章对基于g p u 的k d 树遍历进行了讨论，提出并详细介绍了一种基于g p u 的k d 树遍历算法。 第五章在b r o o k 平台上对第三章和第四章的内容进行了实验和分析。 最后是全文的总结和展望。 基于g p u 的光线跟踪算法研究与实现 2 1 引言 第2 章光线跟踪算法概述 光线跟踪是一种被广泛应用的绘制技术，在其几十年的发展历程中，出现了许 多基于跟踪光线路径这一思想的绘制算法。这些算法虽然都被笼统地称为光线跟踪 算法，但在实现层面上却是有根本区别的。本章将从光线跟踪的原理开始，概述光 线投射、w h i t t e d 光线跟踪和基于光线跟踪的一些其它技术，随后详细地描述了本 文的研究对象一一递归式光线跟踪的流程，最后综述光线跟踪算法的加速策略，为 本文后续章节的研究提供理论基础。 2 2 光线跟踪绘制技术 2 2 1 光线投射和光线跟踪 光线跟踪是一种以模拟现实世界中的光线传播为绘制方式的算法。在现实世 界中，光线由光源发出，它们向四周发散直到被某个物体的表面挡住。此时，光 线的能量可能以四种形式被转化：吸收、反射、折射和荧光。一个物体可能向一 个或多个方向反射所有或者部分的光；它也可能吸收一部分的光能致使反射或折 射光的光强降低；如果该物体是透明或半透明的，一部分光会发生折射进入物体 内；在极少的情况下，物体会吸收部分的光能并以荧光的形式向周围随机的方向 发出荧光。这些被反射、折射或发射出去的光线可能再次碰到其它物体。同样地， 吸收、反射、折射和荧光可能再次作用于入射的光线。经过许多次这样的过程， 从光源发出的一部分光线最终传播到人眼中，使人们看到这个场景。 跟踪光线进行绘制的思想最早为a r t h u ra p p e l 1 】于1 9 6 8 年提出，并形成了光 线投射算法。在光线投射算法中，光线从眼睛发出，透过屏幕像素进入场景。算 法找出场景中挡住光线的物体，并在对应的屏幕像素上绘制这个点的颜色。光线 投射也常用于体数据绘制，其思想是在光线穿过数据体时，累计其路径上采样点 对像素颜色值的贡献。采用从眼睛出发逆向地跟踪光线而不是像自然界中一样从 光源开始跟踪光线，是因为大多数光源发出的光线最终不会进入人眼，对成像没 有任何贡献。跟踪从眼睛出发的光线避免了对这些无效光线的计算，可以将算法 效率提高几个数量级。一个跟踪从光源发出的光线的例子是光子映射算法【9 】，其 时间消耗就远远高于以眼睛为光线出发点的光线跟踪算法。 相比光线投射中光线仅沿着发出的方向前进，由w h i t t e d 3 】提出的算法才称得 上是真正意义的光线跟踪。在w h i t t e d 光线跟踪中，对光线的跟踪并不在第一次碰 4 硕l | 学位论文 撞到物体后就结束，而是在每个碰撞点，可能衍生出三种新的光线：反射线、折 射线和阴影线。如图2 1 所示，反射线会沿反射方向继续前进直至碰撞到下一个物 体。因为反射线与初始光线对应的是同一个屏幕像素，所以只要在渲染这一像素 点时计入反射线的颜色就能够在镜面位置上绘制出其中的影像。同样地，折射光 也将进入透明物体继续前进。光线在进入不同的介质时可能发生转向，跟踪折射 线可以在绘制时体现出透明物体中影像的变形效果。阴影线由碰撞点指向光源， 用于判断该点对光源是否可见。算法依据判断的结果绘制阴影并停止对不可见光 线的继续跟踪。在光线经过一定的碰撞次数或完成一定的行程而没有获得交点时， 算法停止跟踪，并采用某一种渲染方式更新各个像素的颜色值，完成整个画面的 绘制。至此，光线跟踪得以将隐藏面消除、直接光照物体的明暗处理、全局镜面 的相互作用效果和阴影计算结合到一个模型中，成为一个经典的绘制算法。 图2 1 光线跟踪原理 2 2 2 基于光线跟踪的全局光照方法 在光线跟踪被提出之后的几十年中，出现了许多基于光线跟踪的全局光照方 法。如基于蒙特卡洛方法的路径跟踪【4 】和分布式光线跟踪【5 1 ，从光源和眼睛出发沿 两个方向跟踪光线的双向路径跟踪算法【6 1 和光子映射方法【9 1 。 蒙特卡洛方法是一种基于统计采样的估计方法。采用蒙特卡洛方法模拟场景 中的光照分布时，通过每个屏幕像素可能发出多条光线进行采样，在每个碰撞表 面也不再仅仅沿着几何光学的反射方向发射出单一的反射线，而是用随机采样的 方式向多个方向发射出多条光线，算法将这些光线的结果汇总在一起进行绘制。 采用蒙特卡洛方法进行光线跟踪能够提高算法的抗锯齿能力、生成运动模糊效果 以及模拟散射光照。 采用双向光线跟踪的动机是增强绘制结果的真实性。跟踪从眼睛出发的光线 幂于g p u 的光线跟踪笄泫研究j 实现 能生成很真实的直接光照效果，而跟踪从光源出发的光线则能更好地模拟场景中 的间接光照效果，如光线穿过透明物体后聚集到另一个物体表面的焦散现象。早 期的双向路径跟踪算法使用存储光照信息的方式将两个方向发出的光线结合起 来。光线分别从光源和眼睛出发并在漫反射表面上结束，算法通过光线图或照明 图将第一条光线获得的光照信息传递给第二条光线。类似地，光子映射算法也首 先跟踪从光源出发的光子，获得光子在场景中的分布状态，并将这些光能分布信 息存储在一个空间数据结构( i i 光子图) 中，然后算法跟踪从眼睛发出的光线，找到 第一个挡住光线的物体，并使用之前获得的光子图估算在这一点的光照。在这两 种方法中，相比双向路径跟踪，光子映射算法用粒子密度分布表示光照强度，生 成的光子图可以在渲染时重复使用，从而大大提高了渲染速度。 2 2 3 场景表示 场景一般是用几何体图元在三维空间中对物体进行建模来表示的。这些图元通 常是简单的几何形状，如多边形、球形、锥形等。但对于光线跟踪算法，不论用什 么方式表示物体，只要能计算出物体表面与光线的交点，就可以进行绘制。所以光 线跟踪处理的场景可以包含一些更复杂的图元，! 女ib 6 z i e r 1 0 1 或n u r b s 曲面【1 1 1 、等 值面【1 2 】等等。 能绘制几乎所有的图元常被认为是光线跟踪的一个重要特点。如果某些复杂的 图元无需细化为三角形就可以直接地进行光线跟踪，对它们的处理就不会产生离散 失真，而保留较高的精度。此外，不进行细化还可以大大地提高算法效率，比如光 线与球面的交点就可以很快地获得，而用三角形建模球体则需要生成大量的三角形 以保持精度。 但是，仅采用三角形建模场景也有其优势，能够简化数据的写入和维持，使算 法更为简洁，从而大大简化算法的设计和优化。在后文的介绍中我们将会看到，在 g p u 计算中，三角形数据可以非常方便地映射到纹理内存中。加之在诸如虚拟现实、 c a d 、电影特效制作等实际应用的场景中，一般很少出现标准球体或其它的高次 图元。即使存在少数的高次图元，这些图元也都能够细化为三角形模型。基于这些 原因，本文讨论的算法只考虑三角形描述的场景。 2 2 4 递归光线跟踪算法流程 以w h i t t e d 的算法为代表，典型的递归光线跟踪一般包含光线生成、光线遍历、 相交测试、渲染和光线衍生几个步骤，见图2 2 。 首先，光线生成从视点位置通过每个屏幕像素向屏幕内的场景中发射出光线。 我们称从眼睛发出的光线为初始光线以区别反射、折射等衍生光线。给定一条光线 的起点位置r a y o r g 和方向r a y d i r ，光线上任一碰撞点h i t 到眼睛的距离厶。可以由公 式( 2 1 ) 计算获得，其中a 为任一个维。 6 硕i j 学位论文 t h n = ( h i t a 】一r a y o r g a ) r a y d i r a 】 ( 2 1 ) 光线跟踪的核心任务是找到光线和场景中物体的碰撞点。这就需要将光线和组 成场景的图元进行相交测试。显然，直接将每条光线对所有的图元进行相交测试会 带来令人无法接受的巨大开销。所以在算法进行相交测试之前，往往会经过一个加 速过程场景遍历。在算法开始进行遍历前，场景被预组织成某种便于快速地找 到光线附近物体的空间数据结构。常见的加速结构有b s p 树、k d 树、b v h 树等， 树中的每个节点都对应着场景中的一个体素。算法循着光线的路径遍历场景数据 体，返回可能产生交点的光线和节点对。 图2 2 递归光线跟踪流程 在相交测试这一步骤中，场景遍历返回的节点中所包含的所有图元将依次与这 条光线进行测试。如果光线在这个体素中没有产生交点，那么它将跨过这个体素继 续遍历位于其后的场景结构，直至得到有效的交点或者最终穿出场景。在获得有效 的交点时，这一点将被记录以便进行渲染。 光线在碰撞到物体以后，可能在这一点发生反射、折射等现象而衍生出新的光 线，见图2 1 。在算法的最后，根据碰撞点物体的表面属性和入射光线的类型决定 是否生成衍生光线，并将生成的光线送回场景的遍历过程。通过使用合适的权值分 配贡献比例，衍生光线将与初始光线共同决定所对应屏幕像素的颜色。 除能跟踪生成的衍生光线外，渲染也是光线跟踪的一个非常重要的特性。光线 跟踪算法几乎可以采用任意的方式计算光线的颜色。早期的a p p e l ，w h i t t e d 和c o o k 基于g p u 的光线跟踪算法研究与实现 等人仍使用简单、固定的光照模型。但研究者们很快发现，通过修改渲染的方式可 以方便地更换物体的视觉效果。自此以后，出现了许多的渲染方法，包括女h b l i n n 、 p h o n g 、l a f o r t u n e 等各种光照模型、纹理映射、凹凸映射、各种摄像机模型、位移 映射、过程映射等【1 3 】。光线跟踪之所以被众多绘制算法采用正是得益于其渲染方 式的多样性。 光线跟踪因其绘制结果的高度真实性而极为流行，但是早期的光线跟踪却并 不能达到照片真实性。这是因为对光线的跟踪往往是一个递归的计算过程，随着 光线的反射或折射，参与计算的光线数量不断增加，而对这些光线的处理都是相 互独立的，无法通过在像素间共享一部分计算得到有效地加速。受限于计算资源， 在实际应用中几乎不可能也不必完成光线从眼睛到光源的全程跟踪。大多的光线 跟踪系统都只是对现实光照的一个近似模拟，是绘制速度和图像质量之间某一个 程度上的折衷。 增加对光线的跟踪深度或采用2 2 2 节中介绍的方法进行绘制都可以提高绘制 结果的真实度。但采用这些方法的同时也给算法引入了更多的计算。直至今日，高 真实度光线跟踪的实现仍然依赖于昂贵的硬件设备，如何提高光线跟踪的速度始终 是光线跟踪研究的一个重要问题。 2 3 光线跟踪的加速策略 从光线跟踪的原理和流程可以发现：无论采用哪种绘制方法，只要涉及光线跟 踪，就不可避免地要对大量的光线进行相交测试。如果不采用任何方法加速，算法 9 5 的计算时间将被用于进行相交测试【3 】。加速光线跟踪从算法诞生起就是相关研 究的焦点，本文的研究目标也在于加速光线跟踪，所以在此对己存在的加速策略进 行归纳并作简单地介绍。 2 3 1 使用硬件加速绘制 目i j 已有的实时光线跟踪系统大多是基于工作站或计算机集群的，如基于 c e l l 的光线跟踪系统【1 4 1 和基于分布式系统的o p e n r t 【15 1 。除此之外，也有一些专 用的设备可用于光线跟踪的加速。物理计算处理单元p p u 能同时处理几万个物体的 相互作用，也能很方便地用于加速光线和物体的相交检测；s a a r l a n d 大学开发了专 用于光线跟踪的处理器d r p u 1 6 】，配合他们发布的高性能的光线跟踪引擎【1 7 】，该 系统也能进行实时速度的光线跟踪。这些方案的主要缺陷是它们都依赖于成本昂贵 的设备，对于游戏、c a d 和其他一些较小的应用，使用集群机或是采用专用设备 来进行绘制是不实际的。因此更多研究关注利用g p u 进行光线跟踪的加速。 g p u 是g r a p h i c sp r o c e s s i n gu n i t 的缩写，即图形处理单元，也有人称之为视 觉处理单元( v i s u a lp r o c e s s i n gu n i t ，v p u ) 。g p u 是专用于个人计算机，工作站或者 硕 ：学位论文 游戏机的图形设备。从7 0 年代最早出现的为a t a r i8 位计算机提供图形服务的 a n t i c 和c t i a 芯片起，经过2 0 多年的发展，g p u 已经形成了其独特的结构和 特点。现代g p u 不仅拥有超强的浮点数计算能力，同时具备了高度并行的体系结 构和超长流水线。 ( 1 ) 超强浮点计算能力。因为控制电路相对简单，对c a c h e 的需求少，g p u 可 以将大部分的晶体管用于计算工作，从而获得超强的浮点计算能力。此外g p u 通 常具有很高的内存带宽，这使得g p u 的计算速度远远超出同时代的c p u 。到2 0 0 8 年，顶级g p u 的浮点数计算速度已经达到9 0 0 g 次每秒，相当于当时顶级c p u 计 算速度的3 0 0 倍。 ( 2 ) 高度并行性。g p u 可以通过多条绘制流水线的并行执行来完成高度的并行 计算。最新的g t x2 8 5 中已配置多达2 4 0 个流处理器，能提供的相对于并行机而 言成本十分低廉的高效并行性。 ( 3 ) 超长流水线。g p u 图形流水线的设计以吞吐量的最大化为目标( 如n v i d i a g e f o r c e3 流水线有8 0 0 个阶段) ，因此g p u 作为数据流并行处理机，在对大规模 的数据流并行处理方面具有明显的优势。 g p u 最近的发展包括可编程渲染器的出现、提供抗锯齿能力的超采样和插值 技术、支持高精度颜色空间等。而可编程渲染器的出现和数字精度的提高使得开 发人员使用g p u 对一些非图形任务进行处理成为可能。这些使用g p u 执行通用 计算任务的努力逐渐形成了一个新的研究领域：基于g p u 的通用计算( g p g p u ， g e n e r a l p u r p o s ec o m p u t a t i o no ng p u ) 。目前，已经出现了许多进行g p u 编程的开 发工具，如n v i d i a 公司的c u d a 、a m d 公司的a t is t r e a m 和斯坦福大学的b r o o k 等。g p g p u 已经在大型矩阵和向量计算、蛋白质折叠、f f t 、光线跟踪、物理仿 真、序列匹配、语音识别、数据库、排序搜索、医学显影等许多方面有所应用。 第一个用g p u j j n 速光线跟踪的尝试是出现在2 0 0 2 年的r a ye n g i n e 1 1 7 1 。它仅仅在 g p u 上实现了光线和三角形的相交测试，g p u 仍需从c p u 获得几何体数据，二者之 间的通信延迟严重影响了算法的性能。同年，p u r c e l l 等人【1 8 1 模拟了用g p u 完成整个 算法流程的光线跟踪系统。在这个模拟实验中，g p u 被当作一个流处理器。由于 g p u 上进行k d 树遍历的困难，该实验使用较为简单的均匀网格作为场景加速结构。 这个基于流处理的光线跟踪算法不久就得到了实现【l9 1 ，并成为了后来许多g p u 光 线跟踪系统的基础【20 1 ，其缺陷在于加速结构不够高效，算法的性能过分依赖于内 存带宽。因此，后来的研究开始着眼于k d 树等其它加速结构在g p u 上的实现。 在光线跟踪算法中，g p u 不仅能进行光线和三角形的相交测试，也常被用于加 速对特殊表面的相交测试，如分段二次表面【2 i 】和n u r b s t l l 】。 9 基于g p u 的光线跟踪算法研究与实现 2 3 2 设计快速的相交测试算法 光线跟踪的相交测试实际上涵盖了三类问题：找到距离光线起点最近的交点； 找到光线路径上的任意一个交点；找到光线路径上的所有交点【2 2 1 。 通常情况下，光线跟踪需要解决的是第一类问题，即获得离光线起点最近的交 点。这时候，算法不仅需要找到与光线相交的图元，还要得到交点到光线起点距离 乙。以便于比较图元间的遮挡顺序。对于各种适合光线跟踪的图元，已经存在许多 不同的相交测试算法 2 3 , 2 4 】，这些算法在计算速度、简洁度、精确度上都有各自的特 点，所以对任何一种图元，并不存在一个“最优的”相交测试算法。 较为简单的情况是确定是否存在和光线相交的图元。这等同于测试两个点之间 是否可见，所以这种计算也常被称为“可见测试 或“遮挡测试”。使用阴影线进 行可见测试也是光线跟踪中非常常见的操作。这种相交测试比第一类相交测试更容 易实现。对一般的光线来说，需要进行多次相交测试来确定哪一个交点离光线的起 点最近。而对于阴影线，只要获得一个交点就可以结束测试。加速阴影线计算的方 法包括阴影缓存，自适应阴影测试【2 5 , 2 6 】等。 第三类需要找到并返回光线路径上所有交点的情况并不多见，所以相关的优化 方法也很少1 2 7 j 。 2 3 3 减少参与计算的光线数量 一种加速算法的方法是直接减少发射出的初始光线。该方法依据相邻光线颜色 的相近度决定直接插值获得中间像素的颜色或是发射出额外的光线进行采样。在场 景中物体较少的情况下，顶点跟踪【28 j 同样可以减少需要跟踪的初始光线的数量， 这种方法不再通过屏幕像素发射光线，而是直接向场景中物体的各个顶点发射光 线。这几种方法都依赖插值计算获得一部分像素的颜色，对场景的依赖度高，容易 丢失细节信息而造成失真，因此在应用中并不多见。 除初始光线外，减少衍生光线的数量也同样可以减少产生每帧图像所需要跟踪 的光线数量。在场景中光源数目和非漫反射物体较多的情况下，衍生光线将远多于 初始光线。因此，在跟踪光线时需要有一定的终止规则用于限制衍生的无限发生， 如光线的最大反射或折射次数( 即最大深度) 和光线最远行程0 。，。除此之外，许多 场景中高透明度的和反射的物体所占的百分比是很小的。这时，就无需对每一条光 线都跟踪到最大深度了。自适应深度控制【29 】依据光线和物体表面的性质来进行深 度控制，随着光强的削弱，一些衍生光线的计算可以被取消。 对于任何场景，每光线往往都有很多相邻的光线，他们沿着几乎相同的方向前 进，也很可能击中同一个物体。将这些光线当成一道光束进行跟踪也能减少需要参 与计算的光线数量。利用这种光线的空间相关性，出现了包括铅笔技术【3o 】在内的 许多加速方法，本文将在第四章中详细论述如何使用光束跟踪加速光线跟踪算法。 l o 硕上学位论文 2 3 4 减少相交测试的计算次数 在有关光线跟踪的研究中，绝大部分都集中在减少相交测试的这个问题上。 一种常用的办法是针对初始光线的。这种方法使用光栅化替代对初始光线的跟踪： 首先，场景中的每个图元被赋予一个特定的颜色以相互区别。随后，场景被光栅 化。因为每个物体都具有不同的颜色值，最后只要比对帧缓存空间中各个像素的 颜色值就可以确定通过各个像素的初始光线所击中的物体。这种方法的缺点是仅 对初始光线有效，场景中衍生光线较多时该方法对性能的提升有限。另外，在场 景中物体较多时，对场景进行光栅化可能比跟踪初始光线更加耗时【2 3 1 。 更常见的方法是，采用前文中已经提到过的空间数据结构划分场景。这种方 法实际上是利用场景的空间相关性，在计算中只考虑光线路径上的物体，从而忽 略其它不会与光线相交的物体。这类算法的关键问题是如何恰当地分割场景以便 用最小的遍历开销将需要进行相交测试的对象降到最低。能用于加速光线跟踪的 场景数据结构有很多，如层次包围盒( b v h ) 树，b s p 树，八叉树，均匀网格，自适 应网格，k d 树，以及其它一些新的数据结构 3 1 , 3 2 】。在此介绍几类常用的场景数据 结构【3 0 】： ( 1 ) 层次包围体 一个直接的场景划分方式是对每个物体使用一个包围体，如一个球体或方盒。 如果光线不与包围体相交，那么就无需进行进一步的计算，反之则需要进行进一 步的相交测试以确定光线是否与所包围的物体相交。包围体一般都形成层次结构 使用，高层包围体包裹着一组低层的包围体。 根 t a + bcd + e abde 图2 3 层次包围盒示例 图2 3 是一个包围盒的示例，场景中的对象分别标识为a 到e ，所有包围盒 形成一个层次结构。光线渐进地与包围盒进行相交测试。图中，光线a 先与根包 围盒进行相交测试，继而依次与a + b ，c ，d + e 进行相交测试，光线与d + e 相交， 而后分别与d 和e 进行相交测试，最后得到与物体e 的包围盒相交。 基于g p u 的光线跟踪算法研究与实现 层次化包围盒能大大缩减相交计算的数目，但是在计算中每个对象都需要被 光线考虑到。较好的方法应该是只有那些明显在光线路径上的对象才被测试，空 间细分的方法就可以做到这一点。 ( 2 ) 一致空间细分 一致空间细分方法的思想是用轴向对齐的正方体来包围场景，并对空间进行 一致地分割，所得到的每个小的体素存储其中包含的图元的标识符。算法使用 3 d d a 算法的一个改换算法来获得光线穿过的那些体素。图2 4 说明光线是如何被 跟踪的，其中所有光线穿过的体素都必须考虑。由于这种划分方法便于进行光线 遍历，实现简单，p u r c e l l 1 9 】在他最初的g p u 光线跟踪算法设计中就采用了均匀网 格的场景细分方式。 、 、 、一 、 、 图2 4 通过一致空i 司细分跟踪一条光线 ( 3 ) 自适应空间细分 一致空间细分计算光线路径是很省时的，但是它没有考虑到对象的分布。如 果大多物体集中在场景的一个角落中，这种细分将是十分低效的。更好的方法是 使用自适应的层次化细分以便根据对象的分布对空间进行划分。 在层次化细分中，如果一个单元包含了过多的对象，单元将被进一步细分。 八叉树【33 1 ，b s p 树和k d 树【3 4 1 都属这样的划分。k d 树是一种轴向对齐的b s p 树， 在k d 树中，每个空间单元都被轴向对齐的平面分割成两个子节点，每当深度增 加时，依次选择三个主轴中的一个方向做上述划分。图2 5 是一个二维k d 树的示 例，第一个划分点( 7 ，2 ) 在x 轴上，第二层的划分点( 5 ，4 ) 和( 9 ，6 ) 在y 轴上，第三层 的划分点在x 轴上。对于一个场景，有许多种方式进行分割点的位置选择，常见 的有空间均分、物体均分和基于某种代价模型的方案【3 5 】。目前用于光线跟踪的最 优加速结构是使用s a h t 3 6 1 规则构建的k d 树【37 1 ，本文将在第四章中详细讨论k d 树的遍历算法。 1 2 硕j j 学位论文 2 4 小结 图2 5 一个k d 树的示例 x 一。y x 本章是后续工作的理论基础。第一节介绍了几种基于光线跟踪的绘制技术， 详细讨论了递归式光线跟踪的流程，本文的第三章将以此为基础设计算法的流处 理模型。第二节分析和概括了加速光线跟踪的一些策略，并讨论了这些加速策略 的特点，本文的第四章将在此基础上对基于g p u 的光线跟踪算法的加速策略进行 深入的研究。 基于g p u 的光线跟踪算法研究j 实现 3 1 引言 第3 章光线跟踪的流处理模型设计 前面的章节完成了对光线跟踪算法的概述并对加速光线跟踪的技术进行了初 步介绍。在此基础上，本章将深入探讨g p u 作为一个图形处理器是如何应用于光 线跟踪算法的。本章从g p u 并行计算的特点开始论述，继而介绍流处理的概念和 流处理开发平台b r o o k 的计算模型。在这个平台的支持下，可以将g p u 当作一个 流处理器而不是仅仅的图形处理器使用。以此为基础，实现g p u 光线跟踪算法