目录 (12)
掌握 BVH 和 BVTT(文章由 AI 撰写和编辑)
1. 为什么有必要这样做?—— O(n²) 壁
假设一个 3D 场景中有 1000 个物体。要检查每一帧“这些物体是否相互碰撞?”,你只需要检查每一对物体即可。
for A in objects: for B in objects: if A != B: check_collision(A, B)这种暴力搜索方法的复杂度为O(n²) 。对于 1000 个对象,大约需要50 万次检查;对于 1 万个对象,则需要5000 万次检查。在 60fps 的游戏中,每帧都需要重复此操作。显然,这种方法并不实用。
该解决方案的核心思想是,“完全不检查不可能重叠的对象”。
这里起作用的是边界体积(BB)和BVH 。
2. 边界体积 (BB) — 为速度牺牲精度
直接使用复杂的网格形状进行碰撞检测成本太高。因此,我们使用包围物体的简单几何形状来检测碰撞。

上图是一个边界框模型的示例。

最常用的是轴对齐包围盒 (AABB) 。它是一个简单的矩形棱柱,与世界坐标轴对齐。检查两个 AABB 是否重叠只需对每个轴进行六次比较即可完成。虽然速度很快,但对于旋转物体来说,这种方法会造成更多浪费。因此,您可以使用可以旋转轴的包围盒,例如 OBB。
3. BVH——按层级划分空间
仅使用包围盒仍然不够。虽然它简化了碰撞检测,但仍然需要检查每个物体。这就像在游戏中需要遍历场景中的每个物体一样。包围盒层次结构 (BVH)将这些物体分组到一个二叉树结构中,从而允许“如果子物体与父物体不重叠,则跳过整个子物体”。

BVH节点结构
struct BVHNode: aabb: AABB // 此节点周围的边界框 left: BVHNode // 左子节点(如果为空则为叶子节点) right: BVHNode // 右子节点(如果为空则为叶子节点) object: Object // 仅当它是叶节点时有效BVH 构造(自顶向下、递归划分)- 中值划分
function buildBVH(objects): node.aabb = computeAABB(objects) // 一个包裹住整个物体的盒子 if len(objects) == 1: node.object = objects[0] // 叶节点 return node axis = longestAxis(node.aabb) // 沿最长轴(物体最长的方向)分割 sorted = sortByAxis(objects, axis) mid = len(sorted) / 2 node.left = buildBVH(sorted[:mid]) node.right = buildBVH(sorted[mid:]) return node射线交叉搜索 - 利用 SAH 分区
function rayIntersect(node, ray): if not intersects(node.aabb, ray): return null // 跳过整个子树 if isLeaf(node): return preciseIntersect(node.object, ray) hitLeft = rayIntersect(node.left, ray) hitRight = rayIntersect(node.right, ray) return closest(hitLeft, hitRight)SAH(表面积启发式算法) :它并非简单地按中值划分区域,而是基于每个候选划分区域的表面积比来计算估计的搜索成本,从而选择最有效的划分轴。据说它对光线追踪引擎至关重要。下图展示了按中值划分区域和按 SAH 划分区域之间的区别。

4. BVTT — 同时下降两个 BVH
仅使用 BVH,您可以找出“光线击中了哪个物体”。但是,如果您想查找两个复杂物体之间的碰撞,例如“角色 A 是否与角色 B 发生碰撞?” ,情况就有所不同了。
当每个对象都有自己的 BVH 时, BVTT(边界体积遍历树)会递归地同时遍历两个 BVH,以缩小碰撞对的范围。

BVTT巡回赛
function traverseBVTT(nodeA, nodeB, results): // 如果两个节点的 AABB 不重叠,则跳过整个节点对。 if not overlaps(nodeA.aabb, nodeB.aabb): return // 两者都在叶片表面进行精确碰撞测试。 if isLeaf(nodeA) and isLeaf(nodeB): results.add(preciseCheck(nodeA.object, nodeB.object)) return // 先拆分较大的节点(最小化成本) if volume(nodeA) >= volume(nodeB): traverseBVTT(nodeA.left, nodeB, results) traverseBVTT(nodeA.right, nodeB, results) else: traverseBVTT(nodeA, nodeB.left, results) traverseBVTT(nodeA, nodeB.right, results)关键点很简单。如果两个节点的轴对齐包围盒(AABB)不重叠,它们的子节点对就永远不会发生碰撞。这就是为什么整个子树会被剪枝的原因。复杂度变为O(log n · log m) 。
5. BVH 和 BVTT 的总结

在实际应用中,两者通常结合使用。场景范围的BVH用于识别“碰撞候选对”(宽阶段),对于这些候选对,使用BVTT精确检查每个对象的BVH(窄阶段)。
6. 在实际发动机中
- Unity 物理/PhysX :宽阶段使用场景 BVH(DBVT),窄阶段使用每个对象的凸包 BVH
- Unreal Engine :`FBVHTree` 类管理 BVH,`FChaosPhysics` 收集基于 BVTT 的碰撞对。
-光线追踪(DXR、NVIDIA OptiX) :GPU加速的BVH探索,由RTX BVH硬件单元处理
- FCL(灵活碰撞库) :开源机器人/仿真库,提供基于 BVTT 的碰撞查询
结束
BVH 和 BVTT 本质上是同一核心思想的两种应用: “尽早舍弃不重叠空间”。如果说 BVH 解决了场景和光线之间的问题,那么 BVTT 则将这一思想扩展到了两个复杂物体之间的问题。

上图是我使用 VTK 渲染的,用于突出显示多个物体之间的交点。我利用 VTK 实现了即使数据发生变化也能快速重新渲染。最初,我的想法很简单,重叠顶点就足够了,但仔细想想,这变得复杂起来,因为碰撞只发生在面相交的时候。所以,在寻找快速找到碰撞点的方法时,我最终开始研究 BVH 和 BVTT。
