Bounding volume hierarchies (BVHs) were popularized in the ray tracing community by Goldsmith and Salmon in their 1987 paper Automatic Creation of Object Hierarchies for Ray Tracing. In 1988, Eric Haines followed with an article in the Ray Tracing News providing an excellent explanation of creating near optimal bounding volume hierarchies given a list of objects, based on Goldsmith and Salmon's paper.
Two decades later, there is still significant interest in BVHs. In 2006, Lauterbach et al. published RT-DEFORM: Interactive Ray Tracing of Dynamic Scenes using BVHs and in 2007, Eisemann et al. published Automatic Creation of Object Hierarchies for Ray Tracing of Dynamic Scenes. Both of these papers describe using BVHs to reduce the number of intersections calculated per ray for ray tracing dynamic scenes, i.e. scenes with moving objects.
Point Break doesn't care much about ray tracing but it cares a lot about efficiently rendering dynamic scenes which led me to these ray tracing papers. Besides being useful for ray tracing, BVHs are useful for hierarchical view frustum culling. The intersection algorithm is basically the same; just replace the ray/sphere test with a frustum/sphere test. Primitives use BVHs for this purpose.
Although there is a lot of literature on inserting objects into a BVH and updating objects in a BVH, there isn't much in the way of deleting objects from a BVH. This may be because some approaches to the problem are straightforward or because many application don't need to delete objects from BVHs; they just delete the whole BVH. Point Break needs to delete objects from BVHs. In some cases, deletion from a BVH is done in response to a GUI action such as hiding latitude/longitude lines or turning off the ground track or a model representing a satellite.
Deletion Algorithm
I will present a method to delete objects from a BVH that takes advantage of the objects' spatial locality and typically does not require an O(n) tree traversal to cleanup afterwards. Deletion is expected log(n). With good spatial locality, many deletions will be constant time. Deletions are batched and cleaned in a pass with a run-time proportional to the number of dirty nodes. Although the tree is cleaned up (bounding volumes are recomputed, interior nodes are deleted or merged), it is still susceptible to becoming less optimal over time. Both Lauterbach and Eisemann present criterion to determine when a BVH, or one of its sub-trees, has degraded to the point that it should be rebuilt.
