表示球心为(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=(A,B,C)保持不变，d为自由变量，那么我们就定义了一组平
用几组平面就可以构成一个较为紧致的包围盒。Kay和Kajiya对Ni的选取作限制，即整个场景所有景物采用统一方向的n组平行平面来构造包围盒，且
对多面体模型，在场景坐标系中考虑。多面体所有顶点投影到Ni方向，并
景物坐标系中，隐函数曲面体上的点(x,y,z)在Ni方向上的投影为f(x,y,z)
下的极大值和极小值。可以Lagrange乘子法计算。
限于篇幅的原因，关于平行2n面体层次包围盒技术的细节，请参见[KAY86]。 C．三维DDA算法
从光线跟踪的效率来看，算法效率不高的主要要原因是光线求交的盲目性。不仅光线与那些与之不交的景物的求交测试是毫无意义的，而且光线与位于第一个交点之后的其他景物求交也是豪无意义的。将景物空间剖分为网格，由于空间的连惯性，被跟踪的光线从起始点出发，可依次穿越它所经过的空间网格，直至第一个交点。这种方法称为空间剖分技术。可以利用这种空间相关性来加速光线跟踪。我们在这里首先介绍三维DDA算法。
1986年，Fujimoto等提出一个基于空间均匀网格剖分技术的快速光线跟踪算法[FUJI86]，将景物空间均匀分割成为一系列均匀的3维网格，建立辅助数据结构SEADS (Spatially Enumerated Auxiliary Data Structure)。
一旦确定景物空间剖分的分辨率，SEADS结构中的每一个网格可用三元组(i，j，k)精确定位，每一个网格均设立其所含景物面片的指针。于是，光线跟踪时，光线只须依次与其所经过的空间网格中所含的景物面片进行求交测试。
Fujimoto等将直线光栅化的DDA算法推广到三维，称为光线的三维网格跨越算法，以加速光线跟踪。设光线的方向向量为V(Vx，Vy，Vz)，我们先求出被跟踪光线的主轴方向d，是：
设其它两个坐标方向为i和j，那么三维DDA网格跨越过程，可分解为两个二维DDA过程，这个二维DDA过程我们已经在前面的章节中介绍过了。算法首先将光线垂直投影到交于主轴的两个坐标平面上，然后对两投影线分别执行二维DDA算法。
这个算法对于稠密的场景，选取适当的空间剖分分辨率，可以使算法非常有效。目前，该算法已经广泛地应用于各种商业动画软件中。 D．空间八叉树剖分技术
空间八叉树算法是一个空间非均匀网格剖分算法,该算法将含有整个场景的空间立方体按三个方向分割成八个子立方体网格，组织成一棵八叉树。若某一子立方体网格中所含景物面片数大于给定的阈值，则为该子立方体作进一步的剖分。上述剖分过程直至八叉树每一个叶子节点所含面片数均小于给定的阈值为止。这个算法也是利用了空间连贯性。
八叉树的最大深度表示空间分割所达到的层次，称为空间分辨率，而八叉树的终结节点对应分割后的空间网格单元。设八叉树的深度为N，任一个八叉树终结节点的编码为
由上述八叉树结点的编码方式很容易找到空间任一点所在的空间网格单元。设P(x,y,z)为一空间点，x,y,z取整数，其相应的二进制表