笔记：光线追踪
Why Ray Tracing?
光栅化很难表示全局的效果（软阴影、glossy reflection光泽反射（指有一定反射能力但又有其表面粗糙性的物体反射）、indirect illumination间接光照（光线传入到人眼前弹射了不止一次）等）；其次光栅化虽然速度较快，但是质量却很低：
此外，由于光线追踪生成速度非常缓慢，一般用于制作动画视频时使用，而光栅化一般使用于实时场景渲染：
Ray-Tracing Algorithm（光线追踪算法）
Basic Ray-Tracing Algorithm
首先从相机出发遍历每一个试图的像素点（image plane），延伸出去一根直线直到最初接触到某个物体的表面，表示人眼是否能观测到这个位置：
之后将相交的这个点连接到光源，看是否处于阴影部分，然后在image plane对应的网格位置记录该点的颜色信息等，不断重复操作直到遍历完image plane中的所有像素点（实际上就是做了一个类似于光栅化中的深度图的操作）：
Whitted-Style Ray Tracing（Whitted风格的光线追踪）
如下图，Whitted-Style Ray Tracing较好地解决了折射和反射相关的投影到视觉图上的效果：
实现
依旧是遍历每一个image plane像素块，primary ray打在透明球体上产生了反射光线和折射光线又形成了secondary rays；之后在各个光线与物体的接触面上形成了4个观测点，均与光源（这里视为点光源）连接形成了4条shadow rays；最后在红色箭头所指向的该处像素块中按一定的权重比例（如直射光线60%，折射反射光线占40%等）记录下颜色信息：
Ray-Surface Intersection（光线曲面相交）—如何求光线和曲面的交点
光线和球的交点
求光线和球的交点实质上就是求同时满足光线方程和球方程的点：
推广
定义某个点（P）满足某个函数，使得该函数等于0，表面该点在该图形的表面，同时该点在光线上，那么该点P一定可以写成o+td的形式：
如何做光线和三角形的交点
首先先做该三角形的一整个平面，确定一条法线（固定平面的方向）和一个平面必经的点p’（固定平面的大体位置），那么作该平面上任意一点和p’的连线和法线的点乘必为0，拓展可得该平面的公式：
同时，如果我想要确定点p和三角形的关系，首先可以明确的是p位于该平面上且光线必定需要经过该点，即满足二者的方程式，因此可以对其公式进行代换得出t的值：
Möller Trumbore Algorithm
特点
解出该点的在平面上的位置之后直接顺便判断了该点是否在三角形内。
思路
确定光线必定经过该点（P），同时沿用之前的知识（如何判断平面内一点和三角形的关系），即a
P0+b
P1+c*P2=P（其中a+b+c=1；P0,P1,P2是三角形的三个顶点；如果该点P位于三角形中，那么a,b,c均为正数），由此得出红框中的公式。而黄框中的内容是左侧计算方程式中的公式替代，三个方程三个未知数可以计算出这三个未知数（t,b1,b2）：
Accelerating Ray-Surface Intersection（加速光线曲面相交）
简单光线场景相交：
•彻底测试每个三角形的射线相交
•找到最近的命中率（即最小t）
问题：
•朴素算法=像素⨉ 三角形 (⨉ 反射/折射）
•非常慢！
如下图中非常复杂的场景，由大量三角形构成且具备很多细节内容，如果每根光线都与所有三角形求交并找最小t，再加上图中有各种光线的反射和折射现象，将花费大量时间：
Bounding Volumes（包围盒）
以另一种方式去理解包围盒
：一个包围盒实际上是由三对平行面包围而形成的一个三维空间中的区域，所要描述的物体全部位于这个包围盒的内部，该盒仍然无限逼近于物体边界范围：
这样理解的原因
根据平面计算交点方程式中的t较为复杂，如下图中的靠上位置图片；而对于一对平行的面来说，比如下面的面为垂直于x轴的面，我只需要计算p’点的x坐标和点光源o的x坐标的差值，再与光源方程式中d在x方向上的投影作比值即可求出t，只不过需要作三次运算（x,y,z三个方向的分量）但是总体上来说比上面的点乘计算量要小很多：
使用包围盒的好处
运用了包围盒的概念之后，可以先判断光线是否经过该包围盒，如果不经过就不再进行更多的操作，因为它一定不会经过所要描述的物体，这样做可以大大节约计算时间。
做法
首先从二维出发，各自求出光线经过两对平行面的进入时间t(min)和出去时间t(max)，那么光线进入该面积区域的时间是取进入时间的最大值和出去时间的最小值（注意：此处的时间t可以为负数）；进而扩展到三维空间中的包围盒仍然是一样的：
需要注意的是，当计算得最小光线射出时间为负时，代表包围盒在光线的背面；当出射光为正而入射光为负时说明光源位于包围盒中（此时也说明光线经过了包围盒）；只有满足入射光<出射光且出射光>=0时说明该光线一定经过包围盒：
AABB如何加速光线追踪
Uniform grids（均匀网格）
思想和之前的包围盒思想一致，只不过进行了更进一步的划分。
步骤
首先使用包围盒包围所有物体（该包围盒可以不是最小包围盒）；之后在该包围盒的基础上创建网格（网格大小与实际物体数量有关，测试出来网格数量一般为27X物体数量）；之后判断哪些网格与物体相交：
将光线入射，判断是否经过了与物体相交的网格，如果经过了则再判断该光线是否与物体相交（注意：判断光线经过了哪些网格时不需要遍历全部网格，比如光线大体方向是从左下到右上射出，则光线所经过的下一个网格，一定在当前网格的上方或者右方）：
Spatial partitions（空间划分）
简单理解就是在包围盒中物体较密集的地方多划分一些格子，而物体稀疏的地方少分配一些网格。
三种树简介
Oct-Tree（八叉树）：将包围盒中线沿X，Y，Z方向划分一次（在空间中会划分成8个等区域的包围盒，然后再在这各个子包围盒中进行此操作，直到每两两方向划分出来的四个网格中有三个子包围盒中没有物体时停止该方向上的划分；注意，存在高维度不好划分的问题：
KD-Tree（类似二叉树思想）：见如下。
BSP-Tree（类似二叉树思想）：和KD-Tree思想一致，只不过KD-Tree是循环水平方向和竖直方向，BSP-Tree是选定任意特定的几个方向上循环操作；注意，同样存在高维度不好划分的问题：
KD-Tree
如图，对于每一个划分出来的大的网格均要进行有规律的区域划分（先横后竖或者先竖后横，且不一定在正中间），最后将每个大网格中包围物体的各种信息等都保存在对应的叶子节点上（如：图2中B上半区域包围的物体信息保存在绿色的叶子节点里，因为该叶子节点无法再次划分了）；注意，对于A区域也需要进行B区域相同的判断、划分子区域的操作：
之后，如果有光线射入，则就可以依次判断是否与每个父节点相交，若相交则判断与其子节点是否相交，直到判断到叶子节点为止，则遍历判断是否与其中的物体相交：
问题
1、判断物体与包围盒边界的相交关系的算法较难，不容易写出；
2、一个物体可能与多个包围盒相交，那么这个物体的信息可能被多个叶子节点包含（重复包含）；
Object Partitions & Bounding Volume Hierarchy (BVH)（通过物体划分）
将空间按物体边界通过某种算法来不断进行二分（直到该区域内图形数量少到某个数时停止），那么划分出来的每个区域都只会包含该区域完全包含了的图形信息，部分位于该区域的图形信息将不会保存，这样可以很好的避免使用求包围盒与物体相交的算法，同时也可以避免信息的重复包含：
如何进行节点的划分
1、每一次划分总是选择最长轴（X，Y，Z）进行划分，这样可以使得每次划分在空间上大小比较平均；
2、总是选择中间节点进行划分（有n个物体，每次选择第n/2个点进行划分），这样可以使得划分出来的二叉树无限接近于平衡二叉树；
伪代码
若光线与包围盒不相交直接返回；
若为叶子节点，遍历所有物体求交点，返回最近的一个物体；
最终返回左子节点和右子节点重最近的那一个；
Basic radiometry（辐射度量学）
即在物理学的角度上来看，定义了一系列的方法、单位属性（Radiant flux, intensity, irradiance, radiance）来描述光照
单位属性
Radiant Energy（光照能量）
即光线照射下来所得到的能量。使用Q（J）来表示；
Radiant Flux（power）
即单位时间内的能量；使用能量对时间的求导，可以理解成功率， 表示方法：
立体角
即一个物体对特定点在三维空间的角度，是平面角在三维空间的延伸：
对于单位立体角而言，图中从上到下的红框分别代表该单位面积矩形竖直边的角度和水平边的角度，而式子中的d(A)则是根据这些计算该单位面积，值得注意的是，单位立体角对应的球体面积并不是都相同的，例如同样移动一定的角度，靠近z轴或者x、y轴的面积会更小：
因此对整个球体进行积分，可得到整个球体的立体角为4派：
Radiant Intensity（辐射强度）
一个光源在某一方向上的亮度，也就是使用每单位的power/每单位的立体角：
irradiance
指每单位照射面积所接收到的power，并且该光向必须是垂直于该面或者经过投影后垂直于该面的那部分光的能量：
对于下图而言，随着距点光源距离越来越大，Intensity是不会改变的，而irradiance是逐渐变小的
Radiance
power在单位立体角、且在单位面积上的有多少，即对power进行两次微分（立体角相关和投影过来的面积相关）:
因此可以总结
Irradiance、Intensity、Radiance三者的关系
，Irradiance是在单位面积做积分，Intensity则在单位立体角作积分，Radiance则是对这两个部分都做了积分（不分先后关系）：
而通俗理解就是：Irradiance描述的是d(A)接收到的所有能量；Radiance描述的是d(A)接收到的来自某一个方向上的所有能量，因此两者的方程式也同样可以用下述相同的方式式来表示：
Bidirectional Reflectance Distribution Function(BRDF)（双向反射分布函数）
BRDF实际上就是描述的光线和物体之间是如何作用的，其中BRDF定义了不同的材质，以及面对不同的材质光线该如何作用。
下图式子中，红框内容表示，单位方向入射线对该出射方向的能量贡献：
Global illumination（全局光照）—也即可以理解为渲染方程
通过反射方程推导除渲染方程
渲染方程即：物体自身所发出的光 + 其它光源通过BRDF之后方向指向该点的Radiance（此处我们假设所有的方向都指向外面；且下式黑框中的渲染方程只是做了上半球的Radiance，此处认为下半球入射的光贡献是0）：
渲染公式理解
已知最初的单点点光源：
推出有n个点光源时：
在此基础上再加上一个面光源：
渲染方程的简化形式
由于知道渲染方程是自身光源和外来光源的和，因此，可以将渲染方程简化成：
而简化的目的就是为了解该渲染方程（且知道1/(1-x)可以写成泰勒展开式1+x
1
+x
2
…也可推广到1/(i-k)上），即得到L的表达式：
即可得到光源弹射次数的分解：
Monte Carlo Path Tracing（蒙特卡洛路径追踪）
蒙特卡洛积分原理
在如下图中的积分区域[a,b]中，随机采样一点x（x位于a~b的区域中），找到其对应的y值（f(x))，那么则假设这整个区域是一个长为b-a，高为f(x)的矩形，计算其面积；然后重复n次以上随机取x的操作，最后平均所有计算出来的面积，结果将无限接近于实际区域包围的面积（也即是该曲线的定积分）：
蒙特卡洛积分详解
对于a~b中任意一点X(i)的呗采样到的几率p(x)应该是一样的，即可知，被采样到的概率应该为p(x)=1/(b-a)：
即也可知，对于PDF采样到的任意一点X(i)，其被抽到的概率p(Xi)都是相同的：
由于知蒙特卡洛积分就是求被采样到的N个点的和的期望，等于遍历所有采样到的点对应的1/N * f(Xi)/p(Xi)，由于知道p(Xi)始终等于1/(b-a)，可以将其提到公式外面：
注意点
如果采样点较少，可能最终求得的面积和真实面积相差较大（N越大，结果越准）。
Path Tracing（路径追踪）
Ray Tracing缺陷
不能很好表现类似于有光泽(glossy)但并非完全镜面的物体
对于mirror的物体，光线确实是打在一点上，并且对该点进行各种反射操作，而对于glossy的物体，光线可以理解成打在一个点及其附近的一小片区域内，此时呈现在人眼中的效果不能是完全反射周围的物体，也就是说打在物体上的光如果完全按照反射光的方向进行反射是不对的，如下图：
光线打在漫反射物体上就停止了
光线实际上不管打在任何表面上，都会进行反射现象，而且这种反射是无数次的反射，即不会说一根光线反射n次就停了；光线追踪实际上实光线打在一个不具备反射和折射的物体上就会停止，其忽略了漫反射，而其作用后的空间和实际上呈现在人眼内的效果对比图如下。
其次，光线追踪还在物体的黑暗面忽视了color bliding现象（即如下图右图中全局光照下左边箱子的左侧呈现红色，右边箱子的右侧呈现绿色：
A Simple Monte Carlo Solution（即只考虑物体的直接光源）
虽然光线追踪是不完全正确的，但是其使用到的渲染方程是正确的，那么也可以将渲染方程代用到路径追踪上来。但是在此就需要解决渲染方程中的两个问题：1、如何求解半球上的积分；2、如何实现递归操作：
对于黄色箭头所指的点来说，其实是我们需要观测的点，但是在这里都默认方向向外（即虽然是其它各个方向的光打在此点，但我们当作是其向四周散发光线）：
因此，可以得出渲染方程（此处忽略掉点自身的发光项），即求出的是
半球上不同方向上光线的积分
：
此处回顾蒙特卡洛积分的定义，与此相类似，也是求一个区域内f(x)的积分，此时要解决的就是蒙特卡洛积分中的未知项f(x)和p(x)：
因此根据定义来说，在此处f(x)对应了就是渲染积分内的所有项；而p(x)，已知求的是整个区域（半球），半球面的面积是2派，求其中任意一点的概率均相等也就是说p(x)=1/2派：
最终将上述式子代入：
据此可以写出伪代码，对于任意一点p(p对应之前提到的观测的黄点)，从w0方向上观测，设该点随机向N个方向发出光线wi，每个wi的被选择的概率为p(即pdf)，遍历所有的wi方向，若连接p和wi的射线打到了光源上，则使结果加上该点wi的蒙特卡洛积分，最终返回结果Lo：
引入间接光照
如果观测的p点的wi方向打到了物体q上，而物体q又可以通过反射，连接到光源，那么这个就是间接光照。思考，此时可以假设将摄像机放在p点，观测物体q的直接光照，因此可以得到渲染方程的递归形式：
因此在伪代码中，需在上诉的内容中添加以下蓝色部分的代码，其中shade(q,-wi)部分就是递归的实现（
注意
：原式中的shade(p,wo)，wo方向是被观测点p指向摄像机，而如果wi指向q物体时，此时方向是p指向q，因此在递归中要把q当作被观测点，p当作摄像机，则传入的wi方向应该与此时的wi方向相反，即传入-wi）：
存在问题：光线爆炸
对于每一根光线，如果打在物体上，又要对这根光线进行无数次遍历递归，在进行了N次物体折射后，其时间复杂度也是随此指数型增长：
解决方法：Path Tracing
由上可知，当N为1时指数不管多大结果始终为1，则不会产生光线爆炸的问题，因此伪代码应该修改为，注意到其中式子中的1/N和for循环已经不再存在了，因为只选择了其中一条光线，即N=1：
但是在每个方向上只随机选择其中一条光线而不是一束光线，虽然可以解决光线爆炸问题，但是同时又会产生噪音太大的问题：
解决的方法：Ray Generation
就是在每个像素中跟踪更多路径的光线最后再取平均。因此再以上的伪代码shade的基础上，再新增一个ray_generation，传入摄像机位置camPos,和像素区域pixel，在像素区域内取N个样本位置，遍历这N个样本点，对于每一个样本点sample，使其从相机位置向被观测的这个样本点sample射出一条光线r，之后对其进行取radiance的操作（注意：传入shade的第二个变量时被观测点到摄像机的方向，而射线r是摄像机到被观测点的方向）：
存在问题：递归终止条件
伪代码中缺少了光线反射的终止条件，也就是说一条光线是可以被无数次反射的，虽然这与现实中的光线反射相一致，但是这会导致算法无法停止。
解决方法：Russian Roulette俄罗斯轮盘赌 (RR)
即假设向某一个方向上有概率p发射出一条光线，最终返回的结果是Lo/p，而当取到概率(1-p)时，返回的结果是0。最终得到的式子是一个二项分布，而其结果也就是期望值E，仍然是我们所需要的结果Lo：
因此在伪代码的修改也只是在shade中修改，添加一个选取光线的概率P_RR，使设定的一个ksi限定在0~1中，当ksi比P_RR要大则返回0代表着这根光线最终未存活（该处也是终止条件），最终返回结果再除以一个P_RR即可：
存在问题：Low SPP
产生的原因可以参考下图，如果我们进行均匀采样，对于较大的光源来说，被观测点可能只需要打出5根光线就能打到光源，而对于极小的光源来说，可能需要打出50000根光线才能找到光源，其间会导致大量的光线浪费：
解决方法：直接在光源上进行采样
即所有的采样点均在光源上，从光源上进行采样这样就不会导致光线的浪费。
注意点
：之前蒙特卡洛积分要求是在被观测点上采样，被观测点上积分；因此如果在光源上采样则需要转换到在光源上积分才能使用蒙特卡洛。
如下图可知，此时我们就需要找到dw和dA的关系，再在原式子上使用dA来代替dw就完成了转换。他们之间的关系：知道立体角的定义（即：面积/距离的平方）也可以理解成把一个面积投影到单位球的表面上对应的面积，也就是说存在一个相等关系：dw/((x+1)-x)
2
=dAcosθ’/(x’-x)
2
(因为dw位于单位球的表面所以其到球心距离为单位1；dAcosθ’是光源面积连接到球心的分量）：
且知道在光源（面积为A）上任取一点的概率都相等，即pdf=1/A，最后完成了从对被观测点到对光源面积积分的替换：
因此对之前伪代码的修改为：对于光源直接照射到被观测点，不需要设置RR，因为这是直接照射可以被观测到的不会消散，而对于需要被多次折射的物体时，才设置RR：
存在问题：直接光照路径上存在遮挡物
按照上述伪代码可能会产生一个问题：如果从光源出发的某一条光照可以直接到被观测点上，但是其中有一个遮挡物，那么上述代码可能会忽视掉这个遮挡物，最终呈现结果与实际观测到的结果不同。
解决方法
再新加一个判断：如果朝向wi方向光线可以直接到被观测点，那么从被观测点按照-wi的方向射出看是否能直接到光源，不能则设置该光线为0（即被挡住了）：
遗留问题
无法解决点光源的问题，暂时可以将其视为一个占很小面积的面光源。