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

光追动机

光栅化把图元投影到屏幕，再在屏幕像素上决定颜色。这种流程非常适合实时渲染，却不擅长描述需要跨物体、跨多次弹射的全局效果：面积光源产生的软阴影、粗糙金属的 glossy 反射，以及光在多个表面之间传播后形成的间接照明，都需要额外的近似技巧。

光线追踪直接沿光路组织计算。它可以自然地回答“这条光线先遇到哪个表面”“光源与着色点之间是否被遮挡”“反射或折射后下一段路径在哪里”。代价是每条光线都要自己寻找交点，复杂场景、多个像素和多次弹射会带来极高的求交数量。光栅化通常追求每秒30帧以上的实时速度，光线追踪长期用于电影等离线渲染；硬件和算法发展后，部分光追效果逐渐进入实时应用，但两种方法仍各有适用场景。

三条假设

经典几何光学把光近似成射线，并使用三条简化假设：

直线传播：在均匀、各向同性且没有折射率梯度的介质中，光沿直线传播。衍射和干涉属于波动光学现象，超出这里的模型；
光线独立性：光线在空间中交叉时互不碰撞，不改变彼此的能量，因此不同光路的贡献可以线性叠加；
光路可逆性：在互易介质中，把一条有效光路的方向全部反过来，仍得到一条几何上成立的光路。

第三条是从相机反向追踪的依据。光能量真实地从光源经过多个表面进入相机，但从光源发射的大多数光线不会恰好进入镜头；从相机发射的第一条主光线则立刻确定当前像素可见的表面，计算更有效。可逆性保证的是几何路径对应关系，折射率和传输方向会影响能量权重，不能把正向和反向的数值权重简单视为完全相同。

这些假设描述的是几何光学的近似范围：当物体和孔径的尺度明显大于波长时，遮挡、反射和折射可以用射线近似；衍射、干涉和偏振不在这个模型里。还有一些效果尤其依赖方向集中的光路，例如镜面或折射形成的 焦散 Caustics。相机端随机发出的光线很难恰好落入这类高能量窄区域，后续的采样方法需要专门处理这一困难。

相机光线

针孔相机把视点看成一个点。设投影中心为 $\mathbf e$ ，像素采样中心在成像平面上的位置为 $\mathbf s$ ，则从相机穿过该采样点的主光线 Primary Ray 为

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

当 $\mathbf d$ 已归一化时， $t$ 也是沿射线的距离；未归一化时， $t$ 只是参数，但不同交点仍可比较远近。每个像素发射一条主光线，寻找有效区间内最小的交点参数。最近交点自动遮挡更远交点，这与深度缓冲逐像素保留最小深度是同一个可见性思想，只是搜索方向从屏幕空间改成了射线参数空间。

Ray Casting

最简单的光线投射（Ray Casting）流程如下：

从相机穿过每个像素发射主光线；
找到沿射线的最近几何交点；
从交点向点光源发射一条阴影光线，检查中间是否有遮挡物；
若光源可见，用局部光照模型计算颜色并写入像素。

光线投射默认相机是针孔、光源是点光源；它只寻找首个交点并计算一次局部直接光照。阴影光线只关心从交点到光源的线段，不需要寻找光源之后的交点；一旦发现有效遮挡即可停止。理想镜面反射和折射属于下一节的 Whitted 递归扩展。

主光线寻找最近交点

蓝线从视点穿过成像平面的一个像素，先碰到圆形截面，再沿延长线经过后面的三角形。只有最近交点决定这个像素看到的表面，更远交点被遮挡。

首交点着色与阴影光线

主光线确定表面点后，虚线把它连接到光源。局部着色使用该点的法线和材质，虚线上的遮挡测试决定光源贡献是否保留；两次求交分别回答相机可见性与光源可见性。

Whitted递归

若表面是理想镜面或透明介质，只计算局部光照还不够。命中表面后，可以沿镜面反射方向继续发射反射光线，沿折射方向继续发射折射光线，再对新的交点递归求解。Whitted-style ray tracing 在每个交点建立一棵光线树：

主光线确定相机可见表面；
反射光线追踪镜面反射环境；
折射光线穿过透明介质；
阴影光线判断当前交点是否直接看到光源。

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

交点处的辐亮度可以写成局部项与递归项的加权和：

