光线追踪基础

光线追踪基础 Len3d 整理 1.光线与物体的求交 1.1 球面 设光线起点为 O，单位方向向量为 V，则光线的参数方程为： )()( tVOtR  由于我们仅关心光线离开起始点 O 沿 V方向的交点，因而对参数 t<0 的交点可不予考虑。 设球面中心为 C，半径为 r，则起方程为： rCX  |||| 其中 X 为球面上的点，将光线方程代入上述球面方程，经整理得： 02  cbtat 其中 22||||),(2, rCOcCOVbVVa  若判别式△=b2­4ac<0，则上述二次方程无解。若线与球面无交。若△=0，则光线与球面像切。只有 一个交点。若△>0，则光线与球面两个交点。设其参数值分别为 t1 t2，其中大于 0 且参数值较小的交点都 为离起始点最近的交点，将该参数值代入光线方程就可求得最近交点 P，进而可求出该点处的单位法向量 r CP N   1.2 长方体 这里只介绍长方体的边都与坐标轴平行的长方体的情况，这种长方体有时称为 Axis­Aligned Bounding Box，简称 AABB。 一个长方体可以用下面 6 个平面方程来示： x=0 x=rx y=0 y=ry z=0 z=rz 其中 rx，ry和 rz 表示长方体的边长，因为至少有三个平面与光线 V的方向相背，所以需要考虑与光线 的相交问的平面最多有三个。通过检测光线 V 的分量，可以一次性确定这些平面。例如，如果Ｖx=0 那 么光线不可能与平面 x=0 或 x=rx 的任何一个相交，因为 V与它们平行；如果Ｖx>0 那么不需要考虑平面 x=rx 的相交情况，因为它对于光线来说是长方体的背面；同样，如果Ｖx<0 那么不需要考虑平面 x=0 的相 交情况，同样的原理适用于 V 的 y 分量和 z 分量。 一旦找到了光线与平面的交点，则必须确定该点是否位于长方体表面上，这是通过检测交点平行于 该平面的两个坐标分量来完成的。例如，t 对应的是光线与平面 x=rx 的交点，其值如下： Vx Oxrx t   为了保证位于长方体对应的表面上，点 P(t)的 y 和 z 坐标必须满足： rztPrytP  )]([0,)]([0 如果任一条件不满足，那么在表面上不存在任何交点。如果两个条件都满足，则可以得到一个交 点，在这种情况下，因为不会有其它更近的交点产生，所以不需要对其它平面进行检测。 1.3 三角形 假设 P0，P1，P2 为三角形的三个顶点，N0，N1，N2，分别为三顶点处的法向量，它们用来插值产生三角形 内部各点处的法向量，算法首先确定三角形所在的平面方程： 0 dNX 其中 X 为平面上的点， NPd PPPPN   0 0201 )()( 若 x,y,z三方向分别用 0,1,2来表示，则我们可以预先计算并存贮好平面法向量中其分量绝对值最大的 方向       最大，若 最大，若 最大，若 ||2 ||1 ||0 0 Nz Ny Nx i 类似于光线与球面的求交算法，光线与三角形所在平面的交点 Q 的参数值为： VN dON t    设 i1，i2 为不同于 i0 的其它两个方向，则由光线参数方程可计算出交点 Q 的 i1，i2两个分量 Qi1，Qi2 ： tViQiQi tViQiQi   222 111 这里下标为 i1，i2 的量分别表示相应向量的第 i1，i2 分量，因而，交点 Q 关于三角形 P0，P1，P2的三个顶 点的重心坐标为 的第 i0 分量／N 的第 i0 分量2,1,0)()( 3mod)1(3mod)1(3mod)2(   iPQPPi iii ， 其中(j) mod 3 表示整数 j 对 3 取模。 若 0≤β i ≤1 (i=0,1,2) ，则光线与三角形有交，否则无交，当有交点时，交点 Q 处的法向量:    2 0i iNiNq  1.4 牛顿迭代法 Newton­Raphson 迭代法是求根的一种数值方法，使用牛顿法可以求得任意连续函数的根，求解时要对 由该连续函数及其导数所确定的公式进行迭代。 首先，假定一个初始点 x0 作为函数的猜想根，曲线在点(x,f(x))的切线斜率可以由 f 的导数给出，这样 可以给出该切线的方程为： ))(()( 0xxxfxfy  切线与 x 轴相交于一点，该交点比初始猜想根 x0 更接近于 f 的实际根。在上式中令 y=0 并解方程，可 以得到根的求解迭代公式： )('/)(1 iiii xfxfxx  其中，用xi+1重新标识 x，用 xi 重新标识x0，反复运用此公式，可以得到一个数列：x0,x1,x2...在正常情 况下，这些值趋近于 f 的根。 牛顿法收敛得非常快，而且只需要很少得迭代次数就可以达到要求的精度。事实上，利用泰勒级数可 以证明牛顿法是二次收敛的，也就是说每次迭代之后，近似根有效数字的位数大约增加一倍，请自主思 考其证明方法。 2. 光线追踪几何 2.1 法向量的计算 有时用隐函数 f(x,y,z)能够很方便地表示一个曲面，在曲面上任一点(x,y,z)该函数值为零，而在曲面之 外函数值不为零。 假设 f(x,y,z)表示一个曲面 S，则 f(x,y,z)=0对曲面 S 上的所有点都成立，设 C是位于曲面 S 上并且由 可微函数 x(t),y(t)和 z(t)定义的一条曲线，曲线 C 在点的切向量 T 表示为： t z t y t x T        ,, 由于曲线 C在曲面 S 上，所以 T也与曲面 S 相切。同样，由于对任意的 t 值都有 f(x(t),y(t),z(t))=0，所 以在曲线 C 上任一点处 df/dt=0 都成立，根据链式法则，可以写成： ),,( zyxf 因为与 T 的点积总为零，所以向量< f/ x, f/ y, f/ z >肯定是曲面 S 的法向量，这个向量，称 为 f 在点处的梯度，通常记为 grad f(x,y,z) 2.2 反射向量和折射向量的计算 反射光线单位向量可用下式来表示： LLNNR  )(2 其中 L 为单位入射光线方向向量，N为表面单位法向量，且 R，L 和 N 共面。 当光线与一透明表面相遇时，入射光会在景物表面相交处改变方向形成折射光，由折射定律知，入 射角θ１与折射角θ２的关系为： sinθ1/sinθ2=η2/η1 其中η1, η2 分别为入射光和折射光所在空间介质的折射率，单位折射光线方向向量 T与 L，N 共 面，且有： T=1/η L­(cosθ2­1/η·cosθ1)N cosθ2=[1­1/η(1­cos2θ1)]1/2 其中η为相邻介质的相对折射率，即η=η2／η1，值得注意的是，当光线从较大折射率的介质进入 折射率较小的介质时，会出现全反射现象，特别的当入射角大于某个临界角θc时，该光线将在介质表面 产生全反射。 2.3 三角形的重心坐标（barycentric coordinate） 请参考以下链接 http://mathworld.wolfram.com/BarycentricCoordinates.html 3. 光线追踪的加速技术 3.1 层次包围盒算法 包围盒技术用一个形状较简单的包围盒（如球面，长方体等）将复杂景物包裹起来。求交时光线首 先与包围盒进行求交测试。若它们相交，则光线再与包围盒中所含景物进行求交计算。否则光线与景物 无交。由于光线与包围盒的求交相对简单，因而包围盒技术可以较小的代价快速剔除那些与光线不相交 的景物。但对与光线相交的景物来说，光线于其包围盒的求交计算是一种额外的代价。为此包围盒形状 应相对简单的尽可能降低这一代价。另一方面，简单的包围盒可能包裹景物不紧，与包围盒香蕉的光线 并不一定与其中所含景物相交，从而导致算法求交测试的可靠性下降。综上，包围盒技术应在包围盒形 状的简单性和对其中所含景物包裹的紧密程度之间做一折衷。 上述简单包围盒技术的效率并不十分高，其原因在于被跟踪的光线与场景中每一景物的包围盒都必 须进行求交测试，算法的复杂性为 O(N)。这里 N 为场景中景物的数目，包围盒技术的一个重要改进是引 进了层次结构。其基本原理是根据景物的分布情况，将相距较近的景物组成一组局部场景。各相邻组又 可组成更大的组，这样，整个场景就被组织成树状层次结构，算法同时建立起各结点局部场景的包围 盒。它的根结点即为整个场景及其包围盒。 被跟踪的光线首先进入该层次结构的根结点，并从根结点开始从上至下与各相关结点的包围盒进行 求交测试。若其一结点的包围盒与光线有交，则光线将递归地与其子结点进行求交测试，反之则该结点 所含的所有景物必与光线不相交。因而对该结点及其子树无须继续做任何测试。其复杂度为 O(logN)。 请自主思考层次包围盒结构的建立方法。 3.2 3DDDA 3DDDA将景物空间剖分成一系列均匀的三维网格。从而建立起一个称为SEADS(Spatially Enumerated Auxiliary Data Structure)的辅助数据结构。 一旦确定景物空间剖分的分辨率 SEADS 结构中的每一网格可简单地用一整数三元组(i,j,k)来精确定 位。没一网格中均含对应的景物面片表。光线跟踪时，光线只需依次与其经过空间网格中所含的景物面 片进行求交测试即可。 为快速确定位于光线跟踪路径上的各三维网格，可将在屏幕上绘制二维直线的 DDA(Digital DifferentialAnalyzer)算法推广成光线的三维网格跨越算法，请自主查阅 2DDDA 算法资料并思考如何广到 3D情形。 由于 SEADS 结构与景物在场景中实际分布无关联。因而算法的效率严重依赖于空间剖粉的分辨率。 一般来说，分辨率取得越高剖粉产生的三维网格就越多。各网格内包含的景物面片相对较少，光线与景 物面片的求交测试次数亦较少。但光线所需跨越的网格数则大大增加。另外，由于 SEADS 结构需存储所 有的三维网格而不管其是否为空，因次当空间剖分分辨率取得较大时，将导致庞大的内存耗费。当场景 中的景物分布较稀疏时，SEADS结构中常含有大量空网格，这使得每条光线在达到最近交点之前，需跨 越大量的空网格，从而降低了算法的效率。 3.3 空间八叉树(Octree) 空间八叉树算法是一个空间非均匀网格剖分算法，该算法将含有整个场景的空间立方体按三个方向 中剖面分割成八个子立方体网格，组织成一棵八叉树。上述剖分过程递归进行直至八叉树中每一叶结点 子空间所含景物面片数均小于给定阈值为止。 进行光线跟踪时，算法从光线起始点出发，给光线前进方向依次确定光线穿越的八叉树叶结点网 格。若为前叶结点网格为非空结点。则光线匀它所包含的景物进行求交测试，若求得光线与景物的第一 个交点，前进方向继续进行搜索。进入与为前空间网格相邻的下一个叶结点网格进行求交测试。该算法 与 3DDDA 相比的优点在于它可以根据景物在场景中的实际分布对场景空间做非均匀剖分。生成较少的网 格。 请自主搜索空间八叉树的更多信息。 3.4 空间二叉树(BSP) 二叉空间剖分(Binary Space Partitioning)充分利用里平面的定侧性质，即空间中的任一平面总是将整 个空间分成两部分。一部分位于其正侧，另一部分位于其负侧。空间二叉树的每一结点表示一子空间及 其所包含的多边形。在每一枝结点空间中，选取其中一平面将该空间剖分成正负两子空间，作为该结点 的两个子结点，每一子空间包含了位于其内部的多边形。其中与分割平面有交的多边形被分割成两个多 边形，被分别归入相应的子空间中。上述过程递归进行直至处理完场景中有平面多边形为止。这时我们 可采用类似于八叉树的方法来加速光线跟踪算法，请自主思考该方法。 3.5 Beam Tracing 请参考以下链接： http://artis.imag.fr/Publications/1998/GH98/CG98.pdf 3.6 Cone Tracing 请参考以下链接： http://www.cse.yorku.ca/~amana/research/cones.pdf 3.7 Pencil Tracing 请参考以下链接： http://delivery.acm.org/10.1145/40000/37408/p45­ shinya.pdf?key1=37408&key2=2620012511&coll=portal&dl=ACM&CFID=15151515&CFTOKEN=61846 18 3.8 Distributed Ray­tracing 请参考以下链接： http://graphics.pixar.com/DistributedRayTracing/paper.pdf http://www.dgp.toronto.edu/~hertzman/courses/csc418/winter_2006/lectureNotesWeb/DistributionRayTracin g.pdf 3.9 Ray Classification 请参考以下链接： http://artis.imag.fr/~Cyril.Soler/DEA/Ombres/Papers/Arvo.Sig87.pdf 3.10 Ray Differentials 请参考以下链接： http://graphics.stanford.edu/papers/trd/trd_jpg.pdf 更多内容请参考： ray tracing II http://graphics.cs.uni­sb.de/Courses/ws0203/cg/folien/CG02RayTracing2.pdf ray tracing http://www.tml.tkk.fi/Opinnot/Tik­111.500/2002/paperit/harri_hiila.pdf efficiency issues for ray tracing http://www.ce.chalmers.se/edu/course/EDA425/EfficiencyIssuesForRayTracing.pdf interactive rendering with coherent ray tracing http://graphics.cs.uni­sb.de/Publications/2001/InteractiveRenderingWithCoherentRayTracing.pdf rendering complex scenes with memory coherent ray tracing http://graphics.stanford.edu/papers/coherentrt/coherentrt­figs.pdf ray differentials and multiresolution geometry caching http://graphics.pixar.com/RayDifferentials/paper.pdf interactive distributed ray tracing of highly complex models http://graphics.cs.uni­sb.de/Publications/2001/egrw2001.pdf temporally coherent interactive raytracing http://citeseer.ist.psu.edu/rd/34280220%2C607445%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/ papers/cs/30145/http:zSzzSzwww.cs.utah.eduzSzgdczSzpublicationszSzpaperszSzalias.pdf/martin01temporally.p df direct ray tracing of displacement mapped triangles http://www.cs.utah.edu/~bes/papers/height/paper.pdf ray­tracingprocedural displacement shaders http://www.cs.ubc.ca/~heidrich/Papers/GI.98.pdf kd­tree acceleration structures for a gpu raytracer http://graphics.stanford.edu/papers/gpu_kdtree/kdtree.pdf on building fast kd­trees for ray­tracing http://www.sci.utah.edu/~wald/Publications/webgen/2006/KDTreeTR/download/kdtree.pdf fast ray­tracing using kd­trees http://citeseer.ist.psu.edu/rd/7175704%2C563197%2C1%2C0.25%2CDownload/http://coblitz.codeen.org:3125/cit eseer.ist.psu.edu/cache/papers/cs/27523/http:zSzzSzwww.cs.utexas.eduzSzftpzSzpubzSztechreportszSztr88­ 07.pdf/fussell88fast.pdf ray­tracingwith bsp and rope trees http://www.cescg.org/CESCG­2000/JKrivanek/paper.pdf cylindrical space partitioning for ray­tracing http://citeseer.ist.psu.edu/rd/34280220%2C575182%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/ papers/cs/27060/http:zSzzSzwww.labri.frzSzLabrizSzPublicationszSzRapports­interneszSzRR­ 106795.pdf/cylindrical­space­partitioning­for.pdf efficient bounded adaptive tessellation of displacement maps http://www.cgl.uwaterloo.ca/~krmoule/dmap_gi2002.pdf parallel ray­tracing with 5d adaptive subdivision http://wscg.zcu.cz/wscg2001/Papers_2001/R30.pdf multi­level ray­tracing algorithm ftp://download.intel.com/technology/computing/applications/download/mlrta.pdf ray­tracingon a stream processor http://citeseer.ist.psu.edu/rd/41957681%2C705627%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/ papers/cs/33355/http:zSzzSzgraphics.stanford.eduzSzpaperszSztpurcell_thesiszSztpurcell_thesis.pdf/purcell04ray. pdf ray interpolants for fast ray­tracing of reflective and refractive objects http://www.cs.umd.edu/~mount/Papers/egrw01.pdf monte carlo techniques for direct lighting calculations http://citeseer.ist.psu.edu/rd/34280220%2C64612%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/p apers/cs/175/http:zSzzSzwww.cs.utah.eduzSz%7EshirleyzSzpubszSztog94.pdf/shirley96monte.pdf