图形学渲染基础（五）：光线追踪（Ray Tracing）的探索
简介
传统的光栅化方式主要是将每个物体进行光栅化后形成若干个像素，然后每个像素需要计算光源直接照射到自己并反射回眼睛而形成的颜色。这种算法方式是极快的，但是只能表示直接光照，图像质量较低。
光栅化主要依靠三角形每个顶点的信息，难以很好的利用全局信息，没有很好的处理以下场景，如Soft shadows（软阴影）、Glossy reflection （软高光）、Indirect illumination （间接光照）。光线追踪是一种符合物理规律的一种成像方式，相比于光栅化，它利用全局 的信息，计算量大，出图速度慢但质量好。
光线追踪的主要思路是：因为光路是可逆的，那么就让光线从眼睛出发,沿屏幕每个像素投射出去，判断与场景物体的交点，然后计算该交点的受光照情况。形成一个屏幕图像就需要投射出屏幕分辨率个光线出去，这种计算量无疑是巨大的，但是图像质量极高。
Whitted-Style Ray Tracing
Whitted-Style Ray Tracing：也叫递归式光线追踪（Recursive Ray Tracing），是最经典的光线追踪算法。
- 屏幕上的每一个像素都进行一次光线投射。
- 光线的每次投射都需要判断交点，而且投射到交点后还可能产生反射、折射，那么就往相应的方向继续进行新的投射，直到投射在漫反射表面（diffuse surface）上。
- 最后，将每个交点的受光照情况（使用Blinn Phong算法）以一定权重综合起来，得到的颜色即是该像素的颜色。
需要注意的是：
- 为了减少递归次数，可以额外给予一定的递归终止条件（如允许的最大反射或折射次数为10）。
- 光线在每次反射和折射之后都有能量损耗的（由系数决定），因此经过多次投射后的光线贡献的能量就越小。
- 如果投射光线没有碰撞到物体，一般直接返回一个背景色。
- 漫反射表面（diffuse surface）是粗糙的表面，可以认为它会向各个方向等强度地反射光，因此光线投射到该表面时，本应该会有无数条光线反射出去，但是为了减少计算量，Whitted-Style 则直接对该交点进行 Blinn Phong 着色后就终止递归。
Path Tracing
Path Tracing：是目前最主流的光线追踪算法；相较于 Whitted-Style Ray Tracing 算法，Path Tracing 认为光的传播是以能量的形式向各个方向进行辐射（符合基于物理的渲染），这和渲染方程（Rendering Equation）是一致的：
虽然渲染方程简单优雅，但解方程的过程过于复杂，这里引入三个概念将简化这个方程的计算：
蒙特卡洛方法（Monte Carlo Solution）, 俄罗斯轮盘赌（Russian Roulette，RR）, 光源采样（Sampling the Light）。
蒙特卡洛方法（Monte Carlo Solution
蒙特卡洛方法可以通过随机采样的方式求解数学问题，对于求解定积分问题，可以通过蒙特卡洛方法估计出一个近似数值解。我们把积分变量看成连续型随机变量，每次采样，就用采样所得变量映射得到的函数值，代表所有积分区间内所有变量对应的函数值，多次采样逐渐逼近真实函数的在积分域内所得积分值。
上图给出了蒙特卡洛积分的数学表达式，通过表达式我们可以看到，在求解积分过程中，我们只需要知道变量对应的函数值和概率密度分布即可。使用函数值除以概率密度，相当于用单次使用样本来估计总体的过程，然后多次估计求平均即可近似真实值。蒙特卡洛积分是一种无偏估计，通过对积分式求数学期望，可以发现期望就是定积分值。注意，更多次的采样，估计出的误差就会越小，而且需要估计哪个变量，就在哪个变量上面采样和积分。
按照淳朴的蒙特卡洛方法，伪代码实现如下
Randomly choose 1 directions wi~pdf(w);
Lr = 0.0;
Trace a ray r(p, wi);
if(ray r hit the light)
Lr += L_i * f_r * cosine / pdf(wi);
else if(ray r hit an object at q)
Lr += RayTracing(q, -wi) * f_r * cosine / pdf(wi);
return Lr;
}
按照这种方法很容易出现两个问题：
- 光线数量，会随着光照的弹射次数指数级增加，会使得计算量爆炸，这时不可接受的
- 没有终止条件
对于第一个问题，我们将通过改进的蒙特卡洛积分解决：把N取1，那么无论多少次反弹，分化的方向最多也只能是1，就不会出现爆炸增长现象。
那这个噪声该如何解决呢？可对同一屏幕像素重复多次Ray Tracing着色。若干次着色后（渲染一定时间后）就可以得到不那么 noisy 的图像了。
俄罗斯轮盘赌（Russian Roulette，RR）
即使对蒙特卡洛积分改进后，第二个问题仍然没有解决：没有终止条件。（间接光源的能量判定仍然需要通过不断递归才能确定）
最粗糙的想法，限制递归的深度，即弹射次数，但是这样显然是不符合物理规律的，因为真实的光线在环境中是不断弹射的，而且上一节我们介绍过，限制弹射次数，就是舍弃了渲染方程泰勒级数展开的高次项，一定存在能量损失，最明显的表现就是弹射次数少，图片整体比较暗。显然，计算机是无法计算无数次弹射的，这时人们引入了一种方法：俄罗斯轮盘赌。
假如一个 shading 函数理应输出为 Lr，现在给 shading 函数设置一定概率 P 输出能量 Lr/P ，概率 1−P输出能量 0, 这种情况下：函数的输出期望值 E与理应输出 Lr 相等，也就是说那么只要样本数足够多，这种 shading 将会是能量守恒（无丢失能量）
RayTracing(Point p,Vector3 wr){
Manually specify a probability P_RR
Randomly select ksi in a uniform dist. in [0, 1]
if(ksi > P_RR)
return 0.0;
Randomly choose 1 directions wi~pdf(w);
Lr = 0.0;
Trace a ray r(p, wi);
if(ray r hit the light)
Lr += L_i * f_r * cosine / pdf(wi);
else if(ray r hit an object at q)
Lr += RayTracing(q, -wi) * f_r * cosine / pdf(wi); return Lr / P_RR; }
光源采样（Sampling the Light）
Path Tracing 里直接光照部分有一个效率问题：ray 打在光源上的概率往往极低（因为光源面积一般都很小），很容易造成大量的递归运算最终都浪费掉（还没见到光源就因为俄罗斯赌盘的思想被提前终止了）。
为此，聪明的人类转换了采样思路，从对半球上的采样转变成对光源面（假设光源面积=A）上的采样：
由于立体角 = 单位面积/距离平方，所以dW =dAcosθ'/|x-x'|²
这样在计算直接光照时，原本一个半球上的积分转变成一个光源面上的积分，这使得 Path Tracing 可以更容易得到直接光照的结果（ray 更容易打在光源），当然贡献的光量也会根据概率调整（概率从原本的1/2pi变成1/A）
不过还要额外注意直接光照被直接遮挡的情况，一个简易的解决方法是：让 shading point 往光源点投射一条射线，如果没有被遮挡，则计算直接光照并贡献到结果中
Path Tracing 最终伪代码：
// Contribution from the light source. L_dir = 0.0;
Uniformly sample the light at x’ (pdf_light = 1 / A);
Shoot a ray from p to x’; if(the ray is not blocked in the middle)
L_dir = L_i * f_r * cos θ * cos θ’ / |x’ - p|^2 / pdf_light ;
// Contribution from other reflectors.
L_indir = 0.0;
Test Russian Roulette with probability P_RR;
Uniformly sample the hemisphere toward wi (pdf_hemi = 1 / 2pi);
Trace a ray r(p, wi);
if(ray r hit a non-emitting object at q)
L_indir = RayTracing(q, -wi) * f_r * cos θ / pdf_hemi / P_RR;
return L_dir + L_indir; }
在光源上采样，直接光照的时候，就不会出现随机打方向打不到光源浪费光路的问题。
射线相交的加速结构
为什么需要加速结构，因为光线与物体求交点是光线追踪第一步，一般性的，用三角形网格描述物体，问题转化成和光线和三角形求交，场景中的三角形量非常大，不可能用每个光线和三角形求交，于是使用光线和包围核求交来加速求交过程，为方便计算，使用光线和AABB求交，那如何把空间分割成AABB的集合，即如何设计加速结构，就是本节要介绍的内容。
使用Grid
Uniform Grids (均匀划分)。把空间均匀划分成若干相等大小的格子，记录每个格子内是否存在物体表面，然后光线穿过场景，判断沿途的格子是否存在物体表面：若存在，判断是否与物体表面相交；若不存在，continue。
这样均匀的划分，第一个问题就是，按照什么粒度划分，如果太大，极端条件就是一整块，那就没有加速效果；如果太小，空间中存在大量立方块，那就会增加非常多的运算。根据经验，3D应该划分为：cell = 27*objs。第二个问题，均匀划分对于物体均匀的分布在整个场景的case较为适用，那对于物体分布不均匀的场景，尤其是存在大块无物体空间的case，典型的“teapot in a stadium”，这样的场景，浪费了大量的计算在无物体的空间上。
使用KD-Tree
在做光线追踪之前，需要把加速结构建立好，使用kd-tree建立加速结构有以下特性
- 分割平面沿轴分割
- 二叉树形状
- 所有的物体，存储在叶子节点上
光线穿过空间，依次和每一层节点求交，若和某个节点不相交，那么光线就不会和以这个节点为根节点的子树上的所有节点相交；如果和某个节点相交，那么就需要继续判断是否和其左右子节点相交，直到遍历到叶子节点和光线相交，进而判断叶子节点里的物体和光线是否相交即可。
以kd-tree构建加速结构大致如此，我们来思考这个方法存在的问题。第一，判断物体与哪些AABB有交集；第二，也是oct-tree，bsp-tree都会遇到的问题，即存在物体和多个AABB有交集，即一个物体出现了多个叶子节点。由此，引出了下一种空间划分方法，根据物体的分布来划分空间。
使用BVH
BVH是按照物体进行分割的，尽可能是一个物体不被多个AABB包围，方法如下：
- 找到一个包围核
- 按照某种方法，把包围核内的物体分成两个部分
- 两个部分重新计算包围核
- 然后按照kd-tree的思想，按照不同维度循环二分递归，直到满足中止条件（物体数量足够小）
- 把物体存在每个叶子节点上，其他的节点均用来加速判断
总结
光线追踪（Ray Tracing）通过递归的方式实现了间接光的效果（递归多少次意味着反射了多少次），因此在使用光线追踪算法的时候其实就相当于间接实现了全局光照（Global Illumination）的效果，这也是光线追踪的一个明显优点。 光线追踪框架下的两种主要算法：
- Whitted-Style Ray Tracing：基于光照是光线直射的理念。
- Path Tracing：基于光照是能量辐射的理念，使用蒙特卡洛方法（Monte Carlo Solution）+ 俄罗斯轮盘赌（Russian Roulette，RR）+ 直接光照使用光源采样方式。
参考
- 实时渲染基础（7）光线追踪（Ray Tracing） - KillerAery - 博客园 (cnblogs.com)
- GAMES101课程笔记-Ray Tracing4 - 知乎 (zhihu.com)
- GAMES101-现代计算机图形学入门-闫令琪_哔哩哔哩_bilibili