光线追踪是和光栅化不同的着色方式

过去认为的 Ray tracing 就是 whitted-style ray tracing
现在可以理解为：所有光线传播方法的大集合
- （单向和双向）路径跟踪
- 光子映射
- Metropolis light transport（MLT）
- VCM / UPBP

sd
为什么要使用光线追踪？

光栅化不能很好的控制全局效果，运用光线追踪技术，有以下渲染特性：
Pasted image 20221210160907

更精确的反射、折射和透射。
更准确的阴影。包括自阴影、软阴影、区域阴影、多光源阴影等。
更精准的全局光照。
更真实的环境光遮蔽（AO）

光线追踪技术可以精确地反映复杂的反射、折射、透射、阴影、全局光等物理特性。当然，光线追踪也不是万全的渲染技术，它有苛刻的硬件要求、有限度的渲染特性支持以及噪点干扰等负面特点。

本课关于光线追踪的几个假设（非物理正确）

光沿直线传播
光线与光线之间不会发生碰撞
光路的可逆性，光线的路径可以从眼睛到物体，也可以从物体到眼睛

1 光线投射 RayCasting

Pasted image 20221210161157
光线投射的假设：

出射点是一个点
光源点光源
场景物体中的反射为完美的镜面反射，即入射角等于出射角
光线投射的光线只弹射一次

光线投射的步骤：

投射： 从 eye point 穿过成像平面投射光线（每个像素投射一条光线）到场景中
求交： 找到与场景物体的最近交点（完美解决了光栅化的深度测试问题）
检查阴影：将交点和光源连接（shadow ray）, 判断物体对光源来说是不是可见的（即是否在阴影中）。如果中间有阻挡，就说明在阴影里。如果没有阻挡，就说明可见，
着色： 交点处的法线已知，**对可见交点计算着色，相加后写回之前穿过的像素中

v2-33789871a86c5b76463e52b508c692dc_1440w

2 Whitted-Style 光线追踪

Pasted image 20221210161809

光线投射的光线只弹射一次，实际上光线会弹射很多次，这就引出了光线追踪。

Whitted-Style 光线追踪是一种递归光线追踪（Recursive Ray Tracing）

光线不仅仅只会反射，还会折射、然后再与其他物体进行反射
实际上弹射次数不需要太多，弹射 8 次和弹射 16 次区别不大（能量守恒）。

Whitted-Style 光线追踪的步骤：

投射： 从 eye point 穿过成像平面投射光线（每个像素投射一条光线）到场景中
求交： 找到与场景物体的最近交点（完美解决了光栅化的深度测试问题），然后从该点继续反射或者折射（光线每次弹射都会有能量衰减），继续找最近交点。如此递归，直到递归次数达到设定的最大弹射次数。
检查阴影：将所有交点和光源连接（shadow ray）, 判断物体对光源来说是不是可见的（即是否在阴影中）。如果中间有阻挡，就说明在阴影里。如果没有阻挡，就说明可见。
着色： 交点处的法线已知，**对所有可见的交点分别计算着色，相加后写回之前穿过的像素中

最大弹射次数设置为两次的情况

3 射线求交

射线方程

对于每一束光线都满足以下方程：$\mathbf{r}(t)=\mathbf{o}+t\mathbf{d}\quad0\leq t<\infty$
其中 $o$ 为开始点，$d$ 为单位方向向量，$t$ 为时间

Pasted image 20221210162854

射线与球面求交

Pasted image 20230711235159

交点 $P$ 必须同时满足射线方程和球方程，即满足：
$$
(\mathbf{o}+t\mathbf{d}-\mathbf{c})^2-R^2=0
$$
除了 $t$ 以外，其他量已知，解方程即可得 $t$
$$
t=\frac{-b\pm\sqrt{b^2-4ac}}{2a}
$$
其中：
$$
\begin{aligned}
&a=\mathbf{d}\cdot\mathbf{d} \
&b=2(\mathbf{o}-\mathbf{c})\cdot\mathbf{d} \
&\begin{aligned}c=(\mathbf{o}-\mathbf{c})\cdot(\mathbf{o}-\mathbf{c})-R^2\end{aligned}
\end{aligned}
$$
当 $b^{2}-4ac\geqslant0且t\geqslant0$ 时，等式成立。
求出 $t$，代入射线方程就能确定交点位置。

