06 Ray Tracing

光线追踪

光栅化的局限

光栅化并做不好全局的效果，如软阴影，反射，环境光照，渲染的质量不高。相比之下，光线追踪处理速度虽慢，渲染质量却很高。此外，光栅化很容易做到实时，而光线追踪更多的应用于离线渲染。

图形学中的光线假设——光线沿直线传播

光线之间彼此不会发生碰撞
从光源发出光线到达人眼，经过了多次反射与折射，由于光是可逆的，我们可以认为是从人眼发出光线，最终到达了光源。

光线追踪的基本思想

因为光路是可逆的，那么就让光线从眼睛出发，沿屏幕每个像素投射出去，判断与场景物体的交点，然后计算该交点的受光照情况。形成一个屏幕图像就需要投射出屏幕分辨率个光线出去，这种计算量无疑是巨大的，但是图像质量极高。

递归式光线追踪

Whitted-Style Ray Tracing（Recursive Ray Tracing）

从相机出发，发射出屏幕像素个数的光线，穿过每一个像素点，打到物体。由于一条光线可能穿过多个物体，取取光路与物体最近的交点（涉及深度测试），这个点称为着色点。
在这个着色点上，可能发生两种情况：
1. 这一点发生了漫反射：如果光源能看见着色点（着色点不在阴影中），那么就生成一条有效光路，计算能量并着色（我们很容易知道这个着色点的法线，入射方向等信息，这时候可以用各种各样的着色模型（如Blinn Phong））
2. 这一点发生了完美的折射与反射：折射或反射后的光线会打到新的着色点上，对于这个新的着色点进行同样的判断与处理。
最后，将每个交点的受光照情况（使用Blinn Phong算法）以一定权重综合起来，得到的颜色即是该像素的颜色。

需要注意的是：

为了减少递归次数，可以额外给予一定的递归终止条件（如允许的最大反射或折射次数为10）。
光线在每次反射和折射之后都有能量损耗的（由系数决定），因此经过多次投射后的光线贡献的能量就越小。
如果投射光线没有碰撞到物体，一般直接返回一个背景色。

漫反射表面（diffuse surface） ：粗糙的表面，可以认为它会向各个方向等强度地反射光，因此光线投射到该表面时，本应该会有无数条光线反射出去，但是为了减少计算量，Whitted-Style 则直接对该交点进行 Blinn Phong 着色后就终止递归。

光线与物体求交

为了研究光线与物体求交问题，我们需要先定义光线：一个光线可以有一个点（光源）和一个方向（光线方向）确定，则可设光线上的点的表达式：

与球体求交

隐式表面求交

显示表面求交

显示表面中最常见的就是三角形，因此最重要的就是判断与三角形求交的问题

判断点是否在物体内部：判断该点发射的光线与物体的交点数量是奇数还是偶数。

判断三角形与光线的交点：先判断是否与三角面所在平面相交，求出交点，再判断交点是否在三角形内

光线和平面求交

判断交点在不在三角形内部

Möller Trumbore Algorithm——MT算法：利用重心坐标，交点可以被重心坐标表示出来，三个未知数三个方程，可求解

加速光线追踪

对于每一个屏幕像素点投射出来的光线，我们都要计算光线与空间中的所有三角形是否有交点，计算次数=像素数×三角形数×弹射次数。显然这是一个十分巨大的开销。

我们可以利用轴对齐包围盒（AABB） 来优化这个过程。

我们引入包围盒的概念，将一个复杂的物体用简单的形状围起来。如果光线连包围盒都碰不到，那肯定碰不到包围盒里的物体。对于三维的情况，我们一般用特殊的长方体包围盒——轴对齐包围盒，即包围盒的每一个边都对应和一个坐标轴平行。

如上图，可以得出：只有当光线进入了三组对面，才能说明光线进入了包围盒，同理，只要光线离开了任一对面，就说明光线离开了包围盒。

光线与包围盒求交算法

对于任一对面，我们计算出光线进入对面的最小时间tmin和最大时间tmax（负数也无所谓），接着即可求出光线进入和离开包围盒的时间。

如果$t_{enter}$<$t_{exit}$，说明光线进入了这个盒子里，反之就是没有
总的来说
- 如果$t_{exit}<0$：说明包围盒在光线的后面——没有交点
- 如果$t_{exit}>0$ and $t_{enter}<0$：说明光线起点在包围盒之中——有交点
- 总的来说，光线和AABB的交点有且仅有 $t_{enter}=0$

