光线跟踪算法的研究与实现论文.doc

毕业论文 第 35 页

1 引言
1.1 课题研究的背景及意义
计算机图形学主要是研究利用计算机及其相关图形设备输入、表示、生成、存储、处理和输出图形的理论、算法、技术，以及系统的一门科学。它可以生成现实世界中已经存在的物体图形，也可以生成虚构物体图形。自20世纪60年代诞生以来，计算机图形学的应用就十分广泛，涉及的领域遍及科学、工业、工程、航空、航天、商业、政府部门、医学、教育和培训、艺术、广告以及娱乐行业等。如今，计算机图形学的理论、方法和技术都已很成熟。
真实感绘制技术是当前计算机图形学研究的一个热点问题，同时也是计算机图形学的一个重要分支。真实感绘制的目标是：根据实际场景的情况，在计算机中制造模拟场景，如场景内物体的造型与摆放、物体的材质，以及场景内各光源的颜色和分布等，这些因素共同作用，形成一个在视觉效果上和真实场景非常相似的虚拟环境或图像，使观察者具有身临其境的感觉。随着硬件技术和计算机图形学的高速发展，真实感图形绘制技术也取得了举世瞩目的成就，并且已广泛应用于CAD/CAM、计算机动画、虚拟现实、科学计算可视化等众多领域。
光线跟踪算法是真实感图形技术中的重要算法之一。要在计算机中显示出具有真实性的图像，则需要在可见面判别、明暗、透明、多光源照明等多个方面进行考虑，光线跟踪算法则提供了一种实现真实感的方法。
本课题希望能通过对计算机图形学真实感绘制技术中的光线跟踪算法思想进行研究，掌握其算法核心思想，并编写一个小型演示系统来实现最基本的光线跟踪算法，以达到学习的目的
1.2 国内外研究现状
目前，国外对于光线跟踪算法的研究水平、研究进度均领先于国内。国内的研究绝大部分都是直接翻译国外的、已经写好的论文资料，自己加以改编，并没有比较高层次的创新。
目前，国内外对于光线跟踪算法的研究大致在两个方面：
一方面是针对光线跟踪算法的加速，主要集中于光线跟踪中涉及的空间求交问题。2003年，古春生和蔡勇在《β-样条曲面的光线跟踪算法研究》中，提出了一种光线跟踪与β-样条曲面的快速求交算法[1]。2001年，葛明和葛研军发表了《光线跟踪长方体求交高效算法》，基于Cyrus-Beck算法及长方体面上点的约束条件，提出光线跟踪中射线与长方体求交测试和运算法的高效算法，显著改善了光线跟踪条件下数控车削加工仿真图形生成速度，该算法还具有一定的通用性，适用于射线与任意凸多面体的求交测试与运算[2]。2004年，高军风等人发表了《一个基于包围盒技术提高光线与物体求交效率的算法》，介绍了用于光线与物体求取交点的内包围盒技术，并针对这一算法仍存在大量面片需要与光线求交的不足之处提出了改进方法[3]。
另一方面是对于工业生产和科学研究中涉及到的光线跟踪算法的研究。2006年，牛翠霞等人联合发表了《医学体绘制的一种快速光线投射算法》，针对医学体数据场的直接体绘制(DVR)，讨论了基于体绘制的多种加速技术，利用格雷厄姆求凸壳算法和与平面簇求交算法对体数据场和投射光线进行裁剪，结合多边形的扫描线转换和投射光线的离散化、体素化，改进了光线投射算法[4]。2006年，刘文杰等人发表了《光线跟踪算法在高质量三维分子模型设计的应用》，文中分析了显示分子三维结构的光线跟踪算法，并且介绍了POV-RAY开放源代码软件的用法及其脚本语言，可直接应用于分子化学领域，为工业生产带来间接的效益[5]。
如今的光线跟踪正结合到诸如物理、化学、生物等学科领域，逐渐走向了分子化、原子化模型，扩大了其应用领域。例如，国外有人把光线跟踪和物理学中的相对论结合起来，提出了一种新的理念，国内也有相应的研究[6]；在地理学中，对于地层的绘图也可以结合光线跟踪方法。
1.3 本文的研究内容
本文对光线跟踪算法的基本原理进行了研究，从最基本的计算机如何显示图像开始，逐步涉及到光线的传播原理、计算机模拟光照的数学模型、光线跟踪的原理，结合图片和一系列的伪代码，阐述了光线跟踪算法的每一个细节过程。
最后本文还在光线跟踪基本算法的基础上，结合光线跟踪理论，在C++环境下运用windows GDI实现了一个小型算法演示系统。该系统建立了一个空间场景，并在场景中施放若干物体，同时放置一个坐标可变动的光源，模拟光照效果，应用光线跟踪算法确定场景中物体表面所有投影像素点的光强度，然后渲染其阴影效果，达到生成真实感图形的目的。
1.4 本文的内容结构
本文共分为五章：
第一章，引言部分，详细地介绍了光线跟踪算法的研究背景，以及国内外研究的现状等等。
第二章主要介绍理解光线跟踪算法所需要的基础知识，包括物理学、几何光学的基本常识，以及在计算机中如何模拟光线、光照模型等基本知识。本章主要是为下一章系统地介绍光线跟踪算法的原理和过程打基础的。
第三章是本论文的重点章节，根据第二章的基本知识，由浅入深、系统地讲解光线跟踪算法的背景原理，以及基本光线跟踪的整个过程。章节中运用了伪代码来帮助理解，并给出了本文对光线跟踪算法简单实现的思想，列举了两个重要类，以及一系列重要的函数以及相应的伪代码。
第四章是对光线跟踪算法的重要部分——求交计算的研究，也是本文的重点章节。本章介绍了对几种简单的图形的求交方法，并给出求交的公式。
第五章是对全文的总结，以及提出论文的后续深层的研究方向。
2 相关基础知识
2.1 几何光学基础知识
在几何光学中，光的传播方向用一条几何线来表示，这条线称为光线。几何光学是以下列三个实验定律为基础建立起来的，它是各种光学仪器设计的理论根据，借助光线的概念，几何光学基本定律可表述如下[7]：
1、光的直线传播定律：
光在均匀媒质里沿直线传播。即在均匀媒质中，光线为一直线。
2、光的独立传播定律：
自不同方向或由不同物体发出的光线相交，对每一光线的独立传播不发生影响，即它们的传播互不干扰。
3、光的反射和折射定律：
如图2.1所示，设媒质1、2都是透明的，均匀和各向同性的，且它们的分界面是平面（如果分界面不是平面，但曲率不太大时以下结论仍适用）。当光线由媒质1射到分界面上时，在一般情况下被分为反射光线和折射光线，入射光线与分界面的法线构成的平面称为入射面。分界面的法线与入射光线、反射光线、折射光线所构成的角、、分别叫做入射角、反射角和折射角，实验表明：
（1） 反射线和入射线都在入射面内。
（2） 入射角等于反射角：=。
（3） 入射角与折射角正弦之比与入射角无关，是一个与媒质和光的波长有关的常数，即=。
其中，比例常数称为媒质2相对与媒质1的折射率。上式也可称为斯涅耳定律。
任何媒质相对与真空的折射率称为该媒质的绝对折射率。它等于光在真空中的速度c与光在媒质中的速度v之比，即，其中n是媒质的绝对折射率。
实验表明，两种媒质1、2的相对折射率等于他们各自的绝对折射率与之比，即：=/，从而斯涅耳定律还可以表示为：=。
图2.1 光线的入射、反射以及折射
4、光的可逆性原理：
从几何光学的基本定律不难看出，如果光线逆着反射线方向入射，则这时的反射线将逆着原来的入射方向传播；如果光线逆着折射线方向由媒质2入射，则射入媒质1的折射光线也将逆着原来的入射线方向传播，也就是说当光线的方向返转时，光将逆着同一路径传播。
2.2 光线跟踪相关基础知识
2.2.1 光源
光源可以发射出数条光线。当人们观察一个不透明而且不发光的物体时，可以从物体表面看到反射光，这是由场景中的光源和其他物体表面的反射所共同产生的。只要一个物体周围获得光照，即使其自身不直接暴露于光源之下，物体的表面也可能是可见的。有时候将光源称之为发光体，而反射表面（如房屋的墙壁）则称之为反射光源。可以利用光源来表示所有发出辐射能量的物体，如太阳。在所有的光线跟踪的场景中都是基于这样的原理，于是没有光源便不能发出光线，没有光线便就没有光线追踪！
通常一个发光物体可能既是光源又是反射体。例如在一个塑料球内放置一个灯泡，这样在球表面上既发光也反射光，从球面发出的光还可以照亮附近其他物体。点光源是发光体的最简单的模型，光线由光源出发，向四周发散，如图2.2所示。本文中的光源都是有一定坐标位置和强度的点光源。
图2.2 点光源
2.2.2 环境光
环境光是指光源间接对物体的影响，是在物体和环境之间多次反射，最终达到平衡时的一种光。可以近似地认为，在同一环境下，其环境光的光强分布是均匀的，即在任何一个方向上的分布都相同。例如，透过厚厚云层的阳光就可以称为环境光。
环境光没有空间或者方向上的特征，在所有方向上和所有物体表面投射的环境光的数量是恒定不变的，这样每个物体都得到同样的光照，并且相对于该物体表面反射光也是个常数，即反射光与观察方向和物体表面的朝向无关。然而各个物体表面上反射光强度却不一定相同，这取决于各个表面的光学属性，即反射多少入射光，吸收多少入射光。
在简单光照明模型中，用一个常数来模拟环境光，如公式2.1：
（2.1）
其中：参数表示场景中光亮度的大小，为环境光的光亮度，为物体对环境光的漫反射系数，如图2.3所示。
图2.3 具有不同环境光反射系数的两个球
2.2.3 漫反射
当光源来自一个方向时，漫反射光均匀向各方向传播，与视点无关，它是由表面的粗糙不平引起的[8]，因而漫反射光的空间分布是均匀的，如图2.4所示。
图2.4 光的漫反射图示
设入射光强为Ip，物体表面上点P的法向为N，从点P指向光源的向量为L，两者间的夹角为theta，由Lambert余弦定律，则漫反射光强为：
（2.2）
其中，是与物体有关的漫反射系数,0<<1。
当L、N为单位向量时，公式2.2也可用如下形式表达：
（2.3）
可以任意调整物体表面的反射属性，只须为Kd设置一个0与1之间的常数。如果希望反射率较高，则Kd的值接近1，这样就可能得到与入射光强度接近的反射光。若模拟一个能吸收大部分入射光的物体表面，则只须将反射率的值设为接近0。
在有多个光源的情况下，可以有如下的表示：
(2.4)
在RGB颜色模型下，漫反射系数有三个分量，即，分别代表R、G、B三原色的漫反射系数，它们是反映物体颜色的，通过调整它们，可以改变物体的颜色。同样，我们也可以把入射光强I设为三个分量Ir、Ig、Ib，通过这些分量的值来调整光源的颜色。
2.2.4 镜面反射光
对于理想镜面，反射光集中在一个方向，并遵守反射定律[9]。如图2.5所示，对一般的光滑表面，反射光集中在一个范围内，且由反射定律决定的反射方向光强最大。因此，对于同一点来说，从不同位置所观察到的镜面反射光强是不同的。
图2.5 理想镜面反射
镜面反射光强可表示为公式2.5：
(2.5)
其中Ks是与物体有关的镜面反射系数，a为视线方向V与反射方向R的夹角，n为反射指数，反映了物体表面的光泽程度，一般为1～2000，数目越大物体表面越光滑。
镜面反射光将会在反射方向附近形成很亮的光斑，称为高光现象。
同样，将V和R都格式化为单位向量，镜面反射光强可表示为：
（2.6）
其中，R可由计算。对多个光源的情形，镜面反射光强可表示为：
（2.7）
镜面反射光产生的高光区域只反映光源的颜色，如在红光的照射下，一个物体的高光域是红光，镜面反射系数Ks是一个与物体的颜色无关的参数。
正如前面已经提到的，在简单光照明模型中，只能通过改变物体的漫反射系数来控制物体的颜色。
2.2.5 Phong光照明模型
1975年，Phong在Comm.ACM上发表论文，提出图形学中第一个有影响的光照明模型[10]。Phong模型虽然只是一个经验模型，但是其实现的真实感已达到人们可以满意的程度。
光照到物体表面时，物体对光会发生反射、透射、吸收、衍射、折射和干涉。简单光照明模型模拟物体表面对光的反射作用，光源被假定为点光源，反射作用被细分为镜面反射和漫反射。简单光照明模型只考虑物体对直接光照的反射作用，而物体间的光反射作用，只用环境光来表示，Phong光照明模型就是这样的一种模型。
1、Phong光照明模型的建立：
综合上面介绍的光反射作用的各个部分，Phong光照明模型有这样的一个表述[14]：由物体表面上一点P反射到视点的光强I为环境光的反射光强Ie、理想漫反射光强Id和镜面反射光Is的总和，即公式2.8：
(2.8)
如图2.6所示：
图2.6 Phong光照明模型
2、Phong光照明模型的实现：
在用Phong模型进行真实感图形计算时，对物体表面上的每个点P，均需计算光线的反射方向R，再由V计算(R·V)。为减少计算量[11]，可以作如下假设：
（1）光源在无穷远处。即光线方向L为常数；
（2）视点在无穷远处，即视线方向V为常数；
（3）用（H·N）近似（R·V）。这里H为L和V的平分向量，。
在这种简化下，由于对所有的点总共只需要计算一次H的值，节省了计算时间。结合RGB颜色模型，Phong光照明模型最终有如下的形式：
（2.9）
Phong光照明模型是真实感图形学中提出的第一个有影响的光照明模型，生成图像的真实度已经达到可以接受的程度。但是在实际的应用中，由于它是一个经验模型，还具有以下的一些问题：用Phong模型显示出的物体像塑料，没有质感；环境光是常量，没有考虑物体之间相互的反射光；镜面反射的颜色是光源的颜色，与物体的材料无关；镜面反射的计算在入射角很大时会产生失真等。
图2.7展示了n取不同值时候Phong光照明模型示例。

