光线追踪（加速结构）

上一章把光线追踪理解成大量“最近交点查询”：每条光线从某个原点出发，沿方向 $D$ 前进，寻找第一个命中的表面。这个模型很清晰，但如果直接让每条光线检查场景中的所有三角形，渲染会很快变得不可承受。

加速结构 (Acceleration Structure) 的目标不是改变光线追踪的物理或几何含义，而是减少无意义的求交。它回答的问题是：

在真正测试三角形之前，能不能快速判断一大组几何根本不可能被这条光线命中？

本章会从包围体开始，逐步引入空间划分和 BVH (Bounding Volume Hierarchy)。理解它们之后，再看现代实时光线追踪硬件中的 BLAS、TLAS 或 ray traversal 单元，就不会觉得它们只是神秘黑盒。

朴素求交为什么慢

假设画面有 $W \times H$ 个像素，每个像素发出一条主光线，场景中有 $N$ 个三角形。最朴素的做法是：

取出一条光线。
依次与场景中的每个三角形求交。
记录最小的正 $t$ 。
对所有像素重复这个过程。

主光线阶段的复杂度是：

O(W H N)

如果再加上阴影光线、反射光线、折射光线和间接光采样，光线数量会远大于像素数量。真正的瓶颈通常不是某一次三角形求交公式有多复杂，而是求交次数太多。

朴素遍历与 BVH 层级剔除对比

加速结构的核心直觉就是右图：先问“这条光线是否可能碰到一大组物体的外层盒子”。如果连盒子都没碰到，盒子里面的所有三角形都可以跳过。

包围体：用简单形状包住复杂几何

包围体 (Bounding Volume) 是一个简单几何形状，用来包住更复杂的物体或物体集合。常见包围体包括：

包围球 (Bounding Sphere)：用球包住物体。
轴对齐包围盒 (AABB, Axis-Aligned Bounding Box)：盒子边与坐标轴平行。
有向包围盒 (OBB, Oriented Bounding Box)：盒子可以旋转，更贴合物体。

包围体要满足两个要求：

它必须完全覆盖内部几何。
光线与它求交必须比光线与内部几何求交便宜得多。

如果光线没有命中包围体，那么它一定不会命中内部几何。这个结论可以安全地用于剔除。反过来，如果光线命中了包围体，并不代表一定命中内部几何，只说明内部几何值得进一步检查。

AABB 与光线求交

实时渲染和离线渲染中最常用的包围体之一是 AABB。它可以用每个坐标轴上的最小值和最大值表示：

B = [x_{min}, x_{max}] \times [y_{min}, y_{max}] \times [z_{min}, z_{max}]

光线方程仍然是：

P(t) = O + tD

判断光线是否进入盒子，可以把 AABB 看成三组平行平面。对于每个轴，计算光线进入和离开该轴区间的 $t$ 范围：

t_{x0} = \frac{x_{min} - O_x}{D_x}, \quad t_{x1} = \frac{x_{max} - O_x}{D_x}

对 $y$ 、 $z$ 轴也做同样计算。三维盒子的命中区间是三个轴区间的交集：

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

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

如果满足：

t_{enter} \le t_{exit}

并且盒子位于光线前方，就说明光线与 AABB 相交。

空间划分：把场景切成区域

一种加速思路是直接划分空间。常见结构包括：

均匀网格 (Uniform Grid)：把空间切成大小相同的格子。
八叉树 (Octree)：递归地把三维空间分成八个子空间。
KD-Tree：每次用一个轴对齐平面把空间切成两半。

空间划分的直觉是：一条光线穿过哪些区域，就只需要检查这些区域中的物体。如果场景分布比较均匀，均匀网格可以非常直接；如果场景密度变化很大，递归划分会更灵活。

不过空间划分也有代价。一个大三角形可能跨越很多格子，需要被多个空间节点引用；如果划分太细，遍历节点本身也会变贵；如果划分太粗，又无法有效跳过物体。

BVH：把物体组织成包围盒层级

BVH (Bounding Volume Hierarchy) 是现代光线追踪中极其常见的加速结构。它不是先把空间切成固定区域，而是把物体分组，并为每个组建立包围盒。

一个 BVH 节点通常包含：

当前节点的包围盒。
左右子节点，或叶子节点中的几何列表。
可能还会包含用于遍历排序、实例变换或压缩存储的信息。

遍历 BVH 时，光线先测试根节点包围盒。如果没命中，整棵树都跳过；如果命中，再测试子节点包围盒。直到到达叶子节点，才真正与少量三角形求交。

