光线追踪

本文首先将会介绍光线追踪的类别族谱，介绍其公共部分，之后我们会分别对其中的每一个进行详细地剖析。

光线追踪（Raytracing）是一个拥有历史感的词汇。图形学从业者从neutrontransport、heattransfer和illuminationengineering等领域引进其思想。由于这些概念被许多领域所研究，导致光线追踪的术语在学科之间和学科内部都进行着不断发展，有时也会产生分歧。经典的论文也可能会错误地使用术语，这就可能会造成混淆。所以，在介绍光线追踪的概念之前，我们需要分清楚这些术语的概念。

几乎所有的现代光线追踪器都是使用递归和蒙特卡罗方法；但是现在已经很少会有人把他们称为“递归的蒙特卡洛”方法。

第一个用于渲染的光线投射算法最初由ArthurAppel在1968年引入。光线投射通过从观察点对每一个像素发射一条光线并找到在世界场景中阻挡光线路径的最近物体来渲染场景，RayCasting只有两种射线，第一种是眼睛发射的eye射线，来寻找场景中的交点，另一个是从交点发到灯光的阴影射线，看自身是否是处于阴影当中。与传统扫描线渲染算法相比，光线投射的一个显着优点是能够处理不平整的表面和固体。电子世界争霸战（1982年电影TronSeries）的大部分动画都是使用光线投射技术渲染的。

早年间光栅化技术还未流行时，也会用于游戏当中。最著名的一款光线投射的游戏是Wolfenstein3D。接下来将介绍不论在光线追踪还是光线投射算法中都通用的公共部分，避免之后的内容太过的庞杂。

2.1光线投射基本算法

Render()foreachpixelx,ycolor(pixel)=Trace(ray_through_pixel(x,y))首先做的就是创建光线，得到每一个点的光线数据结构，之后开始Trace，这里使用Trace这个函数名是为了和后面统一。是指在场景中追踪这个光线。

Trace(ray)object_point=Closest_intersection(ray)ifobject_pointreturnShade(object_point,ray)elsereturnBackground_ColorRender()foreachpixelx,ycolor(pixel)=Trace(ray_through_pixel(x,y))我们在场景中寻找光线与场景中的物体是否有交点，并返回距离我们最近的那一个object的信息，如果找到，我们进行着色如果没找到我们返回设定的背景颜色。

Closest_intersection(ray)foreachsurfaceinscenecalc_intersection(ray,surface)returntheclosestpointofintersectiontoviewer在光线投射的Closest_intersection中，我们并不需要额外的返回其他的复杂信息。

Shade(point,ray)tocalculatecontributionsofeachlightsource光线投射的着色，你可以自由发挥，最初的实现中也只有阴影的划分。对于像Wolfenstein3D这样的实时游戏中的场景，一般是使用了额外的场景信息，来提高性能。总之这里的shade并不重要，主要是理解RayCast这个思想框架，而之后的所有算法都是在这个框架中的发挥。

当然我们也可以进行简单的着色计算，这就和不进行递归的RayTracing是一致的，我们放在之后来做对比。

在这里，对于局部、世界和相机空间的转换关系是和光栅化渲染中的空间转换的做法基本类似，所以在这里就不进行赘述。

大多数情况下，我们使用p(t)=e+t(s-e)的方法来进行光线的表示，e是我们设定的相机观察点，而s是画布上的点，通常我们渲染之前预先设定的长宽，然后我们通过参数t来表示光线的长度。

对于求交问题，网上非常多的资料，这里就不讲了，只给出思路和参考资料。

这里有一个对于物体来说是显示表示还是隐式表示法的问题。

大致上，WhittedRayTrace其主要把光线分为四种：

为了使光线追踪更有效，引入了后向光线追踪方法。在后向光线中，在眼睛处产生眼睛光线；它通过视平面并进入世界。射线击中的第一个物体是从视平面的那个点可见的物体。

后向光线的缺点是它假设只有通过视平面并进入眼睛的光线对场景的最终图像有贡献。在某些情况下，这种假设是有缺陷的。例如，如果一个透镜被固定在桌子顶部的一个距离处，并且被正上方的光源照亮，那么在透镜下面会有一个具有大光浓度的焦点。如果反向光线追踪试图重新创建此图像，则会计算错误，因为向后发射光线只会确认光线通过透镜；反向光线无法识别通过透镜的正向光线弯曲。因此，如果只进行反向光线追踪，透镜下方将只有一个均匀的光斑，就像透镜是一块普通的玻璃。