图2.7 n取不同值时候的Phong光照明模型示例
2.2.6 整体光照模型
根据前面的光照模型的介绍，简单光照明模型虽然可以产生物体的真实感图像，但它们都只是处理光源直接照射物体表面的光强计算，不能很好的模拟光的折射、反射和阴影等，也不能用来表示物体间的相互光照明影响；而基于简单光照明模型的光透射模型，虽然可以模拟光的折射，但是这种折射的计算范围很小，不能很好的模拟多个透明体之间的复杂光照明现象。
对于上述的这些问题，就必须要有一个更精确的光照明模型。整体光照明模型就是这样的一种模型[12]，它是相对于局部光照明模型而言的。在现有的整体光照明模型中，主要有光线跟踪和辐射度两种方法，它们是当今真实感图形学中最重要的两个图形绘制技术，在CAD及图形学领域得到了广泛的应用。
1980年Whitted提出的光透射模型就是一个整体光照模型[13]，并且第一次给出光线跟踪算法的范例，实现了Whitted模型。1983年Hall在此基础上进一步给出了Hall光透射模型，考虑了漫透射和规律透射光。Whitted光透射模型，简单点说就是在简单光照明模型的基础上，加上透射光这一项，多考虑了一层。
以图2.8为例，从视点观察到的物体A表面的亮度来源于三方面的贡献：
（1）光源直接照射到A的表面，然后被反射到人眼中的光产生的。
（2）光源或其它物体的光经A物体折射到人眼中的光产生的。
（3）物体B的表面将光反射到物体A的表面，再经物体A的表面反射到人眼中产生的。
简单局部光照明模型仅考虑了（1）。
本论文最后实现的光线跟踪的基本场景中的模型，就是这种整体的光照模型，但是仅仅考虑了理想状况下的反射情况。
图2.8 整体光照模型
3 光线跟踪算法
3.1 光线跟踪算法的基本原理
上一章介绍了一些光线跟踪算法中相关联的一些基础知识，包括几何光学中的三大定律，光在传播过程中发生的漫反射，镜面反射等等，还介绍了简单光照模型和整体光照模型。本章则在这些基础上介绍光线跟踪算法的基本原理以及光线跟踪的过程。
由光源发出的光到达物体表面后，产生反射和折射，简单光照明模型和光透射模型模拟了这两种现象。在简单光照明模型中，反射被分为理想漫反射和镜面反射光，在简单光透射模型把透射光分为理想漫透射光和规则透射光。由光源发出的光称为直接光，物体对直接光的反射或折射称为直接反射和直接折射，相对的，把物体表面间对光的反射和折射称为间接光，间接反射，间接折射。这些是光线在物体之间的传播方式，是光线跟踪算法的基础。
最基本的光线跟踪算法是跟踪光线的镜面反射和折射。从光源发出的光遇到物体的表面，发生反射和折射，光就改变方向，沿着反射方向和折射方向继续前进，直到遇到新的物体。但是光源发出光线，经反射与折射，只有很少部分可以进入人的眼睛。因此实际光线跟踪算法的跟踪方向与光传播的方向是相反的，是一种视线跟踪法。由视点与象素(x，y)发出一根射线，与第一个物体相交后，在其反射与折射方向上进行跟踪。如图3.1所示。