确定包围盒的位置——均匀划分

通过上述分析，我们已经知道了光线如何和包围盒求交，接下来需要在空间中确定包围盒的位置。

我们判断光线与物体求交的步骤为：

找到整个场景包围盒
均匀划分该包围盒
判定与物体相交的子包围盒
与物体求交

我们可以使用均匀划分的方法，均匀划分就是将空间均匀划分成包围盒。

量级：如果划分太稀疏或是太密集，效率都不会高，根据经验，人们大概得出划分成场景中物体数目的27倍的格子数比较好
缺点：格子的划分方法在大量均匀分布的物体上比较有效，然而在复杂空旷的场景中，会造成很多资源浪费

确定包围盒的位置——空间划分

在网格均匀划分中划分出来的都是大小相同的格子，但场景中的物体一般不会是均匀分布，空旷的地方不需要进行这样划分

我们希望在没有物体的地方用大的包围盒，有物体的地方用小的包围盒，这也就引出了空间划分的方法。

注意：这里提到的空间划分，不是物体划分。比如说一个物体，可以划分到多个包围盒里

八叉树

每一次把空间划分成八份（三维上），直到满足一定的停止规则（比如某一次划分8个子空间中7个为空）
缺点是维数越高越复杂，n维空间对应叉树

KD树

每次把空间划分为两份，x，y，z轴轮流切分，直到被切分节点中不存在物体则停止

BSP树

一种对空间二分的划分方法，每次选一个方向进行划分，与KD树的区别在于它不是横平竖直地切，且它会有越高维越不好计算的问题（用线切开二维，用面切开三维，维度越高越复杂）

KD树如何进行划分

如果一条光线与当前结点空间有交点，则继续寻找该结点的子节点，直到找到叶子结点，再与其中物体求交

KD树的局限：

给出一个节点的包围盒，要判断他与物体哪些三角形有交集，才能进行后续着色，这种算法确实存在，但不太好写

其次，很多情况下一个物体和很多包围盒都有交集，它可能会存在很多个叶子节点中，会造成重复计算

因此，KD树现在很少使用到，我们更多使用的是根据物体划分的BVHs划分。

确定包围盒的位置——BVHs划分（Bounding Volume Hierarchy）

找到场景包围盒 -> 每次将物体分为两堆 -> 对两堆物体重新计算包围盒 -> 直到一堆中物体少到一定程度

KD树的包围盒不会发生重合，而BVHs会发生相交

辐射度量学

Blinn-Phong着色模型中会设置一个数当做光照强度，但我们都不清楚这个数的真实的物理意义，甚至连单位是什么也不知道，研究过程中我们只是将这些物理量简化为一个数，另外Whitted风格的光线追踪所得到的结果也不是我们所想要的真实的效果（路径追踪会提到），而所有的这些都会被辐射度量学解决，这同样也是后面学习路径追踪的基础。

辐射度量学给出了一系列度量方法和单位去定义光照，它定义了光照在空间中的属性，并且这在物理上是完全正确的

关于这个Radiance，我们认为它的物理意义是，从dA面积上，向某个方向辐射出的能量；或者说某个方向的能量照射到dA上，作为dA吸收到总能量的一部分。

相比于Irradiance的单位面积上的能量，Radiance可以看作是单位面积上吸收到的单个方向上的能量，于是我们有

$dE(\mathbf{p}, \omega) = L_i(\mathbf{p}, \omega) \cos \theta \, d\omega \qquad E(\mathbf{p}) = \int_{H^2} L_i(\mathbf{p}, \omega) \cos \theta \, d\omega$

即dA面积上的能量 = 所有方向的能量之和，因为是连续的方向，所以是求积分。

BRDF

由上式，BRDF就是吸收能量后往某一方向反射时取的比例，即某个角度入射到dA面积上的能量，乘以比例fr后反射到另一个角度。

于是我们只考虑某一个出射方向，毫无疑问的，这个出射方向的能量 = 全部光线打到dA上时，反射到该被考虑方向上的能量之和。

渲染方程与反射方程相比，加上了物体自发光的项，渲染方程如下：

$L_o(\mathbf{x}, \mathbf{\omega}_o) = L_e(\mathbf{x}, \mathbf{\omega}_o) + \int_{\Omega} L_i(\mathbf{x}, \mathbf{\omega}_i) f_r(\mathbf{x}, \mathbf{\omega}_i, \mathbf{\omega}_o) (\mathbf{\omega}_i \cdot \mathbf{n}) \, d\mathbf{\omega}_i$

