加速算法

光线追踪的计算瓶颈主要来自两方面：求交测试的巨大计算量，以及蒙特卡洛积分产生的噪点。本文深入讲解两个关键技术：加速结构（BVH、KD-Tree）和降噪算法，它们是实时光线追踪的基石。

加速结构

朴素的光线追踪对每个三角形都进行求交测试，复杂度是 O(n)，n 是三角形数量。现代场景动辄百万级三角形，这种暴力方法完全不可行。加速结构的核心思想是空间划分：将场景组织成层次结构，快速剔除大量不可能相交的几何，只对少量候选三角形精确求交。

BVH（包围盒层次结构）

BVH 是实时光线追踪最常用的加速结构，将场景递归划分为二叉树，每个节点存储包围所有子节点的轴对齐包围盒（AABB）。

• 构建策略：

  • 自顶向下：从根节点开始，递归将几何划分为两个子集
  • 划分维度：选择包围盒最长的轴作为划分维度（SAH 启发式）
  • 划分位置：按中位数、均值或表面面积启发式（Surface Area Heuristic）选择
  • 叶节点：当三角形数量小于阈值（通常 4-8 个）或深度达到限制时停止划分

• 遍历优化：

  • 包围盒测试使用 AABB slab 方法，快速判断光线与包围盒是否相交
  • 优先遍历更近的子节点，利用栈式遍历避免递归开销
  • 使用短栈优化（Short Stack Optimization），只保存最近的路径

• 构建与更新：

  • 静态场景预构建 BVH，可以使用高质量但慢速的构建算法
  • 动态场景使用增量更新（Refitting）：重新计算包围盒但不重建树结构
  • 高速旋转物体使用局部 BVH，合并到场景的顶层 BVH

KD-Tree

KD-Tree 将空间划分为轴对齐的层次结构，每个节点用一个分裂平面将空间分成两个子空间。

• 与 BVH 的区别：

  • BVH 按几何划分，KD-Tree 按空间划分
  • KD-Tree 的节点重叠更少，遍历效率更高
  • KD-Tree 构建更慢，动态更新更困难
  • KD-Tree 更适合静态场景和离线渲染

• 现代应用：

  • 离线渲染器（如 Arnold、V-Ray）仍大量使用 KD-Tree
  • 实时渲染由于动态场景需求，更倾向于 BVH

光束加速结构

传统的加速结构每条光线独立遍历 BVH，效率较低。光束加速结构追踪一簇相近的光线，利用空间相干性。

• 光线包（Ray Packet）：

  • 将相邻像素的光线打包成 4x4 或 8x8 的光线包
  • 使用 SIMD 指令并行测试包围盒相交
  • 对整个光线包计算共同的包围盒，减少遍历次数

• 光束树（Beam Tree）：

  • 构建时考虑光束的体积，而非单条光线
  • 节点的包围盒包裹整个光束，而非单条光线的路径
  • 适合主光线和少量反射的光线，深度反射后光束发散严重