图3.1 光线经过屏幕入射到场景中与物体相交
为了详细介绍光线跟踪算法，先给出四种射线的定义与光强的计算方法。在光线跟踪算法中，有如下的四种光线：视线是由视点与象素(x，y)发出的射线；阴影测试线是物体表面上点与光源的连线；以及反射光线与折射光线。当光线V与物体表面交于点P时，点P分为三部分，把这三部分光强相加，就是该条光线V在P点处的总的光强：
由光源产生的直接的光线照射光强，是交点处局部光强，可由公式3.1计算：
（3.1）
反射方向上由其它物体引起的间接光照光强，由Is、Ks'计算，Is通过对反射光线的递归跟踪得到；折射方向上由其它物体引起的间接光照光强，由It、Kt'计算，It通过对折射光线的递归跟踪得到。
将对一个由两个透明球和一个非透明物体组成的场景进行光线跟踪。通过这个例子，可以把光线跟踪的基本过程解释清楚。如图3.2所示。

图3.2 光线跟踪示意图
在场景中，有一个点光源L，两个透明的球体O1与O2，一个不透明的物体O3。首先，从视点出发经过视屏一个象素点的视线E传播到达球体O1，与其交点为P1。从P1向光源L作一条阴影测试线S1，很容易发现其间没有遮挡的物体，那么就用局部光照明模型计算光源对P1在其视线E的方向上的光强，作为该点的局部光强。同时还要跟踪该点处反射光线R1和折射光线T1，它们也对P1点的光强有贡献。在反射光线R1方向上，没有再与其他物体相交，那么就设该方向的光强为零，并结束这光线方向的跟踪。然后对折射光线T1方向进行跟踪，来计算该光线的光强贡献。折射光线T1在物体O1内部传播，与O1相交于点P2，由于该点在物体内部，假设它的局部光强为零，同时，产生了反射光线R2和折射光线T2，在反射光线R2方向，可以继续递归跟踪下去计算它的光强，在这里就不再继续下去了。将继续对折射光线T2进行跟踪。T2与物体O3交于点P3，作P3与光源L的阴影测试线S3，没有物体遮挡，那么计算该处的局部光强，由于该物体是非透明的，那么可以继续跟踪反射光线R3方向的光强，结合局部光强，来得到P3处的光强。反射光线R3的跟踪与前面的过程类似，算法可以递归的进行下去。重复上面的过程，直到光线满足跟踪终止条件。这样就可以得到视屏上的一个象素点的光强，也就是它相应的颜色值。
上面的例子就是光线跟踪算法的基本过程，可以看出，光线跟踪算法实际上是光照明物理过程的近似逆过程，这一过程可以跟踪物体间的镜面反射光线和规则透射，模拟了理想表面的光的传播。
虽然在理想情况下，光线可以在物体之间进行无限的反射和折射，但是在实际的算法进行过程中，不可能进行无穷的光线跟踪，因而需要给出一些跟踪的终止条件。在算法应用的意义上，可以有以下的几种终止条件：
（1）该光线未碰到任何物体。
（2）该光线碰到了背景。
（3）光线在经过许多次反射和折射以后，就会产生衰减，光线对于视点的光强贡献很小（小于某个设定值）。
（4）光线反射或折射次数即跟踪深度大于一定值。
最后用伪码的形式给出一般光线跟踪算法的源代码[5]。光线跟踪的方向与光传播的方向相反，从视点出发，对于视屏上的每一个象素点，从视点作一条到该象素点的射线，调用该算法函数就可以确定这个象素点的颜色。
光线跟踪算法的函数名为RayTracing()，光线的起点为start，光线的方向为direction，光线的衰减权值为weight，初始值为1，算法最后返回光线方向上的颜色值color。对于每一个象素点，第一次调用RayTracing()时，可以设起点start为视点，而direction为视点到该象素点的射线方向。
RayTracing(start,direction,weight,color)
{
if ( weight < MinWeight )
color = black;
else
{
计算光线与所有物体的交点中离start最近的点；
if ( 没有交点) color = black;
else
{
Ilocal = 在交点处用局部光照模型计算出的光强；
计算反射方向R；
RayTracing(最近的交点, R, weight*Wr, Ir);
计算折射方向T；
RayTracing(最近的交点, T, weight*Wt, It);
color = Ilocal + KsIr + KtIt;
}}}
3.2 本文算法实现的思想
在VC6.0开发环境下，应用Windows基础画图编程，创建一个MFC对话框架，此框架可以控制光源在场景中的位置，还可以开始和终止光线跟踪。
首先创建一个场景，背景色为黑色。在场景中创建若干个不透明的实体球，以及一个可变动坐标的光源了。为了使过程更加逼真，对球体进行旋转操作。
通过双重循环扫描，再单重循环定位，对场景中的球体进行检测是否相交，并求出最近的交点。
计算该点光强度，通过计算结果，对该球体进行阴影渲染操作，使之更具有真实感。
通过循环使大量的位图每秒以一定的帧数不停地显示，最后输出显示结果，实现在单一场景中的基于简单光照模型下的光线跟踪，进而增加场景中物体的真实感，并且给人一种连续的动态的感觉。
程序设计的两个主要的类，分别是：
1、CDib：主要的windows底层画图类。包括内存文件分配，基本画图工具等。
2、CRayTracerDlg：这个类是最为主要的。包括构造场景、构造光源、构造物体，以及最后的实现光线跟踪的过程方法，并能渲染生成单一位图、连续显示等。
程序中两个最关键的函数为：OnDemo()和TraceScene()。
OnDemo()函数是整程序的入口，负责开始演示程序到结束。以下是OnDemo()函数的伪代码。
OnDemo()
{ 定义3个球体Spheres[3]
创建开始的射线数组GenerateRayDirectionTable；
//如下列形式构造3个球，其中Center为中心，Radius为半径，Color为颜色。
Spheres[1/2/3].Center.X[/Y/Z] = 0;
Spheres[1/2/3].Radius = 0;
Spheres[1/2/3].Color.R[/G/B] = 0;
//构造视角，相当与人的眼睛的位置坐标
视角.X[Y/Z] = 0;
//光线位置
光线.X[Y/Z] = 100;
定义消息msg;
while(图象显示)
{ //旋转球体
for(球体个数)
{ 旋转函数(旋转参数); }
光线跟踪函数(球,光线位置); //场景跟踪函数
画图函数(…);
while (当有一条开始消息)
{ if (中断信息)
{ 中止跟踪; }
}
渲染函数();
}
}
下面这些是函数TraceScene()的伪代码，该函数是光线跟踪算法的核心部分：
void TraceScene(球, 向量 ，光线位置)
{ float 相交距离;
int 相交点;
TraceResult 跟踪结果;
for(框架纵坐标Y的范围)
{ for(框架横坐标X的范围)
{ //设置一个不可能的大值
相交距离 = 无穷远;
相交点 = 错误位置负坐标;
//遍历所有的球寻找最近点
for(3个球)
{ //与球体相交
跟踪结果 = 相交的球;
if(相交)
{ if ( 相交距离 < 最新相交点的距离 )
{ 相交距离 = 最新相交点的距离;
相交点 = 其中一个球;
break;
}}}
//有交叉点
if ( 最新相交球 > - 1)
{ 渲染函数(); }
else
{ 渲染.R[G/B] = 0; }
}
}}}
4 光线与物体的求交
作为真实感生成技术主要算法之一的光线跟踪算法，是典型的整体光照模型。光线跟踪很自然地解决了环境中所有物体之间的消隐、阴影、镜面反射和折射等问题。并且能够生成十分逼真的图形，而且算法的实现也相对简单。但是，作为一种递归算法，其计算量十分巨大。所以，尽可能减少求交计算量是提高光线跟踪效率的关键。
可见，求交算法成为光线跟踪算法的灵魂核心。如何计算优化求交算法一直是国内外研究的焦点、热点问题！本章节介绍几种简单的物体求交算法。
4.1 光线与球的求交
球是光线跟踪算法中最常用的体素，也是我们经常作为例子的物体，这是因为光线与球的交点很容易计算。特别是，球面的法向量总是从球心射出，无需专门的计算。另外，由于很容易进行光线与球的相交判断，所以球又常常用来作为复杂物体的包围盒。
设为光线的起点坐标，为光线的方向，已经单位化。为球心坐标，R为球的半径。下面我们介绍最基本的代数解法，以及为提高求交速度而设计的几何方法。
4.1.1 代数解法
首先用参数方程（公式4.1）来表示由点发出的光线，此时：
（4.1）
公式4.2则表示了一个球心为，球半径为R的球：
（4.2）
将式（4.1）代入（4.2），得到公式4.3：
（4.3）
于是有：
（4.4）
如果，则光线与球无交；
如果则光线与球相切，这时t=－B/2；
如果，则光线与球有两个交点，交点处的t分别是：
（4.1.5）
这时若有t0或t1<0，则说明相应的交点不在光线上，交点无效。
把t值代入（4.1）式，就可以求得交点的坐标，交点处的法向量为，这是一个单位化的向量。
用代数法计算光线与球的交点和法向量总共需要17次加减运算、17次乘法运算、1次开方运算和3次比较操作。
4.1.2 几何解法
用几何方法可以加速光线与球的求交运算。如图4.1所示：

