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

在光线跟踪算法的递归过程中 在光线跟踪算法的递归过程中，加速算法有哪几种？说明他们分别运用与哪些场合光线跟踪的根本原理 由光源发出的光到达物体外表后，产生反射和折射，简洁光照明模型和光透射模型模拟了这两种现象在简洁光照明模型中，反射被分为志向漫反射和镜面反射光，在简洁光透射模型把透射光分为志向漫透射光和规那么透射光由光源发出的光称为干脆光，物体对干脆光的反射或折射称为干脆反射和干脆折射，相对的，把物体外表间对光的反射和折射称为间接光，间接反射，间接折射这些是光线在物体之间的传播方式，是光线跟踪算法的根底 最根本的光线跟踪算法是跟踪镜面反射和折射从光源发出的光遇到物体的外表，发生反射和折射，光就变更方向，沿着反射方向和折射方向接着前进，直到遇到新的物体但是光源发出光线，经反射与折射，只有很少局部可以进入人的眼睛因此实际光线跟踪算法的跟踪方向与光传播的方向是相反的，而是视线跟踪由视点与象素(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的方向上的光强，作为该点的局部光强同时我们还要跟踪该点处反射光线R1和折射光线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 =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]11010年，Rubin和Whitted将它引进到光线跟踪算法之中[RUBI80]，用以加速光线与景物的求交测试 包围盒技术的根本思想是用一些形态简洁的包围盒(如球面、长方体等)将困难景物包围起来，求交的光线首先跟包围盒进展求交测试，假设相交，那么光线再与景物求交，否那么光线与景物必无交它是利用形态简洁的包围盒与光线求交的速度较快来提高算法的效率的 简洁的包围盒技术效率并不高，因为被跟踪的光线必需与场景中每一个景物的包围盒进展求交测试包围盒技术的一个重要改良是引进层次构造，其根本原理是依据景物的分布状况，将相距较近的景物组成一组局部场景，相邻各组又组成更大的组，这样，将整个景物空间组织成树状的层次构造。

进展求交测试的光线，首先进入该层次的根节点，并从根节点起先，从上向下与各相关节点的包围盒进展求交测试假设一节点的包围盒与光线有交，那么光线将递归地与其子节点进展求交测试，否那么，该节点的全部景物均与光线无交，该节点的子树无需作求交测试 11016年，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算法 11016年，Fujimoto等提出一个基于空间匀称网格剖分技术的快速光线跟踪算法[FUJI86]，将景物空间匀称分割成为一系列匀称的3维网格，建立协助数据构造SEADS (Spatially Enumerated Auxiliary Da。