三种情况：

等式不成立->不相交
等式成立->相交
- t 有一个解，此时相切，有一个交点
- t 有两个解，此时相交，有两个交点，我们取最近的交点

射线与隐式几何求交

v2-194d685244aaf670e9bce1664c70086a_1440w

类似球面求交的原理，对于任何隐式的集合体，将射线方程 $r(t)$ 以 $p$ 点带入隐式的方程中算出 $f (o+td)=0$ 即可算出 $t$ 求出交点

已知隐式几何方程 $f$ 和射线方程
交点 $P$ 必须同时满足射线方程和隐式几何方程，即满足：
$$
f(\mathbf{o}+t\mathbf{d})=0
$$

解方程即可得 $t$
$$
t=\frac{-b\pm\sqrt{b^2-4ac}}{2a}
$$
当 $b^{2}-4ac\geqslant0且t\geqslant0$ 时，等式成立。
求出 $t$，代入射线方程就能确定交点位置。

射线与显式几何求交

对于 2D 几何，在图形内部随意取一个点，向外发出射线，和图形的交点数量一定为奇数。相反，在外部取一个点，向图形发出射线，交点一定为偶数。
扩展到 3D，对所有三角形面进行上述 2D 方法判断，但是这种方法效率太低。

几何体性质：

几何体由若干个平面组成
平面可以由一个法线和平面上一个点 $p’$ 来表示（点法式）

已知平面上一点$p’$和法线 $N$，如何判断点 $p$ 是否在平面上：
当向量 $(p-p’)$ 与法线垂直时，说明点 $p$ 在平面上。即满足 $(p-p)’\cdot N = 0$
由此可定义任意在平面 $p’$ 上的点，一系列点的集合就是面，所以也可以用来定义一个表面。

步骤：

可使用 $(p-p’)·N=0$ 表示一个平面
将光线方程以 $p$ 带入光线方程中
求出 $t$ 算出交点
判断交点在三角形的内还是外，若在内则是三角形的交点

Möller Trumbore 算法

推导： https://zhuanlan.zhihu.com/p/451582864

射线三角相交算法是一种快速计算射线与三角形在三个维度上的交点的方法，通过向量与矩阵计算可以快速得出交点与重心坐标，而无需对包含三角形的平面方程进行预计算

已知光线满足 $r (t)=o+td$
$P_0、P_1、P_2$ 为三角形三个顶点
可以得到以下等式，右边是重心坐标形式
通过以下 $E_1、E_2$ 等的参数定义可以解出等式得到交点
通过重心坐标判断交点是否在三角形内：$b1＞0；b2＞0；1 - b1 - b2 ＞0$

4 加速结构

如果三角形面特别多，以上面的算法对每个三角形进行计算将会特别慢。
我们不妨用”对象”来代替三角形，简单来说只对包围盒计算求交，而不是对内部的复杂模型进行计算。

对象在包围盒内
先测试射线是否击中包围盒，如果没有击中包围盒，就说明没有击中物体

现在业界主要使用基于对象划分的层次包围盒（BVH）

轴对齐包围盒 (AABB)

Axis-Aligned Bounding Box（AABB）

思想：如果光线和包围盒不相交，那么更不可能和物体相交
box 是三个对立面（三对无限大的平板，下图为其中一对）的交集
轴对齐：任何一边都沿着 xyz 坐标轴，方便计算

如何判断光线你什么时候与 box 相交？

2D Box

2D Box 有两个对立面

算法思想：

两个对立面都满足光线进入，才能说光线进入了 box
只要离开任意对立面，就说明光线离开了 box

步骤：

计算与 $x_0,x_1$ 这对面与光线相交（进和出）的时间 $t_{min}$、$t_{max}$
计算 $y_0,y_1$ 这对面与光线的相交时间 $t_{min}$、$t_{max}$ （注意此时 $t_{min}$ 为负数）
已经知道了光线什么时候进出这两个对立面，取 $t_{min}$ 的最大值，$t_{max}$ 的最小值（交集）即可得到结果

Pasted image 20221210170221

3D Box

3D Box 有三个对立面

算法思想：

三个对立面都满足光线进入了，才能说光线进入了 box
只要离开任意对立面，就说明光线离开了 box

步骤：