图4.1 几何算法图解
首先要计算光线起点到球心的距离平方，见公式4.6：
（4.6）
若，则光线的起点在球内，光线与球有且仅有一个交点；
若，则光线的起点在球外，光线与球有两个交点或一个切点或没有交点。
然后需要计算光线起点到光线离球心最近点A的距离，见公式4.7：
（4.7）
式中，Rt为单位化的光线方向矢量。当光线的起点在球外，若tca<0，则球在光线的背面，光线与球无交点。再计算半弦长的平方，来判定交点的个数。
半弦长的平方为公式4.8：
(4.8)
若，则光线与球无交；
若，则光线与球相切；
若，则光线与球有两个交点。为了计算交点的位置，需要计算光线起点到光线与球交点的距离，见公式4.9：
(4.9)
用几何法计算光线与球的交点和法向总共需要16次加减运算、13次乘法运算、1次开方运算和3次比较操作。比代数法少1次加减运算和4次乘法运算。
4.2 光线与多边形求交
光线与多边形求交分以下两步：先计算多边形所在的平面与光线的交点，再判断交点是否在多边形内部。
平面方程可以表示为公式4.10：
Ax+By+Cz+D=0 (4.10)
代入公式4.1，可得：
(4.11)
(4.12)
所以：
(4.13)
此时，若分母为0，那么光线与平面没有交点。
一种判断交点是否位于多边型内部的简单方法是：将多边型与交点正投影到定义坐标系得三个平面之一，要获得最精确的结果应该选取有最大投影的方向轴，这时对应于多边形的平面方程中系数绝对值最大的坐标。对多边形顶点与该坐标做正投影。于是该点的包含测试就可以完全在二维中完成。基于奇偶校验原则，从光标所在位置发出一条射线然后计算它与多边形相交的次数。如图4.2所示。
该算法遍历边表，检测交点，并处理特殊情况（例如，交点与顶点重合，边与射线共线）。具体算法与多边形扫描转换算法处理的问题十分相似，稍作修改就可以使用[1]。

