在光线跟踪算法的递归过程中，加速算法有哪几种？说明他们分别使用与哪些场合 光线跟踪的基本原理
由光源发出的光到达物体表面后，产生反射和折射，简单光照明模型和光透射模型模拟了这两种现象。在简单光照明模型中，反射被分为理想漫反射和镜面反射光，在简单光透射模型把透射光分为理想漫透射光和规则透射光。由光源发出的光称为直接光，物体对直接光的反射或折射称为直接反射和直接折射，相对的，把物体表面间对光的反射和折射称为间接光，间接反射，间接折射。这些是光线在物体之间的传播方式，是光线跟踪算法的基础。 最基本的光线跟踪算法是跟踪镜面反射和折射。从光源发出的光遇到物体的表面，发生反射和折射，光就改变方向，沿着反射方向和折射方向继续前进，直到遇到新的物体。但是光源发出光线，经反射与折射，只有很少部分可以进入人的眼睛。因此实际光线跟踪算法的跟踪方向与光传播的方向是相反的，而是视线跟踪。由视点与象素(x,y) 发出一根射线，与第一个物体相交后，在其反射与折射方向上进行跟踪，如图4.6.1所示。
图4.6.1 基本光线跟踪光路示意
为了详细介绍光线跟踪算法，我们先给出四种射线的定义与光强的计算方法。在光线跟踪算法中，我们有如下的四种光线：视线是由视点与象素 (x，y)发出的射线；阴影测试线是物体表面上点与光源的连线；以及反射光线与折射光线。 当光线 V与物体表面交于点P时，点P分为三部分，把这三部分光强相加，就是该条光线V在P点处的总的光强：
a) 由光源产生的直接的光线照射光强，是交点处的局部光强，可以由下式计算：
b) 反射方向上由其它物体引起的间接光照光强，由 IsKs' 计算，Is通过对反射光线的递归跟踪得到 c) 折射方向上由其它物体引起的间接光照光强，由ItKt' 计算，It通过对折射光线的递归跟踪得到。 在有了上面介绍的这些基础之后，我们来讨论光线跟踪算法本身。我们将对一个由两个透明球和一个非透明物体组成的场景进行光线跟踪（图4.6.2）通过这个例子，可以把光线跟踪的基本过程解释清楚。
图4.6.2 光线跟踪算法的基本过程
在我们的场景中，有一个点光源L，两个透明的球体O 1与O2，一个不透明的物体O3。首先，从视点出发经过视屏一个象素点的视线E传播到达球体O1，与其交点为P1。从P1向光源L作一条阴影测试线S1，我们发现其间没有遮挡的物体，那么我们就用局部光照明模型计算光源对P1在其视线E的方向上的光强，作为该点的局部光强。同时我们还要跟踪该点处反射光线R
1和折射光线T1，它们也对P1点的光强有贡献。在反射光线R1方向上，没有再与其他物体相交，那么就设该方向的光强为零，并结束这光线方向的跟踪。然后我们来对折射光线T1方向进行跟踪，来计算该光线的光强贡献。折射光线T1在物体O1内部传播，与O1相交于点P2，由于该点在物体内部，我们假设它的局部光强为零，同时，产生了反射光线R2和折射光线T2，在反射光线R2方向，我们可以继续递归跟踪下去计算它的光强，在这里就不再继续下去了。我们将继续对折射光线T2进行跟踪。T2与物体O3交于点P3，作P3与光源L的阴影测试线S3，没有物体遮挡，那么计算该处的局部光强，由于该物体是非透明的，那么我们可以继续跟踪反射光线R3方向的光强，结合局部光强，来得到P3处的光强。反射光线R3的跟踪与前面的过程类似，算法可以递归的进行下去。重复上面的过程，直到光线满足跟踪终止条件。这样我们就可以得到视屏上的一个象素点的光强，也就是它相应的颜色值。 上面的例子就是光线跟踪算法的基本过程，我们可以看出，光线跟踪算法实际上是光照明物理过程的近似逆过程，这一过程可以跟踪物体间的镜面反射光线和规则透射，模拟了理想表面的光的传播。 虽然在理想情况下，光线可以在物体之间进行无限的反射和折射，但是在实际的算法进行过程中，我们不可能进行无穷的光线跟踪，因而需要给出一些跟踪的终止条件。在算法应用的意义上，可以有以下的几种终止条件： • 该光线未碰到任何物体。 • 该光线碰到了背景。 • 光线在经过许多次反射和折射以后，就会产生衰减，光线对于视点的光强贡献很小（小于某个设定值）。 • 光线反射或折射次数即跟踪深度大于一定值。 最后我们用伪码的形式给出光线跟踪算法的源代码。光线跟踪的方向与光传播的方向相反，从视点出发，对于视屏上的每一个象素点，从视点作一条到该象素点的射线，调用该算法函数就可以确定这个象素点的颜色。光线跟踪算法的函数名为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; } } }
光线与物体的求交 对于反射光线与折射光线的方向计算问题，我们已经在前面的Whitted光透射模型中做了详细的介绍，在这里我们就不再讨论了。由于光线跟踪算法中需要用到大量的求交运算，因而求交运算的效率对于整个算法的效率影响很大，光线与物体的求交是光线跟踪算法的核心。我们将要在这一小节中按照不同物体的分类给出光线与物体的求交运算方法。 A．光线与球的求交 球是光线跟踪算法中最常用的体素，也是我们经常作为例子的物体，这是因为光线与球的交点很容易计算，特别是，球面的法向量总是从球心射出，无需专门的计算。另外，由于很容易进行光线与球的相交判断，所以球又常常用来作为复杂物体的包围盒。 设(x0,y0,z0)为光线的起点坐标，(xd,yd,zd)为光线的方向，并已经单位 绍最基本的代数解法，以及为提高求交速度而设计的几何方法。 1）代数解法 首先我们用参数方程
来表示由点(x0,y0,z0
)发出的光线，这t>=0。用隐式方程 表示球心为(xc,yc,zc
),求半径为R的球面。将式(4.6.1)代入(4.6.2)，得：
用代数法计算光线与球的交点和法向量总共需要17次加减运算、17次乘法运算、1次开方运算和3次比较操作。 2）几何解法
图4.6.3 几何法进行光线与球的求交 用几何方法可以加速光线与球的求交运算。如图4.6.3所示，几何方法具体的步骤我们在下面介绍。首先要计算光线起点到球心的距离平方，为： 点。然后，我们需要计算光线起点到光线离球心最近点A的距离，为： 式中，Rt为单位化的光线方向矢量。当光线的起点在球外，若tca
<0，则球在光线的背面，光线与球无交
点。再计算半弦长的平方，来判定交点的个数。半弦长的平方为：
与球有两个交点。为了计算交点的位置，我们需要计算光线起点到光线与球交点的距离为： 同样，将t值代入式（4.6.1），可得交点的坐标为：
用几何法计算光线与球的交点和法向总共需要16次加减运算、13次乘法运算、1次开方运算和3次比较操作。比代数法少1次加减运算和4次乘法运算。 B．光线与多边形求交 光线与多边形求交分以下两步：先计算多边形所在的平面与光线的交点，再判断交点是否在多边形内部。光线与平面求交的具体方法我们前面的章节中已有详细的介绍，这里不再重复了。 C．光线与二次曲面求交 二次曲面包括球面、柱面、圆锥、椭球、抛物面、双曲面。平面和球面是一般二次曲面的一个特例。为了提高光线与二次曲面的求交效率，对每个二次曲面可以采取专门的求交算法。这里介绍光线与一般表示形式的二次曲面的求交方法。
二次曲面方程的一般形式可以表示为：
或者写成矩阵形式就是： 把光线的参数表达式(4.6.1)代入上式，并且整理得：
光线跟踪算法的加速
基本的光线跟踪算法，每一条射线都要和所有的物体求交，然后再对所得的全部交点进行排序，才能确
定可见点，对于复杂环境的场景，这种简单的处理地效率就很低了，这里就需要对光线跟踪算法进行加速。光线跟踪加速技术是实现光线跟踪算法的重要组成部分。加速技术主要包括以下几个方面：提高求交速度、减少求交次数、减少光线条数、采用广义光线和采用并行算法等。我们在这里只是简单的介绍其中的几种方法。 A．自适应深度控制 在基本光线跟踪算法中，结束光线跟踪的条件是光线不与任何物体相交，或已达到预定的最大光线跟踪深度。事实上，对复杂的场景，没有必要跟踪光线到很深的深度，应根据光线所穿过的区域的性质来改变跟踪深度，来自适应的控制深度。实际上，我们在前面给出的光线跟踪算法的源代码就是可以做到自适应的控制深度的。 B．包围盒及层次结构 包围盒技术是加速光线跟踪的基本方法之一，由Clark于1976年提出[CLAR76]。1980年，Rubin和Whitted将它引进到光线跟踪算法之中[RUBI80]，用以加速光线与景物的求交测试。 包围盒技术的基本思想是用一些形状简单的包围盒(如球面、长方体等)将复杂景物包围起来，求交的光线首先跟包围盒进行求交测试，若相交，则光线再与景物求交，否则光线与景物必无交。它是利用形状简单的包围盒与光线求交的速度较快来提高算法的效率的。 简单的包围盒技术效率并不高，因为被跟踪的光线必须与场景中每一个景物的包围盒进行求交测试。包围盒技术的一个重要改进是引进层次结构，其基本原理是根据景物的分布情况，将相距较近的景物组成一组局部场景，相邻各组又组成更大的组，这样，将整个景物空间组织成树状的层次结构。 进行求交测试的光线，首先进入该层次的根节点，并从根节点开始，从上向下与各相关节点的包围盒进行求交测试。若一节点的包围盒与光线有交，则光线将递归地与其子节点进行求交测试，否则，该节点的所有景物均与光线无交，该节点的子树无需作求交测试。 1986年，Kay和Kajiya针对通常采用的长方体具有包裹景物不紧的特点，提出根据景物的实际形状选取n组不同方向的平行平面包裹一个景物或一组景物的层次包围盒技术[KAY86]。 令3D空间中的任一平面方程为Ax+By+Cz-d=0，不失一般性，设(A,B,C)为单位向量，上式定义了一个以Ni=(A,B,C)为法向量，与坐标原点相距d的平面。若法向量Ni
