Bounding Volume Hierarchy

BVH-vs-BVH collision detection between two triangle meshes

Testing two triangle meshes for collision by comparing every triangle of mesh $A$ against every triangle of mesh $B$ costs $O(n_A \cdot n_B)$ — fine for two triangles, hopeless for two meshes with hundreds each. The standard solution, used for example in cloth and character collision in games and in the classic OBBTree algorithm [GLM96], builds a bounding volume hierarchy (BVH) for each mesh separately, then traverses both trees at once, discarding huge groups of triangle pairs with a single box test wherever an entire branch of one mesh cannot possibly touch a branch of the other.

One tree per mesh

Each mesh gets its own tree, built once over its triangles exactly as in a single-object BVH: a leaf holds one triangle and its bounding box; an internal node's box is the union of its two children's boxes. The split axis is chosen as the one along which the triangles' centroids are spread out the most (the same heuristic used for sweep-and-prune's sweep axis and for the earlier single-mesh BVH), and the triangles are split at the median along that axis, recursively, down to individual triangles.

Traversing two trees together

The query here is "do these two meshes collide, and if so, which triangles?". Starting from the two roots, it proceeds as a walk over pairs of nodes, one from each tree:

1. Pop a pair $(n_A, n_B)$. If their boxes do not overlap, no triangle under $n_A$ can touch any triangle under $n_B$ — prune this pair outright, discarding every triangle combination below it in one step.
2. If both are leaves, run an exact triangle–triangle intersection test (2D separating-axis test: check each triangle's three edge normals as a candidate separating axis; if none of the six separates them, the triangles overlap — a fixed, small set of candidate axes, in contrast to how GJK searches for such a separation via a growing simplex).
3. Otherwise, descend into the children of whichever node is larger (by box area), keeping the other side fixed. This keeps both subtrees shrinking roughly evenly instead of always drilling into the same mesh.

Each triangle is colored by what happened to it: red means it was involved in a detected collision, yellow means it was tested exactly but found not to overlap, and its normal mesh color means the traversal never even reached it — typically the large majority of triangles, even for meshes with dozens of triangles each. Toggle "Show internal boxes" to also see which node boxes were pruned (amber) versus descended into (blue) during the same pass.

Refitting a rigid mesh needs no rebuilding

Both meshes only translate and rotate rigidly here (no deformation), so each frame the tree is kept valid the same way as a single moving object's BVH: refit every node's box bottom-up from its (now moved) children, without touching the tree's topology. Unlike a scene of independently drifting objects, a single rigid mesh's own triangles never change position relative to each other, so refitting alone keeps every box exactly as tight as a fresh top-down build would — there is no quality to lose, and hence nothing to rebuild, as long as the mesh stays rigid. This stops being true the moment a mesh actually deforms (as in a real cloth or soft-body simulation), where periodic rebuilding — or a hierarchy specifically designed to tolerate some deformation, e.g. [vdB97] — becomes necessary again.

Properties

• Far fewer triangle tests than brute force in typical (non-degenerate) configurations — compare the "Triangle tests (BVH)" and "Triangle tests (brute force)" counters directly, especially once the two meshes are far apart.
• Correct in the worst case too: if the meshes deeply interpenetrate almost everywhere, the traversal degrades towards brute force, since there is little to prune — the same caveat every hierarchical pruning method in this series shares.
• Validated live: a brute-force pass over every triangle pair runs alongside on every step purely to double-check the two methods agree; the "Colliding pairs" counts should always match.
• Generalizes beyond pairs of rigid meshes: the same two-tree traversal is how self-collision within a single deforming mesh is typically handled too (traverse the mesh's tree against itself, skipping pairs of triangles that share a vertex).

References

• [GLM96] Stefan Gottschalk, Ming C. Lin, Dinesh Manocha. OBBTree: A Hierarchical Structure for Rapid Interference Detection. In Proceedings of SIGGRAPH, 1996.
• [vdB97] Gino van den Bergen. Efficient Collision Detection of Complex Deformable Models using AABB Trees. Journal of Graphics Tools, 1997.
• [Eri04] Christer Ericson. Real-Time Collision Detection. Morgan Kaufmann, 2004.