光线跟踪算法

光线跟踪算法的研究与进展刘进摘要 光线跟踪算法是图形绘制技术中的经典算法，但是该算法光线与物体的求交量庞大，严重制约着应用。 本文从经典的光线跟踪算法出发， 研究了目前光线跟踪算法的国内外研究状况， 具体从改进的光线跟踪算法和光线跟踪算法的加速技术， 并进行了对比和分析。 最后对近几年的光线跟踪方法发展进行了总结，对未来研究热点及应用前景进行了展望。关键词 可视化；光线跟踪算法；并行绘制； GPU Research Status and Prospect for ray tracing algorithms Abstract As an classic algorithms of volume rendering in computer graphics, ray tracing algorithms is hindered by the huge computation cost in ray and volume. This paper summarizes the research status in ray tracing technology from the two main solutions different extended ray tracing algorithms and the acceleration techniques in ray tracing algorithms. Comparison and analysis the different performance. Both current research focus and the future research prospect are also discussed in recent years. Key words visualization; ray tracing algorithms; parallel rendering; GPU引言随着科学技术和计算机高速发展， 人类已经进入到一个科技支撑的时代， 在我们的生活中到处充满了高科技产品和技术， 给我们的生活带来了改变和方便， 其中计算机图形学的应用已经渗透到了各个工程技术领域， 其已经成为计算机科学的重要学科之一， 具有相当的重要性和无可替代的作用。 计算机图形学自诞生以来得到了飞速发展， 其通过计算机的输入设备、显示设备及绘制设备等对图形的表示、绘制、存储、显示等相关理论知识、算法技术进行研究的一门学科。 真实感图形绘制是计算机图形学的主要研究内容之一， 在虚拟现实、 文物保护、影视游戏、三维动画、医学研究、建筑设计和系统仿真等领域中得到广泛应用，它追求对场景的逼真渲染 [1]。其中逼真的图形绘制技术是最为活跃的研究领域之一。光线跟踪算法是真实感图形绘制技术的主要算法之一， 其原理简单， 能够有效生成具有比较真实视观效果的各种各样的场景。 该算法可通过一些光照明模型模拟在光源或环境光照射下物体表面发生的多种光照效果，例如漫反射、高光、镜面映像、场景消隐及阴影等。在计算机中对现实场景或是虚拟场景进行显示， 除了要构建场景图形外， 还要将场景中的各种光照效果模拟出来， 这样生成的场景才能更逼真， 光线跟踪算法就是既在几何上相似， 也能模拟出大部分的光照效果的生成真实感图形的方法。 光线跟踪算法是逆着真实光线的投射方向进行反向跟踪的， 从视点向场景发射光线， 光线与场景中的物体相交，计算光分量， 因为视点向场景的光线较多， 因而该算法光线与物体的求交量较大， 但是因为其对场景的模拟的逼真，及其可以模拟漫反射、镜面反射、反射折射以及阴影等光照效果 [1-2]。进入 90 年代，随着计算机技术的发展，光线跟踪技术广泛应用于三维特技电影、电视广告、电子游戏的制作中，其应用领域也正在向如物理、化学、生物等其他学科领域渗透，其应用的范围正不断扩大， 很多基于光线跟踪算法的新理论也应运而生， 物理学中的相对论、地理中地层的绘图等与光线跟踪算法相结合的研究已经实现， 极大的推动其学科的发展。 可以说它已经与我们的生活息息相关了， 因此对光线跟踪进行研究具有很现实的重要意义 [1-3]。1.光线跟踪算法原理对光线跟踪算法研究最早可以追索到 1968 年， Appel 等在对消除隐藏面的研究时运用的光线投射算法，在原理上第一次描述了光线跟踪算法。 1979 年， Kay 与 Greenberg 对光的折射进行了研究，直到 1980 年， Whitted 综合考虑了多种光照效果，模拟出了漫反射、镜面反射、 高光、 反射折射以及阴影等光照效果， 提出了第一个整体的光照明模型 Whitted 模型 [4]。光线跟踪思路 从视点出发， 通过图像平面上每个像素中心向场景发出一条光线， 光线的起点为视点， 方向为像素中心和视点连线单位向量。 光线与离视点最近的场景物体表面交点有三种可能1.当前交点所在的物体表面为理想漫射面，跟踪结束。2.当前交点所在的物体表面为理想镜面，光线沿其镜面发射方向继续跟踪。3.当前交点所在的物体表面为规则透射面，光线沿其规则透射方向继续跟踪。图 1 三个半透明玻璃球场景跟踪图如图 1 中，场景中有三个半透明玻璃球，视点发出光线与场景最近交点为 P1，使用任意局部光照模型可以计算出 P1 点处的局部光亮度 Ilocal ，为了计算周围环境在 P1 点处产生的镜面发射光和规则折射光，光线 1 在 P1 点处衍生出两支光线反射光 2 和折射光 3。 P1处的光照由三部分组成Ilocal ks * I 2 k t * I 3 1 其中 I3 为折射光线 3 的颜色， K t 为折射率， I 2 为反射光线 2 的颜色， Ks 为反射率， I 3 和I 2 的计算需要递归。我们知道光源向其四周发射出数不清的光线， 从光源对光线进行跟中是永远也跟踪不完的。 而光源发出的光线进入人眼的只有少部分直接或是通过场景中的物体表面之间的折射和反射后间接地射入观察者眼中。 所以， 标准的光线跟踪算法是逆着射入观察者眼中的光线进行跟踪的方法来完成整个跟踪过程的。 在光线跟踪的过程中选定视点， 将一个与视点位置相当的平面矩形区域当做显示屏幕， 将显示屏幕均匀网格划分， 每一个网格表示显示屏幕的一个像素， 从视点向像素网格中心引射线作为跟踪光线进行跟踪， 跟踪该光线得到的光亮度就是显示屏幕对应的像素的光亮度，所有像素点组成场景图形 [5]。光线跟踪的流行来源于它比其它渲染方法如扫描线渲染或者光线投射更加能够现实地模拟光线， 象反射和阴影这样一些对于其它的算法来说都很难实现的效果， 却是光线跟踪算法的一种自然结果。 光线跟踪易于实现并且视觉效果很好， 所以它通常是图形编程中首次尝试的领域。 光线跟踪的一个最大的缺点就是性能， 扫描线算法以及其它算法利用了数据的一致性从而在像素之间共享计算， 但是光线跟踪通常是将每条光线当作独立的光线， 每次都要重新计算。 但是， 这种独立的做法也有一些其它的优点， 例如可以使用更多的光线以抗混叠现象， 并且在需要的时候可以提高图像质量。 尽管它正确地处理了相互反射的现象以及折射等光学效果， 但是传统的光线跟踪并不一定是真实效果图像， 只有在非常近似或者完全实现渲染方程的时候才能实现真正的真实效果图像。由于渲染方程描述了每个光束的物理效果，所以实现渲染方程可以得到真正的真实效果， 但是， 考虑到所需要的计算资源， 这通常是无法实现的。 于是， 所有可以实现的渲染模型都必须是渲染方程的近似， 而光线跟踪就不一定是最为可行的方法。 包括光子映射在内的一些方法， 都是依据光线跟踪实现一部分算法， 但是可以得到更好的效果 [5-6]。2 光线跟踪算法及扩展算法光线跟踪算法通过模拟光的传播方式， 即光从光源出发经过若干次反射或折射到达摄像机的过程来实现全局光照效果。其思想起源于光线投射算法 [5]。目前，国内外对光线跟踪算法的研究大部分处于理论研究的水平， 集中在对光线跟踪算法的加速， 而对于光线跟踪算法在生产生活和科学研究中的应用还是较少的， 还处于起步阶段。 针对标准的光线跟踪算法的不足，研究者提出了很多基于标准光线跟踪算法的改进算法。Cook 等 [7]提出分布式的光线跟踪算法，根据分布函数进行采样而产生一定方向分布的光线，并在场景中进行跟踪而产生运动模糊、景深、半影和模糊反射等光照效果。 Kajiya等 [8]提出基于分布式光线跟踪的层次采样算法， 它适应具有广泛多样性的基于蒙特卡洛方法的光线跟踪。 Mitchell [9]将图像的非均匀采样方法应用到高维的分布式的光线跟踪算法中。Walter 等 [10]通过对光源进行聚类生成相应的树状结构， 对多种光源进行光线跟踪， 产生丰富的视觉效果。 Hachisuka 等 [11] 提出光线跟踪的多维自适应采样与重建技术，通过多维函数的综合进行分布式的绘制效果。在具有复杂的漫反射和镜面反射成分表面的场景中， Ward 等[12] 提出一个计算全局光照效果的有效方法，即在绘制阶段用蒙特卡洛方法计算间接光照并将其保存起来，提高计算效率。 Lafortune 等 [13]提出双向的路径跟踪算法，即先从人眼与光源两个方向发射光线并在场景中 进行分布式跟踪，然后进行光照计算，达到增强室内间接光照的绘制效果的目的。 Lafortune 等 [14] 描述了种的全局反射分布函数的概念， 通过简化光照模型，对射能量和聚集能量进行卡洛绘制方法，提高成像效果。 Veach 等 [15]对优化的光线方向进行采样而计算光照， 在增加少量的计算成本下提高成像效果。 Veach 等 [16]提一种新的蒙特卡洛光线跟踪算法， 根据光线跟踪的路径对场景中明亮的区域进行密集采样， 对多维采样空间进行自适应采样。 M ller 等 [17]提出高效的并且所需内存空间最小的光线与三角形的求交算法； Kajiya [18] 和 Toth[19] 分别提出了光线与参数表面的求交算法； Hanrahan [20]提出光线与代数曲面的求交算法； Hart 等 [21] 提出光线与确定性的不规则碎片形表面的求 交算法；Knoll 等 [22] 提出高效的光线与代数隐式曲面的求交算法； Heckbert 等 [23] 提出光柱和网格模型的求交算法； Amanatides [24] 提出光锥和三维模型的求交算法。 Reshetov[25]提出以层次性的光束作为光线集合的代理，实现 多级的光线跟踪算法，能极大减少计算量并且能严格保证了方案的几何正确性。 Moon 等 [26]提出光线跟踪的光线重新排序的缓存算法，能有效地匹配光线跟踪中各级缓存的数据， 极大地提高了光线跟踪效率， 特别就无法全部载入内存的大规模的三维模型而言。 Mora [27]提出基于分而治之策略的光线跟踪算法，即在空间细分时直接计算光线与场景的交点，无需存储相关的数据，大大提高动态场景的绘制效率。 Hou 等 [28] 提出高效的基于微三角形的光线跟踪的重用算法。光线跟踪算法简洁灵活且修改移植方便， 绘制结果真实感程度高， 绘制速度慢一直是一个严峻的问题。 对此人们提出了许多改进的算法来加快绘制速度， 但由于体数据庞大， 单纯的算法改进越来越难以满足现在的需求， 随着图形处理器的迅速发展， 因此人们开始将目光转向图形硬件，希望借助硬件来实现光线跟踪体绘制，提高实际应用价值。3 基于加速技术的光线跟踪法光线跟踪需要完成大量的光线与场景的求交测试运算， 所以求交计算构成了光线跟踪算法的瓶颈，因此，要提高光线跟踪的效率就必须提高光线与场景的求交测试效率。近几年，快速发展的图形处理器 GPU 强大的并行处理能力和高精度的浮点运算能力使得越来越多的应用研究开始利用 GPU 来完成 [29]。目前基于 GPU 的光线跟踪、交互式体绘制技术是国内外研究热点。Purcell [30]首先提出完全基于 GPU 的光线跟踪算法， 成为一些基于 GPU 的光线跟踪渲染器的基础。 Cullip 等首先将体数据沿投影轴进行切片依次装入 GPU 纹理内存，在体数据内定义代理几何体元进行重采样、 颜色合成等操作。 Meiner [31]采取压缩纹理的方式以提高速度，但影响绘制结果准确度。 Kruger [32] 在 GPU 上进行光线投射绘制时，将与光线相交的体元从纹理表中取出， 计算并更新其透明度和颜色值， 利用片段着色沿光线方向采用步进法完成采样进行最终绘制。 Chen[33] 使用视点相关的层次采样将面向多边形绘制的图形引擎转化为体光线投射算法引擎，提供了基于 GPU 的一种新的体光线投射绘制方法。 Singh 等 [34]在 GPU上实现了实时的光线与代数隐式曲面的求交算法。 Zhou 等 [35]通过在图形硬件上实现光线跟踪的加速结构 k-d 树的实时构造，以现对动态场景进行实时地光线跟踪。 Woop[36]研制的可编程光线处理芯片 RPUray processing unit 可用来实时光线跟踪动态绘制复杂的几何场景，达到了理想的交互绘制速度。在加速光线跟踪体绘制技术中， 另一种有效地方法是采用并行技术， 利用多个处理单元，将整个绘制任务合理地分成若干个子任务提供给若干个绘制单元分别进行绘制， 最后将每个绘制单元得到的结果进行拼接或是合成得到最终的绘制结果， 以达到负载均衡和加速绘制的目的。 Pfister 等 [37] 给出的 Cube4 系统是一个比较成功并行体系结构的设计，它能在 30 帧 /秒速率下实现 512 级大小数据场的实时绘制 , Knitel 等 [38] 提出将体数据内存组织成 8 个可同时访问的内存模块，以支持三线性插值计算中对 8 个相邻体素的同时存取。 2010 年等人在文献 [39] 采用的就是层次包围体加速结构 “它将标准的光线跟踪算法分解为一些可以数据并行的多个阶段，采用的是广度优先遍法将这些并行阶段能有效地映射到 GPU 的并行结构上。4 总结和讨论光线跟踪算法是计算机图形学中生成真实感图形的核心算法之一， 它的研究和应用一直是计算机图形学研究的热点。 本文着重论述了国内外体光线跟踪算法、 加速的光线跟踪绘制技术等， 并讨论了各自特点及其相互联系。 目前， 基于硬件加速的光线跟踪绘制技术应用越来越广泛， 但是如何构造有效的数据结构以及高效的遍历算法一直是研究的重点， 使这些数据结构和算法能够在硬件上达到优化配置， 如何充分发挥图形硬件的功能、 实时生成真实感强的图像将是今后的重点研究方向。随着强大的可编程性 GPU 高端图形卡的和并行可视化技术的不断发展，具有高度真实感的实时可视化技术将会应用得越来越广泛。参考文献[1] 张少帅 . 真实感图形中光线跟踪算法及其加速技术的研究 [D]. 西安电子科技大学 , 2008. [2] 裴雪飞 . 光线跟踪体绘制算法的研究 [D]. 燕山大学 , 2007. [3] 周鹏 . 基于光线跟踪的真实感全局光照问题研究 [D]. 山东大学 , 2012. [4] Whitted T. A scan line algorithm for computer display of curved surfaces[J]. ACM SIGGRAPH Computer Graphics, 1978, 12SI 8-13. [5] 彭群生、 鲍虎军、 金小钢编著 . 计算机真实感图形的算法基础 [M]. 北京 科学出版社，1999， 6 [6] 蔡勋 , 曾亮 , 刘光国 . 光线跟踪方法在体绘制中的应用与发展 [J]. 计算机工程与设计 , 2009 21 4956-4959. [7] Robert Cook, Thomas Porter, and Loren Carpenter Distributed Ray Tracing. Computer Graphics Proceeding of SIGGRAPH 84, 183137-144, 1984. [8]Kajiya J T. The rendering equation[C]//ACM Siggraph Computer Graphics. ACM, 1986, 204 143-150. [9]Mitchell D P. Spectrally optimal sampling for distribution ray tracing[J]. ACM SIGGRAPH Computer Graphics, 1991, 254 157-164. [10]Walter B, Drettakis G, Parker S. Interactive rendering using the render cache[M]//Rendering techniques ’ 99. Springer Vienna, 1999 19-30. [11] Hachisuka T, Jarosz W, Weistroffer R P, et al. Multidimensional adaptive sampling and reconstruction for ray tracing[C]//ACM Transactions on Graphics TOG. ACM, 2008, 273 33. [12] Ward G J, Rubinstein F M, Clear R D. A ray tracing solution for diffuse interreflection[J]. ACM SIGGRAPH Computer Graphics, 1988, 224 85-92. [13] Lafortune E P, Willems Y D. Bi-directional path tracing[C]//Proceedings of CompuGraphics. 1993, 93 145-153. [14] Lafortune E P, Willems Y D. A 5D tree to reduce the variance of Monte Carlo ray tracing[M]//Rendering Techniques ’ 95. Springer Vienna, 1995 11-20. [15] Veach E, Guibas L J. Optimally combining sampling techniques for monte carlo rendering [C]. Computer Graphics Proceedings, Annual Conference Series, 1995 419 – 428. [16] Veach E, Guibas L J. Metropolis light transport [C]. Computer Graphics Proceedings, SIGGRAPH 97, 1997 65-76. [17] M ller T, Trumbore B. Fast, minimum storage ray-triangle intersection [J]. Journal of Graphics Tools, 1997, 21 21-28. [18] Kajiya J T. Ray tracing parametric patches [J]. Computer Graphics, 1982, 163 245-254. [19] Toth D L. On ray tracing parametric surfaces [J]. Computer Graphics, 1985, 193 171-179. [20] Hanrahan P. Ray tracing algebraic surfaces [J]. Computer Graphics, 1983, 173 83-90. [21] Hart J C, Sandin D J, Kauffman L H. Ray tracing deterministic 3-D fractals [J]. Computer Graphics, 1989, 233 289-296. [22] Knoll A. Ray tracing implicit surfaces for interactive visualization. PhD Thesis, University of Utah, May 2009. [23] Heckbert P S, Hanrahan P. Beam tracing polygonal objects [J]. Computer Graphics, 1984, 183 119-127. [24] Amanatides J. Ray tracing with cones [J]. Computer Graphics, 1984, 183 129-135. [25] Reshetov A, Soupikov A, Hurley J. Multi-level ray tracing algorithm [J]. ACM Transactions on Graphics, 2005, 243 1176-1185. [26] Moon B, Byun Y, Kim T-J, Claudio P, Kim H-S, Ban Y-J, Nam S W, Yoon S-Eui. Cache-oblivious ray reordering [J]. ACM Transactions on Graphics, 2010, 293 1-10. [27]Mora B. Naive ray-tracing A divide-and-conquer approach [J]. ACM Transactions on Graphics, 2011, 305 1-12. [28] Hou Q M, Zhou K. A shading reuse method for efficient micropolygon ray tracing [J]. ACM Transactions on Graphics, 2011, 306 1-8. [29] 柳有权 , 张曼 . 光线跟踪算法的加速技术研究 [J]. 计算机与数字工程 , 2013, 416 863-865. [30] Purcell T J, Buck I, Mark W R, et al. Ray tracing on programmable graphics hardware[C]//ACM Transactions on Graphics TOG. ACM, 2002, 213 703-712. [31] Meiner M,Guthe S,Strasser W.Interactive lighting models and pre-integration for volume rendering on PC graphics accelera-tors[C].Proceedings of Graphics Interface,2002209-218. [32]Kruger J, Westermann R. Acceleration techniques for GPU-based volume rendering[C]. Proceedings of IEEE Visualization, 2003114-121. [33] 陈为 ,彭群生 ,鲍虎军 .视点相关的层次采样 一种新的硬件加速体光线投射算法 [J].软件学报 , 2006,173587-601. [34] Singh J M, Narayanan P J. Real-time ray tracing of implicit surfaces on the GPU[J]. Visualization and Computer Graphics, IEEE Transactions on, 2010, 162 261-272. [35] Zhou K, Hou Q M, Wang R, Guo B N. Real-time KD-tree construction on graphics hardware [J]. ACM Transactions on Graphics, 2008, 275 1-11. [36] Woop S, Schmittler J.RPUA programmable ray processing unit for real time ray tracing[C].Proceedings of ACM SIGGRAPH, 2005221-226. [37] Pfister H, Kreeger K A, Marks J W, et al. Temporal and spatial coherent ray tracing for rendering scenes with sampled and geometry data U.S. Patent 6,556,200[P]. 2003-4-29. [38] Knittel J, Schnieder L, Buess G, et al. Endoscope-compatible nonlocal microscope using a gradient index-lens system[J]. Optics Communications, 2001, 1885 267-273. [39] Garanzha K, Loop C. Fast Ray Sorting and Breadth‐ First Packet Traversal for GPU Ray Tracing[C] //Computer Graphics Forum. Blackwell Publishing Ltd, 2010, 292 289-298.