光线追踪算法的GPU加速算法(学习版)

加速构建KD树的方法

（声明：本文仅为笔者的相关整理和理解）

摘要：光线追踪算法是用来生成照片逼真的渲染效果最有前途的算法之一。然而，算法的计算开销使算法远达不到实时显示效果。许多学者提出了不同的改进，不断加速光线追踪算法。在本文中，我们将介绍一些的改进方法的关键步骤，例如GPU构建kd树，和专用硬件加速引擎。

关键词：KD树光线追踪 GPU 硬件

A Method Of Accelerating

The Construction Of KD-Tree

Abstract: The ray tracing algorithm is one of the most promising algorithms, which is used to generate photo realistic rendering effects. However, the expense cost of computing puts the real time ray tracing far from reaching. Many scientists come up with different improvements to stand closer to, real time ray tracing, the terminal goal. In this paper, we will introduce some key points of certain outstanding improvements, such as, constructing the KD tree on GPU, and dedicated hardware acceleration engine. Key words: KD Tree ray tracing GPU hardware

一、简介

光线追踪算法在真实感填充方面的效果非常出色，考虑了不同方向反射光线与折射光线对空间特定点亮度的影响，通过多次的迭代达到真实的效果。然而多次迭代跟踪反射光线与折射光线带来的结果就是三维空间中要进行大量的求交点运算，特别现在提倡的高清的时代，在2560*1440的区域上进行光线追踪算法，每秒几乎要发射出20亿条光线。有学者提出区域分割、八叉树、KD树等方法来快速计算光线与物体表面交点。区域分割是将整个空间划分成为相等大小的子区域，如果某个子区域内有实体，就标记该区域为有实体。八叉树是在空间划分上进行的一个改进，空间不是被等分，而是将实体使用大小不同的正方体来表示实体，算法中大小相邻的正方形空间之间大小比例是8:1。KD树可以看作是八叉树的一种改进，KD在划分子空间的时候总是选取散度最大的坐标轴方向，使得空间划分更有效。所以KD树是使用最广泛，并被认为是最有前景的方法。在加速构建KD树的领域，研究人员也做出了许多探索，部分小组成功的把构建KD树的算法移植到4核的CPU上运行。所以在并行计算能力非常强大的GPU上实现KD树构建算法成了很热的一个方向，与此同时，部分研究人员把目光转向专用硬件芯片FPGA，并取得了很好的成绩。

本文的结构是这样安排的：我们在第二本分介绍传统的序列SAH KD树的构建方法；在随后的第三部分介绍并行化计算SAH代价和排序的算法；在第四部分介绍现已有的硬件专用芯片；第五部分是实验结果的展示；最后是对本文的总结。

二、序列SAH KD树的构建

在构建KD树之前，我们要提前构建三个事件列表，分别对应三个坐标轴。对于每一个轴对齐包围盒（AABB），在某一坐标轴上有两种事件：开始事件定义为轴对齐包围盒在坐标轴方向的最小值；结束事件定义为轴对齐包围盒在坐标轴方向的最大值。算法计算三个坐标轴方向的散度，对散度最大的坐标轴方向进行空间划分，在确定分割平面的时候，通常是要最小化SAH代价来确定最优分割平面，SAH代价需要计算候选分割平面两侧周对齐包围盒的数目然，两侧三角形的面积和。确定候选分割平面两侧三角形的数量可以通过

计数平面某一侧开始事件或结束事件的数目来完成。例如计数候选分割平面左侧三角形的数量，可以通过计数候选分割平面左侧开始事件的数目。如果候选分割平面穿过某个三角形，那么这个三角形既属于左侧三角形有属于右侧三角形。在确定最优分割平面之后，子空间会进一步被分割，为了使子空间仍然能被细分，需要对得到的子空间的图元进行排序，构建子空间的事件列表。

三、GPU构建SAH KD树

在上一部分讲到，计算SAH代价的时候，很重要的一步就是确定候选分割平面两侧三角形的数目。因为事件列表已经提前构建存储，所以能够使用并行数据图元扫描的方法并行计算三角形的数目，其中图1展示了如何具体实现，其中关键词PARALLEL表示产生大量线程。

在算法中，最有可能的分割平面往往在三角形轴对齐包围盒的表面为了便于计算，我们使用标志暂时表示开始事件与结束事件，如图2，我们用1表示开始事件，用0表示结束事件。这样就能通过扫描标志列表来计算三角形的数目。标志列表的前项和就是开始事件的数目，因为开始事件数目与结束事件数目之间是相关的，可以通过算法3展示的伪码算得结束事件的数目。