图4.2 光线与多边形是否相交的判定。
光线与多边形的交点P被投影到其中一个坐标系
平面上，再判定P'是否与投影多边形内部
4.3 光线与二次曲面求交
二次曲面包括球面、柱面、圆锥、椭球、抛物面、双曲面。平面和球面是一般二次曲面的一个特例。为了提高光线与二次曲面的求交效率，对每个二次曲面可以采取专门的求交算法。这里仅介绍光线与一般表示形式的二次曲面的求交方法。
二次曲面方程的一般形式可以表示为：
(4.14)
光线的参数表达式为：
(4.15)
把式(4.15)代入(4.14)式，并且整理得：
(4.16)
解出t，得：
(4.17)
如果t为实数，则将t代入式(4.15)就可以得到光线与二次曲面的交点坐标：
(4.18)
交点处的法向量为函数F(x,y,z)关于x,y,z的偏导，即：
(4.19)
4.4 本文程序实现部分应用的求交算法
本文的光线跟踪算法在求交的部分主要是应用几何解法对球进行求交。其好处是比代数解法的效率更高。根据上文提到的几何解法的相关内容，本节给出实现过程中应用的几何解法的伪代码。具体如下：
求交函数(光线, 球)
{ 定义眼睛到球体中心的向量;
定义眼睛到球体中心距离的平方;
定义最近相交球的距离;
定义球体中心到射线的垂直点与射线与球体交点的距离平方;
定义跟踪结果;
跟踪结果 = false;
眼睛到球体中心的向量并归到单一的原点;
眼睛到球体中心距离的平方 = 向量点积(球心, 眼睛到球体中心的距离);
最近相交球 = 向量点积(眼睛到球体中心的向量, 光线的方向);
// 如果是在背面，就返回失败（背面照不到光线）
if (最近相交球< 0) return跟踪结果;
求出球体中心到射线的垂直点与射线与球体交点的距离平方;
if (射线未与球体相交) return光线未照到球体；
跟踪结果 = true;
跟踪结果中相交球的距离 = float(最近相交球距离 - sqrt(球体中心到射线的垂直点与射线与球体交点的距离平方));
return 跟踪结果;
}
5 论文总结
5.1 展望研究方向：光线跟踪算法的加速
本文所研究的光线跟踪算法仅仅是其中最为简单易懂的部分，其实光线跟踪算法还有一个很广阔的研究方向就是对于光线跟踪算法加速的研究。这也是目前国内国外重点研究的对象。
基本的光线跟踪算法，每一条射线都要和所有的物体求交，然后再对所得的全部交点进行排序，才能确定可见点，对于复杂环境的场景，这种简单处理地效率就很低了，这里就需要对光线跟踪算法进行加速。光线跟踪加速技术是实现光线跟踪算法的重要组成部分。加速技术主要包括以下几个方面：
提高求交速度、减少求交次数、减少光线条数、采用广义光线和采用并行算
法等。这里只简单介绍其中的几种方法：
1、自适应深度控制
在基本光线跟踪算法中，结束光线跟踪的条件是光线不与任何物体相交，或已达到预定的最大光线跟踪深度。事实上，对复杂的场景，没有必要跟踪光线到很深的深度，应根据光线所穿过的区域的性质来改变跟踪深度，来自适应的控制深度。实际上，我们在前面给出的光线跟踪算法的源代码就是可以做到自适应的控制深度的。
2、包围盒及层次结构
包围盒技术是加速光线跟踪的基本方法之一，由Clark于1976年提出。1980年，Rubin和Whitted将它引进到光线跟踪算法之中[15]，用以加速光线与景物的求交测试。包围盒技术的基本思想是用一些形状简单的包围盒(如球面、长方体等)将复杂景物包围起来，求交的光线首先跟包围盒进行求交测试，若相交，则光线再与景物求交，否则光线与景物必无交。它是利用形状简单的包围盒与光线求交的速度较快来提高算法的效率的。
简单的包围盒技术效率并不高，因为被跟踪的光线必须与场景中每一个景物的包围盒进行求交测试。包围盒技术的一个重要改进是引进层次结构，其基本原理是根据景物的分布情况，将相距较近的景物组成一组局部场景，相邻各组又组成更大的组，这样，将整个景物空间组织成树状的层次结构。进行求交测试的光线，首先进入该层次的根节点，并从根节点开始，从上向下与各相关节点的包围盒进行求交测试。若一节点的包围盒与光线有交，则光线将递归地与其子节点进行求交测试，否则，该节点的所有景物均与光线无交，该节点的子树无需作求交测试。
1986年，Kay和Kajiya针对通常采用的长方体具有包裹景物不紧的特点，提出根据景物的实际形状选取n组不同方向的平行平面包裹一个景物或一组景物的层次包围盒技术。
3、三维DDA算法
从光线跟踪的效率来看，算法效率不高的主要原因是光线求交的盲目性。不仅光线与那些与之不交的景物的求交测试是毫无意义的，而且光线与位于第一个交点之后的其他景物求交也是豪无意义的。将景物空间剖分为网格，由于空间的连惯性，被跟踪的光线从起始点出发，可依次穿越它所经过的空间网格，直至第一个交点。这种方法称为空间剖分技术。可以利用这种空间相关性来加速光线跟踪。我们在这里首先介绍三维DDA算法。
1986年，Fujimoto等提出一个基于空间均匀网格剖分技术的快速光线跟踪算法，将景物空间均匀分割成为一系列均匀的3维网格，建立辅助数据结构SEADS (Spatially Enumerated Auxiliary Data Structure)。一旦确定景物空间剖分的分辨率，SEADS结构中的每一个网格可用三元组(i，j，k)精确定位，每一个网格均设立其所含景物面片的指针。于是，光线跟踪时，光线只须依次与其所经过的空间网格中所含的景物面片进行求交测试。Fujimoto等将直线光栅化的DDA算法推广到三维，称为光线的三维网格跨越算法。目前，该算法已经广泛的应用于各种商业动画软件中。
4、空间八叉树剖分技术
空间八叉树算法是一个空间非均匀网格剖分算法，该算法将含有整个场景的空间立方体按三个方向中剖面分割成八个子立方体网格，组织成一棵八叉树。若某一子立方体网格中所含景物面片数大于给定的阈值，则为该子立方体作进一步的剖分。上述剖分过程直至八叉树每一个叶子节点所含面片数均小于给定的阈值为止。这个算法也是利用了空间连贯性。八叉树的最大深度表示空间分割所达到的层次，称为空间分辨率，而八叉树的终结节点对应分割后的空间网格单元。
5.2 辐射度方法
另一个新的真实感图形绘制技术的算法是辐射度方法[16]，这也是目前最先进的算法。在以后的研究过程中，完全可以作为一个独立的课题来深入研究。
辐射度方法是继光线跟踪算法后，真实感图形绘制技术的一个重要进展。尽管光线跟踪算法成功地模拟了景物表面间的镜面反射、规则透射及阴影等整体光照效果，但由于光线跟踪算法的采样特性，和局部光照模型的不完善性，该方法难于模拟景物表面之间的多重漫反射效果，因而不能反映色彩渗透现象。
1984年，美国Cornell大学和日本广岛大学的学者Nishita[17]分别将热辐射工程中的辐射度方法引入到计算机图形学中，用辐射度方法成功地模拟了理想漫反射表面间的多重漫反射效果。经过十多年的发展，辐射度方法模拟的场景越来越复杂，图形效果越来越真实。与前几章介绍的光照模型与绘制方法有所不同，辐射度方法基于物理学的能量平衡原理，它采用数值求解技术来近似每一个景物表面的辐射度分布。由于场景中，景物表面的辐射度分布与视点选取无关，辐射度方法是一个视点独立(View independent)的算法,使之可广泛应用于虚拟环境的漫游(walkthrough)系统中[18]。
5.3 论文结语
本文对光线跟踪算法进行了深入的研究，从简单的光线跟踪模型，达到整体光线模型，从简单的单一场景道复杂的多光