$L=L_{local}+k_rL_r+k_tL_t,$

其中 $k_r,k_t\in[0,1]$ 表示反射与透射的能量分配。权重不能省略：如果每次反射和折射都把全部能量原样相加，路径越长，像素就会不断积累能量并过曝。递归可以按深度或贡献阈值终止；深度上限会丢掉长路径，固定的微小偏移也必须结合场景尺度和法线方向，否则会出现自身相交。

Whitted 风格沿确定的镜面方向传播，通常只对漫反射表面计算一次直接光照。它不能自动覆盖粗糙反射和完整的间接漫反射积分，这正是路径追踪要解决的问题。

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

玻璃球的阴影比镜面球浅，是因为一部分光线可以折射穿过玻璃继续到达地面；镜面球把入射能量反射到别的方向，地面接收到的透射能量更少。透明物体仍然会投下阴影，只是阴影中可能保留透射贡献。

图中的光线树以相机和像素为根：主光线先穿过成像平面命中球面，球面交点再分别沿镜面反射方向和折射方向发射次级光线；从每个交点连接到光源的虚线是阴影光线。它们的职责不同：反射/折射光线寻找间接的可见表面，阴影光线只检查到光源的线段是否被挡住。若阴影光线用于面积光源，还需要在光源表面取多个样本，单条阴影光线只能给出一个可见性样本。

射线与隐式曲面

光线与物体的交点必须同时满足两个条件：点在射线上，也在物体表面上。对隐式曲面 $f(\mathbf p)=0$ ，把

$\mathbf p=\mathbf o+t\mathbf d$

代入即可得到

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

求出的实根对应几何交点，物理有效的根还要满足 $t\ge0$ 或更一般的 $t_{min}\le t\le t_{max}$ 。没有实根是相离，一个重根是相切，多个实根通常表示穿过物体。没有解析解时，可以在有效区间使用二分、牛顿迭代或其他数值求根方法，并取最小的正根。

球面求交

设球心为 $\mathbf c$ 、半径为 $R$ ，球面满足

$(\mathbf p-\mathbf c)\cdot(\mathbf p-\mathbf c)-R^2=0.$

令 $\mathbf q=\mathbf o-\mathbf c$ ，代入射线得到

$(\mathbf d\cdot\mathbf d)t^2 +2(\mathbf d\cdot\mathbf q)t +(\mathbf q\cdot\mathbf q-R^2)=0.$

记 $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.$

若方向已经归一化， $A=1$ 。判别式

$\Delta=B^2-4AC$

决定几何状态： $\Delta<0$ 无交， $\Delta=0$ 相切， $\Delta>0$ 有两个实根

$t_{1,2}=\frac{-B\mp\sqrt\Delta}{2A}.$

渲染器要在有效区间内取最小正根。两个根都为正时取较小者；若 $t_1<0<t_2$ ，说明起点在球内，应取穿出球面的 $t_2$ ；两个根都为负时，球在射线反向延长线上。对次级光线使用略大于零的 $t_{min}$ ，可以避免浮点误差导致的自身相交。

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

图中三条射线分别与圆（二维示意）相离、相切和相交，对应判别式的负、零、正三种情况；相交时射线与球面有两个参数根，渲染只保留最近的有效正根。

平面求交

一个无限平面由平面上一点 $\mathbf p'$ 与单位法线 $\mathbf n$ 定义：

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

法线单独不能确定平面，因为平面可以沿法线平移；还必须给出一个平面上的点。把射线代入得到