图1 并行计算最优平面算法

图2 计算三角形数目

确定分割平面之后，我们可以将原先的三

角形放入到子节点上，完全位于分割面一侧的三角形保持不变，对于被分割平面穿过的三角形，需要分裂轴对称包裹盒，分裂操作能够极大的提升KD树的质量和光线追踪的表现。最简单的方法是将子节点的三角形重新构建事件列表，然而这样效率很低。为了优化构建子节点的事件列表，我们将事件分为E

only

事件

与E

both

事件两类。E

only

事件表示三角形位于分割平面一侧，只用从原先的事件列表中继承，

而E

both

事件择不会。首先选出所有的E

both

事件，

随后将其与E

only

事件融合成为新的事件列表，如图3所示。然而这个过程在GPU中的表现并不是很好。

图3 重新排序子节点事件

四、现有的专用芯片

现在我们介绍的专用硬件芯片的主要架构在下页图4中完整介绍其中的主要部分将在以下部分重点介绍：

A ．场景边界计算单元（SBCU ）

场景边界计算单元以8个32比特浮点数作为输入，通过比较当前值与已存最大值最小值比较，更新上边界与下边界。这里使用两个场景边界计算单元并行计算上边界与下边界。

B ．前项和单元（PSU ） 在前一部分介绍道，计算分割平面两侧开始事件和结束事件可以通过计算前项和实现。前项和单元是重复使用率很高的一个部分。它将很长的序列分割成很小的部分，并行地在每一个小的部分上进行前项和计算，最后将所得部分整合成为完整的序列。图5展示出了32位的前项和单元。

图5 计算8项前缀和

C ．莫顿码生成单元（MCGU ）

莫顿码生成单元用来产生莫顿码，并在需要的情况下复制三角形。 D ．基筛选单元（RSU ）

E ．叶结点生成单元（LNGU ）

F ．内部节点生成单元（INGU ）与位编码器（BEU ）

G ．路径压缩单元（PCU ）

路径压缩单元使用节点莫顿码的值计算在压缩KD 树上节点的双亲节点。 H ．片上缓存

算法需要16KB 的片上缓存来标记节点是否是必要的。

图 4 硬件架构

表1 各种方法的计算开销

五、实验结果

上述硬件专用芯片不仅能保证近似实时并且效果非常逼真。渲染效果在图6展示，并且算法的计算速度与其他方法的计算速度在表1列出

图6 渲染效果

六、总结

在众多的改进算法中，已经实现简单场景实时光线追踪。特别是在加速构建KD树方面的改进，光线追踪的效果和效率都得到了保障，在高速GPU并行运算和专用硬件的加速下，基于构建KD树的光线追踪算法有很好的使用前景。

参考文献：

[1] Ni, and Z. Li, “Fast-tree: a hardware kd-tree construction acceleration engine for real-time ray tracing”, Design, Automation & Test in Europe, 2015:1595-1598

[2] Z Ma，Z Li, “The Real-Time and Realistic Rendering for 3D Sea Terrain Based on Electronic Chart”, International Conference on Virtual Reality and Visualization (ICVRV) 2015:160-165

[3] Zhefeng Wu , Fukai Zhao , Xinguo Liu, “SAH KD-tree construction on GPU” - Acm

Siggraph/eurographics Conference on High Performance Graphics - 2011

光线跟踪讲解及源代码

计算机图形学期末作业 作业题目：Ray Tracing算法的实现 姓名：李海广 学号：S130201036 任课教师：秦红星

摘要 Ray Tracing算法又叫光线跟踪算法，它能通过递归方法逐个计算每个像素点的光强，然后就可以绘制出高度真实感的图像，因此该方法在图形学领域得到了广泛的应用。Ray Tracing算法的思想还能应用到移动通信终端定位领域，该领域里的射线跟踪法与此算法思想类似。MFC是微软公司提供的一个类库，以C++类的形式封装了Windows的API，并且包含一个应用程序框架，以减少应用程序开发人员的工作量。其中包含的类包含大量Windows句柄封装类和很多Windows的内建控件和组件的封装类。MFC在处理Windows窗口应用程序方面具有很大的优势，因此，本文使用MFC在VC6.0里实现Ray Tracing算法，并给出了该算法的详细讲解。 【关键词】Ray tracing 光线跟踪递归像素光强 MFC C++

