计算机图形学-08：光线追踪与加速

基本假设

经典 光线追踪 Ray Tracing 从几何光学出发，采用三个近似：

光在均匀介质中沿直线传播；
光线相遇时互不影响；
光路可逆，从相机反向追踪到光源与从光源正向传播等价。

这些假设忽略了衍射、干涉等波动现象，却足以解释遮挡、镜面反射和折射。反向追踪只计算最终到达相机的路径，可以避免从光源发出大量永远不会落到传感器上的光线。

相机光线

设针孔相机中心为 $\mathbf e$ ，成像平面上某个像素的采样点为 $\mathbf s$ ，对应的主光线写成

$\mathbf r(t)=\mathbf e+t\mathbf d, \qquad \mathbf d=\frac{\mathbf s-\mathbf e}{\lVert\mathbf s-\mathbf e\rVert}, \qquad t\ge 0.$

Ray Casting 为每个像素发射一条主光线，取最近交点并计算直接光照。Whitted-Style Ray Tracing 还会在交点继续生成反射光线、折射光线与指向光源的阴影光线，通过递归组合得到玻璃、镜面和硬阴影。

Whitted 光线追踪中的主光线、反射光线、折射光线和阴影光线

递归反射、折射和阴影光线合成的最终渲染效果

递归必须设置终止条件，例如最大深度或路径贡献阈值。每次求交都要忽略出发点附近很小的一段区间，或者沿法线偏移新光线的起点，否则浮点误差会让光线立刻再次击中原表面。

光栅化从三角形出发，寻找它覆盖的像素，并用 Z-buffer 在同一像素的多个片元中选择最近者；光线追踪从像素出发，在整条射线上选择最小有效 $t$ 。两者都要解决最近可见面，组织查询的方向不同。光线追踪的主光线可见性不需要另建屏幕 Z-buffer，但每条射线的求交器仍在维护“当前最近 $t$ ”。材质着色模型并不专属于某一种方法。

隐式求交

对隐式曲面 $f(\mathbf p)=0$ ，把光线方程代入即可得到关于 $t$ 的一元方程：

$f(\mathbf o+t\mathbf d)=0.$

球心为 $\mathbf c$ 、半径为 $R$ 的球满足

$\lVert\mathbf p-\mathbf c\rVert^2=R^2.$

令 $\mathbf q=\mathbf o-\mathbf c$ 。代入光线并展开：

$\begin{aligned} \lVert\mathbf o+t\mathbf d-\mathbf c\rVert^2 &=(\mathbf q+t\mathbf d)\cdot(\mathbf q+t\mathbf d)\\ &=(\mathbf d\cdot\mathbf d)t^2 +2(\mathbf d\cdot\mathbf q)t +\mathbf q\cdot\mathbf q. \end{aligned}$

与 $R^2$ 移到同一侧，得到

$At^2+Bt+C=0,$

其中

$A=\mathbf d\cdot\mathbf d,\qquad B=2\mathbf d\cdot\mathbf q,\qquad C=\mathbf q\cdot\mathbf q-R^2.$

判别式与两个根为

$\Delta=B^2-4AC, \qquad t_\pm= \frac{-B\pm\sqrt{\Delta}}{2A}.$

$\Delta<0$ 表示没有实交点， $\Delta=0$ 表示相切， $\Delta>0$ 时光线穿过球面两次。渲染器不会简单取“最小非负根”，而是在当前射线区间 $[t_{\min},t_{\max}]$ 内选最小根。主光线通常令 $t_{\max}=+\infty$ ；指向点光源的阴影光线必须把 $t_{\max}$ 限制在光源距离之前，避免把光源后方的物体误判为遮挡。若方向已归一化，则 $A=1$ 。

ray-sphere 求交的无交、相切和两次相交三种情况

平面求交

给定平面上一点 $\mathbf p'$ 和单位法线 $\mathbf n$ ，平面方程为

