= Solution
A <bounding volume hierarchy> is a <tree> whose leaves contain geometric primitives, here <triangles>, and whose internal nodes store cheap-to-test <bounding volumes> containing all descendant geometry. A <bounding volume> may be an <axis-aligned bounding box> or a <sphere>. The key containment guarantee is
$$
\boxed{\text{ray misses a node's bounding volume}\Rightarrow\text{ray misses every triangle below that node}.}
$$
Traverse from the root. Reject a whole subtree when its <bounding volume> is missed; otherwise visit its children and perform the full <ray-triangle intersection> test only at surviving leaves. Hitting a <bounding volume> is only permission to investigate, not evidence of hitting an enclosed <triangle>.
For nearest-hit queries, visit the nearer child first and keep the current nearest parameter. A second child whose volume begins farther away than this parameter can be pruned. For a <shadow ray>, restrict the traversal to the segment before the source and terminate at any blocker.
A flat list of $N$ <triangles> needs up to $N$ detailed tests per primary <ray> or <shadow ray>. A well-built <bounding volume hierarchy> can reject large groups with a few cheap tests and substantially reduce the average work. A balanced, well-separated scene often gives traversal resembling a short root-to-leaf search, but balance alone does not guarantee logarithmic query time: extensive overlap or an unfortunate <ray> can force examination of most or all leaves. Its advantage is spatial rejection, not a universal worst-case bound.
Back to article page