光线角度: 8° 模式: 显示编号:

蓝色框是根包围盒，绿色和红色框是子节点。BVH 模式会先测试包围盒，错过盒子时直接跳过整组物体；朴素遍历则不管光线方向如何，都要逐个测试所有物体。

上面的组件展示了 BVH 的剔除效果。切换到朴素遍历时，不论光线朝哪里走，都要测试所有物体；切换到 BVH 遍历时，光线会先测试包围盒，错过某个子盒子就跳过这一组物体。

BVH 遍历顺序与最近命中

光线追踪要找的是最近交点，因此 BVH 遍历不能只问“有没有命中”，还要维护当前最近的 $t$ 。

一个常见遍历流程是：

把根节点放入待访问栈。
取出一个节点，测试光线是否命中它的包围盒。
如果没命中，跳过该节点。
如果命中且是内部节点，把子节点加入栈。
如果命中且是叶子节点，测试其中的三角形并更新最近命中。
如果某个节点的进入距离已经大于当前最近命中距离，可以提前跳过。

为了更快找到最近交点，通常会优先遍历离光线原点更近的子节点。这样更容易早点得到一个较小的 $t_{hit}$ ，后续更远的节点就可能被提前剔除。

BVH 如何构建

BVH 的查询效率很大程度取决于构建质量。构建时要决定：

哪些物体放在同一个节点里。
节点从哪里拆成左右子树。
什么时候停止拆分，生成叶子节点。

最简单的做法是按某个轴排序，然后从中间切开。例如选择当前包围盒最长的轴，把物体中心按这个轴排序，再一分为二。这种方法实现简单，构建快，但不一定得到最高质量的树。

更常见的质量度量是 表面积启发式 (SAH, Surface Area Heuristic)。它的直觉是：光线命中某个包围盒的概率大致与包围盒表面积相关。一个候选拆分的成本可以粗略写成：

C = C_{trav} + \frac{A_L}{A_P} N_L C_{isect} + \frac{A_R}{A_P} N_R C_{isect}

其中 $A_P$ 是父节点表面积， $A_L$ 、 $A_R$ 是左右子节点表面积， $N_L$ 、 $N_R$ 是左右子节点中的几何数量。这个公式鼓励构建更紧凑、重叠更少、几何分布更合理的树。

动态场景与两级加速结构

如果场景完全静态，BVH 可以预先构建好。但游戏、动画和实时渲染中，物体会移动、旋转、变形，几何也可能更新。

常见策略包括：

重建 (Rebuild)：每帧重新构建 BVH，质量好但成本高。
重拟合 (Refit)：保持树结构不变，只更新节点包围盒，速度快但树质量可能逐渐变差。
局部重建：只重建变化严重的部分。

现代光线追踪 API 和硬件中常见两级结构：

BLAS (Bottom-Level Acceleration Structure)：描述单个网格或物体内部的几何层级。
TLAS (Top-Level Acceleration Structure)：描述场景中实例之间的层级。

这样，同一个模型可以被多个实例复用。物体移动时，通常只需要更新顶层实例变换或局部结构，而不必复制整份几何。

加速结构的局限

加速结构能显著减少求交次数，但它不是免费的。

首先，构建和更新本身需要时间和内存。对于快速变化的场景，构建成本可能成为瓶颈。其次，树的质量会影响遍历效率：如果包围盒重叠严重，光线仍然可能进入很多节点。最后，不同类型的光线行为不同：相机主光线方向较一致，阴影光线和间接光线方向更分散，缓存命中和遍历效率也会不同。

因此实际渲染器会在构建质量、更新时间、内存占用和遍历速度之间权衡。没有一个结构在所有场景里都绝对最好。

本章小结

本章围绕一个目标展开：让光线少做无意义求交。

朴素光线追踪会让每条光线遍历所有几何，求交次数随像素、光线数量和三角形数量快速增长。
包围体用简单形状包住复杂几何，光线错过包围体时可以安全跳过内部全部物体。
AABB 常用于光线追踪，因为它表示简单、求交便宜，并适合层级结构。
空间划分按区域组织场景，BVH 按物体分组组织包围盒层级。
BVH 遍历通过包围盒测试、节点跳过和最近命中距离裁剪减少三角形求交。
BVH 构建质量很重要，SAH 的核心直觉是减少未来光线进入昂贵子树的概率。
动态场景需要在重建、重拟合、两级结构和更新成本之间权衡。

下一章会从“如何快速找到交点”继续走向“找到交点之后光能如何计算”：辐射度量学、BRDF 与渲染方程会把光线追踪和物理光照连接起来。