Real-Time Collision Detection

Chapter 6

Bounding Volume Hierarchies

Wrapping objects in bounding volumes and performing tests on the bounding volumes before testing the object geometry itself can result in significant performance improvements. However, although the tests themselves have been simplified, the same number of pairwise tests are still being performed. The asymptotic time complexity remains the same and the use of bounding volumes improves the situation by a constant factor. By arranging the bounding volumes into a tree hierarchy called a bounding volume hierarchy (BVH), the time complexity can be reduced to logarithmic in the number of tests performed.

The original set of bounding volumes forms the leaf nodes of the tree that is this bounding volume hierarchy. ...