如上所述，有效且最容易实现性能优化的一种方法是从眼睛向后发射光线，而不是从光源光发射线。通过这种方式，不会浪费计算能力来从未击中模型或相机的光线。

3.1.3混合光线追踪由于前向光线追踪和后向光线追踪都有其缺点，最近的研究试图开发出会影响速度和精度的混合解决方案。在这些混合解决方案中，仅执行某些级别的前向射线。算法记录数据，然后继续执行后向光线追踪。场景的最终着色将后向光线和前向光线计算都考虑在内。

Veach（1995）发明出了后向光线追踪+前向光线追踪+连接线（BidirectionalPathTracing）的混合方法，这在后面会讲解。

综上，而我们的Whitted光线追踪一般而言都时使用的向后渲染的方式来进行的（从眼睛发射光线）。

之前的框架是一样的，所以这里就不都列出来了，只列出不一样的部分。

Shade(point,ray)calculatesurfacenormalvectorusePhongilluminationformulatocalculatecontributionsofeachlightsource首先如之前所列的年代关系，出现Whitted光线追踪时，并没有提出我们现在做全局光照的渲染方程，所以当时依旧是使用的基于经验的光照模型，就像这里的phong。当然你也可以用其他的。

我们来看递归的形式：

Shade(point,ray)radiance=black;/*初始化*/foreachlightsourceshadow_ray=calc_shadow_ray(point,light)if!in_shadow(shadow_ray,light)radiance+=phong_illumination(point,ray,light)ifmaterialisspecularlyreflectiveradiance+=spec_reflectance*Trace(reflected_ray(point,ray)))ifmaterialisspecularlytransmissiveradiance+=spec_transmittance*Trace(refracted_ray(point,ray)))returnradiance首先进行这个点的颜色初始化，如果不在阴影中，我们phong模型的着色，如果材质拥有镜面反射，最后的颜色要加上镜面反射光线的颜色贡献，如果材质拥有折射特性，加上折射的贡献。

还有一个比较重要的问题是什么时候结束这个罪恶的递归？有两种情况。第一种情况是，光线没有打到物体上，第二种是由于每一次反射或者折射，贡献值会逐渐的降低，我们预先设定一个阈值，当它小于这个阈值的时候，我们停止。当然，如果你只按照上面的做法来渲染一个图片出来是可行的，但是会有一些需要解决的问题。

我们首要问的问题时，为什么会产生锯齿？由于之前的光线追踪算法对每一个像素值，都只创建了一个光线，都只采样了场景中的一个点，和那一个颜色，但是，对于一个像素而言，有可能包含了很多个不同的点，尤其是在物体边缘的情况下时，这些点不一定都有相同的颜色。而我们这种有规律的采样，就会导致这种锯齿。

3.3.2自适应超级采样自适应超级采样（也称为蒙特卡罗采样）是一种以更智能的方式进行超采样的尝试。首先发出固定数量的光线并比较它们的颜色。如果颜色相似，则程序假定像素正在查看同一个对象，并且光线的平均值被计算为该像素的颜色。如果光线颜色不同（由某个阈值定义）那么我们认为这个像素比较特殊需要进一步检查。在这种情况下，像素被细分为更小的区域，并且每个新区域被视为一个完整的像素。这个过程再次开始，同样的固定光线模式被射入每个新的部分。

遗憾的是，自适应超级采样仍然将像素划分为规则的光线模式，并且会受到常规像素细分可能出现的混叠的影响。例如对象和采样网格几乎是对齐的。总之有规律的方法都不得劲。

3.3.3随机采样Stochastic（随机）采样将固定数量的光线发送到像素中，但确保它们是随机分布的（但或多或少均匀地覆盖该区域）。此外，Stochastic射线试图解决在凹凸不平的表面上跟随入射光线的问题。这是分布式光线追踪中比较核心的概念，所以放在下面来说。

3.4加速结构

加速结构用于限制要检查的对象数量以找到与谁相交的技术。例如，如果我们有一条射线，它将一个物体与数千个物体相交，我们想以某种方式智能地清除远离光线的物体。

3.4.1包围盒（BoundingVolumes）基于层次关系的划分方法中包围盒层次结构最有代表性。层次包围盒算法的基本思想是：用形状简单的包围盒（如球形、长方体等）将场景中的面片包围，相邻的包围盒被包含在一个更大的包围盒里，逐级扩大，生成一个层次的结构；在进行光线与物体相交测试之前，先进行光线与包围盒的测试，如果光线与包围盒相交，再与其包含的物体面片进行相交测试，提高效率；通过将包围盒按照有效的层次结构进行组织，减少进行相交测试的数目，降低复杂度，进一步得到效率上的提升。在包围盒的选取中，一方面应该选择形状简单的包围盒，降低光线与包围盒相交测试的代价；另一方面应该选取能够紧密包围物体面片的包围盒，提高光线与包围盒进行相交测试的有效性。