目录 1.Ray Tracing算法概述 (1) 1.1Ray Tracing算法简介 (1) 1.2Ray Tracing算法的实现原理 (1) 2.Ray Tracing算法的具体实现 (2) 2.1算法的实现环境 (2) 2.2实现算法的C++程序简介 (2) 2.3算法的具体实现过程 (3) 2.4 程序运行结果 (11) 3.总结 (11) 3.1 通过该算法学到的东西 (11) 3.2本程序未完成的任务 (12) 4.参考文献 (12)

1.Ray Tracing算法概述 1.1Ray Tracing算法简介 光线跟踪（Ray tracing），又称为光迹追踪或光线追迹，它是来自于几何光学的一项通用技术，它通过跟踪与光学表面发生交互作用的光线从而得到光线经过路径的模型。它用于光学系统设计，如照相机镜头、显微镜、望远镜以及双目镜等。这个术语也用于表示三维计算机图形学中的特殊渲染算法，跟踪从眼睛发出的光线而不是光源发出的光线，通过这样一项技术将具有一定数学模型的场景显现出来。这样得到的结果类似于光线投射与扫描线渲染方法的结果，但是这种方法有更好的光学效果，例如对于反射与折射有更准确的模拟效果，并且效率非常高，所以在追求高质量结果时我们经常使用这种方法。 在光线跟踪的过程中，我们要考虑许多因素。要跟踪的光线包括反射光线、散射光线和镜面反射光线，利用递归方法并且设定一定的阀值来跟踪；在计算光强度时，我们要考虑场景中物体的反射系数、漫反射系数和镜面反射系数，还有交点处的法向量，出射光线的方向向量；在求视线以及反射光线和场景中物体的交点时，要计算出离眼睛以及出射点最近的交点作为击中点，得到击中点之后，我们就可以计算出击中点的坐标。最终，通过三个公式计算出每一个像素点处三种光线的光强值，再将三个光强值相加，就得到了该像素点出的总光强值，最后将颜色缓冲器中的三种颜色值输出到屏幕上，就得到了我们需要的光线跟踪图像。 1.2Ray Tracing算法的实现原理 （1）对图像中的每一个像素，创建从视点射向该像素的光线； （2）初始化最近时间T为一个很大的值，离视点最近的物体指针设为空值； （3）对场景中的每一个物体，如果从视点出发的光线和物体相交，且交点处的时间t比最近时间T小，则将t的值赋给最近时间T，并设置该物体为最近物体，将物体指针指向该物体； （4）经过第三步的计算后，如果最近物体指针指向空值NULL，则用背景色填充该像素。如果该指针指向光源，则用光源的颜色填充该像素；

光线投射,光线追踪与路径追踪的概念与区别

