如果你写过一个带光线追踪的渲染器或者做过任何物理模拟、游戏里的碰撞模块大概率会遇到同一个瓶颈场景三角形数量从几千冲到几百万时之前那套“每根光线遍历所有三角形”的做法会把帧率直接拖到个位数。我自己的第一个渲染器就是这样场景里放一个带精细雕刻的角色模型渲染一张 1024x768 的图要跑快四十分钟后来一看大部分时间全耗在光线和每一个三角形的逐个求交上。解决这个问题的经典方案之一就是 BVH。BVHBounding Volume Hierarchy层次包围盒是一棵二叉树它把场景里的三角形按照空间位置组织成层级包围结构。光线求交的时候先测大包围盒不相交就整棵子树全部跳过碰撞检测同理物体之间先测包围盒盒都不重叠就不必进入三角形级别的精确检测。这篇文章我会从数据结构设计、BVH 构建、光线遍历求交再到碰撞检测的实战用法把我自己踩过的坑和验证过有效的写法完整拆开适合正在写渲染器、物理引擎或者对空间加速结构感兴趣的 C 开发者参考。1. 为什么需要 BVH暴力求交的困局与树形加速的破局1.1 暴力遍历简单但昂贵的写法很多刚入门光线追踪的人第一版代码是这样的遍历场景里的所有三角形调用一次光线与三角形求交函数记录最近的交点。逻辑没有任何问题写起来也快但复杂度是 O(N) 每根光线。假设场景有 100 万个三角形一张 1024x768 的图像每像素发射一根主光线那至少要做约 7.8 亿次三角形求交每次还涉及几个向量叉积和点积。CPU 再快也顶不住这种暴力扫描。碰撞检测也一样。两个角色模型各有几万个三角形要做“是否碰到对方”的判断双层循环测三角形与三角形相交复杂度 O(M×N)在游戏帧循环里跑一帧就知道什么叫灾难。暴力方法唯一的优点就是正确性容易保证所以适合当基准实现去验证加速结构的正确性但生产环境里必须靠空间加速结构。1.2 BVH 的核心思想空间分层与剪枝BVH 的思路非常直观先给整组三角形算一个能包住它们的大盒子也就是包围盒再把三角形按空间位置分成两堆分别再算包围盒分出来的每一堆再递归分下去直到盒子里三角形数量足够少形成叶子节点。这样整棵树上越靠上包围盒越大越往下包围盒越小、三角形越集中。光线求交时从树根开始测光线是否穿入根节点包围盒。如果光线和根盒子都不相交说明光线永远碰不到场景里任何一个三角形直接返回“无命中”。如果相交就继续测两个子节点的盒子。子节点盒子不相交的那一整个子树就不用进去了。这个“跳过一大片区域”的行为就是加速的核心术语叫剪枝pruning。碰撞检测里的逻辑完全一样两个物体的 BVH 分别从根节点开始先测两个根节点包围盒是否重叠。不重叠两个物体绝对没碰重叠就递归去测它们的子节点盒子。只有当叶子节点的盒子都重叠了才真正进入三角形级别做精确求交。这种“先用简单几何做粗筛再用精确几何做细筛”的分层思想在几乎所有空间加速结构里都用得上。1.3 不同加速结构的对比我常被问到的一个问题是为什么要选 BVH而不是均匀网格、八叉树或者 K-D 树这几者的核心区别在于划分方式。均匀网格把空间切成固定大小的体素实现简单但三角形分布不均匀时格子要么过多要么过少八叉树适合自适应划分但在动态场景里更新麻烦K-D 树是切平面划分对静态场景的光线追踪效果很好但构建和更新更复杂也不容易直接用于碰撞检测。相对而言BVH 的构建简单遍历高效稍微动点心思就能同时服务光线求交和碰撞检测两个需求所以我推荐先用 BVH 入门。结构构建复杂度光线求交适合度碰撞检测适合度动态场景友好度均匀网格低中中中八叉树中中中低K-D 树高高低低BVH中高高中这个对比不是绝对的工程里有很多混合方案但单论“一套结构通吃光线与碰撞”BVH 是我个人最推荐的选择。2. 基础功底AABB 与节点数据结构设计2.1 为什么用 AABB 而不是球体或 OBBBVH 里的包围体最常见的是 AABBAxis-Aligned Bounding Box轴对齐包围盒也就是每条边分别平行于 X、Y、Z 轴的六面体。它只需要存两个三维向量min 和 max占内存极小。更关键的是光线与 AABB 的相交测试可以分解成三个独立维度上的区间判断计算量非常低几乎没有分支也能实现得很好。球体包围盒更快但球体对细长三角形族拟合很差一个长条地形用球体包空余体积极大剪枝效果骤减。OBB有向包围盒拟合更紧但要存旋转矩阵相交测试复杂很多。AABB 处在“拟合度可以接受、计算速度极快”的最佳平衡点所以 BVH 节点里几乎都是用 AABB。2.2 C 内存布局别把节点搞成对象写 BVH 的时候最容易犯的错是把每个节点定义成一个包含std::vector、std::shared_ptr子节点的高层类。树结构没问题但性能会非常难看因为每一次递归都要解引用指针缓存命中率极低。现代 CPU 做光线遍历时瓶颈很多时候不在浮点运算而在内存访问。我实际使用的方案是用一个扁平的std::vectorBVHNode存所有节点节点通过数组下标互相引用不存指针。这样所有节点在内存里是连续的遍历时按顺序访问缓存友好度直接上一个档次。节点大小也需要注意。AABB 占了 6 个 float就是 24 字节再加上左右孩子索引或者叶子信息很容易到 32 字节或 40 字节。这里有个经验值把节点对齐到 32 字节正好对应常见的缓存行对齐遍历时会非常舒服。2.3 一套够用的 C 数据结构骨架先给出最基础的向量与光线定义。为了代码简洁我用了一个简化版的三维向量实际项目里可以直接换成 glm 或自研的 SIMD 向量库。struct Vec3 { float x, y, z; Vec3 operator(const Vec3 b) const { return {x b.x, y b.y, z b.z}; } Vec3 operator-(const Vec3 b) const { return {x - b.x, y - b.y, z - b.z}; } Vec3 operator*(float s) const { return {x * s, y * s, z * s}; } float operator[](int i) const { return i 0 ? x : (i 1 ? y : z); } float operator[](int i) { return i 0 ? x : (i 1 ? y : z); } }; struct AABB { Vec3 min; Vec3 max; }; struct Ray { Vec3 origin; Vec3 direction; Vec3 invDir; // 1 / direction提前算好除以三的代价 };然后是 BVH 节点。我把内部节点和叶子节点放在同一个结构体里用isLeaf()区分。内部节点用left和right存两个子节点的数组下标叶子节点用primStart和primCount指向图元索引数组的一段连续区间。struct BVHNode { Vec3 bboxMin; Vec3 bboxMax; union { struct { int left; // 内部节点左孩子下标 int right; // 内部节点右孩子下标 }; struct { int primStart; // 叶子节点图元起点 int primCount; // 叶子节点图元数量 }; }; bool isLeaf() const { return right 0; // 约定右孩子为负数表示叶子 } };这里的技巧是内部节点的right一定是非负下标叶子节点里我把right置成负数同时复用内存存放primCount。这样每个节点只占用 8 个 float 的空间最小化内存占用。再加上一个std::vectorint primIndices存所有图元索引构建时不断对索引做分区实际三角形数据保持不动避免频繁拷贝三角形本身。光线在生成时提前算好invDir可以避免遍历时每个节点都做三次除法。除法是昂贵的运算光线数量百万级节点访问千万级这个提前计算收益非常明显。3. 构建 BVH从简单分割到 SAH 的进阶之路3.1 最容易理解的中点分割构建 BVH 最简单的方式是算出所有三角形的包围盒取包围盒中心作为参考点沿着最长轴把三角形分成左右两组左边中心小于中点右边大于中点然后递归构建。这个方案叫中点分割midpoint partitioning。优点是好写三十分钟能跑通一版。缺点是它完全不管三角形的空间分布。假设有一堆三角形挤在包围盒的左下角另一半空间只有一个三角形中点分割还是会把它们按中心一刀切结果造成两个子树包围盒大量重叠光线遍历时两边都可能要进去测剪枝效果大打折扣。类似的情况在真实场景里并不少见——一个角色模型堆积在原点附近周围散落几个道具就是典型的非均匀分布。3.2 为什么用 SAH把“代价”变成数学函数SAHSurface Area Heuristic表面积启发式是解决非均匀分布的主流方案。它的核心思想是把光线穿过某个节点的概率近似看作这个节点包围盒的表面积占整个场景包围盒表面积的比例。基于这个假设可以写出一个估计递归求交成本的公式。假设一个内部节点左右两个子包围盒的表面积分别是 A(L) 和 A(R)对应三角形数量是 N(L) 和 N(R)父节点包围盒表面积为 A(P)单次三角形求交成本和单次 AABB 求交成本都是常数。那么光线经过这个内部节点的期望求交成本 C 可以近似为C 1 A(L)/A(P) * N(L) A(R)/A(P) * N(R)构建的时候我们尝试不同的分割方案选成本最小的那个。这个公式里A(L)/A(P)可以理解为“光线进入父节点的前提下也进入左子节点的概率”。三角形多的子树即使表面积大也未必是坏事因为 SAH 会自动在“盒子大小”和“盒子里的三角形数量”之间找平衡。3.3 基于 Binning 的 SAH 构建如果每层构建都对所有三角形按每个可能的切割位置做一次计算复杂度会非常高。工程上常用的是“分桶 SAHbinned SAH”把三角形的质心沿某个轴分成固定数量的桶我常用 16 个每个桶统计三角形数量和包围盒然后枚举相邻桶之间作为切割点计算 SAH 成本。这样切割点数量从三角形数量降到了桶数量构建速度飞快质量损失却很小。下面是一个简化但能直接跑通的核心构建逻辑int BVH::build(int* primIndices, int first, int count) { if (count leafSize) { BVHNode node; node.bboxMin computeBounds(primIndices, first, count).min; node.bboxMax computeBounds(primIndices, first, count).max; node.primStart first; node.primCount count; node.right -1; nodes.push_back(node); return (int)nodes.size() - 1; } AABB overallBounds computeBounds(primIndices, first, count); int bestAxis 0; int bestSplit first count / 2; // 默认用中点防止退化 float bestCost FLT_MAX; // 对三个轴分别做分桶 SAH for (int axis 0; axis 3; axis) { float bucketMin[16], bucketMax[16]; int bucketCount[16]; // 把三角形质心映射到 [0,15] 的桶号 for (int i 0; i 16; i) { bucketMin[i] FLT_MAX; bucketMax[i] -FLT_MAX; bucketCount[i] 0; } for (int i first; i first count; i) { Vec3 centroid computeCentroid(primIndices[i]); float t (centroid[axis] - overallBounds.min[axis]) / (overallBounds.max[axis] - overallBounds.min[axis] 1e-6f); int bucket (int)(t * 16.0f); if (bucket 0) bucket 0; if (bucket 16) bucket 15; // 更新对应桶的包围盒和计数 } // 从左到右扫描维护前缀包围盒和数量计算每个切割点成本 AABB leftBox[16], rightBox[16]; int leftCount[16], rightCount[16]; // 具体扫描我这里略过就是反复合并包围盒与累加计数 // 每一刀的位置 k 表示 [0, k] 去左边[k1, 15] 去右边 for (int k 0; k 15; k) { float cost 1.0f leftBox[k].surfaceArea() / overallBounds.surfaceArea() * leftCount[k] rightBox[k].surfaceArea() / overallBounds.surfaceArea() * rightCount[k]; if (cost bestCost) { bestCost cost; bestAxis axis; // 记录该轴该切法对应的实际三角形分界位置 } } } // 按 bestAxis 重新分区这里使用 std::partition 按质心切到最佳切割点 int mid partitionByAxis(primIndices, first, first count, bestAxis, overallBounds, bestSplit); int leftChild build(primIndices, first, mid - first); int rightChild build(primIndices, mid, first count - mid); BVHNode parent; parent.bboxMin min(nodes[leftChild].bboxMin, nodes[rightChild].bboxMin); parent.bboxMax max(nodes[leftChild].bboxMax, nodes[rightChild].bboxMax); parent.left leftChild; parent.right rightChild; nodes.push_back(parent); return (int)nodes.size() - 1; }这段代码里我刻意省略了不少细节只保留了骨架但两个重要细节值得单独说明。第一个是叶子大小leafSize。太小会导致树太深、节点过多内存和遍历开销增大太大会让叶子里的三角形求交变成小规模暴力循环。我测试下来leafSize 4到8之间表现最好具体数值和场景、三角形大小有关建议做一个参数跑实验。第二个是bestSplit的记录问题。用分桶 SAH 时我们已经在桶的粒度上找到了最佳切割位置但桶是一个近似区间真正切分数组时我们要把质心落在左边桶的三角形放到左边落在右边桶的放到右边。实际实现里我会把最佳切割点精确到“某个桶之后”然后用std::partition按桶号去划分而不是把质心坐标重新计算一遍。构建完之后我习惯做一次“节点合法性检查”作为调试断言每个内部节点的左右包围盒都被父包围盒包含每个叶子节点的三角形确实都落在自身包围盒内。这个检查在 Debug 版本里跑一遍能帮你躲过很多隐蔽的构建 bug。3.4 构建阶段的两个常见问题包围盒退化怎么办当很多三角形质心完全相同或者某个轴方向的最小最大范围接近零分桶时会出现分母为零或桶号全挤到同一个桶的情况。我处理的办法是给分母加一个极小量如果整个包围盒三个轴的范围本来就接近零就直接退化成叶子节点不再往下分避免进入死循环。排序还是分区std::sort会带来 O(N log N) 复杂度而构建 BVH 只需要把所有元素按某个中间位置分成两边不需要完全有序。所以要用std::partition它是 O(N)整个构建复杂度能降到 O(N log N) 以下场景大时差距非常明显。4. 光线求交遍历 BVH 的正确打开方式4.1 slab 光线-包围盒相交测试光线与 AABB 的求交最经典的方法是 Slab Method。核心思路是把 AABB 看成三对平行平面形成的“薄片”的交集光线分别计算进入和离开每一对平面的参数 t 值再取三组区间的交集。具体公式是t0 (bboxMin - ray.origin) / ray.direction t1 (bboxMax - ray.origin) / ray.direction如果方向分量是负的t0 和 t1 恰好会交换。所以我们先对两个值取最小和最大然后用三个轴上的最小值取最大三个轴的最大值取最小最后比较这两个值。区间交集的逻辑就是光线必须在所有轴上都处于盒子内部才算穿过了盒子。bool intersectAABB(const Ray ray, const AABB box, float tEnter, float tExit) { float t0 0.0f; float t1 1e30f; for (int i 0; i 3; i) { float invDir ray.invDir[i]; float origin ray.origin[i]; float a (box.min[i] - origin) * invDir; float b (box.max[i] - origin) * invDir; if (invDir 0.0f) std::swap(a, b); t0 std::max(t0, a); t1 std::min(t1, b); if (t0 t1) return false; } tEnter t0; tExit t1; return t1 0.0f; }这里有个容易踩的坑光线方向某个分量为 0 时invDir是无穷大box.min 和 origin 相等时会出现0 * inf NaN。很多实现会用if (a ! a) return false之类的 NaN 检测来规避但我在实际代码里更推荐显式处理当方向分量接近 0 时如果 origin 落在盒子范围内就把这个轴向的区间设成全程有效否则直接判定不相交。这样可以避免 NaN 带来的不确定行为。4.2 自顶向下遍历显式栈代替递归BVH 遍历如果写成递归每访问一层都要压栈树深几十层时虽然没问题但函数调用开销存在而且 Debug 模式下递归栈会变得很深慢场景下甚至可能爆栈。我在工程实现里统一用显式栈。核心流程是从根节点开始把根节点压栈每次从栈里弹出一个节点先和光线做 AABB 求交。如果不相交或者求交得到的 t 值已经大于当前已知最近命中距离说明这个子树里不可能有更近的三角形直接跳过。如果是叶子节点就遍历它包含的三角形更新最近命中距离如果是内部节点则计算两个子节点的相交情况决定压栈顺序。bool BVH::intersect(const Ray ray, float tHit, int hitPrimIndex) { tHit 1e30f; int stack[64]; int stackPtr 0; stack[stackPtr] rootIndex; while (stackPtr 0) { int nodeIndex stack[--stackPtr]; const BVHNode node nodes[nodeIndex]; float tEnter, tExit; if (!intersectAABB(ray, node, tEnter, tExit) || tEnter tHit) { continue; } if (node.isLeaf()) { for (int i node.primStart; i node.primStart node.primCount; i) { int primIdx primIndices[i]; float t; if (intersectTriangle(ray, primIdx, t) t tHit) { tHit t; hitPrimIndex primIdx; } } } else { int leftIdx node.left; int rightIdx node.right; float tLeftEnter, tLeftExit; float tRightEnter, tRightExit; bool hitLeft intersectAABB(ray, nodes[leftIdx], tLeftEnter, tLeftExit); bool hitRight intersectAABB(ray, nodes[rightIdx], tRightEnter, tRightExit); if (hitLeft hitRight) { // 先访问近的子树提升提前命中概率 if (tLeftEnter tRightEnter) { stack[stackPtr] rightIdx; stack[stackPtr] leftIdx; } else { stack[stackPtr] leftIdx; stack[stackPtr] rightIdx; } } else if (hitLeft) { stack[stackPtr] leftIdx; } else if (hitRight) { stack[stackPtr] rightIdx; } } } return tHit 1e29f; }这个遍历版本的精髓有两个地方。第一是先访问近的子树。注意我是先把远的子节点压栈再把近的子节点压栈这样弹栈时先弹出来的是近的那个。先处理近处的子树可以更快拿到一个较小的 tHit后面的远子树即使被访问到也会因为tEnter tHit的条件被快速跳过。第二是栈大小。64层的栈对于绝大多数场景够用了。BVH 是二叉树理想深度是 log2(N) 量级百万三角形大概 20 层64 已经很保守。但如果树构建质量差深度可能异常增大建议加一个栈溢出计数器Debug 版本里如果发现深度超过 64就回退去检查构建逻辑。4.3 叶子处三角形求交的衔接当我找到一个可能命中的三角形时我用的是经典的 Moeller-Trumbore 算法。这里不打算展开他的数学推导只提一个与 BVH 遍历配合的关键点三角形求交得到的 t 值必须和当前全局的tHit做比较。很多初版实现会忘记这个比较导致明明是后面更近的三角形已经被跳过却返回了一个更远的三角形。另一个技巧是在遍历过程中如果tEnter已经大于tHit就提前跳过整个节点这本质上是把“先访问近节点”和“全局剪枝”结合在一起。实践中这一步能挡掉大量无效的三角形求交特别是在遮挡比较严重的场景里收益极其明显。4.4 遍历性能的其他尝试遍历部分我能再给几个优化方向但从性价比角度排序我最推荐先做好前面几项再考虑 SIMD 和 GPU 化。把Ray里的invDir用 4 分量浮点存配合 SIMD 做 4 路光线同时遍历。这个改动量大但效果非常显著。叶子节点里如果三角形数量少直接手写内联循环。现代编译器会帮忙展开但你要保证三角形求交函数是inline的。如果场景大多是静态模型可以把 BVH 节点按 DFS 顺序重新排列让相邻节点在内存中尽量连续提高缓存命中率。5. 从光线求交到碰撞检测BVH 的另一半江山5.1 对象与对象的碰撞两个 BVH 的递归重叠碰撞检测和光线求交本质上是同一个问题的两种变体光线求交是“一维查询对象”碰撞检测是“三维区域查询对象”。当我们要检测两个物体是否碰撞时最直接的办法是同时遍历两个物体的 BVH比较两个节点包围盒是否重叠。基本流程是准备一个栈初始放入两个根节点的索引对。弹出一对节点先判断两个节点 AABB 是否重叠。不重叠就跳过重叠了如果两边都是叶子节点则进入三角形级别的三角形-三角形相交测试如果有一边或两边是内部节点则把可能的子节点组合继续压栈。bool BVH::overlap(const BVH a, const BVH b) { struct NodePair { int aIdx; int bIdx; }; NodePair stack[128]; int stackPtr 0; stack[stackPtr] {a.rootIndex, b.rootIndex}; while (stackPtr 0) { NodePair pair stack[--stackPtr]; const BVHNode na a.nodes[pair.aIdx]; const BVHNode nb b.nodes[pair.bIdx]; if (!overlapAABB(na, nb)) continue; bool aLeaf na.isLeaf(); bool bLeaf nb.isLeaf(); if (aLeaf bLeaf) { for (int i na.primStart; i na.primStart na.primCount; i) { for (int j nb.primStart; j nb.primStart nb.primCount; j) { if (triangleIntersectTriangle(a.prims[primIndices[i]], b.prims[primIndices[j]])) { return true; } } } } else { // 展开非叶节点把子节点组合压栈 if (aLeaf) { stack[stackPtr] {pair.aIdx, nb.left}; stack[stackPtr] {pair.aIdx, nb.right}; } else if (bLeaf) { stack[stackPtr] {na.left, pair.bIdx}; stack[stackPtr] {na.right, pair.bIdx}; } else { stack[stackPtr] {na.left, nb.left}; stack[stackPtr] {na.left, nb.right}; stack[stackPtr] {na.right, nb.left}; stack[stackPtr] {na.right, nb.right}; } } } return false; }这套代码的逻辑不复杂但要注意一个细节当两个叶子重叠时需要做三角形-三角形精确碰撞这个测试本身也不便宜所以前面几层的包围盒粗筛越严格精确测试的调用次数就越少。这又回到了 BVH 构建质量的重要性。5.2 动态场景重建与 Refit 的取舍静态场景里 BVH 表现无懈可击但游戏和物理模拟里三角形经常动这时就要面临一个选择每帧重建 BVH还是只更新包围盒。重建rebuild的意思是每一帧重新运行整个构建流程。优点是树的质量始终保持最优缺点是构建开销可能占掉整个 CPU 预算的很大一块。对于几万个三角形的小型场景重建很快可以接受几百万三角形的大型场景每帧重建直接卡死。Refit 的意思是只更新节点包围盒不改变树结构。先更新叶子节点把三角形的新位置重新算盒范围然后从叶子向根逐层重新合并父节点包围盒。这个操作非常快遍历速度也能维持不错的水平但随着物体移动初始分割可能不再合理包围盒会变得松散树的质量逐渐下降。我个人的实践建议是如果场景里三角形位移不大优先用 refit如果物体发生了大规模形变比如布料从平面变成团状就直接重建。也可以做混合策略先 refit隔几十帧或者当 refit 后的遍历耗时超过阈值时触发一次全局重建。这个阈值需要根据项目实际场景调但思路很实用。策略构建速度遍历速度实现复杂度适用场景重建慢高中静态场景、大规模变形Refit非常快中低小范围移动、实时游戏5.3 宽阶段和窄阶段BVH 在碰撞管线里的位置实际碰撞系统通常是两阶段架构。宽阶段负责快速排除不可能碰撞的物体对引擎里常用 Sweep and Prune 或网格用的也是“先测大包围盒”的思路。窄阶段才做三角形级别的精确碰撞。BVH 在这套架构里的角色很灵活。小型项目可以只用 BVH 同时扮演宽阶段和窄阶段物体的根节点就是它的粗包围体叶子节点就是三角形。大型项目里宽阶段用其他更适合动态物体排序的算法窄阶段再对每个物体内部使用 BVH 做自碰撞或物体对碰撞。以布料模拟为例布料的顶点数量很大且会连续形变做自碰撞检测时就非常依赖每帧 refit 后的 BVH否则一针一线的穿透判断会变成 O(N^2) 的地狱。碰撞检测里的浮点问题也值得多说一句。两个物体如果处于刚好接触的状态三角形求交测试会因为浮点误差出现“时而相交、时而不相交”的抖动表现为物体微微颤动。工程上常见的解法是在求交时给距离阈值设一个极小偏移量比如 1e-4 或 1e-5 级别的宽容度把“刚好贴在一起”的情况当成接触处理。这样会牺牲一点点精度但换来的稳定性对游戏和物理系统非常重要。6. 调试与性能实测从“能跑”到“跑得快”6.1 验证 BVH 是否正确我见过太多人写完了 BVH跑出来的图看起来也正常就以为万事大吉。但其实很多细微 bug 只有当场景特别复杂时才会突然爆发比如阴影中少了一小块、碰撞时偶尔穿透。所以我会在开发阶段做三层验证。第一层是视觉验证。写一个独立渲染模式把所有 BVH 节点的 AABB 以线框形式画出来叠加在场景上。你一眼就能看出树结构是否合理包围盒之间重叠是否严重叶子大小是否均匀有没有某些节点盒子巨大但只包了一个三角形。第二层是数值验证。拿一张低分辨率图逐像素对比暴力遍历和 BVH 遍历的命中结果要求每个像素命中的三角形索引和 t 值完全一致。这个对比只需要小场景跑一遍就能筛出遍历逻辑里的排序、剪枝错误。第三层是随机光线测试。随机发射大量光线对比暴力结果和 BVH 结果既能验证正确性又能顺便统计每个节点的命中次数帮助定位性能瓶颈。6.2 性能分析的实用经验性能优化不能靠感觉。我常用的手段是在遍历代码里插入轻量计数器分别统计 AABB 求交次数、三角形求交次数和最终命中次数。理想状态下三角形求交次数应该远小于 AABB 求交次数AABB 求交次数又远小于暴力情况下的三角形求交次数。如果发现 AABB 求交次数异常多大概率是构建质量差导致包围盒重叠严重。实测时我还会看两个指标阴影光线和主光线的耗时差异。主光线通常能很快找到近处命中然后 tHit 剪枝生效阴影光线则常常在确定“被遮挡”后立刻返回所以二者耗时差异能反映树的剪枝效率。如果阴影光线平均耗时还很高通常说明包围盒重叠太多或者叶子太大。下面这个表是我一个小型测试场景里记录的耗时分布三角形数量 128 万主光线 1024x768。数据不具备普适性但可以看出大致比例关系。阶段耗时占比备注BVH 构建一次3.8%构建时间占比很低主光线遍历28.5%大部分时间在 AABB 求交与三角形求交阴影光线遍历31.2%遮挡判断大量触发提前返回着色与像素写入23.4%非加速结构相关其他开销13.1%相机、内存分配等看到这个比例我的第一反应往往不是继续优化遍历而是先看三角形求交函数是否足够快。因为三角形求交才是真正的浮点重活AABB 再怎么优化也只是多挡几下。6.3 我踩过的坑清单这里列几个我在实际编码里真实遇到过、而且排查很久的问题给你提个醒。未更新全局 tHit这个最隐蔽。光线穿过了多个三角形如果叶子处理时没把最近命中距离写回后续叶子就会用初始的极大值去遍历导致远处三角形也能被当作最近命中。我一度因为这个问题看到了极其诡异的“半透明物体遮挡不准确”效果。零方向分量的 NaN 传播光线平行于某个轴时invDir 是无穷大和 box 边界做乘加会得到 NaN。我强烈建议在 Ray 构造时显式处理方向分量接近零的情况把 invDir 对应分量设成一个极大值而不是直接除零。栈溢出显式栈设为固定大小时如果场景三角形分布极度不均树可能变得很深。解决方法是加边界检查Debug 模式下越界直接抛断言不要等到内存爆炸再查。SAH 分母为零三角形质心范围在一个轴上是零时分桶计算会出现除零。加一个小 epsilon 通常是够用的。图元索引顺序改变构建时我用了std::partition不断重排primIndices如果之后叶子节点的primStart和primCount算错了会把别的三角形索引当成自己的画面上的表现是随机若干三角形消失或出现错误交点。建议构建结束后把每个叶子对应的原始三角形索引打印出来和暴力遍历做一轮严格比对。最后再说两句BVH 这个东西原理说起来不复杂但真正把它做到又快又稳需要投入不少时间在数据布局、构建策略和遍历细节上。我在最初实现时以为写完构建和遍历就结束了后来调试过程里才发现大量时间其实花在验证正确性和优化内存访问上。不过这些投入完全值得因为同样的结构稍微改一改就能服务于光线追踪和碰撞检测两个系统。如果你正在写自己的渲染器或物理引擎我建议第一版不要急着上 SAH 和分桶这类优化先用中点分割把完整结构跑通再用暴力遍历做结果对照最后逐步替换成 SAH 构建并引入性能计数器。一步一步来你会对树的构建质量和遍历速度之间的关系有特别直观的感受。 BVH空间加速结构：光线追踪与碰撞检测的C++实战指南
如果你写过一个带光线追踪的渲染器或者做过任何物理模拟、游戏里的碰撞模块大概率会遇到同一个瓶颈场景三角形数量从几千冲到几百万时之前那套“每根光线遍历所有三角形”的做法会把帧率直接拖到个位数。我自己的第一个渲染器就是这样场景里放一个带精细雕刻的角色模型渲染一张 1024x768 的图要跑快四十分钟后来一看大部分时间全耗在光线和每一个三角形的逐个求交上。解决这个问题的经典方案之一就是 BVH。BVHBounding Volume Hierarchy层次包围盒是一棵二叉树它把场景里的三角形按照空间位置组织成层级包围结构。光线求交的时候先测大包围盒不相交就整棵子树全部跳过碰撞检测同理物体之间先测包围盒盒都不重叠就不必进入三角形级别的精确检测。这篇文章我会从数据结构设计、BVH 构建、光线遍历求交再到碰撞检测的实战用法把我自己踩过的坑和验证过有效的写法完整拆开适合正在写渲染器、物理引擎或者对空间加速结构感兴趣的 C 开发者参考。1. 为什么需要 BVH暴力求交的困局与树形加速的破局1.1 暴力遍历简单但昂贵的写法很多刚入门光线追踪的人第一版代码是这样的遍历场景里的所有三角形调用一次光线与三角形求交函数记录最近的交点。逻辑没有任何问题写起来也快但复杂度是 O(N) 每根光线。假设场景有 100 万个三角形一张 1024x768 的图像每像素发射一根主光线那至少要做约 7.8 亿次三角形求交每次还涉及几个向量叉积和点积。CPU 再快也顶不住这种暴力扫描。碰撞检测也一样。两个角色模型各有几万个三角形要做“是否碰到对方”的判断双层循环测三角形与三角形相交复杂度 O(M×N)在游戏帧循环里跑一帧就知道什么叫灾难。暴力方法唯一的优点就是正确性容易保证所以适合当基准实现去验证加速结构的正确性但生产环境里必须靠空间加速结构。1.2 BVH 的核心思想空间分层与剪枝BVH 的思路非常直观先给整组三角形算一个能包住它们的大盒子也就是包围盒再把三角形按空间位置分成两堆分别再算包围盒分出来的每一堆再递归分下去直到盒子里三角形数量足够少形成叶子节点。这样整棵树上越靠上包围盒越大越往下包围盒越小、三角形越集中。光线求交时从树根开始测光线是否穿入根节点包围盒。如果光线和根盒子都不相交说明光线永远碰不到场景里任何一个三角形直接返回“无命中”。如果相交就继续测两个子节点的盒子。子节点盒子不相交的那一整个子树就不用进去了。这个“跳过一大片区域”的行为就是加速的核心术语叫剪枝pruning。碰撞检测里的逻辑完全一样两个物体的 BVH 分别从根节点开始先测两个根节点包围盒是否重叠。不重叠两个物体绝对没碰重叠就递归去测它们的子节点盒子。只有当叶子节点的盒子都重叠了才真正进入三角形级别做精确求交。这种“先用简单几何做粗筛再用精确几何做细筛”的分层思想在几乎所有空间加速结构里都用得上。1.3 不同加速结构的对比我常被问到的一个问题是为什么要选 BVH而不是均匀网格、八叉树或者 K-D 树这几者的核心区别在于划分方式。均匀网格把空间切成固定大小的体素实现简单但三角形分布不均匀时格子要么过多要么过少八叉树适合自适应划分但在动态场景里更新麻烦K-D 树是切平面划分对静态场景的光线追踪效果很好但构建和更新更复杂也不容易直接用于碰撞检测。相对而言BVH 的构建简单遍历高效稍微动点心思就能同时服务光线求交和碰撞检测两个需求所以我推荐先用 BVH 入门。结构构建复杂度光线求交适合度碰撞检测适合度动态场景友好度均匀网格低中中中八叉树中中中低K-D 树高高低低BVH中高高中这个对比不是绝对的工程里有很多混合方案但单论“一套结构通吃光线与碰撞”BVH 是我个人最推荐的选择。2. 基础功底AABB 与节点数据结构设计2.1 为什么用 AABB 而不是球体或 OBBBVH 里的包围体最常见的是 AABBAxis-Aligned Bounding Box轴对齐包围盒也就是每条边分别平行于 X、Y、Z 轴的六面体。它只需要存两个三维向量min 和 max占内存极小。更关键的是光线与 AABB 的相交测试可以分解成三个独立维度上的区间判断计算量非常低几乎没有分支也能实现得很好。球体包围盒更快但球体对细长三角形族拟合很差一个长条地形用球体包空余体积极大剪枝效果骤减。OBB有向包围盒拟合更紧但要存旋转矩阵相交测试复杂很多。AABB 处在“拟合度可以接受、计算速度极快”的最佳平衡点所以 BVH 节点里几乎都是用 AABB。2.2 C 内存布局别把节点搞成对象写 BVH 的时候最容易犯的错是把每个节点定义成一个包含std::vector、std::shared_ptr子节点的高层类。树结构没问题但性能会非常难看因为每一次递归都要解引用指针缓存命中率极低。现代 CPU 做光线遍历时瓶颈很多时候不在浮点运算而在内存访问。我实际使用的方案是用一个扁平的std::vectorBVHNode存所有节点节点通过数组下标互相引用不存指针。这样所有节点在内存里是连续的遍历时按顺序访问缓存友好度直接上一个档次。节点大小也需要注意。AABB 占了 6 个 float就是 24 字节再加上左右孩子索引或者叶子信息很容易到 32 字节或 40 字节。这里有个经验值把节点对齐到 32 字节正好对应常见的缓存行对齐遍历时会非常舒服。2.3 一套够用的 C 数据结构骨架先给出最基础的向量与光线定义。为了代码简洁我用了一个简化版的三维向量实际项目里可以直接换成 glm 或自研的 SIMD 向量库。struct Vec3 { float x, y, z; Vec3 operator(const Vec3 b) const { return {x b.x, y b.y, z b.z}; } Vec3 operator-(const Vec3 b) const { return {x - b.x, y - b.y, z - b.z}; } Vec3 operator*(float s) const { return {x * s, y * s, z * s}; } float operator[](int i) const { return i 0 ? x : (i 1 ? y : z); } float operator[](int i) { return i 0 ? x : (i 1 ? y : z); } }; struct AABB { Vec3 min; Vec3 max; }; struct Ray { Vec3 origin; Vec3 direction; Vec3 invDir; // 1 / direction提前算好除以三的代价 };然后是 BVH 节点。我把内部节点和叶子节点放在同一个结构体里用isLeaf()区分。内部节点用left和right存两个子节点的数组下标叶子节点用primStart和primCount指向图元索引数组的一段连续区间。struct BVHNode { Vec3 bboxMin; Vec3 bboxMax; union { struct { int left; // 内部节点左孩子下标 int right; // 内部节点右孩子下标 }; struct { int primStart; // 叶子节点图元起点 int primCount; // 叶子节点图元数量 }; }; bool isLeaf() const { return right 0; // 约定右孩子为负数表示叶子 } };这里的技巧是内部节点的right一定是非负下标叶子节点里我把right置成负数同时复用内存存放primCount。这样每个节点只占用 8 个 float 的空间最小化内存占用。再加上一个std::vectorint primIndices存所有图元索引构建时不断对索引做分区实际三角形数据保持不动避免频繁拷贝三角形本身。光线在生成时提前算好invDir可以避免遍历时每个节点都做三次除法。除法是昂贵的运算光线数量百万级节点访问千万级这个提前计算收益非常明显。3. 构建 BVH从简单分割到 SAH 的进阶之路3.1 最容易理解的中点分割构建 BVH 最简单的方式是算出所有三角形的包围盒取包围盒中心作为参考点沿着最长轴把三角形分成左右两组左边中心小于中点右边大于中点然后递归构建。这个方案叫中点分割midpoint partitioning。优点是好写三十分钟能跑通一版。缺点是它完全不管三角形的空间分布。假设有一堆三角形挤在包围盒的左下角另一半空间只有一个三角形中点分割还是会把它们按中心一刀切结果造成两个子树包围盒大量重叠光线遍历时两边都可能要进去测剪枝效果大打折扣。类似的情况在真实场景里并不少见——一个角色模型堆积在原点附近周围散落几个道具就是典型的非均匀分布。3.2 为什么用 SAH把“代价”变成数学函数SAHSurface Area Heuristic表面积启发式是解决非均匀分布的主流方案。它的核心思想是把光线穿过某个节点的概率近似看作这个节点包围盒的表面积占整个场景包围盒表面积的比例。基于这个假设可以写出一个估计递归求交成本的公式。假设一个内部节点左右两个子包围盒的表面积分别是 A(L) 和 A(R)对应三角形数量是 N(L) 和 N(R)父节点包围盒表面积为 A(P)单次三角形求交成本和单次 AABB 求交成本都是常数。那么光线经过这个内部节点的期望求交成本 C 可以近似为C 1 A(L)/A(P) * N(L) A(R)/A(P) * N(R)构建的时候我们尝试不同的分割方案选成本最小的那个。这个公式里A(L)/A(P)可以理解为“光线进入父节点的前提下也进入左子节点的概率”。三角形多的子树即使表面积大也未必是坏事因为 SAH 会自动在“盒子大小”和“盒子里的三角形数量”之间找平衡。3.3 基于 Binning 的 SAH 构建如果每层构建都对所有三角形按每个可能的切割位置做一次计算复杂度会非常高。工程上常用的是“分桶 SAHbinned SAH”把三角形的质心沿某个轴分成固定数量的桶我常用 16 个每个桶统计三角形数量和包围盒然后枚举相邻桶之间作为切割点计算 SAH 成本。这样切割点数量从三角形数量降到了桶数量构建速度飞快质量损失却很小。下面是一个简化但能直接跑通的核心构建逻辑int BVH::build(int* primIndices, int first, int count) { if (count leafSize) { BVHNode node; node.bboxMin computeBounds(primIndices, first, count).min; node.bboxMax computeBounds(primIndices, first, count).max; node.primStart first; node.primCount count; node.right -1; nodes.push_back(node); return (int)nodes.size() - 1; } AABB overallBounds computeBounds(primIndices, first, count); int bestAxis 0; int bestSplit first count / 2; // 默认用中点防止退化 float bestCost FLT_MAX; // 对三个轴分别做分桶 SAH for (int axis 0; axis 3; axis) { float bucketMin[16], bucketMax[16]; int bucketCount[16]; // 把三角形质心映射到 [0,15] 的桶号 for (int i 0; i 16; i) { bucketMin[i] FLT_MAX; bucketMax[i] -FLT_MAX; bucketCount[i] 0; } for (int i first; i first count; i) { Vec3 centroid computeCentroid(primIndices[i]); float t (centroid[axis] - overallBounds.min[axis]) / (overallBounds.max[axis] - overallBounds.min[axis] 1e-6f); int bucket (int)(t * 16.0f); if (bucket 0) bucket 0; if (bucket 16) bucket 15; // 更新对应桶的包围盒和计数 } // 从左到右扫描维护前缀包围盒和数量计算每个切割点成本 AABB leftBox[16], rightBox[16]; int leftCount[16], rightCount[16]; // 具体扫描我这里略过就是反复合并包围盒与累加计数 // 每一刀的位置 k 表示 [0, k] 去左边[k1, 15] 去右边 for (int k 0; k 15; k) { float cost 1.0f leftBox[k].surfaceArea() / overallBounds.surfaceArea() * leftCount[k] rightBox[k].surfaceArea() / overallBounds.surfaceArea() * rightCount[k]; if (cost bestCost) { bestCost cost; bestAxis axis; // 记录该轴该切法对应的实际三角形分界位置 } } } // 按 bestAxis 重新分区这里使用 std::partition 按质心切到最佳切割点 int mid partitionByAxis(primIndices, first, first count, bestAxis, overallBounds, bestSplit); int leftChild build(primIndices, first, mid - first); int rightChild build(primIndices, mid, first count - mid); BVHNode parent; parent.bboxMin min(nodes[leftChild].bboxMin, nodes[rightChild].bboxMin); parent.bboxMax max(nodes[leftChild].bboxMax, nodes[rightChild].bboxMax); parent.left leftChild; parent.right rightChild; nodes.push_back(parent); return (int)nodes.size() - 1; }这段代码里我刻意省略了不少细节只保留了骨架但两个重要细节值得单独说明。第一个是叶子大小leafSize。太小会导致树太深、节点过多内存和遍历开销增大太大会让叶子里的三角形求交变成小规模暴力循环。我测试下来leafSize 4到8之间表现最好具体数值和场景、三角形大小有关建议做一个参数跑实验。第二个是bestSplit的记录问题。用分桶 SAH 时我们已经在桶的粒度上找到了最佳切割位置但桶是一个近似区间真正切分数组时我们要把质心落在左边桶的三角形放到左边落在右边桶的放到右边。实际实现里我会把最佳切割点精确到“某个桶之后”然后用std::partition按桶号去划分而不是把质心坐标重新计算一遍。构建完之后我习惯做一次“节点合法性检查”作为调试断言每个内部节点的左右包围盒都被父包围盒包含每个叶子节点的三角形确实都落在自身包围盒内。这个检查在 Debug 版本里跑一遍能帮你躲过很多隐蔽的构建 bug。3.4 构建阶段的两个常见问题包围盒退化怎么办当很多三角形质心完全相同或者某个轴方向的最小最大范围接近零分桶时会出现分母为零或桶号全挤到同一个桶的情况。我处理的办法是给分母加一个极小量如果整个包围盒三个轴的范围本来就接近零就直接退化成叶子节点不再往下分避免进入死循环。排序还是分区std::sort会带来 O(N log N) 复杂度而构建 BVH 只需要把所有元素按某个中间位置分成两边不需要完全有序。所以要用std::partition它是 O(N)整个构建复杂度能降到 O(N log N) 以下场景大时差距非常明显。4. 光线求交遍历 BVH 的正确打开方式4.1 slab 光线-包围盒相交测试光线与 AABB 的求交最经典的方法是 Slab Method。核心思路是把 AABB 看成三对平行平面形成的“薄片”的交集光线分别计算进入和离开每一对平面的参数 t 值再取三组区间的交集。具体公式是t0 (bboxMin - ray.origin) / ray.direction t1 (bboxMax - ray.origin) / ray.direction如果方向分量是负的t0 和 t1 恰好会交换。所以我们先对两个值取最小和最大然后用三个轴上的最小值取最大三个轴的最大值取最小最后比较这两个值。区间交集的逻辑就是光线必须在所有轴上都处于盒子内部才算穿过了盒子。bool intersectAABB(const Ray ray, const AABB box, float tEnter, float tExit) { float t0 0.0f; float t1 1e30f; for (int i 0; i 3; i) { float invDir ray.invDir[i]; float origin ray.origin[i]; float a (box.min[i] - origin) * invDir; float b (box.max[i] - origin) * invDir; if (invDir 0.0f) std::swap(a, b); t0 std::max(t0, a); t1 std::min(t1, b); if (t0 t1) return false; } tEnter t0; tExit t1; return t1 0.0f; }这里有个容易踩的坑光线方向某个分量为 0 时invDir是无穷大box.min 和 origin 相等时会出现0 * inf NaN。很多实现会用if (a ! a) return false之类的 NaN 检测来规避但我在实际代码里更推荐显式处理当方向分量接近 0 时如果 origin 落在盒子范围内就把这个轴向的区间设成全程有效否则直接判定不相交。这样可以避免 NaN 带来的不确定行为。4.2 自顶向下遍历显式栈代替递归BVH 遍历如果写成递归每访问一层都要压栈树深几十层时虽然没问题但函数调用开销存在而且 Debug 模式下递归栈会变得很深慢场景下甚至可能爆栈。我在工程实现里统一用显式栈。核心流程是从根节点开始把根节点压栈每次从栈里弹出一个节点先和光线做 AABB 求交。如果不相交或者求交得到的 t 值已经大于当前已知最近命中距离说明这个子树里不可能有更近的三角形直接跳过。如果是叶子节点就遍历它包含的三角形更新最近命中距离如果是内部节点则计算两个子节点的相交情况决定压栈顺序。bool BVH::intersect(const Ray ray, float tHit, int hitPrimIndex) { tHit 1e30f; int stack[64]; int stackPtr 0; stack[stackPtr] rootIndex; while (stackPtr 0) { int nodeIndex stack[--stackPtr]; const BVHNode node nodes[nodeIndex]; float tEnter, tExit; if (!intersectAABB(ray, node, tEnter, tExit) || tEnter tHit) { continue; } if (node.isLeaf()) { for (int i node.primStart; i node.primStart node.primCount; i) { int primIdx primIndices[i]; float t; if (intersectTriangle(ray, primIdx, t) t tHit) { tHit t; hitPrimIndex primIdx; } } } else { int leftIdx node.left; int rightIdx node.right; float tLeftEnter, tLeftExit; float tRightEnter, tRightExit; bool hitLeft intersectAABB(ray, nodes[leftIdx], tLeftEnter, tLeftExit); bool hitRight intersectAABB(ray, nodes[rightIdx], tRightEnter, tRightExit); if (hitLeft hitRight) { // 先访问近的子树提升提前命中概率 if (tLeftEnter tRightEnter) { stack[stackPtr] rightIdx; stack[stackPtr] leftIdx; } else { stack[stackPtr] leftIdx; stack[stackPtr] rightIdx; } } else if (hitLeft) { stack[stackPtr] leftIdx; } else if (hitRight) { stack[stackPtr] rightIdx; } } } return tHit 1e29f; }这个遍历版本的精髓有两个地方。第一是先访问近的子树。注意我是先把远的子节点压栈再把近的子节点压栈这样弹栈时先弹出来的是近的那个。先处理近处的子树可以更快拿到一个较小的 tHit后面的远子树即使被访问到也会因为tEnter tHit的条件被快速跳过。第二是栈大小。64层的栈对于绝大多数场景够用了。BVH 是二叉树理想深度是 log2(N) 量级百万三角形大概 20 层64 已经很保守。但如果树构建质量差深度可能异常增大建议加一个栈溢出计数器Debug 版本里如果发现深度超过 64就回退去检查构建逻辑。4.3 叶子处三角形求交的衔接当我找到一个可能命中的三角形时我用的是经典的 Moeller-Trumbore 算法。这里不打算展开他的数学推导只提一个与 BVH 遍历配合的关键点三角形求交得到的 t 值必须和当前全局的tHit做比较。很多初版实现会忘记这个比较导致明明是后面更近的三角形已经被跳过却返回了一个更远的三角形。另一个技巧是在遍历过程中如果tEnter已经大于tHit就提前跳过整个节点这本质上是把“先访问近节点”和“全局剪枝”结合在一起。实践中这一步能挡掉大量无效的三角形求交特别是在遮挡比较严重的场景里收益极其明显。4.4 遍历性能的其他尝试遍历部分我能再给几个优化方向但从性价比角度排序我最推荐先做好前面几项再考虑 SIMD 和 GPU 化。把Ray里的invDir用 4 分量浮点存配合 SIMD 做 4 路光线同时遍历。这个改动量大但效果非常显著。叶子节点里如果三角形数量少直接手写内联循环。现代编译器会帮忙展开但你要保证三角形求交函数是inline的。如果场景大多是静态模型可以把 BVH 节点按 DFS 顺序重新排列让相邻节点在内存中尽量连续提高缓存命中率。5. 从光线求交到碰撞检测BVH 的另一半江山5.1 对象与对象的碰撞两个 BVH 的递归重叠碰撞检测和光线求交本质上是同一个问题的两种变体光线求交是“一维查询对象”碰撞检测是“三维区域查询对象”。当我们要检测两个物体是否碰撞时最直接的办法是同时遍历两个物体的 BVH比较两个节点包围盒是否重叠。基本流程是准备一个栈初始放入两个根节点的索引对。弹出一对节点先判断两个节点 AABB 是否重叠。不重叠就跳过重叠了如果两边都是叶子节点则进入三角形级别的三角形-三角形相交测试如果有一边或两边是内部节点则把可能的子节点组合继续压栈。bool BVH::overlap(const BVH a, const BVH b) { struct NodePair { int aIdx; int bIdx; }; NodePair stack[128]; int stackPtr 0; stack[stackPtr] {a.rootIndex, b.rootIndex}; while (stackPtr 0) { NodePair pair stack[--stackPtr]; const BVHNode na a.nodes[pair.aIdx]; const BVHNode nb b.nodes[pair.bIdx]; if (!overlapAABB(na, nb)) continue; bool aLeaf na.isLeaf(); bool bLeaf nb.isLeaf(); if (aLeaf bLeaf) { for (int i na.primStart; i na.primStart na.primCount; i) { for (int j nb.primStart; j nb.primStart nb.primCount; j) { if (triangleIntersectTriangle(a.prims[primIndices[i]], b.prims[primIndices[j]])) { return true; } } } } else { // 展开非叶节点把子节点组合压栈 if (aLeaf) { stack[stackPtr] {pair.aIdx, nb.left}; stack[stackPtr] {pair.aIdx, nb.right}; } else if (bLeaf) { stack[stackPtr] {na.left, pair.bIdx}; stack[stackPtr] {na.right, pair.bIdx}; } else { stack[stackPtr] {na.left, nb.left}; stack[stackPtr] {na.left, nb.right}; stack[stackPtr] {na.right, nb.left}; stack[stackPtr] {na.right, nb.right}; } } } return false; }这套代码的逻辑不复杂但要注意一个细节当两个叶子重叠时需要做三角形-三角形精确碰撞这个测试本身也不便宜所以前面几层的包围盒粗筛越严格精确测试的调用次数就越少。这又回到了 BVH 构建质量的重要性。5.2 动态场景重建与 Refit 的取舍静态场景里 BVH 表现无懈可击但游戏和物理模拟里三角形经常动这时就要面临一个选择每帧重建 BVH还是只更新包围盒。重建rebuild的意思是每一帧重新运行整个构建流程。优点是树的质量始终保持最优缺点是构建开销可能占掉整个 CPU 预算的很大一块。对于几万个三角形的小型场景重建很快可以接受几百万三角形的大型场景每帧重建直接卡死。Refit 的意思是只更新节点包围盒不改变树结构。先更新叶子节点把三角形的新位置重新算盒范围然后从叶子向根逐层重新合并父节点包围盒。这个操作非常快遍历速度也能维持不错的水平但随着物体移动初始分割可能不再合理包围盒会变得松散树的质量逐渐下降。我个人的实践建议是如果场景里三角形位移不大优先用 refit如果物体发生了大规模形变比如布料从平面变成团状就直接重建。也可以做混合策略先 refit隔几十帧或者当 refit 后的遍历耗时超过阈值时触发一次全局重建。这个阈值需要根据项目实际场景调但思路很实用。策略构建速度遍历速度实现复杂度适用场景重建慢高中静态场景、大规模变形Refit非常快中低小范围移动、实时游戏5.3 宽阶段和窄阶段BVH 在碰撞管线里的位置实际碰撞系统通常是两阶段架构。宽阶段负责快速排除不可能碰撞的物体对引擎里常用 Sweep and Prune 或网格用的也是“先测大包围盒”的思路。窄阶段才做三角形级别的精确碰撞。BVH 在这套架构里的角色很灵活。小型项目可以只用 BVH 同时扮演宽阶段和窄阶段物体的根节点就是它的粗包围体叶子节点就是三角形。大型项目里宽阶段用其他更适合动态物体排序的算法窄阶段再对每个物体内部使用 BVH 做自碰撞或物体对碰撞。以布料模拟为例布料的顶点数量很大且会连续形变做自碰撞检测时就非常依赖每帧 refit 后的 BVH否则一针一线的穿透判断会变成 O(N^2) 的地狱。碰撞检测里的浮点问题也值得多说一句。两个物体如果处于刚好接触的状态三角形求交测试会因为浮点误差出现“时而相交、时而不相交”的抖动表现为物体微微颤动。工程上常见的解法是在求交时给距离阈值设一个极小偏移量比如 1e-4 或 1e-5 级别的宽容度把“刚好贴在一起”的情况当成接触处理。这样会牺牲一点点精度但换来的稳定性对游戏和物理系统非常重要。6. 调试与性能实测从“能跑”到“跑得快”6.1 验证 BVH 是否正确我见过太多人写完了 BVH跑出来的图看起来也正常就以为万事大吉。但其实很多细微 bug 只有当场景特别复杂时才会突然爆发比如阴影中少了一小块、碰撞时偶尔穿透。所以我会在开发阶段做三层验证。第一层是视觉验证。写一个独立渲染模式把所有 BVH 节点的 AABB 以线框形式画出来叠加在场景上。你一眼就能看出树结构是否合理包围盒之间重叠是否严重叶子大小是否均匀有没有某些节点盒子巨大但只包了一个三角形。第二层是数值验证。拿一张低分辨率图逐像素对比暴力遍历和 BVH 遍历的命中结果要求每个像素命中的三角形索引和 t 值完全一致。这个对比只需要小场景跑一遍就能筛出遍历逻辑里的排序、剪枝错误。第三层是随机光线测试。随机发射大量光线对比暴力结果和 BVH 结果既能验证正确性又能顺便统计每个节点的命中次数帮助定位性能瓶颈。6.2 性能分析的实用经验性能优化不能靠感觉。我常用的手段是在遍历代码里插入轻量计数器分别统计 AABB 求交次数、三角形求交次数和最终命中次数。理想状态下三角形求交次数应该远小于 AABB 求交次数AABB 求交次数又远小于暴力情况下的三角形求交次数。如果发现 AABB 求交次数异常多大概率是构建质量差导致包围盒重叠严重。实测时我还会看两个指标阴影光线和主光线的耗时差异。主光线通常能很快找到近处命中然后 tHit 剪枝生效阴影光线则常常在确定“被遮挡”后立刻返回所以二者耗时差异能反映树的剪枝效率。如果阴影光线平均耗时还很高通常说明包围盒重叠太多或者叶子太大。下面这个表是我一个小型测试场景里记录的耗时分布三角形数量 128 万主光线 1024x768。数据不具备普适性但可以看出大致比例关系。阶段耗时占比备注BVH 构建一次3.8%构建时间占比很低主光线遍历28.5%大部分时间在 AABB 求交与三角形求交阴影光线遍历31.2%遮挡判断大量触发提前返回着色与像素写入23.4%非加速结构相关其他开销13.1%相机、内存分配等看到这个比例我的第一反应往往不是继续优化遍历而是先看三角形求交函数是否足够快。因为三角形求交才是真正的浮点重活AABB 再怎么优化也只是多挡几下。6.3 我踩过的坑清单这里列几个我在实际编码里真实遇到过、而且排查很久的问题给你提个醒。未更新全局 tHit这个最隐蔽。光线穿过了多个三角形如果叶子处理时没把最近命中距离写回后续叶子就会用初始的极大值去遍历导致远处三角形也能被当作最近命中。我一度因为这个问题看到了极其诡异的“半透明物体遮挡不准确”效果。零方向分量的 NaN 传播光线平行于某个轴时invDir 是无穷大和 box 边界做乘加会得到 NaN。我强烈建议在 Ray 构造时显式处理方向分量接近零的情况把 invDir 对应分量设成一个极大值而不是直接除零。栈溢出显式栈设为固定大小时如果场景三角形分布极度不均树可能变得很深。解决方法是加边界检查Debug 模式下越界直接抛断言不要等到内存爆炸再查。SAH 分母为零三角形质心范围在一个轴上是零时分桶计算会出现除零。加一个小 epsilon 通常是够用的。图元索引顺序改变构建时我用了std::partition不断重排primIndices如果之后叶子节点的primStart和primCount算错了会把别的三角形索引当成自己的画面上的表现是随机若干三角形消失或出现错误交点。建议构建结束后把每个叶子对应的原始三角形索引打印出来和暴力遍历做一轮严格比对。最后再说两句BVH 这个东西原理说起来不复杂但真正把它做到又快又稳需要投入不少时间在数据布局、构建策略和遍历细节上。我在最初实现时以为写完构建和遍历就结束了后来调试过程里才发现大量时间其实花在验证正确性和优化内存访问上。不过这些投入完全值得因为同样的结构稍微改一改就能服务于光线追踪和碰撞检测两个系统。如果你正在写自己的渲染器或物理引擎我建议第一版不要急着上 SAH 和分桶这类优化先用中点分割把完整结构跑通再用暴力遍历做结果对照最后逐步替换成 SAH 构建并引入性能计数器。一步一步来你会对树的构建质量和遍历速度之间的关系有特别直观的感受。