对每一对立面分别计算 $t_{min}$ 和 $t_{max}$
$t_{进入}=\max{t_{\mathrm{min}}},\quad t_{离开}=\min{t_{\mathrm{max}}}$
如果 $t_{进入} ＜ t_{离开}$，说明光线在 box 中留存了一段时间，即相交

应该检查时间 $t$ 是否为负值，以保证物理正确性
t 为负值的情况：

$t_{离开}<0$ 则说明 box 在光线的背面（无交点）
$t_{离开}\geqslant0$ 且 $t_{进入}<0$ 则说明光源在 box 内部，这样才能解释 $t_{进入}<0$（有交点）

总结： AABB 有交点当且仅当 $t_{离开}\geqslant t_{进入}$ 且 $t_{离开}\geqslant0$

AABB 均匀网格划分

Uniform grids 均匀网格
均匀网格适合物体分布均匀的场景，对于分布不均匀的场景，考虑空间划分进行优化加速。

AABB 均匀划分的步骤：

1. 找到包围盒（最外层的正方体）
1. 建立网格（黑色网格）
1. 标记物体表面与 box 相交的网格（灰色标记）

Pasted image 20221210173123

1. 从光线发射方向逐个遍历网格
1. 光线每次经过物体表面在在的网格时，就判断—次是否相交

Pasted image 20221210173553

网格数量应该取多少比较合适？$27 * 物体数量$（3D 空间）

AABB 空间划分

空间划分的分类

为了适应物体分布不均匀的场景，有多种空间划分方法
思想：物体分布密集的区域用更多网格，分布稀疏的区域用少量网格

Pasted image 20221210173202

八叉树 Oct-Tree

Pasted image 20230712112504|500

八叉树是在每个子树下面画十字，划分为八块（在二维下是分为四块，三维是八块）
由于是均匀划分，会出现将同一个物体划分为两块的问题。

KD-Tree

每次划分只划分为两块（类似二叉树）
在二维中第一次为水平的划分，第二次为竖直的，然后循环划分
在三维中类似，以 xyz 轴顺序进行划分
这样可以保证划分比较均匀

建立 KD 树
通过一次对 x, y（二维）进行递归划分，得到下面的 KD 树 (例子中没有对蓝色区域进一步划分，实际上是和右边部分进行相同的划分，这里只是为了做对比所以没有划分)

内部节点不存储对象
叶子节点存储对象列表

遍历 KD 树

假设有一条光线射出
逐个对每个子树进行判断是否有与包围盒相交
若相交则对他的子树继续遍历知道将找到所有与光线相交的包围盒
将其包围盒下的物体查找交点

KD 树的问题：

难以判断物体与包围盒边界的相交问题
一个物体容易同时穿过多个包围盒被重复计算影响性能

因此 KD 树的应用场景越来越小。

目前广泛使用的技术名叫层次包围盒（BVH）

BSP-Tree

划分和 kd 树类似
由于划分不是横平竖直的不能用于 AABB 的划分

对象划分 &层次包围盒（BVH）

Bounding Volume Hierarchy（BVH）

不是通过空间划分，而是通过对象划分。

将包围盒中的对象划分成两组，每一组重新求包围盒，然后在新的包围盒内再次划分，并求新的包围盒，递归进行，直到叶子节点里有比较少的对象（比如 5 个三角形）。
一个对象只可能出现在一个叶子节点
每次的划分都选择 XYZ 中最长的轴进行划分，这样保证划分的大小比较平均（也有其他办法）
总是选择中间大小的对象进行划分（快速划分算法），这样划分出来树更加接近平衡二叉树

一组无序数，找到第 i 大的数，可以使用快速划分算法，时间内复杂度 O (n)。

Pasted image 20221210175639
BVH 的存储结构：

中间节点：包围盒，子节点指针
孩子节点：包围盒，物体列表

BVH 的伪代码：

Intersect(Ray ray, BVH node) 
{
    if (ray misses node.bbox) 
        return;//如果与节点光线都不相交就返回
    if (node is a leaf node)//如果相交且这是一个叶子节点
    {
        test intersection with all objs;//将节点内三角形都做判断
        return closest intersection;//返回最近的那个
    }
    hit1 = Intersect(ray, node.child1);//如果不是叶子节点则递归找到最近的那个
    hit2 = Intersect(ray, node.child2);
    return the closer of hit1, hit2;
}