光线投射,光线追踪与路径追踪的概念与区别 光线投射Ray Casting [1968] 光线投射（Ray Casting），作为光线追踪算法中的第一步，其理念起源于1968年，由Arthur Appel在一篇名为《Some techniques for shading machine rendering of solids》的文章中提出。其具体思路是从每一个像素射出一条射线，然后找到最接近的物体挡住射线的路径，而视平面上每个像素的颜色取决于从可见光表面产生的亮度。 光线投射：每像素从眼睛投射射线到场景 光线追踪Ray Tracing [1979] 1979年，Turner Whitted在光线投射的基础上，加入光与物体表面的交互，让光线在物体表面沿着反射，折射以及散射方式上继续传播，直到与光源相交。这一方法后来也被称为经典光线跟踪方法、递归式光线追踪（Recursive Ray Tracing）方法，或Whitted-style 光线跟踪方法。 光线追踪方法主要思想是从视点向成像平面上的像素发射光线，找到与该光线相交的最近物体的交点，如果该点处的表面是散射面，则计算光源直接照射该点产生的颜色；如果该点处表面是镜面或折射面，则继续向反射或折射方向跟踪另一条光线，如此递归下去，直到光线逃逸出场景或达到设定的最大递归深度。 经典的光线追踪：每像素从眼睛投射射线到场景，并追踪次级光线（(shadow, reflection, refraction），并结合递归 光线追踪（Ray tracing）是三维计算机图形学中的特殊渲染算法，跟踪从眼睛发出的光线而不是光源发出的光线，通过这样一项技术生成编排好的场景的数学模型显现出来。这样得到的结果类似于光线投射与扫描线渲染方法的结果，但是这种方法有更好的光学效果，例如对于反射与折射有更准确的模拟效果，并且效率非常高，所以当追求高质量的效果时经常使用这种方法。

光线跟踪算法思想

光线跟踪算法思想 一、概述 本试验完成了基本光线跟踪、高级光线跟踪（反射、折射、透明、阴影）、光线跟踪加速算法等三个与光线跟踪有关的内容。 二、算法简述 1．面片求交 面片求交采用了先求交后判断的方法。现将光线的方程代入平面方程中求出交点。然后将该面片与交点都投影到同一个平面中如XOY平面。投影时需要判断投影结果是否会退化为一条直线，如果发生这种情况则要投影到另一平面内。 投影后，将交点坐标代入到面的边线方程中（要保证线的方向一致），并判断符号，如果符号始终相同，则表示点在面内。 2．球体求交 球体求交也采用了将光线方程代入球体方程的方式。如果方程无解表示没有交点。如果有两个大于0的解，则取较小的一个；如果一个大于0，一个小于0的解，则取大于零的解。 如果没有大于零的解则仍判定为不相交。 3．光线跟踪算法 设定视点和画布 for 画布上的每一行 { for 每一行上的每个像素 { 生成一条从视点到像素点的光线ray LT[i,j] = ray.RayTrace(物体数组，光源数组，1) } } //计算光线与物体的交点，并计算光强 V oid RayTrace(物体数组，光源数组，递归深度) { for 每个物体 { 计算光线与该物体的交点 if 光线起点到交点的距离小于已记录的最短距离且大于0 { 将最短距离设置为该距离

在这条光线对象中记录交点坐标，平面法向量，透明度，物体序号等 } } 对于距光线起点最近的那个点，执行 ComputeIntensity（物体数组，交点数组序号，光源数组，递归深度） } V oid ComputeIntensity(物体数组，交点数组序号，光源数组，递归深度) { 给物体加上环境光强 for (每个光源) { 生成一条从光源指向交点的光线 判断该光线是否与其他不透明的物体相交 if （不相交） 将该光线光强乘以满反射系数和镜面反射系数加到被跟踪光线的光强中 } if （递归深度< 设定深度） { if （需要反射） { 生成一条以交点为起点的反射光线reflectRay reflectRay.RayTrace(物体数组，光源数组，递归深度+1) 将reflectRay的光强与镜面反射系数相乘，加到原被跟踪光线光强中} if （需要折射） { 生成一条以交点为起点的折射光线refractRay refractRay.RayTrace(物体数组，光源数组，递归深度+1) 将refractRay的光强与透明系数相乘，加到原被跟踪光线光强中} } } 4．光线跟踪加速算法（层次包围球） 本作业选择了包围球而不是包围和来实现加速。这是基于光线与包围球求交比与包围盒求交速度快的考虑。虽然包围盒比包围球能更紧密地包围住物体，但与包围盒求交时需要处理所有可见面片并且对求出的交点还要判断是否在面片内，这样，当物体数量较少时反而起不到加速的作用。因此我觉得包围盒更适合于规模很大的光线跟踪计算。

光线跟踪算法

光线跟踪算法的研究与进展 刘进 摘要：光线跟踪算法是图形绘制技术中的经典算法，但是该算法光线与物体的求交量庞大，严重制约着应用。本文从经典的光线跟踪算法出发，研究了目前光线跟踪算法的国内外研究状况，具体从改进的光线跟踪算法和光线跟踪算法的加速技术，并进行了对比和分析。最后对近几年的光线跟踪方法发展进行了总结，对未来研究热点及应用前景进行了展望。 关键词：可视化；光线跟踪算法；并行绘制；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年代，随着计算机技术的发展，光线跟踪技术广泛应用于三维特技电影、电视广告、电子游戏的制作中，其应用领域也正在向如物理、化学、生物等其他学科领域渗透，其应用的范围正不断扩大，很多基于光线跟踪算法的新理论也应运而生，物理学中的相对论、地理中地层的绘图等与光线跟踪算法相结合的研究已经实现，极大的推动其学科的发展。可

光线追踪的应用及发展趋势

课程论文 课程论文题目：光线追踪的应用及未来发展 学院：人民武装学院 专业：计算机科学与技术 班级：物联人151 学号： 1500860346 学生姓名：谭朝艳 指导教师：宁阳 2016 年6 月3 日