$(\mathbf o+t\mathbf d-\mathbf p')\cdot\mathbf n=0,$

因此

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

分母为0表示射线与平面平行；若分子也为0，射线完全落在平面内，交点不是唯一的；否则无交。分母接近0时，除法会放大浮点误差，实际实现应设置阈值。对有限矩形或多边形，还要在平面交点之后执行点内测试。三角形可以用下面的 Möller–Trumbore 算法把两步合并。

三角形求交

设三角形顶点为 $\mathbf P_0,\mathbf P_1,\mathbf P_2$ ，令

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

三角形内一点可写成

$\mathbf P=\mathbf P_0+b_1\mathbf E_1+b_2\mathbf E_2,$

用重心坐标表示时，其中三个权重为 $(1-b_1-b_2,b_1,b_2)$ 。将它与射线点相等：

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

令 $\mathbf S=\mathbf O-\mathbf P_0$ ，得到三元线性方程组

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

Möller–Trumbore 算法用 Cramer 法则和叉积求解。定义

$\Delta=(\mathbf D\times\mathbf E_2)\cdot\mathbf E_1, \qquad \mathbf S_1=\mathbf D\times\mathbf E_2, \qquad \mathbf S_2=\mathbf S\times\mathbf E_1,$

则

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

这里的行列式也有几何含义。若三角形面积为 $S$ 、单位法线为 $\hat{\mathbf n}$ ，则

$|\Delta|=2S\,|\mathbf D\cdot\hat{\mathbf n}|.$

三角形越接近退化，或射线越接近平行于三角形平面， $|\Delta|$ 越小，求出的 $t,b_1,b_2$ 对浮点扰动越敏感。算法返回的重心权重 $(1-b_1-b_2,b_1,b_2)$ 不仅用于内测，也可直接插值 UV、顶点法线和颜色；因此一次求交的结果会继续影响局部着色以及下一条反射光线的方向。

除法前要检查 $|\Delta|$ 是否足够大。 $\Delta=0$ 表示射线与三角形平面平行，或者三角形退化；接近0时误差会被放大。命中条件为

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

边界取等号时通常仍算命中。算法直接返回重心权重，可立即插值 UV、法线和其他顶点属性。

内外判定

同一次射线-三角形求交还可以判断一个点是否位于封闭网格内部。任选一点，从它向任意方向发射一条射线并统计与网格的交点数：奇数次穿越意味着起点在内部，偶数次意味着在外部。这是射线奇偶规则。

它要求网格封闭且没有洞，射线不能恰好穿过三角形的边或顶点，否则一次穿越可能被重复计算或漏算。实现中通常选择不平行于面的方向，必要时对起点或方向加微小扰动。开放网格不能用这个规则可靠地定义内外。

求交瓶颈

若场景有 $N$ 个三角形，每条光线逐个测试，单条光线成本是 $O(N)$ 。画面总成本近似为

$\text{求交次数} \approx \text{像素数} \times\text{每像素光线数} \times N.$

4K 约有830万像素，千万级三角形、阴影光线和多次弹射会把测试次数推到无法接受的数量级。加速结构不能减少像素数和每像素样本数，它的作用是用便宜的包围体测试排除大批不相关图元，再对少数候选做精确三角形求交。树平衡、包围盒重叠较少时访问量常接近对数级，但没有普遍的 $O(\log N)$ 最坏保证；分布集中或盒子高度重叠时仍可能退化到接近暴力。

例如只算一条主光线、完全不算阴影和次级光线， $8.3\times10^6$ 个像素乘以 $10^7$ 个三角形就约有 $8.3\times10^{13}$ 次三角形测试；实际的每像素采样、阴影光线和多次反弹还会继续乘上额外因子。加速结构减少的是最后一个因子中的实际候选数，而不是把几何或图像分辨率本身变小。

轴对齐包围盒

轴对齐包围盒 Axis-Aligned Bounding Box, AABB 是六个面分别平行于 $X,Y,Z$ 轴的长方体，可以表示为

$[x_{min},x_{max}]\times[y_{min},y_{max}]\times[z_{min},z_{max}].$

它把复杂物体包住。光线与盒不相交时，盒内所有三角形都不可能相交；光线与盒相交只表示存在候选，仍需精确求交。

把 AABB 看成三对无限大平行平面组成的交集。沿坐标轴 $i$ ，射线与两张板的参数为

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

由于 $d_i$ 可能为负，进入和离开参数应统一为

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

三维盒内的有效区间是三个 slab 区间的交集：

$t_{enter}=\max(t_{x,enter},t_{y,enter},t_{z,enter}),$

$t_{exit}=\min(t_{x,exit},t_{y,exit},t_{z,exit}).$

只有当

$t_{enter}\le t_{exit}, \qquad t_{exit}\ge0$

时，射线才命中 AABB。前者表示三个板层存在共同区间，后者排除盒子完全位于射线起点后方的情况。若 $t_{enter}<0\le t_{exit}$ ，说明射线起点已在盒内，沿正方向离开盒子仍算命中。与具体光线的有效区间合并时，使用

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

若 $d_i=0$ ，不能直接除法：原点在该轴 slab 内时该维不限制区间，原点在外时直接无交。轴对齐让求交只需分量减法、倒数和极值，不需要一般平面的叉积；但无分支写法使用无穷大时要避免 $0\times\infty$ 产生 NaN。

预先缓存射线方向各分量的倒数后，一个盒子的测试只需少量减法、乘法和极值比较；它比对任意平面做点积更适合作为每个树节点都会调用的粗筛。需要注意，这个数量级优势只属于盒测试，命中盒子后仍然必须做精确的三角形求交。

两个 slab 区间的交集

左图红线是射线位于两张 x 平面之间的区间，中图是两张 y 平面之间的区间，后者进入参数为负。右图只保留公共部分：进入参数取最大值，离开参数取最小值。单个 slab 的进入参数为负并不意味着无交，还要检查完整交集是否包含正向射线。

区间写法可以直接实现为逐轴收紧射线的有效参数范围。方向分量为零时单独处理，避免除零：

RayBox(ray, box, tMin, tMax):
    enter = tMin
    exit = tMax
    对 x、y、z 三个轴：
        若方向分量为 0：
            若原点在该轴的 slab 外，返回无交
            否则继续处理下一个轴
        a = (box.min[axis] - ray.origin[axis]) / ray.direction[axis]
        b = (box.max[axis] - ray.origin[axis]) / ray.direction[axis]
        enter = max(enter, min(a, b))
        exit = min(exit, max(a, b))
        若 enter > exit，返回无交
    返回区间 [enter, exit]

均匀网格

一个包围盒太大时排除效果有限。均匀空间网格 Uniform Grid 把场景外接盒划分成规则体素，并在光线追踪前建立索引：

计算场景的外接盒和每个图元的 AABB；
将图元登记到与其表面包围盒重叠的网格单元；
沿光线经过的网格顺序遍历，只在当前单元测试登记的图元。

内部为空的物体不需要把所有内部单元都登记。3D-DDA 可以按光线穿过网格的拓扑顺序推进，每次只进入相邻单元；如果当前单元找到小于其离开参数的交点，就可以停止。

网格太粗时，一个单元含有大量图元；网格太细时，光线要走过大量空单元。一个格子等于没有加速，细到每个三角形几乎独占一格又会把代价转移到大量空格步进。课程中的经验规则是体元数量约为 $C$ 倍图元数，三维示例可取 $C\approx27$ ，但它只是针对分布均匀场景的启发式，不能当作所有场景的最优常数。

沿射线逐格测试

蓝色带表示光线经过的单元，红点标出找到的交点。远离蓝色带的圆不必精确测试，跨多个单元的大圆需在相关单元中登记。找到落在当前单元有效参数区间内的最近交点后，可以停止遍历。

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

“体育场中的茶壶”说明均匀网格的退化：空间很大，几何只集中在一小块区域。按密集区域决定网格尺寸，空旷部分会产生大量无意义步进；按空旷区域取粗网格，茶壶所在单元又会积压大量三角形。此时需要局部自适应结构。

构建时登记图元，查询时只访问光线实际经过的单元。跨单元图元的重复测试可用缓存避免：

为场景建立包围盒和规则网格
把各图元登记到所有与它相交的单元
若光线不命中场景包围盒，返回无交
按射线参数从小到大遍历经过的单元：
    对当前单元登记的图元做精确求交
    更新最近的有效交点
    若交点位于当前单元的参数区间内：
        返回这个交点
返回无交

空间划分

空间划分把几何密集区域继续切小，把空区域保持为大块。常见结构包括：

八叉树 Octree：每次把三维立方体沿三个轴切成8个子立方体；二维对应四叉树，一维退化为二叉树；
KD-tree：每次只沿一个轴用平面二分空间，并轮换 $x,y,z$ ，避免始终沿同一轴切成细长条；
BSP tree：用任意方向平面切分空间，能贴合斜向几何，但平面求交和高维推广更复杂。

停止条件通常是区域为空或图元已经少到可以直接测试。内部节点记录划分轴/平面和子指针，叶节点保存实际图元。遍历时，射线未命中节点包围盒即可整棵子树剪枝。

KD-tree 的主要问题是跨分割平面的三角形可能要同时存放在多个叶节点，增加内存和重复求交；把三角形是否与轴对齐盒相交判断正确也并不简单，三个顶点都在盒外时，三角形仍可能穿过盒子，例如一个小盒子可以完全落在大三角形的内部。漏掉这样的交叠会让本应被挡住的像素出现孔洞。

三种空间划分

左图在二维中沿两轴同时分成四块，对应三维八叉树；中图每次沿一个轴二分；右图允许斜分割。密集处继续细分、空旷处保留大区域，跨边界的圆也说明图元可能同时属于多个区域。

空间区域与 KD-tree 叶节点

左侧颜色区域对应右侧树的叶节点。光线穿过几个区域后在橙色区域找到 t_hit 交点，后续进入参数比 t_hit 更大的分支可以跳过。树的划分轴和位置决定这些区域的访问顺序。

BVH

包围盒层次结构 Bounding Volume Hierarchy, BVH 不切分连续空间，而是把图元集合递归分成两组，每组重新计算自己的 AABB。每个图元只属于一个叶节点，子节点的盒子允许重叠。重叠会增加遍历分支，但不需要在构建时判断三角形与切分区域的精确相交，结构更容易实现，也更适合动态更新。

均匀网格、KD-tree 与 BVH 对场景采用不同的划分方式

图的上半部分是空间划分：空间区域互不重叠，但跨边界的大三角形可能被重复登记；下半部分是对象划分：三角形只归入一组，每组有自己的包围盒，但不同包围盒可能重叠。这个交换正是 KD-tree 与 BVH 的核心取舍。

BVH 的构建流程为：

为当前图元集合计算合并 AABB；
选择当前盒跨度最长的轴作为划分方向；
按图元中心或重心在该轴上的位置把集合分为两组；
递归构建子节点，直到叶节点图元足够少。

按中位数划分能让左右子集数量接近，使树深度较平衡。完整排序需要 $O(n\log n)$ ，只找中位数可以使用 Quickselect，期望时间为 $O(n)$ ；工程中直接排序也常常足够。更高级的 Surface Area Heuristic, SAH 会估计不同切分位置的期望遍历成本。若一条随机光线穿过父盒，命中子盒的概率可近似看作子盒表面积与父盒表面积之比，因此可写成：

$C=C_{trav}+\frac{S_A}{S_C}N_A C_{isect} +\frac{S_B}{S_C}N_B C_{isect},$

其中 $S_A,S_B,S_C$ 是子盒和父盒表面积， $N_A,N_B$ 是两侧图元数， $C_{trav}$ 和 $C_{isect}$ 分别是盒遍历和精确求交成本。第一项表示无论如何都要付出的节点遍历代价，后两项是两侧子树的期望求交代价。SAH 改善的是划分质量，不保证整棵树全局最优；叶节点阈值也需要权衡，过大时叶内暴力测试过多，过小时树太深、盒测试过多。

动态场景中的物体移动或新增图元会使原有划分失效，需要重建或增量更新 BVH；这也是动态光线追踪的重要开销。

BVH遍历

给定射线与 BVH 节点，遍历过程是递归的：

射线不命中当前节点 AABB，直接返回；
当前节点是叶节点，逐个测试叶内少量三角形并返回最近交点；
当前节点是内部节点，分别测试两个子盒，并递归访问可能命中的子节点；
先访问进入参数更小的子节点，尽早得到较近交点并收紧 $t_{max}$ ，随后可剪掉进入参数更大的分支。

子盒可能重叠，因此命中一个子盒不能自动跳过另一个；两侧都可能包含最近交点。遍历顺序只影响效率，不影响最终最近交点的正确性。

下面保留递归版本的主要逻辑。叶节点才执行精确图元求交，内部节点用已找到的近交点收紧后续搜索：

IntersectBVH(node, ray, tMin, tMax):
    若 RayBox(ray, node.box, tMin, tMax) 无交：
        返回无交
    若 node 是叶节点：
        返回叶内图元在有效区间内的最近交点
    按子盒的进入参数排序两个子节点
    hit1 = IntersectBVH(较近子节点, ray, tMin, tMax)
    若 hit1 存在，令 tMax = min(tMax, hit1.t)
    hit2 = IntersectBVH(另一个子节点, ray, tMin, tMax)
    返回 hit1、hit2 中最近的有效交点

命中一个子盒不能直接跳过另一个，只有区间已经排除它时才能剪枝。实际 GPU 实现可以改用显式栈，求交语义不变。