$(\mathbf p-\mathbf p')\cdot\mathbf n=0.$

代入光线可得

$t= \frac{(\mathbf p'-\mathbf o)\cdot\mathbf n} {\mathbf d\cdot\mathbf n}.$

当 $\mathbf d\cdot\mathbf n=0$ 时，光线与平面平行。若分子也为零，整条光线位于平面内，交点不唯一；否则没有交点。非平行情形仍要检查 $t_{\min}\le t\le t_{\max}$ 。有限多边形还需在得到平面交点后做边界测试。

三角形求交

三角形网格是最常见的显式几何。直接做法是先求光线与三角形所在平面的交点，再用叉积或重心坐标判断交点是否位于三角形内部。

Möller–Trumbore 求交算法 把两个步骤合并。令

$\mathbf E_1=\mathbf P_1-\mathbf P_0,\qquad \mathbf E_2=\mathbf P_2-\mathbf P_0,\qquad \mathbf S=\mathbf O-\mathbf P_0,$

求解

$\mathbf O+t\mathbf D = \mathbf P_0+b_1\mathbf E_1+b_2\mathbf E_2.$

移项后得到一个 $3\times3$ 线性系统：

$\begin{pmatrix} -\mathbf D&\mathbf E_1&\mathbf E_2 \end{pmatrix} \begin{pmatrix} t\\b_1\\b_2 \end{pmatrix} = \mathbf S.$

系数矩阵的行列式是

$\Delta = \det[-\mathbf D,\mathbf E_1,\mathbf E_2] = (\mathbf D\times\mathbf E_2)\cdot\mathbf E_1.$

$\Delta=0$ 表示三个列向量线性相关，即光线与三角形平面平行或三角形退化。定义

$\mathbf S_1=\mathbf D\times\mathbf E_2,\qquad \mathbf S_2=\mathbf S\times\mathbf E_1.$

用 Cramer 法则把对应列替换为 $\mathbf S$ ，再把行列式写成标量三重积：

$b_1=\frac{\mathbf S_1\cdot\mathbf S}{\Delta}, \qquad b_2=\frac{\mathbf S_2\cdot\mathbf D}{\Delta}, \qquad t=\frac{\mathbf S_2\cdot\mathbf E_2}{\Delta}.$

三角形上的点为

$\mathbf P =(1-b_1-b_2)\mathbf P_0 +b_1\mathbf P_1 +b_2\mathbf P_2,$

所以三个重心权重为 $(1-b_1-b_2,b_1,b_2)$ 。有效交点满足

$t_{\min}\le t\le t_{\max}, \qquad b_1\ge0, \qquad b_2\ge0, \qquad b_1+b_2\le1.$

这些权重还能插值法线、纹理坐标和其他顶点属性。若启用背面剔除，可以利用 $\Delta$ 的符号排除背向三角形；双面材质只判断 $|\Delta|$ 是否足够大。

Möller–Trumbore 同时解出了光线参数和三角形重心坐标，因此不需要先求平面交点再做一次内部测试。

求交代价

若场景含有 $N$ 个三角形，每条光线逐一测试的成本为 $O(N)$ 。一个像素可能生成多条次级光线，路径追踪还会对每个像素采样很多次，因此朴素算法很快成为瓶颈。

加速结构利用一个事实：多数光线只经过场景中的很小区域。先用便宜的包围体排除大片不相关几何，再对少量候选图元做精确求交。在树较平衡、包围盒重叠较少且几何分布合理时，期望访问量常接近对数级；它不是对任意场景和任意光线的最坏情况保证。

包围盒

轴对齐包围盒 Axis-Aligned Bounding Box，简称 AABB，是三个轴向区间的笛卡尔积：

$[x_0,x_1]\times[y_0,y_1]\times[z_0,z_1].$

沿每个轴，它对应一对平行平面。光线在第 $i$ 个轴上进入和离开的参数为

$t_{i,0}=\frac{p_{i,0}-o_i}{d_i}, \qquad t_{i,1}=\frac{p_{i,1}-o_i}{d_i}.$

不必单独依据方向交换两个值，直接定义

$t_{i,\min} = \min(t_{i,0},t_{i,1}), \qquad t_{i,\max} = \max(t_{i,0},t_{i,1}).$

第 $i$ 个平板 Slab 允许的射线参数区间是 $[t_{i,\min},t_{i,\max}]$ 。射线位于盒内，要求三个轴的条件同时成立，因此有效区间是集合交：

$[t_{\mathrm{enter}},t_{\mathrm{exit}}] = \bigcap_{i\in\{x,y,z\}} [t_{i,\min},t_{i,\max}].$

区间交的左端点取所有左端点最大值，右端点取所有右端点最小值：

$t_{\mathrm{enter}}=\max_i t_{i,\min}, \qquad t_{\mathrm{exit}}=\min_i t_{i,\max}.$

最终还要与射线自身区间 $[t_{\min},t_{\max}]$ 求交。命中条件为

$\max(t_{\mathrm{enter}},t_{\min}) \le \min(t_{\mathrm{exit}},t_{\max}).$

若 $d_i=0$ ，光线在该轴上没有移动：原点不在对应 slab 内则立即不相交，原点在其中则该轴不限制参数区间。

当 $t_{\mathrm{enter}}=t_{\mathrm{exit}}$ 时，光线只接触盒子的面、棱或角。若交点边界被视为有效，应使用 $t_{\mathrm{enter}}\le t_{\mathrm{exit}}$ ；只有在算法明确要求穿过正体积时才使用严格不等式。实现中还要先把该区间与 $[t_{\min},t_{\max}]$ 相交，否则盒子虽然命中，交点可能仍位于射线的反向或已裁剪部分。

均匀网格

均匀网格 Uniform Grid 先建立场景包围盒，再把空间划成规则单元：

将每个物体登记到与其包围盒重叠的单元；
光线从进入场景的位置开始，按穿越顺序访问网格；
只测试当前单元中的物体；
找到比下一个单元边界更近的交点后即可停止。

网格分辨率太低时，一个单元包含过多几何；太高时，存储和穿越成本上升。规则网格适合几何分布较均匀的场景。若大量三角形集中在小茶壶里，而周围是广阔空旷空间，固定分辨率很难同时照顾两种尺度，这类情形常称为“teapot in a stadium”。

茶壶集中在大场景中的 teapot in a stadium 分布

空间划分

层次空间划分根据局部复杂度继续细分。Octree 每次把三维盒子分成八块，结构简单但不能顺应几何方向。BSP Tree 可以使用任意切分平面，表达能力强，构建和求交也更复杂。KD-Tree 每层选择一个坐标轴并用轴对齐平面二分空间，三种轴通常轮换或按范围选择。

KD-tree 的内部节点保存切分轴和位置，叶节点保存与该空间重叠的图元。遍历时先访问光线进入的一侧；只有另一侧可能包含更近交点时才继续。一个横跨切分面的物体可能被同时登记到两个子空间，构建时必须权衡节点开销、重复图元和叶节点求交成本。

BVH

包围盒层次结构 Bounding Volume Hierarchy，简称 BVH，按物体集合划分，而不是切割空间：

为当前图元集合计算包围盒；
选择包围盒最长的轴；
按图元中心在该轴上的位置排序，并在中位数附近二分；
递归建立两个子节点，直到叶节点只含少量图元。

中位数划分能保持树高近似平衡。更高质量的实现常用 表面积启发式 Surface Area Heuristic 估计不同切分的遍历成本。叶节点容纳多少图元取决于节点开销和三角形求交代价，课程示例中可取约五个作为起点。

遍历时先测试当前节点的包围盒。未命中便立即返回；叶节点逐个测试图元；内部节点优先访问较近的子盒并保留较近结果。找到当前最近交点 $t_{\mathrm{hit}}$ 后，令

$t_{\max}\leftarrow t_{\mathrm{hit}},$

后续包围盒与新的射线区间没有交集时便能立即剪枝。

实现递归遍历时，近子节点和远子节点应各传入一次；排序后又执行一次无条件的公共递归，可能重复访问同一子节点并抵消剪枝收益。划分轴也必须针对当前子盒重新计算最长轴，不能把根节点的轴一路复用到所有后代。每次包围盒测试都要使用该盒自己的 $t_{\mathrm{enter}}$ 、 $t_{\mathrm{exit}}$ ，并接受相切边界 $t_{\mathrm{enter}}\le t_{\mathrm{exit}}$ 。