目录 摘要 ............................................................... II 第一章绪论 . (1) 1.1 光线追踪的定义 (1) 1.2 光线追踪的原理 (1) 1.2.1 自然现象 (1) 1.2.2 光线追踪的原理 (1) 1.3 光线追踪的特点 (3) 1.3.1 光线追踪的优点 (3) 1.3.2 光线追踪的缺点 (3) 第二章光线追踪的应用 (4) 2.1 光线追踪在图形渲染中的应用 (4) 2.2 光线追踪在物理学中的应用 (4) 2.3 光线追踪在实际应用 (4) 2.4 实时跟踪 (4) 第三章光线追踪的未来发展趋势 (6) 3.1 光线追踪VS光栅化 (6) 3.2 显卡何时才能实时光线追踪 (7) 3.3 光线追踪的未来发展 (8)

光线追踪的应用及未来发展 摘要 光线跟踪是一种真实地显示物体的方法，该方法由Appe在1968年提出。光线跟踪方法沿着到达视点的光线的反方向跟踪，经过屏幕上每一个象素，找出与视线相交的物体表面点P0，并继续跟踪，找出影响P0点光强的所有光源，从而算出P0点上精确的光线强度，在材质编辑中经常用来表现镜面效果。光线跟踪或称光迹追踪是计算机图形学的核心算法之一。在算法中，光线从光源被抛射出来，当他们经过物体表面的时候，对他们应用种种符合物理光学定律的变换。最终，光线进入虚拟的摄像机底片中，图片被生成出来。 关键字：光线跟踪（Ray tracing），真实感

光线追踪实验报告

Ray Tracer---光线跟踪实验报告 711064XX XXX 一、实验目的 在计算机图形学课程作业中，题目要求是做Ray Tracing 或碰撞检测，其中对Ray Tracing 的要求是： (1)多种形状物体，Ball, box等 (2)包含多种材质物体：纯镜面反射、透明物体、纯漫反射、半透明物体等 (3)Moving in a 3D world (4)environment texture 二、实验原理 在这次实验中，使用了真正的光线跟踪算法，而不是采用环境纹理来反映周围环境。 1、光线跟踪简介 光线跟踪是一种真实地显示物体的方法，该方法由Appel在1968年提出为了 生成在三维计算机图形环境中的可见图像，光线跟踪是一个比光线投射或者 扫描线渲染更加逼真的实现方法。这种方法通过逆向跟踪与假象的照相机镜 头相交的光路进行工作，由于大量的类似光线横穿场景，所以从照相机角度 看到的场景可见信息以及软件特定的光照条件，就可以构建起来。当光线与 场景中的物体或者媒介相交的时候计算光线的反射、折射以及吸收。由于一 个光源发射出的光线的绝大部分不会在观察者看到的光线中占很大比例，这 些光线大部分经过多次反射逐渐消失或者至无限小，所以对于构建可见信息 来说，逆向跟踪光线要比真实地模拟光线相互作用的效率要高很多倍。计算 机模拟程序从光源发出的光线开始查询与观察点相交的光线从执行与获得正 确的图像来说是不现实的。 2

由以上经典的光线追踪算法可以发现，在此算法中，环境中的物体等模型，并不是 一次性的画好的，而是对整个场景一个像素一个像素的画上去的，光线跟踪算法中 的每一根光线要与场景中的每一个物体所含的每一个面求交。 三、光线跟踪算法实现 1、计算观察光线 首先需要确定光线的数学表达式。一条光线实际上只是一个起点和一个传播方向， 假设起点为O（x1，y1，z1），屏幕上一点为D（x2，y2，z2），则光线的方向dir（x3，y3，z3）为： dir=O–D； 即 在程序中，光线的起点定义为： 方向为： 由此可以确定一条光线

在光线跟踪算法的递归过程中