3.4.2均匀网格空间网格是把三维空间分别沿着三个方向轴以特定宽度划分，得到一定分辨率的网格，场景中的面片都被分配到相应的网格中。每个网格可以含有不同的面片，每个网格保存其所包含的场景面片的引用。最简单的便是均匀网格，把场景进行均匀划分。

这种方法的优点便是方便简洁，易于创建，并且可以快速将场景中的面片分配到相应的网格中。然而，在实际的场景中，面片的分布是比较不均匀的，比如大多数的面片集中在少数几个网格中，则当进行光线遍历时需要遍历很多面片，也有可能一次相交测试能够踢除的无关面片非常少，遍历过程很麻烦。所以，如果场景中面片分布不够均匀的时候，这种分割方法的遍历效率非常低。

以后单独讲这一块，下面的东西还非常的多，主线上不能丢下。

基本的直接光间接光的采样方式和pathtrace一样，在下一节介绍。

4.1针对像素的采样正如之前我们在Whitted中讲到的抗锯齿的方法一样，如果没有随机性的话，不管怎样都会出现特殊的情况从而导致错误。所以，我们分布式光线追踪中使用的就是随机采样的方式（stochasticsampling），这种方法避免了像网格抽样的那种规律性。

一种简单的实现泊松圆盘分布的方法是：

（1）随机生成采样位置，如果随机生成的采样位置与已经选择过的距离小于一给定值，则丢弃它，至少采样区域满为止，采用这种方法可以创建一个查询表（LookupTable）；

（2）还需要计算滤波器的值，该值描述了每个采样点与周围的像素点的关系。位置信息和滤波器的值存储在一个查询表中，这种简单的方法确实能产生很好的图像效果，但是要求有一个非常大的查询表。因此这里引入另外一种技术：抖动（Jittered）。

抖动技术又有很多种类型，这里主要介绍规格网格的抖动技术，这种技术能产生较好的实验结果并且很适用于图像渲染算法。其具体原理是对于每一个像素进行分割，并对于每一块的中心区域增加一个随机的偏移，保证偏移在同一块像素里。当然这种的采样方式也可用在对区域光的采样当中。

抖动可以使得高频信号降低，但是降低的高频信号中的能量会出现在噪声中而不会消失，因此基本的光谱组合没有发生变化。与纯种的泊松圆盘分布技术相比，该技术可能会造成更多的噪声，而且可能会留下部分锯齿。

分布式光线追踪随机采样模式的一个有趣的副作用是它们实际上将噪点注入到解决方案中（略微更粗糙的图像）。这种噪点比失真的图像更容易接受吧。

把一个像素看成是一个网格，或者由多个子像素（subpixel）网格构成的大网格，这样就是一个二维的抖动。噪声随机的加到X方向上的位置或者Y方向上的位置，X、Y方向相互独立，就相当于是两个一维的抖动构成的，要求使得每个采样点发生在某个像素网格范围内的随机位置上。如果已知道哪些采样点是可见的，则通过重构过滤器（ReconstructionFilter）对那些采样点的值进行处理。

这对于距离很远的光源而言，这是相当准确的，但对于大型光源或近距离的光源来说，这个表示很差。这种离散决策的结果是阴影的边缘非常清晰。从点到可见光点到光源点都有明显的过渡。现实世界中的阴影要柔和得多。从完全阴影到部分阴影的过渡是渐进的。这是由于真实光源的有限区域和其他表面的光的散射。

在所有在focallength里面的物体都是清晰的，其它的物体会变模糊。

4.7分布式光线追踪的缺点

当Kajiya在1986年提出渲染方程时，他也给出了解决这个方程的方法。Kajiya将渲染方程转换为一个基于路径积分的形式。

路径追踪是分布式光线追踪的一种变体，其中每个点只发出一条反射和折射光线。这样可以避免光线数量的激增，但太简单的实现会导致拥有非常多噪点的图像。为了弥补这一点，每个像素都对多条光线进行追踪。

