Archive for February, 2008

Deletion in Bounding Volume Hierarchies

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.


Bounding Sphere

The first maxim of improving frame rate is: the fastest way to draw an object is not to draw it. This has always been tempered with "unless determining not to draw it takes longer than drawing it." Ideally, for example, the triangles of a 3D model would not be sent to the GPU if the model were not visible. To check if each triangle of the model was visible or not would be too CPU intensive and result in a lower frame rate than always sending the model to the GPU.

Graphics applications typically create bounding spheres that encompass logical sets of triangles, such as a model. A sphere can quickly be checked for visibility. The model is drawn only if the bounding sphere is visible. Because the sphere doesn't exactly represent the 3D model, sometimes the model will be sent to the GPU even though the model isn't visible. Tighter bounding spheres reduce these false positives.

STK has always calculated bounding spheres for 3D models, terrain, et al. For Point Break, we decided to revisit our bounding spheres to see if we could calculate tighter spheres.