开头我会让文章足够长做光追渲染的人不管是写离线渲染器还是搞实时光追迟早都会撞上同一个瓶颈求交太慢了。场景里几十万上百万个三角形每根光线都要逐一去试项目一上手就跑不动这时候加速结构就成了绕不开的必修课。针对这个主题我结合自己这些年调过的渲染器、踩过的坑把加速结构这块从原理到实操拆开聊透——包括为什么需要它、BVH 和 KD-Tree 怎么选、构建时哪些细节决定性能、遍历时哪些优化真正有效。不管你是正在入门光追的图形学学生还是想把渲染管线性能抠出来的引擎开发者这篇内容应该都能给你一些可直接落地的参考。坦白讲加速结构是光追里最“值钱”的部分之一。很多项目的渲染速度差出十倍二十倍不是着色器写得不好而是加速结构构建得糙、遍历得差。这篇文章我不打算罗列一堆 API而是从工程角度把加速结构的设计逻辑和实现要点讲清楚。1. 暴力求交的代价加速结构存在的根本原因1.1 一个光线要跟多少三角形胡扯先算笔账。假设场景里有一万个三角形一根光线从相机出发穿过屏幕的一个像素。如果不做任何加速这根光线就要跟这一万个三角形做相交测试。一个画面 1080p 大概两百万个像素每一帧至少两千万根光线一次采样每根跟一万个三角形做测试那就是两千亿次求交运算。这还只是一帧、一次采样。要做软阴影、全局光照光线数量再翻十倍百倍这套算力在普通机器上基本是天文数字等不起。我当时第一次写小白光线追踪器的时候场景才几百个球体就已经卡得不能自理更何况三角形网格。后来给场景加了带纹理的模型面数一多渲染一张图直接烧掉半小时。回头看问题不在于求交函数本身效率低——而是绝大多数求交都是白做的。比如一根光线射向画面左上角它根本不可能命中画面右下角的那堵墙但暴力遍历不知道这件事它非得挨个问一遍。1.2 加速结构的本质把“无意义”的求交提前扔掉加速结构的核心思路特别朴素先把场景里的几何体按空间位置分组离得近的三角形放进一个包围盒或者一个格子。光线来的时候先跟这些粗粒度的“容器”做低成本的相交测试若光线连容器的边都不沾容器里的所有几何体就整个跳过。只有光线确实打进了容器才去测试容器内的三角形。这个过程很像查资料你要在图书馆找一本书不会一本一本翻而是先去目录系统查它在几楼、哪个书架然后直奔那个书架。加速结构就是“目录系统”包围盒就是“书架”。它的核心贡献是把“每根光线与 N 个三角形求交”降成“每根光线与 logN 量级的小集合求交”在 N 达到百万级时性能差距可以轻松超过一百倍。这类结构里的数据关系大概是这样场景几何被嵌套进一层层包围盒或者空间网格光线沿路径行进时维护一个待探测节点列表每探测到一个叶子节点才做三角形层面的求交。所有加速结构的差异本质上都落在两个决策上怎么“分组”空间划分方式以及“探测顺序”怎么定遍历策略。2. 主流加速结构选型从BVH、KD-Tree到Grid2.1 BVH为什么是事实标准BVHBounding Volume Hierarchy包围体层次结构是当下使用最广的加速结构图形学书里讲的、商业渲染器里跑的、游戏引擎里用的大多都是它。它的思路是递归地把场景物体集合按空间邻近关系分成两堆每堆继续分直到每堆内的三角形数量降到阈值并把每一堆用一个紧凑的包围盒包起来最终形成一棵树。BVH 最讨喜的地方是它的包围盒允许相互重叠。正因为允许重叠物体可以“原样”放进树上不需要把三角形切开或修改网格。这意味着构建 BVH 不改变几何数据三角形的数量和排列完全不变只是多了一棵树来描述它们的空间关系。这对大部分渲染器和引擎而言非常省事因为后续还有着色、贴图、蒙皮等一堆逻辑依赖原几何拓扑。另一个关键点是 BVH 对动态场景相对友好。如果物体只是平移旋转不用整棵树重建只需要更新物体对应的叶子节点的包围盒再自底向上重新计算祖先包围盒就够了。我见过一些项目动态物体不多时用这个方法能轻松保住实时帧率而换成分割式结构就做不到这一点因为任何变化都可能牵扯到空间划分的全局调整。2.2 KD-Tree与Grid何时还有用武之地KD-Tree 是另一种经典方案做法是沿着某个轴用平面把空间切成两半子空间分别递归再切。它跟 BVH 最大的区别空间被严格分割成不相交的区域三角形也可能被平面切开。这个特性让它非常“硬”遍历效率理论上很高尤其是光线在空旷场景里可以快速跳过大量空白区域过去在离线渲染里风行过一段时间。但事物总有两面。KD-Tree 由于要“劈开”三角形树的构建比 BVH 复杂不少而且对动态场景几乎无法增量更新一旦物体动了切割平面和三角形归属都变了基本只能全量重建。这在高面数的动画场景中是个大问题。加上现代 GPU 更擅长执行“同一条路径、多个分支判断”的 SIMD 式遍历BVH 的层级结构和更宽松的包围盒反而更好做批处理和预取。如今除了特定体素化场景或风格化渲染KD-Tree 已经逐渐边缘化新手可以了解原理但没必要花太多时间实现。Grid均匀网格就更好理解了把场景切成规则的三维格子三角形分桶丢进格子里。光线用类似“体素遍历”的方式沿着格子走一格一格检测。它的优势是实现极其简单、构建飞快缺点也很明显场景密度不均时要么格子细化到爆炸要么大格子塞几百个三角形加速效果大打折扣。我个人的经验是Grid 只适合均匀分布的粒子系统或稀疏体数据对于那些三角形分布极不均匀的常规场景它基本顶不住。2.3 一张表看懂三种结构的关键差异特性BVHKD-TreeGrid空间划分方式物体层次、包围盒可重叠轴对齐平面、空间严格分割均匀网格分桶是否修改原几何不修改可能切三角形不修改构建复杂度适中O(N logN)偏高切割计算复杂极低近似 O(N)遍历效率稀疏场景优秀理论最优之一一般动态场景支持可局部更新几乎只能重建重建成本低但空间效率差GPU 友好度高中等中等适用场景通用模型、动画、大场景静态密集场景、物理模拟均匀粒子、体素化你可以把 BVH 当成“按目录找书”KD-Tree 是“把图书馆按区域硬切成隔间书必须放进某个隔间”Grid 则是“把书按楼层格子扔进去格子里有多少书取决于运气”。工程上我几乎总是推荐 BVH它带来的麻烦最少、收益最稳。3. BVH构建实操从朴素分割到SAH优化3.1 分割策略中位分割 vs 表面积启发式BVH 构建的方式决定树的形态而树的形态在很大程度上决定了遍历速度。最常见的构建方法是自顶向下Top-Down每次把一个几何体集合分成两堆递归处理子集。核心问题只有一个——怎么分这两堆最简单、最容易想到的做法是按空间坐标排序。先找到几何体集合的质心在三个轴上的分布范围选最长的那个轴然后按这个轴上的位置取中位数把几何体分成前后两半。这样做法的思路是“保证两边数量大致均衡”树的高度会比较稳定构建也很快。但“两边数量均衡”不等于“遍历高效”。想象一个极端场景一面墙上有两扇门大量三角形集中在门的角落少量三角形散落在地板中央。按数量均分的话你会把密密麻麻的门板三角形一分为二而地板中央那几个三角形独占一个子树结果就是每根光线都得同时探测两个大区域白跑很多包围盒测试。真正决定光追效率的是“光线落到某个区域后有多大可能继续往下走”而不仅仅是“这个区域住了多少三角形”。这就引出了表面积启发式SAHSurface Area Heuristic。它的核心洞察来自于概率论一条随机方向的光线击中某个包围盒的概率正比于这个包围盒的表面积。于是与其追求两边三角形数量相等不如追求“包围盒表面积 × 三角形数量”的加权和最小。直观地说SAH 倾向于把空间切在“缝隙”处让分割后的两个包围盒尽量紧、尽量小减少光线同时命中两个盒子的概率。你甚至可以枚举多个候选分割位置逐一计算 SAH 代价挑最小的那个。3.2 SAH公式的推导与代码实现SAH 的常见代价公式长这样C K_T K_I * (SA(L)/SA(P) * N_L SA(R)/SA(P) * N_R)其中 C 是某个分割方案的估算代价K_T 是一次遍历节点的固定开销比如访问子节点、判空K_I 是一次“真正打到几何体”的相交测试开销SA(L) 和 SA(R) 是左右子包围盒的表面积SA(P) 是父包围盒的表面积N_L 和 N_R 是左右子节点里的三角形数量。这个公式通过“表面积占比”估算光线进入左右节点的概率再乘以各自的三角形数量最终算出一个期望开销。我实际实现时一般不会在每个节点都完全重新扫描所有三角形并枚举几十个分割点——那样构建会慢得难以忍受。更常见的做法是先用所有三角形的质心坐标对某个轴排序然后只在排序后的相邻区间里枚举分割点。每枚举一个分割点左右两侧的包围盒和三角形数量可以通过一次线性前缀扫描提前算好。整个构建过程的复杂度大约是 O(N log²N)对百万三角形来说完全够用。代码上很多实现会用类似下面这种骨架struct BVHNode { AABB bounds; int left, right; // 子节点索引 int start, count; // 叶子节点对应的图元区间 bool isLeaf; }; // 递归构建 int buildNode(vectorAABB primBounds, vectorint primIndices, int begin, int end) { AABB parentBounds computeUnionBounds(primBounds, primIndices, begin, end); int nodeIndex nodes.size(); nodes.push_back(BVHNode{parentBounds, -1, -1, begin, end - begin, false}); if (end - begin leafSize) { nodes[nodeIndex].isLeaf true; return nodeIndex; } // 1. 选最大跨度轴 int axis parentBounds.maxExtentAxis(); // 2. 按质心在该轴上的值排序 primIndices[begin..end) std::sort(primIndices.begin() begin, primIndices.begin() end, [](int a, int b) { return primBounds[a].centroid(axis) primBounds[b].centroid(axis); }); // 3. 在排序后的区间上枚举分割点评估SAH取最优 int split chooseSplitBySAH(primBounds, primIndices, begin, end, axis); // 4. 递归构建左右子树 int left buildNode(primBounds, primIndices, begin, split); int right buildNode(primBounds, primIndices, split, end); nodes[nodeIndex].left left; nodes[nodeIndex].right right; return nodeIndex; }这里 chooseSplitBySAH 需要扫描候选位置对每个位置计算左右 AABB。为了不重复计算可以预先扫描出每个前缀区间的包围盒和统计数据这一步算完SAH 求值就是常数时间。我第一次做的时候图省事直接在枚举时实时算包围盒结果是构建时间翻了五六倍后来才学乖。3.3 自底向上构建与莫顿码大规模场景的解法自顶向下递归在大场景下还有个隐患递归深度太深可能爆栈而且并行度不好做。现代 GPU 和大规模离线场景里更常用的是自底向上Bottom-Up构建或它的典型代表 LBVHLinear BVH。LBVH 的思路非常优雅把每个三角形的质心坐标映射到三维网格再用一个 30 位左右的整数把一个网格坐标编码成一个“莫顿码”Morton Code然后对莫顿码排序。由于莫顿码的排序天然让空间邻近的三角形排在相邻位置你只需要按排序后的顺序把相邻三角形配对合并就能快速生成一棵空间层次树。我对莫顿码的形容是“把三维空间压成一个字符串前缀相同的字符串在空间上必然挨得近”。代码实现上莫顿码的生成通常通过位交织bit interleaving完成// 把 [0,1] 区间的值映射到 0~(2^10-1) 并写出其位交织 uint32_t mortonEncode(float x, float y, float z) { uint32_t ix quantize(x, 1023); uint32_t iy quantize(y, 1023); uint32_t iz quantize(z, 1023); uint32_t code 0; for (int i 0; i 10; i) { code | (ix (1 i)) (2 * i); code | (iy (1 i)) (2 * i 1); code | (iz (1 i)) (2 * i 2); } return code; }排序之后构建一棵“层次化二叉树”就变得非常直接而且天然适合并行每个线程处理一段连续区间构建的中间节点可以按区间长度归并。坏处是纯 LBVH 的质量一般不如精心 SAH 的 Top-Down 树因为它不对分割质量做太多评估。工程上常做的是混合方案——先用莫顿码快速建一棵粗树再用 SAH 对局部子树精修水平和性能都能兼顾。4. 遍历与求交阶段真正的性能分水岭4.1 栈遍历最稳但最容易写错的版本BVH 建好了接下来是遍历。最常见的遍历方式是用一个显式栈模拟递归。光线从根节点出发若与左子包围盒相交就把左子节点压栈若与右子包围盒相交也压栈然后从栈顶取出一个节点若它是叶子就对叶子里的三角形逐一求交否则继续判断子节点。这里有个细节很多人第一次写都会踩坑光线同时命中了左右两个包围盒时应该先探测哪个任选一个并不会造成结果错误但会影响性能。由于保存的是最近命中距离tHit如果先走到一个“实际命中距离更远”的子树里做了很多求交最后却发现命中的是另一个子树的物体这部分计算就白费了。为了减少这种浪费遍历时应该按照“与包围盒的交点距离从近到远”的顺序访问子节点。实现上也很简单两个盒子都命中后比较进入距离 tNearL 和 tNearR小的那个优先入栈或优先取出来处理。还有一个我后来才明白的点即使你已经拿到了一个不错的 tHit栈里可能还压着一些节点这些节点的进入距离如果已经超过了 tHit就可以直接跳过不用再弹出处理。这个“按距离剪枝”对开阔场景里的长光线特别有效能砍掉近一半的包围盒测试。栈遍历的伪代码维持在认知负荷可接受的范围内struct StackItem { int nodeIdx; float tNear; }; StackItem stack[MAX_DEPTH]; int sp 0; stack[sp] { root, 0.0f }; float tHit far; while (sp 0) { StackItem item stack[--sp]; if (item.tNear tHit) continue; // 剪枝 BVHNode node nodes[item.nodeIdx]; if (node.isLeaf) { for (int i node.start; i node.start node.count; i) { float t intersectTriangle(rays, prims[i]); if (t tHit) tHit t; } } else { float tL, tR; bool hitL intersectAABB(node.left, rays, tL); bool hitR intersectAABB(node.right, rays, tR); if (hitL !hitR) stack[sp] { node.left, tL }; else if (hitR !hitL) stack[sp] { node.right, tR }; else if (hitL hitR) { if (tL tR) { stack[sp] { node.right, tR }; stack[sp] { node.left, tL }; } else { stack[sp] { node.left, tL }; stack[sp] { node.right, tR }; } } } }这个版本能处理绝大多数光追需求。我在某个测试场景里比较过“随便压栈”和“按 tNear 排序压栈”的差异同一棵树、同一批光线后者遍历节点的数量短了将近 40%效果非常显著。4.2 无栈遍历与扁平化内存布局栈遍历虽然直观但别忽略它的隐形成本栈内存需要维护、动态分配会命中缓存不佳而且 GPU 上递归和栈本身就不受欢迎。工程上更常用的是把 BVH 存成扁平数组配合无栈遍历。无栈遍历的思路是给每个节点额外存储一个 Skip 索引也叫 restart 索引——如果当前节点没有命中直接跳转到某个祖先节点的兄弟节点继续探测而不是回溯到栈。由于树是静态的这些跳转关系可以预先算好。这样整个遍历只需要一个 while 循环不依赖系统栈代码在 GPU 上跑得飞起。内存布局上我特别建议大家把每个非叶子节点的两个子节点连续存储并把包围盒按节点的访问顺序排好。这样做的好处是当处理一个节点时仅需一次缓存行加载就能拿到左右两个包围盒的数据。我见过不少优化不力的项目BVH 节点数组和三角形数组分散在内存各处每次访问都像翻箱倒柜找东西直接拖慢了整个渲染循环。还有一个小技巧如果你存储的是 AABB 的“最小点最大点”可以用两个 float3 表示。访问时可以把最小点三个分量和最大点三个分量分别打包成两个 SIMD 向量这样相交测试就能一次处理三个轴分支更少。GPU 上更常见的做法是使用 float4 对齐避免内存未对齐导致的额外开销。4.3 降低分支预测与缓存未命中的工程技巧光追遍历里最消耗性能的往往不是浮点运算而是“分支预测失败”和“缓存未命中”。当你在一根光线里连续判断多个节点的命中情况时结果几乎随机有时命中左子树有时命中右子树或者两个都命中。CPU 的分支预测器根本猜不中你的规律每次跳转都可能带来十几个周期的惩罚。缓解手段有不少。第一尽量把“是否命中”转换成“选择索引”而不是显式分支。比如你可以用命中位生成一个 0/1 标志位然后使用数学运算选择要压栈的子节点索引减少分支。第二把光线打包成一批packet一次处理 4 根或 8 根光线。如果这组光线在空间上比较一致它们访问的节点也类似遍历路径几乎一致这种一致性既能摊薄分支惩罚也便于 SIMD 化。代价是光线发散时例如反射方向各异的漫反射加速效果下降所以不要无脑整包。关于缓存最实际的办法是“用空间换时间”。把三角形数据按 BVH 叶子的顺序重新排列让同一个叶子里的三角形在内存里连续存放同时把叶子索引和三角形索引做一次映射。这样当光线命中一个叶子时加载三角形的缓存命中率会大幅上升。我实测过同一个百万三角形场景只做这一个重排渲染时间就能缩短 15% 到 20%。不需要改算法只是整理内存收益却意外地大。最后提醒一下遍历循环里尽量少做重复计算。比如 AABB 相交测试中有一堆倒数1/dx, 1/dy, 1/dz如果是多根光线一起遍历可以提前算好存在寄存器里如果单根光线遍历就把这些值放在循环外、函数入参里而不是每次比较都重算。很多老代码的性能问题都是这种细节累积出来的。5. 落地踩坑记录动态场景、叶子大小与实例化5.1 叶子大小一条被忽视的调参线叶子大小每个叶子允许容纳的最大三角形数量是最容易被忽视的参数。经验不足时我会把阈值设为 1觉得越细分越好。结果树深度巨深遍历层级多每次几乎都在测包围盒反而比叶子放 4 个三角形还慢。道理也不难理解遍历节点的开销和叶子内求交的开销需要平衡。叶子太小树的高度高包围盒测试多叶子太大命中叶子后要测很多三角形无效求交变多。我做过一组对照测试一个密度的场景叶子阈值为 1 时遍历 1200 万次节点阈值 4 时节点遍历降到 600 万但三角形求交次数只增加了 10%整体性能反而提升了一倍以上。当然这个最优值跟场景有关三角形大且稀疏的场景叶子可以小三角形微小且聚团的场景叶子应该稍大。一个可靠的策略是构建时设定叶子上限为 4 或 8再用 SAH 决定是否提前停止细分。对于 GPU 端大一点的叶子比如 8~16通常更友好因为它能让线程组内的光线分摊读取三角形内存的开销。5.2 动态场景与重建策略什么时候全量重建什么时候局部更新动态场景是加速结构落地时最容易让人头疼的部分。我做过一个模拟项目场景里有一千个移动的刚体每个刚体由数万三角形组成。如果每一帧都全量重建 BVH构建时间会占到帧预算的 60% 以上帧率直接崩掉。后来我改用两层结构顶层是每个物体的包围盒组成的 BVH底层是每个物体自己的静态 BVH。物体移动时只需要更新顶层树的叶子包围盒并从底向上重新计算祖先的包围盒整个顶层重建很快。底层那个静态 BVH 不用动。这是一大类“可实例化动态场景”的标准解法性能相当可观。但如果场景是大量独立的三角形都在动比如布料模拟局部更新就很吃力这时就得考虑每一帧或每隔几帧全量重建并尽量用并行构建来压缩耗时。还有一类情况别忽略有些项目里三角形不动但包围盒动了——例如骨骼动画的蒙皮网格顶点移动但网格整体包围盒没怎么变。这时候只更新叶子节点的 AABB 会出错因为三角形本身的分布变了叶子的包围盒必须重新计算祖先节点的包围盒也要相应更新。这个“看起来小但必须要做”的环节漏掉的话渲染结果会时不时出现整块物体消失或截断的诡异现象。5.3 实例化与多级加速避免把每辆车当成一万个三角形最后一个落地要点是实例化Instance。如果场景里有一百辆完全相同的车每辆车一万个三角形你不会希望构建一棵含一百万个三角形的树。更合理的做法是只构建一辆车的 BVH然后在顶层场景树里放一百个“实例节点”每个实例节点引用同一个底层 BVH但带一个不同的变换矩阵。光线跟实例求交时先把光线变换到实例的局部空间再在底层 BVH 里遍历。这个方案能大幅降低构建时间和内存占用。我在一个城市街道场景里就这么干同一种路灯、同一款车辆、同一栋楼全部走实例化最后场景总三角形数看起来上千万实际唯一几何也就几十万构建时间从秒级降到了毫秒级。多层加速结构的组织方式也可以很灵活顶层格网加速建筑群中层 BVH 加速建筑物底层 BVH 加速房间内的家具。这个思路跟数据库的多级索引很像——上一级索引定位大范围下一级索引精确定位。项目里什么时候该设计多级我的判断标准是构建成本是否成为瓶颈、是否需要快速剔除大型静态区域、是否有大量重复摆放的物体。如果三个问题里满足两个就值得做多级。收个尾从暴力求交到 BVH从 SAH 构建到无栈遍历加速结构这条路我断断续续走了好几年。我现在的体会是与其追求某个花哨的数据结构不如先把 BVH 的构建细节打磨到位把遍历的实现从“能跑”优化到“跑得稳”。调试时你可以先在小场景里验证正确性再用一个带统计信息的渲染器去记录每个节点被访问的次数找出“热点”到底是加载内存慢还是命中测试多——我靠这个方法发现过好几处意想不到的性能陷阱。最后再分享一个小技巧如果你不确定自己的加速结构写得好不好把构建出来的 BVH 可视化一下。把每个节点的包围盒画成线框叠加在场景上一眼就能看出有没有臃肿的包围盒、有没有失衡的子树。这种直观反馈比任何 profiler 数字都来得直接。加速结构看起来是件“工具活”实际做起来处处是权衡希望这篇内容能让你少走一些我走过的弯路。