路径追踪的一个优点是，由于每个像素发出较多的可见性光线，因此可以以很少的额外成本合并景深和运动模糊等相机效果。另一方面，与分布式光线追踪相比，要确保反射光线（例如通过分层）的良好分布更为困难。简而言之，分布式光线追踪在光线树中发出的光线最多，而路径追踪追踪在初始时发出的光线最多。

5.1路径追踪方程渲染方程有两种形式，第一个就是我们经常使用的半球面形式，但是它还有一个重要的形式，那就是面积形式。Kajiya将渲染方程转换基于路径积分的显式方程，光照计算才能有效的进行蒙特卡洛计算。

这就是LTE的路径和形式。这是一个n-1维的高维积分，我们之后每一个采样样本都是一个n-1维的向量。我们称这个向量所在的空间为路径空间。

directIllumination(x,theta)//x是表面的点estimatedRadiance=0;forallshadowraysgeneratepointyonlightsource;estimatedRadiance+=Le(y,yx)*BRDF*radianceTransfer(x,y)/pdf(y);estimatedRadiance=estimatedRadiance/#shadowRays;return(estimatedRadiance);蒙特卡罗积分的方差以及最终图像中的噪点，主要由p(y)的选择决定。理想情况下p(y)，等于每个点y对最终估计量的贡献，但实际中，这几乎是不可能的，必须进行更实际的选择，主要是易于实现。p(y)的经常使用的选择是：

光源区域的均匀采样

光源对立体角的均匀采样

为了消除由余弦项和平方因子引起的噪声，可选择根据立体角进行采样。这需要将光源区域上的积分重写为光源所对的立体角上的积分。这将从被积函数中去掉一个余弦项和距离因子。但是，可见性测试仍然存在。这种采样技术通常很难实现，因为在任意立体角上生成方向并不简单。

5.2.1多盏灯的照明当场景中有多个光源时，最简单的方法是依次为每个光源分别计算直接照明。我们为每个光源生成一些阴影光线，然后总结每个光源的总贡献。这样，每个光源的直接照明分量将独立地计算，并且可以根据任何标准选择每个光源的阴影射线的数量。

但是，通常最好将所有组合光源视为单个，并将蒙特卡罗积分应用于组合积分。当产生阴影射线时，它们可以被任何光源使用。因此，可以仅用单个阴影射线计算任意数量光源的直接照射，并且仍然可以获得无偏图像（尽管在这种情况下，最终图像中的噪声可能非常高）。这种方法之所以有效，是因为我们将光源完全抽象为单独的解析曲面，只需查看一个集合。然而，为了获得能工作的算法，我们仍然需要单独访问任何光源，因为任何单独的光源可能需要单独的采样程序来在其表面上生成点。

5.3间接光照与直接照明计算相反，间接光照这个问题通常要困难得多，因为间接光从所有可能的方向到达表面点。因此，很难按照与直接照明相同的路线优化间接照明计算。

间接照明包括在光源和x之间的中间表面上至少反射一次后到达目标点X的光。间接照明是全局光照的一个非常重要的组成部分。

5.3.2间接光的重要性采样在半球上进行均匀采样是一种非常鲁莽的决策，因为这显得好像我们对间接照明积分中的被积函数没有任何了解。为了降低噪点，我们需要某种形式的重要性采样。我们可以构造一个与以下任何因素成比例（或近似成比例）的半球形PDF：

余弦项采样

这里，唯一的噪点来自于Lr。

BRDF采样

BRDF采样是一种很好的降噪技术，当有光泽或高镜面BRDF时。它降低了在BRDF值较低或为零时对方向进行采样的概率。然而，只有少数的特定的BRDF模型才有可能精确地按照BRDF比例采样。更好的办法是，试着按照BRDF和Cosine项的乘积比例取样。从分析上讲，这更难做到，除非在少数情况下。通常，根据这种PDF，需要结合拒绝进行抽样。

发生吸收的比例q3，贡献值为0。q1+q2+q3=1

5.4完整的算法

缺点也是很明显的，首先效果上因为取巧不如分布式光线追踪，然而纯路径追踪的收敛速度是很慢的，从视点打出的光线有的时候很难找到一条贡献大的路径（即找到这样一条路径的概率很小），造成图像往往有很多噪点，每个像素需要上千个采样才能达到满意的效果。

关于俄罗斯轮盘赌就是不能简单的固定步长的终止追踪，因为贡献度高的应该长度越长，低的就越短。主要也是能量守恒。这个网上比较多，不说了。

双向路径追踪算法，是由Veach和Guibas和Lafortune和Willems分别提出的，它可以很好的生成焦散和镜面。