在光线跟踪算法的递归过程中，加速算法有哪几种？说明他们分别使用与哪些场合光线跟踪的基本原理 由光源发出的光到达物体表面后，产生反射和折射，简单光照明模型和光透射模型模拟了这两种现象。在简单光照明模型中，反射被分为理想漫反射和镜面反射光，在简单光透射模型把透射光分为理想漫透射光和规则透射光。由光源发出的光称为直接光，物体对直接光的反射或折射称为直接反射和直接折射，相对的，把物体表面间对光的反射和折射称为间接光，间接反射，间接折射。这些是光线在物体之间的传播方式，是光线跟踪算法的基础。 最基本的光线跟踪算法是跟踪镜面反射和折射。从光源发出的光遇到物体的表面，发生反射和折射，光就改变方向，沿着反射方向和折射方向继续前进，直到遇到新的物体。但是光源发出光线，经反射与折射，只有很少部分可以进入人的眼睛。因此实际光线跟踪算法的跟踪方向与光传播的方向是相反的，而是视线跟踪。由视点与象素(x,y) 发出一根射线，与第一个物体相交后，在其反射与折射方向上进行跟踪，如图4. 6.1所示。 图4.6.1 基本光线跟踪光路示意

为了详细介绍光线跟踪算法，我们先给出四种射线的定义与光强的计算方法。在光线跟踪算法中，我们有如下的四种光线：视线是由视点与象素 (x，y)发出的射线；阴影测试线是物体表面上点与光源的连线；以及反射光线与折射光线。当光线V与物体表面交于点P时，点P分为三部分，把这三部分光强相加，就是该条光线V在P点处的总的光强： a) 由光源产生的直接的光线照射光强，是交点处的局部光强，可以由下式计算： b) 反射方向上由其它物体引起的间接光照光强，由 I s K s'计算，I s通过对反射光线的递归跟踪得到 c) 折射方向上由其它物体引起的间接光照光强，由I t K t'计算，I t通过对折射光线的递归跟踪得到。 在有了上面介绍的这些基础之后，我们来讨论光线跟踪算法本身。我们将对一个由两个透明球和一个非透明物体组成的场景进行光线跟踪（图4.6.2）通过这个例子，可以把光线跟踪的基本过程解释清楚。

光线追踪算法的GPU加速算法(学习版)

加速构建KD树的方法 （声明：本文仅为笔者的相关整理和理解） 摘要：光线追踪算法是用来生成照片逼真的渲染效果最有前途的算法之一。然而，算法的计算开销使算法远达不到实时显示效果。许多学者提出了不同的改进，不断加速光线追踪算法。在本文中，我们将介绍一些的改进方法的关键步骤，例如GPU构建kd树，和专用硬件加速引擎。 关键词：KD树光线追踪 GPU 硬件 A Method Of Accelerating The Construction Of KD-Tree Abstract: The ray tracing algorithm is one of the most promising algorithms, which is used to generate photo realistic rendering effects. However, the expense cost of computing puts the real time ray tracing far from reaching. Many scientists come up with different improvements to stand closer to, real time ray tracing, the terminal goal. In this paper, we will introduce some key points of certain outstanding improvements, such as, constructing the KD tree on GPU, and dedicated hardware acceleration engine. Key words: KD Tree ray tracing GPU hardware 一、简介 光线追踪算法在真实感填充方面的效果非常出色，考虑了不同方向反射光线与折射光线对空间特定点亮度的影响，通过多次的迭代达到真实的效果。然而多次迭代跟踪反射光线与折射光线带来的结果就是三维空间中要进行大量的求交点运算，特别现在提倡的高清的时代，在2560*1440的区域上进行光线追踪算法，每秒几乎要发射出20亿条光线。有学者提出区域分割、八叉树、KD树等方法来快速计算光线与物体表面交点。区域分割是将整个空间划分成为相等大小的子区域，如果某个子区域内有实体，就标记该区域为有实体。八叉树是在空间划分上进行的一个改进，空间不是被等分，而是将实体使用大小不同的正方体来表示实体，算法中大小相邻的正方形空间之间大小比例是8:1。KD树可以看作是八叉树的一种改进，KD在划分子空间的时候总是选取散度最大的坐标轴方向，使得空间划分更有效。所以KD树是使用最广泛，并被认为是最有前景的方法。在加速构建KD树的领域，研究人员也做出了许多探索，部分小组成功的把构建KD树的算法移植到4核的CPU上运行。所以在并行计算能力非常强大的GPU上实现KD树构建算法成了很热的一个方向，与此同时，部分研究人员把目光转向专用硬件芯片FPGA，并取得了很好的成绩。 本文的结构是这样安排的：我们在第二本分介绍传统的序列SAH KD树的构建方法；在随后的第三部分介绍并行化计算SAH代价和排序的算法；在第四部分介绍现已有的硬件专用芯片；第五部分是实验结果的展示；最后是对本文的总结。