Object subdivision

Object subdivision methods traverse a hierarchical bounding volume tree containing the objects. Some objects are naturally hierarchical; but often the bounding hierarchy must be constructed, typically at a cost in $O(n\lg n)$. The hierarchy is extended upward until there are a small number of top-level objects.

Collision detection begins at this top level. If no top-level bounding volumes intersect, the algorithm is finished; otherwise the next level bounding boxes for the offending objects are examined. The process recursively descends the object tree wherever needed until the lowest level is reached, when the algorithm falls back to the simple pairwise collision detection of Section . See Figure  for an example.

Figure: Object subdivision to intersect two curves. From left to right: the curves' top-level bounding boxes overlap; so the algorithm recursively examines the curves' subsections; overlapping subsections are examined further

One major advantage of this approach is that for repeated queries on rigid objects, the hierarchical representation need only be built once. If there are few collisions, so only a few parts of the tree are examined, sublinear performance is possible.

A variety of bounding volumes have been examined in the literature. Axis-aligned bounding boxes and spheres are well known [#!Hubbard95!#]. Gottschalk et al. [#!GLM96!#] examines oriented bounding boxes; Klosowski et al. [#!KHM96!#] uses discrete-orientation polytopes ($k$-DOPs); and Krishnan et al. [#!KPLM98!#] use a higher-order bounding volume that can closely approximate curved surfaces.

For deformable objects, object subdivision schemes must rebuild the bounding volume hierarchy at each timestep. For engineering and simulation applications, this is a significant limitation.