= Bounding volume hierarchy
{wiki}
= BVH
{c}
{synonym}
A <bounding volume hierarchy> is a <data structure> arranged as a <rooted tree>: leaves store objects, and each internal node stores a <bounding volume> enclosing its <children in a rooted tree>. Consequently, every node encloses all objects in its <subtree>. A common choice is a <binary tree> of <axis-aligned bounding boxes>. The objects assigned to sibling <subtrees> can be different even when their <bounding volumes> overlap.<Physically Based Rendering: From Theory to Implementation (4th edition) by Matt Pharr and others/7.3 Bounding Volume Hierarchies>[§7.3, opening paragraphs and Figure 7.3: leaves, descendant bounds and rejection of a subtree]{ref}
Here is an exact two-dimensional example. Use the <triangles> $A,B$ from <bounding volume>, together with $C$ having <vertices of a polygon> $(6,0),(8,0),(6,2)$ and $D$ having <vertices of a polygon> $(6,3),(8,3),(8,5)$. Group $A,B$ under $L$, and $C,D$ under $R$. Their parent <axis-aligned bounding boxes> and the box at the <root of a tree> are
$$
B_L=[0,7/2]\times[0,7/2],\qquad B_R=[6,8]\times[0,5],\qquad B_{\mathrm{root}}=[0,8]\times[0,5].
$$
The diagram shows all seven nodes. Taking the <coordinate>-wise <minimum> and <maximum> of the two child boxes constructs each parent box; the resulting box contains the <set union> of the children, and can also contain empty space between them.
\Image[/bounding-box-enclosures-and-hierarchy.png]
{title=Four exact <triangles>, their enclosing boxes, and a seven-node <bounding volume hierarchy> arranged as a <binary tree>}
{id=bounding-box-enclosures-and-hierarchy}
A <bounding volume hierarchy traversal> starts at the <root of a tree> and discards a <subtree> when its <bounding volume> misses the query. Accepted internal nodes expose their children; accepted leaves supply candidates for actual shape tests. Box2D's official <Collision: Dynamic Tree> describes <axis-aligned bounding box> region queries that return overlapping leaf boxes. A query box that bounds a different query shape can produce additional false candidates.
For the closed query <rectangle>
$$
Q=[8/5,9/5]\times[8/5,9/5],
$$
left-first <depth-first search> tests the node boxes in order: root, $L$, $A$, $B$, $R$. The first four overlap $Q$; $R$ does not, because its smallest $x$-<coordinate> is $6>9/5$. Pruning $R$ skips both $C$ and $D$. Five box tests leave two <broad phase> candidates. The <narrow phase> rejects $A$, since $x+y\geq16/5>2$ throughout $Q$, and accepts $B$: the <point> $(7/4,13/8)$ belongs to both $Q$ and $B$. There are two detailed shape tests and one true hit.
\Image[/bounding-volume-hierarchy-query-pruning.png]
{title=An exact <rectangle> query prunes the right <subtree> and leaves two box candidates but only one <triangle> hit}
{id=bounding-volume-hierarchy-query-pruning}
For a query asking for all intersections, <time complexity> depends on the number $v$ of visited nodes and the cost $T_j$ of each candidate shape test. With fixed dimension and constant bookkeeping cost per node, the work is
$$
O\!\left(v+\sum_{j=1}^{c}T_j\right),
$$
where $c$ counts candidate objects and $O$ is <Big O notation>. A balanced <binary tree> has small <height of a binary tree>, but a query can enter both children at every level. In this example a query containing $[0,8]\times[0,5]$ visits all seven nodes and tests all four <triangles>. More generally, a <full binary tree> with $n$ single-object leaves has $2n-1$ nodes, so such a query takes $O(n)$ work for constant-cost shape tests even when its <height of a binary tree> is $O(\log n)$. Listing $n$ hits itself requires $n$ outputs. Small height alone gives no unconditional logarithmic query bound.
For <collision detection> between two <bounding volume hierarchies>, traverse pairs of nodes: reject disjoint pairs of <bounding volumes>, expand a nonleaf member of an accepted pair, and apply the <narrow phase> at accepted leaf pairs. A single collection's self-query must exclude pairing an object with itself and avoid duplicate unordered pairs. If every object overlaps every other object, reporting all pairs already requires $n(n-1)/2$ results. Construction quality, empty space in boxes and the queries determine how much pruning is useful.<GPU Gems 3/Chapter 32. Broad-Phase Collision Detection with CUDA>[§32.1: the n(n−1)/2 pair baseline and worst-case quadratic broad-phase work]{ref}
For a short correctness outline, an object is enclosed by its leaf box, and each child box is enclosed by its parent box. Repeated <subset> relations carry this property to every ancestor. A true query intersection therefore prevents rejection at every ancestor of the object's leaf. Updating leaf boxes after motion also requires restoring all affected ancestor bounds before querying.
Back to article page
