做离线渲染和游戏引擎的人迟早都会碰到同一堵墙场景三角形数量一上来暴力求交的性能就彻底失控。我第一次写路径追踪器的时候一个二十万三角形的场景渲染单帧要跑十几分钟换成 BVH 之后直接快了两个数量级。Bounding Volume HierarchiesBVH要解决的就是这么一件事——用一棵树状的包围盒结构把逐三角形求交的平均成本从 O(N) 压到接近 O(log N)。这篇文章不打算给你复述教科书上的定义而是把我在实际构建和遍历 BVH 时验证过的结论、踩过的坑、以及工程上真正管用的做法原原本本讲一遍。适合正在写软光栅、路径追踪器、碰撞检测或几何处理相关代码的开发者参考硬件的硬件光追管线那套东西理解了这套基础之后也能看懂一大半。1. 暴力求交撞墙之后BVH 要解决的根本问题1.1 先算一笔逐三角形求交的账很多教程上来就讲 BVH 的构造算法反而把为什么要这个结构这个问题跳过去了。我建议大家先动手算一笔账算完你就知道暴力求交到底有多贵。一条射线和一个三角形的求交标准 Moller-Trumbore 算法大概需要 30 到 50 个 CPU/GPU 周期这个数字比大多数人想的要大。拿一个不算大的场景来说二十万三角形720p 分辨率下大概有九十二万个像素每个像素四条采样射线这就是三百七十万条主射线。如果每条主射线都要和二十万三角形挨个求交一次光是主射线的求交次数就是七千四百亿次。再算上阴影射线、间接光照射线这个数量级直接起飞普通桌面 CPU 完全扛不住。即便你把三角形求交优化到极致问题也不在单次求交成本而在无效求交的数量上。场景里绝大多数三角形离射线很远跟当前像素毫无关系但我们还是花同样的周期去测了一遍。所以加速结构的核心思路只有一个用尽可能便宜的方式把一大批不可能命中的三角形直接排除掉。1.2 包围盒把精确判断换成快速否定排除大批三角形的最廉价方式就是给它们套一层包围盒。最常见的是 AABB轴对齐包围盒射线和 AABB 的求交只需要六次 slab 测试成本大约是三角形求交的五分之一到十分之一而且 SIMD 友好可以一次处理好几条射线。这里的关键逻辑是否定优先射线如果连包围盒都打不中那么盒子里面的三角形必定全部打不中可以直接跳过。如果打中了包围盒并不代表一定能命中里面的三角形我们只是把问题缩小到一个更小的范围内再去做精确求交。换句话说AABB 给出的是一个可能命中的保守集合它允许误报但绝不允许漏报。漏报在渲染里就是缺三角形、出现裂缝属于致命的正确性问题。生活里也有类似的经验比如你在图书馆找一本特定书名的书肯定先看图书分类书架再在书架那几排里翻而不是把整栋楼每本书都翻一遍。围盒起到的就是书架标签的作用。1.3 一棵树的价值让排除操作叠加成对数级单个包围盒只能做一次整批排除场景一多还是要逐个盒子和三角形去试。所以 BVH 的做法是把场景递归地二分每个内部节点保存一个包围盒和两个孩子节点叶子节点保存一小撮三角形。射线从根节点出发先测根节点的包围盒只要命中就往两个孩子节点里走。这样每做一次包围盒测试就有机会淘汰掉当前节点下一整棵子树的所有三角形。理想情况下每向下走一层候选集合规模减半。二十万三角形的场景二叉树深度大约十八层最坏情况下也就是做十八次左右包围盒测试就到叶子了然后只需要跟叶子里的几个三角形做精确求交。这里要特别区分一下 BVH 和空间划分结构的区别。八叉树、k-d 树是在切割空间三角形的归属会被空间格子卡住一个三角形可能同时出现在多个格子BVH 切的是物体的集合每个三角形只属于一个叶子节点不会重复存储。这个特性让 BVH 在动态场景里维护起来舒服得多——物体移动了更新对应叶子节点的包围盒就行三角形的归属关系通常不需要变。2. 构建一棵能打的 BVH分裂策略与 SAH 的工程实践2.1 自顶向下构建的基本骨架构建 BVH 最常用的方法是自顶向下递归分裂把一组三角形套一个总包围盒然后选一条轴、选一个分割位置把这组三角形分成左右两堆分别递归构建。核心骨架是这样的struct BVHNode { AABB bounds; // 节点包围盒 union { int leftChild; // 内部节点左孩子索引 int primStart; // 叶子节点三角形起始下标 }; int rightChildOrCount; // 右孩子索引或叶子三角形数量 bool isLeaf; }; BVHNode build(std::spanTriangle tris, int start, int count) { AABB nodeBounds computeBounds(tris, start, count); if (count leafSize) { return makeLeaf(nodeBounds, start, count); } // 选择分裂轴和位置中位分裂或 SAH Split split chooseSplit(tris, start, count, nodeBounds); int mid partition(tris, start, count, split); BVHNode left build(tris, start, mid - start); BVHNode right build(tris, mid, count - (mid - start)); return makeInternal(nodeBounds, left, right); }这个骨架里最核心的部分就是chooseSplit。叶子大小建议取 4 到 8 个三角形取 1 会浪费节点内存取太大则叶子内部仍是线性扫描两者都会拖慢遍历。我实际测试下来叶子放 4 个三角形通常比放 1 个快 15% 到 25%因为省掉了大量节点访问开销。2.2 中位分裂怎么就把树给废了最简单的分裂策略是中位分裂选一条轴比如最长轴把三角形按中心坐标排序后从中间切开保证左右两边三角形数量大致相同。这个方案构建极快但树的质量完全看运气。它的问题在于平均分三角形数量不等于平均分空间。一个典型的坏场景是一个巨大的地面平面三角形占据了场景一半的面积周围散布几百个小物件。中位分裂按数量切结果左边子树包含了地面三角形和几十个小物件包围盒几乎等于整个场景右边子树全是小物件包围盒也很小。遍历的时候缓冲区包围盒几乎和父节点一样大射线命中它的概率极高你明明做了树却退化成了对左边几百个物体挨个求交。我一开始偷懒用中位分裂渲染一堵墙加一堆散落道具的场景帧时间只比暴力求交快了不到三倍完全没体现出树的优势。后来换成 SAH 分裂才真正把性能提上来。所以结论很清楚三角形数量分布和空间分布不一致的时候按数量切是稳不住的必须让切开后的空间尽量均衡。2.3 SAH把命中概率和遍历成本放进同一个公式SAHSurface Area Heuristic表面积启发式是目前构建 BVH 的事实标准。它的核心想法很朴素一次射线遍历的总成本等于访问根节点的固定开销加上进入左子树/右子树的概率乘以子树内部继续遍历的成本。关键在于概率怎么估算。如果射线在场景里是均匀分布的那么一条能命中父节点包围盒的射线实际命中某个孩子包围盒的概率近似等于这个孩子的表面积占父节点表面积的比例。这背后用的是几何概率里一个经典结论均匀随机射线命中凸体的概率与凸体表面积成正比。于是我们可以写出递归成本模型[ C(p)C_{\text{trav}}P(L|p)\cdot C(L)P(R|p)\cdot C(R) ]其中 (P(L|p)S_L / S_p)(S) 是包围盒表面积。对一个候选分割位置左右子树的叶子数量分别记为 (n_L) 和 (n_R)每个叶子内部做一次三角形求交的估算成本记为 (C_{\text{isect}})那么实际使用的近似公式是[ C C_{\text{trav}} \frac{S_L}{S_p}\cdot n_L\cdot C_{\text{isect}} \frac{S_R}{S_p}\cdot n_R\cdot C_{\text{isect}} ]这个公式的物理意义非常直观我们希望左右子树的表面积尽量小这样射线不容易命中它们的包围盒同时三角形数量尽量均衡这样即使命中内部扫描量也不大。表面积小和数量均衡是互相拉扯的——把空间切得很细表面积自然小但两边数量可能严重失衡。SAH 的价值就是把这个权衡量化成一个成本数字让算法可以做全局最优选择。2.4 Binning 近似别真的穷举所有切分位置理论上要找到最优分割得在每个轴上、每两个三角形之间的间隙都算一遍 SAH代价是 O(N²)构建大场景根本跑不动。工程上的标准做法是 binning 近似把当前三角形集合的中心坐标在某个轴上均匀分到 12 到 16 个盒子bin里先累加每个 bin 的包围盒和三角形数量然后只尝试 bin 之间的 15 个分割点每个分割点的左右包围盒都能从累积结果里 O(1) 查出来。采样 16 个 bin 的 SAH 构建质量和完全最优的 SAH 差距极小通常不超过 1% 的遍历成本差异但构建速度快了一个数量级以上。我自己的实现里三个轴各分 16 个 bin二十万三角形的场景单线程构建大约 400 毫秒三百五十万三角形的密集场景大概 3 秒左右。这个量级在离线渲染里完全可以承受——场景通常只构建一次之后要复用好几年只要不修改几何数据。如果场景小于几万三角形SAH 的收益其实很有限中位分裂配个最长轴就够用了。我建议把是否启用 SAH做成一个可配置选项小场景用快速构建大场景再切到完整 SAH实测能省不少开发和调试时间。3. 遍历 BVH近端优先、提前终止与栈式实现3.1 Ray-AABB 求交的 Slab 方法与数值稳定性遍历 BVH 的基础操作是射线与 AABB 求交。标准做法是 slab 方法把 AABB 看成三组平行平面slab分别求出射线进入和离开这组平面的参数 t最终的 tmin 取三组进来的最大值tmax 取三组离开的最小值。如果 tmin tmax说明射线穿过了这个盒子。这里有个非常经典的数值稳定性坑当射线方向在某条轴上为 0 时1/dir会出现无穷大或者非法值。朴素写法在t (origin - slabMin) * invDir时可能得到 NaN而 NaN 参与比较会让结果变成 false导致错误的未命中。我自己踩过这个坑表现是渲染画面里随机丢三角形而且是完全不可复现的随机——换线程调度顺序结果都不一样。后来采用了一个简单但可靠的写法关键点是对斜率和边界做条件判断而不是直接算除法bool rayAABB(const Ray r, const AABB b, float tmin, float tmax) { tmin -INFINITY; tmax INFINITY; for (int i 0; i 3; i) { float o r.origin[i]; float d r.direction[i]; float t1 (b.min[i] - o) * (1.0f / d); float t2 (b.max[i] - o) * (1.0f / d); if (d 0.0f) std::swap(t1, t2); tmin std::max(tmin, std::min(t1, t2)); tmax std::min(tmax, std::max(t1, t2)); } return tmax tmin tmax 0.0f; }如果方向分量为 01/d是无穷大但min/max的写法配合d 0的交换能保证输出不出现 NaN——前提是你用的浮点运算符合 IEEE 规则。另一个更稳妥的方案是预计算invDir和正负方向标记在构建时就存进节点数据里遍历时直接按标记查边界省掉每次求交的分支。3.2 先近后远命中概率最大的孩子优先射线穿过父节点包围盒时进入左右两个孩子的参数区间通常是不同的。如果只按先后顺序访问两个孩子可能先处理了距离更远的那个结果在里面找到一个命中点 t_hit然后还得回头处理近的那个等处理完发现近的其实也有更近的命中白费了一圈。正确的做法是先访问t_near更小的孩子也就是让射线先碰到的那个。这样一旦在近端子树里找到命中它就有很大概率是全场景最近的命中远端子树可以直接跳过。实现上我们在射线和两个孩子的包围盒求交时分别得到(tminL, tmaxL)和(tminR, tmaxR)比较两个tmin就能决定访问顺序。这个排序访问的收益在大多数场景下非常显著。我做过一次对照实验同一场景、同一棵树随机顺序遍历比近端优先慢了 30% 到 50%而且场景越复杂差距越大。3.3 递归遍历改显式栈的工程原因BVH 的递归遍历代码写起来很漂亮命中父节点就递归两个孩子找到命中就返回 t_hit。但工程上我强烈建议大家改成显式栈。原因有两个一是函数调用本身有开销虽然树深通常只有二十来层但每层都要压栈弹栈累积起来并不少二是递归版本很难在提前终止时优雅地管理状态——你需要在递归调用返回后还能记得我还有一个更远的孩子没试。显式栈的经典做法是入栈时保存节点索引 这个节点对射线的 tmax。遍历时先取栈顶tNear最小的节点或直接后进先出配合预先排好序的孩子求交后把两个孩子按近远顺序压栈同时记录一个全局bestT。整个流程可以写成float traverse(Ray r, const BVHNode* nodes, const int* primIndices, const Triangle* tris) { float bestT INFINITY; StackEntry stack[64]; int sp 0; stack[sp] {0, 0.0f}; // 根节点 while (sp 0) { StackEntry e stack[--sp]; if (e.tNear bestT) continue; // 这个节点不可能产生更近命中 const BVHNode node nodes[e.index]; if (node.isLeaf) { for (int i 0; i node.count; i) { float t intersectTriangle(r, tris[primIndices[node.primStart i]]); if (t 0 t bestT) bestT t; } } else { float tLmin, tLmax, tRmin, tRmax; bool hitL rayAABB(r, nodes[node.left].bounds, tLmin, tLmax); bool hitR rayAABB(r, nodes[node.right].bounds, tRmin, tRmax); if (hitL hitR) { if (tLmin tRmin) { stack[sp] {node.right, tRmin}; stack[sp] {node.left, tLmin}; } else { stack[sp] {node.left, tLmin}; stack[sp] {node.right, tRmin}; } } else if (hitL) { stack[sp] {node.left, tLmin}; } else if (hitR) { stack[sp] {node.right, tRmin}; } } } return bestT; }栈大小 64 足够覆盖绝大多数场景。万一遇到极端不平衡的树深超过 64我一般直接断言失败因为这种树本身就说明构建策略出了问题找问题比硬撑更深栈有价值。3.4 提前终止最容易忽略的大杀器遍历时最影响性能的其实是剪枝一旦找到了一个三角形命中其他任何tNear bestT的节点都不可能产生更近的命中直接跳过整个子树连包围盒求交都不做。这个剪枝在视觉上有直接体现场景中靠近相机的三角形一旦被命中它后面的所有节点全被剪掉射线根本不用管理远处的内容。对路径追踪来说主射线命中近处物体后后面的天空盒、远景全部免测收益极其可观。我在做性能分析时发现加了提前终止之后总的包围盒求交次数大约下降了一半。很多人以为遍历瓶颈在二叉树深度其实在树的宽度——你检查的节点越多缓存失效和算力浪费越严重。提前终止就是在源头减少检查次数效果比优化单个求交函数的 SIMD 还明显。4. 实战落地内存布局、动态重建与构建期雷区4.1 节点内存布局别用指针散块很多教学实现把每个节点写成new出来的堆对象用指针连接。这种做法在核心逻辑教学没问题一旦场景上百万三角形节点数量几十万个每个节点分散在内存里遍历时缓存命中率会差到没法看。因为遍历是随机的深度优先行走访问顺序不是线性内存顺序散块分配的节点每次访问都可能触发缓存 miss。工程上更稳的做法是预先分配一个连续数组存所有节点内部用索引代替指针。构建时用深度优先先序分配节点——每个内部节点的左右孩子紧挨着放——这样遍历时访问一个兄弟节点极大概率落在同一个缓存行里。节点结构我推荐压到 40 字节以内AABB 用 2 个 float3 共 24 字节左右孩子索引或叶子信息用 8 字节再加上少量标志位。实际写代码时可以按 32 字节对齐性能比随意布局好很多。如果你做的是硬件光追或者 SIMD 加速路径建议进一步改成两路/四路宽节点一个节点直接存 2 个或 4 个孩子的包围盒一次遍历用 SIMD 同时测试多个包围盒。这就是现代硬件光追里 BVH4 / BVH8 的由来——用多路宽节点榨取访存带宽缺点是构建复杂度高不少单路 BVH 的优化经验可以无缝迁移过去。4.2 动态场景全部重建还是局部 Refit静态场景的 BVH 构建一次就行但实时应用里的物体经常动。每帧全量重建 SAH 树对于百万级三角形场景单帧几毫秒的构建开销通常可以接受一旦三角形数量上到千万全量重建就有点吃力了。另一种思路是 refit不动树的拓扑结构每帧只自底向上重新计算所有节点的包围盒。这样做速度极快几乎就是一次线性扫描但问题是包围盒会膨胀——物体移动后原本贴合三角形集的盒子越变越大树的排除能力越来越差。跑几十帧之后包围盒可能膨胀到覆盖整个场景退化回暴力求交。我的经验是做个折中每隔一定帧数或者当物体位移超过包围盒半径的某个阈值时挑出受影响子树做局部重建其余部分 refit。具体阈值要看场景规模和物体动画方式没有万能数字。一个保守的做法是先记录 refit 后的总包围盒表面积和原始 SAH 构建时的表面积当比值超过 1.5 到 2.0 就强制全量重建。这个度量相当于树烂到什么程度心里有个数。4.3 构建期的几何退化零面积三角形、巨大背景面和 NaN构建 BVH 时最容易让人抓狂的是一堆边界三角形零面积三角形、重复面片、面积特别大的背景平面等。零面积三角形会让包围盒在某个轴上厚度为 0导致 SAH 公式里出现除零或者极不稳定的结果。我遇到过一个实际案例从某软件导出的场景存在几百个退化的补片面构建时这些零厚度包围盒的表面积算出来是 NaN整个树的构建结果全是乱的渲染直接黑屏。解决方法是构建前先过滤几何把面积小于某个 epsilon 的三角形剔除或标记为不可见。这个过滤对渲染正确性没有影响因为零面积三角形本来就不会对图像有任何贡献。巨大背景面比如地面、天空穹顶是另一个麻烦。它们把包围盒撑得极大SAH 在计算时很容易把它们和一堆小物件分到同一边导致树的平衡性极差。工程上常见做法是把这种超大型三角形单独拎出来不进 BVH或者强制要求跨越某个尺寸阈值的三角形单独成叶子。这样做对渲染结果没有影响但能显著提升树的遍历效率。构建算法本身还有个隐蔽问题递归划分时如果选的分割点把所有三角形都分进同一边比如所有三角形中心坐标相同递归会无限下去。一定要加上退出条件当一次划分没有产生两边都有三角形时直接按中位分裂的数量平均强制切一刀或者退化成叶子。我记得某个开源渲染器的早期版本就有这个 bug特定模型下直接栈溢出。4.4 一个完整的对照BVH 和其他加速结构怎么选下表是我实际选项中经常拿来做对比的维度参考价值大于教科书里的分类维度BVHk-d 树八叉树均匀网格构建速度中SAH 较慢中快最快遍历质量好适应非均匀分布优秀空间切分最细中差非均匀场景动态更新容易refit/局部重建困难拓扑依赖空间中容易重建网格哈希内存占用中等节点紧凑较高节点多中受分辨率影响大多路 SIMD容易宽节点较难中容易实现复杂度中高低低BVH 胜在对象集合切分带来的动态友好性和遍历稳定性非常适合离线渲染、碰撞检测、光照求交这类三角形分布极不均匀的场景。k-d 树的遍历理论上比 BVH 更优它切割的是空间不会有重叠的包围盒但构建慢、更新难现代引擎基本不用于动态场景。均匀网格在粒子系统、均匀分布的流体模拟里性能很好但一旦场景里有明显的稀疏密集差异网格分辨率就很难调调小了密集区退化调大了稀疏区浪费。我的经验是工程上优先考虑 BVH除非你的场景本身就是均匀分布的才考虑网格。5. 硬件光追与两层 BVHBVH 在现代管线里的生态位5.1 顶层和底层场景实例化后的两层结构现代实时渲染里的硬件光追单元用的是两层 BVH底层Bottom-Level是单个网格物体自己的 BVH顶层Top-Level是场景中所有实例带变换矩阵的物体引用的 BVH。射线先测顶层命中实例后拿实例的变换矩阵把射线变换到物体局部空间再测对应实例的底层 BVH。这个设计非常聪明同一个网格被实例化一百次底层 BVH 只需要构建一次一百个实例共享物体移动只要更新顶层中该实例的包围盒底层完全不动。这和我在第四节讲的 refit/全量重建取舍本质上是一回事只不过硬件把这两层焊死成了管线规范。对软件渲染器来说理解这个两层结构也很有用。我自己的路径追踪器就借鉴了这个思路场景里大量重复出现的道具路灯、树木、椅子各建一棵底层 BVH一个城市场景只要几十棵小树加一棵顶层实例树内存和构建时间都省了一大截。直接用一棵大 BVH 把所有三角形摊平了构建重复几何的内存开销很浪费。5.2 构建质量要服务于遍历时的实际查询分布最后说一个很多教材不提、但实际影响巨大的点SAH 的默认假设是射线均匀分布。真实渲染里的射线分布并不均匀——阴影射线通常从光源方向集中打向一小片区域焦散和反射射线的分布更是严重偏离均匀。这时候完全按默认 SAH 构建的 BVH 可能不是最优的。我踩过的一个具体例子在一个室内场景做聚光灯阴影灯光角度非常窄大量阴影射线都集中在同一个锥体里。默认 SAH 构建的树把灯光附近的高密度三角形区域切得很细但实际射线的分布和它们并不匹配导致遍历时频繁访问到空节点。后来我改成带权重的 SAH给光源可见区域内的三角形更高的权重让树在这些区域切得更细阴影射线遍历快了大约 20%。当然这种定制化是有代价的权重要场景类型换个灯光方案就要重新调。我的建议是先把默认 SAH 做对、做稳定再考虑查询分布优化。树的构建质量决定了遍历速度的上限而遍历实现决定了能逼近这个上限多少。顺序不能反。5.3 调试 BVH 的土办法先画包围盒再谈性能无论你是第一次实现 BVH 还是优化现有代码我强烈建议保留一个调试可视化模式把节点包围盒画成线框。这个能力救了我很多次。具体做法是在遍历里加一个开关当某个节点被访问到时把它包围盒的两个顶点输出到一张调试图像或者直接改透明度叠加到最终渲染结果上。看到包围盒的形状和层次你立刻能知道树的质量好不好如果某层的包围盒重叠面积巨大说明 SAH 没生效如果某棵子树包围盒特别大但里面只有几个三角形说明分裂选位出错如果叶子内部三角形分布和包围盒形状明显不贴合多半是三角形归属集合出了问题。我记得第一次画出来的时候看到地面平面那棵子树几乎覆盖了半张图一下就明白了中位分裂为什么不行。这个可视化工具比任何 profiler 都直观建议写进你的构建代码里不删。还有一个小技巧性能调优时不要只看帧时间要统计每次遍历平均做了多少次包围盒测试和三角形求交。这两个数字能帮你判断瓶颈到底在树的质量还是遍历的剪枝逻辑。有一次我优化遍历代码让帧时间快了一倍但包围盒测试次数没怎么变说明瓶颈本来就不在树的质量而在三角形求交函数本身——这个发现省掉了我大量无效优化。做 BVH 这件事越往后越会发现真正决定性能的不是某一个花哨算法而是一连串不起眼的工程决策叠加起来的结果节点内存是否连续、提前终止判断是否够早、叶子大小是否合理、退化几何有没有提前处理。这些细节每一项单独看都不起眼合在一起就是数量级的差距。先跑通一个正确但不快的版本再对照着这些点逐个优化是我在这条路上摸索出来的最稳路径。