（信号与信息处理专业论文）光线跟踪加速算法在异构多核平台上的设计与实现.pdf

南京邮电大学硕士研究生学位论文 摘要 摘摘 要要 随着多核技术的发展， 越来越多的研究人员开始关注和着手多核技术的研究 与应用。在多核技术中，多核处理器和众核处理器（gpu 可以看作众核处理器 的一种）越来越受到研究人员的关注和利用。随着 gpu 计算能力和可编程能力 的提高，已经成为高性价比的并行计算协处理器，特别适于密集的、高并行的通 用计算。研究人员开始把各种基于 cpu 的密集计算引入到 gpu 上，利用 gpu 巨大的运算能力来加速计算过程。在计算机图形中，光线跟踪算法作为生成真实 感图像的重要方法，广泛应用在电影娱乐等行业。由于光线跟踪本身具有高度并 行化的条件，因此，利用 gpu 加速光线跟踪算法已成为一种趋势。 本文首先分别在 cpu、gpu 以及异构多核三种平台上构建光线跟踪算法的 加速结构 kd-tree，并证明异构多核平台更加适合构建 kd-tree 加速结构。其次 在异构多核平台上实现完全重建动态光线跟踪算法以及分析其适应范围。 最后提 出两种动态光线跟踪算法以及分析其适应范围。本文的主要内容如下： 1） 研究了光线跟踪的基本原理和流程， 选择合适的加速结构， 在支持 cuda 的 gpu 上构建了光线跟踪模型系统。 2）分别在 cpu、gpu 以及异构多核三种平台上构建加速结构 kd-tree；通 过测试不同静态三维场景，证明在异构多核平台构建的 kd-tree 的效果 最好。 3）在研究并实现了完全重建动态光线跟踪算法之后，提出了部分重建动态 光线跟踪和光线坐标变换动态光线跟踪算法。并对这三种动态光线跟踪 算法的优缺点和在异构多核平台上实现的性能进行了分析比较。 关键词：关键词：光线跟踪，异构多核，kd-tree，gpgpu i 南京邮电大学硕士研究生学位论文 abstract ii abstract with multi-core technology developing, more and more researchers pay attention to using multi-core processors and many-core processor (gpu can be considered as many-core processor). with the rapidly increasing computing power and the growing of the levels of the programmability of the gpu, it has become a cost-effective parallel computing coprocessor, particularly suitable for intensive and high parallel general purpose computing. researchers have begun to introduce the gpu to do a variety of intensive calculations based on cpu. in the computer graphics, as an important method for generating photorealistic images, ray tracing has been widely used in the film entertainment industry. because ray tracing is of highly parallel, therefore, it becomes a trend to accelerate ray tracing algorithm by gpu. this paper firstly discusses three platforms to achieve the accelerated structure of ray tracing algorithm. by comparing, proves that heterogeneous multi-core platform is more suitable for building kd-tree. secondly, implements the algorithm of completely rebuild dynamic ray tracing on the heterogeneous multi-core platform and analyzes performance of the algorithm. lastly, proposes two dynamic ray tracing algorithms and analyzes their performance. the main content of this paper is as follows: 1) study the basic principle of ray tracing algorithm; select the suitable accelerated structure and construct ray tracing model system on the gpu which supports the cuda. 2) study the accelerated structure of ray tracing on the cpu、gpu and heterogeneous multi-core platform. and prove that the heterogeneous multi-core platform is more suitable for building the accelerated structure of ray tracing algorithm by testing different static three-dimension scenes. 3) propose the partly reconstructed and rays coordinate transferred dynamic ray tracing after studying and achieving the completely rebuild dynamic ray tracing. analyze the performance of these three algorithms and get the performance when these three algorithms apply on the heterogeneous multi-core platforms. key words: ray tracing, heterogeneous multi-core, kd-tree, gpgpu 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：_ 日期：_ 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布（包括刊登）论文的全部或部分内容。 论文的公布（包括刊登）授权南京邮电大学研究生院（筹）办理。 研究生签名：_ 导师签名：_ 日期：_ 南京邮电大学硕士研究生学位论文 第一章 绪论 1 第一章 绪第一章 绪 论论 1.1 光线跟踪的研究现状 1.1 光线跟踪的研究现状 近年来， 随着技术的不断发展， 人们对渲染场景的真实感和规模提出了更高的要求， 越来越需要用计算机生产高质量的图片。光线跟踪是一种真实感绘制算法，利用光路可 逆原理，通过逆向跟踪光线，生成栩栩如生漂亮非凡的图像。它作为计算机图形学 (computer graphics，cg)的重要组成部分，在模拟仿真、医药卫生、以及游戏娱乐等各 种领域都有着广泛的应用， 是生成真实感图形的主要算法之一1,2。 由于该算法原理简单、 实现方便，且能生成各种逼真的视觉效果，因而在 cad 及图形学各个领域得到了广泛 的应用。 在计算机娱乐产业（特别是电影和游戏产业）和半导体制造工艺进步推动下，图像 处理单元（graphics processing units :gpus）的发展速度非常快。考虑到硬件的性价比， gpu 无疑是现在能够获得的功能强大的计算硬件。gpu 的并行处理的架构，使得 gpu 本质上就具有很强的计算能力，也使得 gpu 的处理速度比 cpu 还要快。随着 gpu 上 的可编程性的提高，以及 gpu 上的高级语言的提出，gpu 不在是一个只能处理图形应 用的功能固定的芯片，而是一个 simd 可编程单元，并且 gpu 也已开始在密集计算成 为一个非常吸引人的平台。而这种应用不仅仅局限于图形领域，还可以应用到通用计算 领域（general purpose graphics processing units : gpgpu）,如矩阵乘法，光线跟踪，数 值模拟等等3。 对于计算机图形学而言，光线跟踪算法是一个非常基础而流行的渲染算法，并且这 个算法本身具有并行执行的特性，这对于在 cpu、gpu 以及异构多核下利用其并行特 性，来实现光线跟踪算法显得非常适合。 1.1.1 cpu光线跟踪器 wald5提出矢量化光线跟踪算法，此种方法几乎可以使传统方法的性能提高一倍。 该算法提出一个并行处理四条光线的 cpu 光线跟踪器，该跟踪器利用单输入流多数据 南京邮电大学硕士研究生学位论文 第一章 绪论 2 流（simd）指令并行执行四条光线的遍历求交计算。同时在文中还提到网络优化环境 使用多个 cpu 可以实现对复杂场景的实时渲染，指出光线跟踪算法的速度与使用的处 理器数目基本上呈线性正比关系。 reshetov 等人6提出使用一个层次的“光束”结构作为一系列光线的代表。这使得在 同一个光束中的光线能够从一个树的内部节点开始他们的遍历，以此来减少计算量。 最近，ryan overbeck7等人利用光线包和锥形剔除法，在两个四核 cpu 平台上使 用 simd 指令并行计算光线跟踪，实现了实时的光线跟踪渲染效果。 1.1.2 gpu光线跟踪器 随着 gpu 在通用计算方面的发展， 在 gpu 的光线跟踪器也产生。 purcell8和 carr9 等人几乎同时提出来在 gpu 上实现的光线跟踪算法的框架，但二者有所不同。purcell 等人提出的光线跟踪算法将所有的光线跟踪内核都建立在 gpu 之上，包括光线（视线） 产生器，光线遍历器，求交器和着色器。而 carr 等人仅仅把一个光线和三角面片求交器 在 gpu 上实现，将其它的光线跟踪的工作留给 cpu。这两种方法的不同之处在于，前 者能够避免因 cpu 与 gpu 之间的频繁的数据传输，消除其带来的损失，但这种方法会 使 gpu 多时处于空闲阶段，后者能够获得更高的 gpu 使用率，因为光线在被传送到 gpu 之前，已经预先在 cpu 上被处理成束，所以光线已经获得的内在一致性，但是这 种方法缺点是 cpu-gpu 之间需要大量的数据传输，虽然 gpu 的带宽比较宽，但 cpu 的带宽相当 gpu 而言比较窄， 因此在 cpu-gpu 之间的传输数据， 以 cpu 的带宽为主， 因此会导致性能上的损失。另外，purcell 等人还对 gpu 和 cpu 上的编程的多种趋势进 行了评估，证明了在 gpu 上的光线跟踪器的性能必然优于在 cpu 上的光线跟踪器。 随着 gpu 计算的推广，很多原来用在 cpu 上的光线跟踪加速数据结构也被引入到 gpu 上，如均匀栅格(uniform grid)，kd-tree 和包围体层次(bvh)。均匀栅格是在 gpu 上的光线跟踪算法中第一个被使用的加速结构， 因为这种结构无论是在构造还是在遍历 上都非常的简单，christen10，karlsson 和 ljungstedt11等人都使用均匀栅格作为 gpu 上光线跟踪算法的加速结构，但它的性能同 cpu 上的实现相比要差。kd-tree 被认为是 cpu 上光线跟踪算法最快的加速结构12，但 gpu 不能够支持堆栈结构，因此在 gpu 上不能够实现递归遍历的堆栈结构。foley 和 sugerman 等人13提出了能够在 gpu 上实 现的kd-tree遍历算法， 并且指出kd-tree的性能超过均匀栅格。 斯坦福大学daniel reiter 南京邮电大学硕士研究生学位论文 第一章 绪论 3 horn 等人14在 foley 研究的基础上进行了改进，采用了 packets 、push-down 和 short-stack ，将其中的 kd-restart 算法从多过程 cpu 负载均衡改进为单过程 gpu 分支 循环实现，进一步提升了光线跟踪器的性能。thrane12等人首次实现了使用 bvh 加速 结构的作为 gpu 光线跟踪器。gpu 结构的特殊性导致场景的存储和切换是一个挑战， carr 15提出了在 gpu 的快速三角网格切割算法，从而能高效地切换和构建几何图像。 此外 nvidia 所推出的 cuda（common unified device architecture）开发平台同样引起 研究者的注意，holger scherl16将这一革命性的技术应用于 ct 三维重建中，运行效率 有显著提高。 1.1.3 专用硬件上的光线跟踪器 schmittler 等人通过重建一个光线跟踪算法无组织内存存取结构模式，以及比重建 一个用于渲染场景的显存大的虚拟内存结构， 提出了一个完全的硬件体系结构17。 最近， scmittler 等人提出了， 在一个 fpga 芯片上对动态场景的高性能光线跟踪和一个完全可 编程的光线处理单元 rpu（ray processing unit） 。在多数情况下，它们在性能上已经超 过了高度优化的多核 cpu 实现。但是专用的硬件比 cpu 和 gpu 更加难以获得。 1.1.4 静态和动态光线跟踪算法 静态光线跟踪的技术已经相当成熟， 其已经能够实现交互式甚至实时重建三维静态 场景。目前研究人员一致认为：在所有的加速结构中，kd-tree 加速结构被认为静态光 线跟踪中最好的加速结构12，其最大的问题是建树时间过长；但建树时间在光线跟踪渲 染静态场景中，没有影响其渲染时间，因为建树时间作为预处理时间。 目前动态光线跟踪还没有一个统一的算法，其原因有两点，其一，在动态场景中， 部分物体的位置或形状随时间发生变化， 这导致了原有的加速结构必须随着物体的变化 而变化，从而能够得到正确的渲染的图片；其二，在动态场景的中，运动物体的运动分 类会影响到数据的表示和加速结构的建立19。因此本文着重解决 kd-tree 构建的速度过 慢和实现交互式动态光线跟踪算法。 南京邮电大学硕士研究生学位论文 第一章 绪论 4 1.1.5 光线跟踪算法目前存在的问题 虽然光线跟踪算法能够正确地处理相互反射的现象以及折射等光学效果， 但是其存 在的一个最大缺点是效率不高。光线跟踪算法是将每条光线作为独立的光线，每次都需 要重新计算，从而带来巨大的计算量；因此自光线跟踪技术以来，这一技术基本上都作 为离线处理对待。但随着多核 cpu、计算机群集技术的发展，利用这些硬件条件，已经 实时实现光线跟踪渲染，而多核 cpu、计算机群集、大型工作站成本较高，因此实现实 时性代价较高。随着 gpu 的发展与应用，研究人员已经利用其并行特性实现静态光线 跟踪算法，达到交互式甚至实时的效果。在 gpu 上实现静态光线跟踪时，对于基于 kd-tree 实现光线跟踪算法而言，构建 kd-tree 的时间较长，考虑到 kd-tree 的特点， kd-tree 也适合在 gpu 上构建，但由于 kd-tree 前几层的节点数目较少，并行粒度低， 所以本文采用在异构多核上构建 kd-tree。除了静态光线跟踪的 kd-tree 加速结构构建 速度慢的缺点外，光线跟踪的最大缺点是光线跟踪算法目前还不能在线渲染动态场景。 这也将是本文最后待解决的问题。 1.2 本文的研究内容 本文的研究内容 1.2.1 本文的研究工作 为快速构建 kd-tree 加速结构，本文首先讨论研究光线跟踪的基本原理，同时分析 simd 架构的 gpu 的优势， 结合两者讨论基于 gpu 的光线跟踪系统模型的构建， 在此模型 上讨论 kd-tree 在不同平台下的构建，分析和比较各种平台的优劣势，获取一种构建 kd-tree 的最佳平台，为研究动态光线跟踪做准备。 在讨论不同平台下构建 kd-tree 加速结构后， 在异构多核平台下实现完全重建加速 结构动态光线跟踪后，本文提出部分重建加速结构和光线坐标变换动态光线跟踪算法， 分析三种动态光线跟踪算法的优劣势以及这三种动态光线跟踪算法适应范围， 并且最后 还证明了异构多核平台下更适应动态光线跟踪算法。 南京邮电大学硕士研究生学位论文 第一章 绪论 5 1.2.2 章节安排 第一章，结合国内外对光线跟踪算法的研究现状和发展趋势，指出存在问题和本文 的研究内容。 第二章，介绍基于 gpu 的静态光线跟踪器模型系统的设计和实现，此模型为讨论并 行构建加速结构提供了实验模型。 第三章， 介绍 kd-tree 在不同平台下的实现以及试验比较。 通过在不同测试场景的实 验证实在异构多核平台上构建 kd-tree 的速度效果最优。 第四章，介绍三种动态光线跟踪算法及通过测试比较，分析三者方法各自优点和缺 点以及其适应性，同时证明异构多核平台更适应动态光线跟踪算法。 第五章，对全文进行总结。根据本文的研究成果，对异构多核平台下动态光线跟踪 算法的研究进行分析与展望。 南京邮电大学硕士研究生学位论文 第二章 基于 gpu 的光线跟踪模型系统 第二章第二章 基于基于gpu的光线跟踪模型系统的光线跟踪模型系统 2.1 基于基于gpu的的cuda架构介绍架构介绍 gpu（graphic processing unit，图形处理单元）是类似于cpu的一个概念，由于利 用计算机处理图形越来越重要，需要一个专门的图形处理器。nvidia公司在 1999 年提 出gpu的概念并发布geforce 256 图形处理芯片20。gpu执行了部分原本在cpu上的工 作，减少了对cpu的依赖，尤其是在 3d图形处理时。 如图 2.1 所示，gpu 与 cpu 的设计目标不同，cpu 中的大部分晶体管主要用于 control（控制电路）和 cache（缓存） ，只有少量的晶体管来完成实际的运算工作。而 gpu 的控制电路相对简单， 而且对 cache 的需求较小， 所以更多的晶体管专用于数据处 理，如 alu（arithmetic logic unit，算术逻辑单元） ，因此 gpu 的计算速度有了飞 跃性的提高，并拥有惊人的处理浮点运算的能力。 图 2.1 gpu 将更多的晶体管用于数据处理 gpu已经具有高度的可程序化能力，由于gpu通常具有相当高的内存带宽，以及大 量的执行单元，因此开始有利用gpu来帮助进行一些计算工作的想法，因此，nvidia公 司针对gpu的通用运算，推出了cuda(compute unified device architecture，计算统一 设备架构) c语言开发环境，用于通用并行计算21。这样，通过片上（on-chip）上百个 处理器同步协作快速解决复杂的运算问题。其基本思想是尽量开发线程级并行(thread level parallel)， 这些线程能够在硬件中被动态的调度和执行。 图 2.2(a)显示了cpu与gpu 之间通过cuda软件栈协调工作。在 cuda 的架构下，一个程序分为两个部份：host 端 6 南京邮电大学硕士研究生学位论文 第二章 基于 gpu 的光线跟踪模型系统 和 device 端。host 端是指在 cpu 上执行的部份，而 device 端则是在显示芯片上执 行的部份。device 端的程序又称为 kernel。通常 host 端程序会将数据准备好后， 复制到显卡的内存中，再由显示芯片执行 device 端程序，完成后再由 host 端程序将 结果从显卡的内存中取回。 除了数据并行的核以外， 程序中也有标准的串行程序 （运行在 cpu 上） 。 如图 2.2(b) 所示，在两个核之间运行的就是串行代码。若两个核函数之间没有串行代码，它们就可 以被合并为一个。 (a)cuda 软件栈 (b)cuda 编程模型 图 2.2 cuda 开发环境 2.2 光线跟踪原理光线跟踪原理 光线跟踪算法用于生成照片级真实感强的合成图像， 它是计算机图形学核心算法之 一。1979 年 turner whitted 提出的经典光线跟踪算法4是跟踪镜面反射和折射，它是 在全局模型中加入局部模型，也即一个部分全局照明算法。这就意味着经典光线跟踪算 法中，某个物体的外表不仅受光源的影响，还会受到它周围环境的影响。 最基本的光线跟踪算法是跟踪镜面反射和折射。从光源出发的光遇到物体的表面， 发生反射和折射，光就改变方向，沿着反射方向和折射方向继续前进，直到遇到新的物 体，但是光源发出光线，经反射与折射，只有很少部分可以进入人的眼睛。因此实际光 线跟踪算法的跟踪方向与光传播的方向是相反的，而是视线跟踪。由视点与像素（x，y） 发出一根射线，与第一个物体相交后，在其反射与折射方向进行跟踪，如图 2.3 所示。 光线跟踪算法实际上是光照明物理过程的近似逆过程， 这一过程可以跟踪物体间的镜面 7 南京邮电大学硕士研究生学位论文 第二章 基于 gpu 的光线跟踪模型系统 反射光线和规则透射，模拟了理想表面的光的传播。 图 2.3 基本光线跟踪光路示意 2.3 光线跟踪模型系统框架设计光线跟踪模型系统框架设计 基于 gpu 的光线跟踪器主要有两种。第一种是 carr 等人9提出来的，把 gpu 作为 一个用来执行光线与三角片求交的计算器，大部分的渲染工作仍然在 cpu 上执行的， 但 gpu 的利用率不高。第二种方法是由 purcell8提出的，它将整个光线跟踪算法都在 gpu 上实现，从光线的产生到加速结构的遍历，到最后的着色都在 gpu 上执行，因此 对 gpu 的利用率高。由于第一种方法不能充分利用目前 gpu 并行计算的能力，因此本 文的光线跟踪模型系统采用第二种方法来实现。 2.3.1 模型系统 本文模型系统包括用户i/o接口、场景数据准备及预处理模块、kd-tree建立及管理 模块、基于cuda的光线跟踪引擎和opengl显示引擎共五个模块，分别实现了用户键 盘与鼠标的控制、场景数据的准备与预处理、kd-tree的建立和存储处理，光线与场景的 三角片求交及光强计算，图像的显示等功能，具体的层次和支撑关系参见图2.4。图中， 基于cuda的光线跟踪引擎在gpu上实现，其它模块主要为接口和数据预处理模块，相 对而言计算密集度较低，因此均在cpu上实现。 8 南京邮电大学硕士研究生学位论文 第二章 基于 gpu 的光线跟踪模型系统 基于cuda的光线跟踪引擎 光线跟踪的模型系统 用户控制 场景数据处理 kd-tree处理 光线求交及光强计算 图像显示 opengl引擎 kd-tree建立及管理模 块 场景数据准备及 预处理模块 用户i/o 接口 图 2.4 基于 gpu 的光线跟踪模型系统架构 2.3.2 模型系统的数据流 本文模型系统中的数据流走向和处理如图 2.5。图中带有斜线阴影的数据处理模块 均位于 gpu 上实现，其它部分主要为输入输出接口，在 cpu 上实现。 图中光源数据包括光源的个数、 每个光源的三维坐标、 漫反射分量和镜面反射分量， 在不影响正确性的前提下，本文采用的光源均为点光源。图中的三角片属性数据包括所 有三角片的顶点数据，即三维坐标和法线方向。图中的三角片纹理数据包括：各个顶点 的漫反射分量、镜面反射分量、三角片所对应的纹理图片及顶点的纹理坐标。 图 2.5 模型系统数据流 9 南京邮电大学硕士研究生学位论文 第二章 基于 gpu 的光线跟踪模型系统 10 2.4 基于基于gpu的光线跟踪算法流程的光线跟踪算法流程 光线跟踪的一个重要的特性，光线之间是相互独立的，因此多条光线可以以并行的 方式同时与几何体的求交计算。另外，wald 曾给出了一个结论4：随着执行初次光线求 交计算的处理器的增加，光线跟踪渲染速度将随着所使用的处理器的数量呈线性增长。 因此，本文利用 gpu 多处理器的性能，可以大幅度提高光线跟踪运算速度。 经典的静态光线跟踪算法的实现过程是一个简单的递归过程，但是由于 cuda 不 支持递归过程，因此将这一过程改为顺序执行，具体步骤如下： 1. 生成初始光线； 2. 光线与场景中的物体求交，并判断交点对光源的可见性； 3. 计算该交点对图像像素点色彩的贡献； 4. 计算反射光线 5. 如不满足终止条件，则回到第2）步继续执行。 在光线跟踪开始前必须将场景数据全部准备好，并导入到gpu内存。下面将按照上 述步骤详细介绍光线跟踪模型系统的实现过程。 2.4.1 测试场景数据的准备 本文原始场景数据文件由查尔摩斯理工大学给出的 aff (animated file format)文 件。该文件中将场景中的物体由很多小的三角片组成，并且给出每个三角片的三个顶点 的坐标，还包含不同物体的材质数据（包括漫反射系数、环境光反射系数、镜面反射系 数等）；该文件同时将物体的纹理贴图用 ppm 文件给出。文件中也给出光源的数据（包 括光源数目，每个光源的位置、亮度、颜色等属性值）。 本文选用三个测试场景进行光线跟踪渲染，分别为 cornell-box（32 个三角面片）， kitchen（110561 个三角面片）和 robots（71708 个三角面片），其中 kitchen 既可以作 为动态光线跟踪测试场景，也可以像 cornell-box 作为静态光线跟踪测试场景。 2.4.2 初始光线的生成 在进行光线跟踪渲染时，首先要确定视点、观察方向和视角，并由此确定生成的图 南京邮电大学硕士研究生学位论文 第二章 基于 gpu 的光线跟踪模型系统 像平面，如图 2.6（a）所示。当确定了图像平面后，根据图像分辨率确定像素位置，从 而得到初始光线，开始进行渲染。本文的初始视点位置、观察方向可由程序输入；视角 选取 67.38 度作为缺省值。视点（即图中 location）与像屏的距离为 1（即图中向量 的模），像屏的水平宽度为 1.33。根据视点位置、观察方向、视角和图像 分辨率，可以确定像平面上的每个像素点的位置，再根据视点位置，可以确定每条初始 光线的方向，从而确定初始光线，如图 2.6（b）所示，其中为光线起点（即 location）， 是光线方向(归一化为单位矢量)， 为参数。例如，所渲染的图像的分辨率为 ，则穿过像素点 m 的初始光线的方向为： directiondirection o dt heightwidth * d_ijdirectiondd_ijdirectiond+= （2.1） 其中 height/2)-yoffsetwidth/2)-xoffset(+=d_jd_id_ijd_jd_id_ij， )0 , 0 , 2/ )2/tan( ( width angle =d_id_i，) 0 , 2/ )2/tan( , 0( height ratioangle =d_jd_j， widthheightratio/=， ),(yoffsetxoffset分别为此像素点在水平和垂直方向上距离右上角像素点的偏移量。 (a) 像平面 (b) 光线及其参数 图 2.6 视点、观察方向、像平面与光线 11 南京邮电大学硕士研究生学位论文 第二章 基于 gpu 的光线跟踪模型系统 2.4.3 光线跟踪中的加速结构kd-tree 光线跟踪过程中，需要确定与光线相交的三角面片的索引及交点位置，而当三角面 片数量较多时，计算非常耗时。为减少计算量，本文采用 kd-tree 加速结构。kd-tree， 即 k 维搜索树。 它的每一层通过检测不同的属性（关键字）值以决定选择分枝的方向。 kd-tree 是本文讨论的重点，下面章节会重点讨论。 2.4.4 光线在kd-tree中的遍历与求交 光线在 kd-tree 中的遍历与求交，本文选择标准的 kd-tree 遍历算法，具体的算法 流程如下： （1）产生初始光线，确定每条光线的起点和方向。 （2）从 kd-tree 的根节点开始遍历，若光线与场景相交，求出光线在根包围盒的全局跨 度区间scene_min, scene_ max 。对于每条光线，在光线同节点的包围盒相交的地方需 要找出参数范围t_min，t_max（初始的 t_min、t_max 为包围盒的全局跨度区间）转到 （3）遍历该 kd-tree 的每个节点；如果该节点是中间节点，则光线与此节点的分割平面 会有交点，光线到交点距离为 t_split（可能为负值） ， 如果 t_min wvu),(wvut 210 )1 (),(vvuvvvuvut+= 210 ,vvv)(tr ),(vut),()(vuttr=的求解，得到线性方程组如 下: (2.2) 00201 )(vo v u t vvvvd= 从而得到交点的重心坐标和光线方程中参数 的值。若),(vu)(trt0t或，则光线 与三角片所在平面无交点。若,但 =t 0tvuvu+,不在01之间，则交点不在三角面片内； 13 南京邮电大学硕士研究生学位论文 第二章 基于 gpu 的光线跟踪模型系统 只有,且在01之间，光线才与三角面片相交，交点为 。 0tvuvu+,tdo+ 在进行光线跟踪过程中，如果满足条件，光线就会发生反射。这个过程是光线衍生 的过程。产生的反射光线，首先在kd-tree中遍历和求交，并获得相应的交点、交点处的 表面法线和材质等基本的信息。反射光线的起点就是当前光线与景物的交点，反射方向 r则由下面的公式给出17： ll)2n(nrll)2n(nr= (2.3) 其中，是表面法线，是当前光线方向，如图2.9所示。 nlnl 图2.9光线反射示意图 2.4.5 阴影探测 阴影效果在真实感图像的生成和光源位置判断方面是一个非常重要的元素， 光线跟 踪可以自动的生成阴影效果。当确定光线和三角面的交点后，在光源与交点之间生成探 测光线，如图2.10所示，并利用上述kd-tree的求交方法，判断在交点和光源之间是否有 物体遮挡，如有遮挡，光源对该像素点的色彩无直接贡献，否则在计算像素色彩时，需 要考虑光源的贡献。由于对光源贡献的不同处理，最终渲染的效果自动出现阴影，如图 2.10所示。 14 南京邮电大学硕士研究生学位论文 第二章 基于 gpu 的光线跟踪模型系统 图2.10探测光线 2.4.6 像素颜色贡献值的计算 在本文模型系统中， 图像像素点的颜色值是由以下两个部分组成22： 局部分量和全 局反射光线的贡献。 （1）局部分量 局部分量的贡献由局部光照模型确定， 也即光照情况仅依赖于光源所发出的光， 而 不是其他物体表面反射或者折射出来的光。局部分量由环境分量、漫反射分量和镜面分 量共同组成。 环境分量：在现实世界中，从光源散发的光线可能会在一个物体表面上产生反射并 到达另一个物体。为了模拟这种间接光照，光照模型由材料和光照强度等环境因素常量 组成，如式2.4所示，其中：为环境光亮度、为物体的环境光分量、为光源 的环境分量、表示分量相乘。增加环境分量更加符合实际条件，使远离光源的物体表 面看上去非完全黑色。 amb i i amb m m amb s s ambambamb smismi= (2.4) 漫反射分量：一个基于lambert定律22的几何属性，该定律认为，对于理想漫反射 的物体表面（完全不光滑且没有光泽）来说，反射光由物体表面法线和光向量l l的余 弦决定，光向量是从物体表面点p到光源的方向向量，如图2.11所示。 n n 15 南京邮电大学硕士研究生学位论文 第二章 基于 gpu 的光线跟踪模型系统 图2.11 漫反射表面 当光线垂直射到物体表面，光线之间的间隔距离 ，光的强度随着 的增大而减少。 当光线来自不同方向，与平面的法线夹角为 ll ，光线到表面的距离为/ cosl。由于光的 强度与距离成反比，这也意味着漫反射光照与cos成比例。对于漫反射，反射方向的 概率分布在每个方向上都是均匀的，这意味着漫反射分量不依赖视点位置与观察方向。 从任何角度看上去，表面的光照效果都是一样的。最终漫反射分量为： diffdiffdiffdiffdiff smlnsmismlnsmi=)(cos (2.5) 其中：为材质的漫反射颜色，为光源的漫反射颜色。由于当和l l之间的角 度大于 diff m m diff s sn n 2/时，漫反射为零，上式改为： diffdiffdiff smlnismlni=)0),max( (2.6) 镜面反射分量的目的则是通过产生高光来使物体表面出现闪闪发光的效果。如果光 源发射向量从背面指向视点，那么镜面反射分量最大，于是就会产生高光。随着视点与 反射方向之间的夹角逐渐变大，镜面反射分量也会逐步减弱。因此随着视点和观察方向 的变化，高光在物体表面的位置也会随之改变。blinn给出了这一影响因子： (2.7) shishi mm )(cos)(=hnhn 图2.12 镜面光照方程模型 其中：n n为物体表面法线、l l为光向量、v v是物体表面点到视点之间的向量。h h是l l和p pv v 16 南京邮电大学硕士研究生学位论文 第二章 基于 gpu 的光线跟踪模型系统 之间的归一化半向量： vl vl h vl vl h + + = (2.8) 考虑到当和之间的夹角大于n nh h2/时，镜面反射为零，最终的镜面反射分量为： specspec m spec shi smhnismhni=)0),max( (3.9) 其中：为材质的镜面反射系数，为光源的镜面反射颜色。 spec m m spec s s 综合上述三种分量，光源产生的色彩为： = += n k k spec k diff k amb k spottotal c 1 )(iiiiiiii (2.10) 其中表示共有个光源；若第个光源发出的光线能够到达物体表面点，则为1， 否则为0。 nnk k spot c （2）全局反射光线的贡献 除了光源产生影响外，像素点的颜色值还受到其它物体产生的次级光线的影响。次 级光线即为初始光线照射到物体后，经过反射产生的光线。由于在局部光照模型中已经 考虑的环境分量，这里只考虑镜面反射的影响。光线跟踪是光照明物理过程的近似逆过 程，这一过程可以跟踪物体间的镜面反射光线，模拟了理想表面的光的传播。 理论上说这种跟踪需要无限的进行下去，直到跟踪到光源或背景为止。在实际处理 过程中，一般会根据一些判据终止跟踪，常用的终止条件有： 与一个完全漫反射表面相交 光线跟踪达到一个预设的深度 光线能量低于阈值 光线跟踪是个混合物即在全局照明模型中加入局部模型，所以像素点最终的颜色值 为： = = += 1 1 1 0 0 )( refnum i i total i k ktotal r iiiiii (2.11) 其中：（）表示第 i total i i10=refnumil1+i次反射光线与场景中的物体相交后，由局部 光照模型计算得到的贡献；refnum是光线跟踪的预设深度