$L_o(x,ω_o)$：表示从点 x 沿方向 $ω_o$ 发出的光强（出射光强）。
$L_e(x,ω_o)$：表示点 x 在方向 $ω_o$上的自身发光强度（发射光强），对于非光源物体，这一项通常为零。
$L_i(x,ω_i)$：表示从点 x 沿方向$ω_i$到达的光强（入射光强）。
$fr(x,ω_i,ω_o)$：表示双向反射分布函数（Bidirectional Reflectance Distribution Function，BRDF），它描述了从方向 ωi 到方向 ωo 的反射光强的比例。
$ω_i⋅n$：表示方向 ωi 与表面法线 n 的点积，用于表示入射光与表面的夹角，只有当入射光与表面夹角小于90度时（即点积大于零）才会有有效反射。
Ω：表示所有可能的入射方向的集合，通常是一个半球面。

渲染方程描述了从一个点出发的光强由两部分组成：

自身发光：物体自身发出的光（如灯泡、荧光屏等）。
反射光：其他物体或光源发出的光照射到该点后，经过表面反射而产生的光。

蒙特卡洛积分

在这之中，$F_N = \int_{a}^{b} f(x) \, dx$

蒙特卡洛方法可以通过随机采样的方式求解数学问题，对于求解定积分问题，可以通过蒙特卡洛方法估计出一个近似数值解。

我们把积分变量看成连续型随机变量，每次采样，就用采样所得变量映射得到的函数值，代表所有积分区间内所有变量对应的函数值，多次采样逐渐逼近真实函数的在积分域内所得积分值。

路径追踪

Whitted-Style光线追踪的做法是，光线在镜面反射表面弹射，而在漫反射表面停止，这显然是不符合现实的

其中一个问题，拿经典的Utah teaport为例，whitted光追只能做左图的光照效果，而对于那种有光泽但不全是镜面反射的glossy材质（右图），whitted做出来的效果并不尽如人意

第二个问题，whitted风格光线追踪不考虑漫反射，虽然递归的思想是正确的，但就像下图（康奈尔盒子）所示，whitted的天花板由于接收不到来自环境光照，呈现一个全黑的状态，并且whitted渲染出的长方体并没有表现红墙和绿墙上反射过来的带有色彩的光，相比之下，路径追踪的结果就真实很多

求解渲染方程

对于之前的渲染方程，我们可以用蒙特卡洛积分法进行求解，忽略自发光项（仅计算直接光照），简单考虑均匀采样的情况

接着引入间接光照：要知道着色点P因Q的反射获得多少能量，其实就相当于摄像机在P点处计算Q的直接光照

那么就只需要在上述算法中加一条判断，看看从P点反射出来的光线有没有打到其他物体

问题

至此，基本的求解渲染方程已经有了大概的架构，但依然存在一些不可忽视的问题

问题传递的可行性

P点的着色需要Q点的环境光照信息，而Q点的环境光照信息又必须包含其他物体的环境光照信息，如此需要追踪的光线数量会呈指数级增长

只有当采样数为1的时候，即N=1时，才不会受到这种影响，路径追踪也因此得名（N!=1时称为分布式光线追踪）

虽然但是，这样一来误差就会特别大，渲染结果势必会有非常多的噪点，为了解决这个问题，我们对单个像素计算多次路径追踪结果（SPP），随后求平均，这个过程其实也用到了蒙特卡洛方法

递归结束条件

很容易看出，上述算法的递归没有终止条件，放到现实中这也是非常合理的，因为现实中的光并不会弹射一定次数后终止弹射，而会一直弹射下去，在算法中强行设置终止次数结束递归不满足现实情况的能量守恒定律，会有一定亮度差异（弹射3次和弹射17次的亮度差异是非常明显的），为了解决这一问题，我们需要用到与俄罗斯轮盘赌类似的思想

这个思想其实就是一个伯努利分布（均匀分布）概念，让光线在每个弹射点都有一定概率继续弹射，设这个概率为p，那么光线停止弹射的概率为（1-p），为了得到相同的路径追踪结果，意味着这个伯努利实验的期望值必须保持Lo不变，那么我们可以巧妙的认为p概率继续弹射得到的能量是L_0/P（终止弹射的结果很自然就是0）