从眼睛生成长度为nE的子路径：x1、x2、x3、x4...，从光源生成nL条子路径，y0、y1...。然后，我们分别连接这两条子路径上的每个结点，只有两个位于两条子路径上不被其他物体遮挡的结点才可以连接。这样，我们可以得到不同长度的一组路径，而且这组中相同长度的路径有多条。例如我们要得到一条长度为k的路径，我们可以从光源子路径中选择长度为s的路径然后从眼睛子路径中选择长度为t(t=k+1)的路径，所以对于长度为k的路径，我们可以有k种选择，每一种s的选择,实际上就代表了一种不同的对路径空间的采样策略，这些策略每一种都有它适用的情况，对于产生某种特殊的效果产生各自的作用，将这些策略综合起来，我们就可以得到适应性更强的渲染算法，得到更好的渲染效果。这些策略大体上可以分为三类,

S=1,…k，例如，x0(E)x1...xiyk-i-1y0(L)，这是一般的情况，需要注意互联的两个点是否可见。

[Veach1995]提出了多重重要性采样（MultipleImportanceSampling）的方法，可以将各种采样方法采样的结果以合适的权重合并起来，非常有效地降低图像的噪声。比如，现在要求解积分中所有长度为4的光路的贡献，可以有以下几种采样方法：视点子路径长度为0，光源子路径长度为3，记为（0,3）；和（1,2），（2,1），（3,0）。这些方法采样出来的路径贡献可能相差很大，使用多重重要性采样合并这些采样可以达到很好的降噪效果。然而双向路径追踪也有明显的缺点，当两个顶点都在纯镜面或折射面上时，双向路径追踪方法不会去连接这两个顶点，这样就造成了它难以有效地模拟Caustics的反射和折射。

Choosealightrayfromthelight//从光源选择一条光线Findray-surfaceintersection//找到光线和物体表面的交点Reflectortransmit//进行反射或者折射u=Uniform()ifu

1953年，Metropolis等人为了解决计算物理领域的复杂采样问题，提出了一种新的采样方法，这就是Metropolis方法。他们最早使用Metropolis方法的初衷是为了计算流体的材质属性，现在，Metropolis方法已经在物理、化学等很多领域得到了广泛的应用。同样，我们也可以将Metropolis方法应用在全局光照领域，来解决复杂的采样问题。之前的这些光线追踪的算法最大的问题是它们都有不适和的场景，也就是说没有一种方法对任意场景都起作用，因为这些方法对场景中从光源到视点的路径进行采样时都没有考虑到场景的路径分布特征，都是采用随机采样的方法采样路径并计算贡献。因此，一旦场景的路径空间中路径分布极不均匀，这些方法就会因为大量的路径没有带来贡献而造成效率的极度降低，例如在间接光照主导的场景中，光源和视点之间被严重遮挡，只有很小的通道可以通过，随机采样时，只有很少的路径可以通过这个通道带来贡献，其它的路径只能被丢弃。

重要性采样的选取需要样本与函数f成比例，即采样样本要成比例于函数f的概率分布。而在实际无偏的渲染过程中，函数f为已知函数，但由于其形式较为复杂和不规则，采样过程中样本的选取所形成的概率分布很难成比例于函数f，这样就会导致样本的方差较大。Metropolis提出了一种方法可以生成采样，样本的概率分布可以成比例于任何可以估计的函数。

采样分布的获得是通过对突变样本的接收和拒绝实现的，最终样本的接收和拒绝取决于接收概率的设置。接收概率表示接收突变样本y为当前样本x的概率表示为a(y|x)。最终马尔可夫过程将收敛至一个平稳分布，若此过程处于平稳状态，空间中两个样本的转移密度也处于平稳状态。这种性质被称作细节平衡条件。

当接收概率满足细节平衡条件，突变策略满足遍历性，生成采样序列的概率密度将服从平稳分布。为了尽快使采样过程收敛达到平稳分布，将接收概率设置得尽可能大是一种较好的策略。

Ptran就是马尔科夫过程的转移概率矩阵。

7.1.3平稳分布如果一个马尔科夫过程的某个状态经过有限次状态转移后又回到自身，那么我们称这个马尔科夫过程具有周期性。如果一个马尔科夫过程存在两个状态，它们之间是互相转移的，那么我们称这个马尔科夫过程可约。若一个马尔科夫过程既没有周期性又不可约，那么这个马尔科夫过程是各态遍历的。各态遍历这个概念我个人的理解是，每个状态都有一定的概率会出现。