Bounding-Volume Hierarchy

A bounding volume of a set X is any set containing X. Examples of standard simple bounding volumes include the convex hull, the (smallest, axis-aligned) bounding box, and the (smallest) bounding sphere. Consider a set S of geometric primitives (e.g., polygons, spheres, cylinders, or other simple surfaces) that specify a geometric model. A hierarchy on S based on bounding volumes is called a bounding-volume tree. Formally, it is a tree in which each node a corresponds to a subset S' of S, together with an appropriate bounding volume for S', and the parent of a corresponds to a superset of S'. Depending on the design choice, the leaves of a bounding-volume tree may contain only one geometric primitive, or a collection of primitives. For QuickCD, we used ``discrete orientation polytopes'' as bounding volumes. Given a set of k vectors in 3-space, a discrete orientation polytope (or k-dop, for short) is a convex polytope all of whose k facets have outward normals from the given discrete set of k vectors. An axis-aligned bounding box is simply a special case of a k-dop for a given set of k=6 normal vectors parallel to the coordinate axes.

The following images show some levels - namely, levels 0, 1, 2, 5, and 8 - of a bounding-volume tree for a model of a WW-II aircraft. (I have received conflicting reports concerning the type of the aircraft. It seems to be a Spitfire or a Hawker Hurricane Mk IIa.) For comparison purposes, the approximations achieved by means of 6-dops (axis-aligned bounding boxes), 14-dops, 18-dops, and 26-dops are displayed for each level. Individual k-dops are colored by random colors. (Click on an image icon in order to see the full-size image. The full-size images have about 800x800 pixels.)

Level 0 of the bounding-volume trees for 6-dops, 14-dops, 18-dops, and 26-dops. (The aircraft and all dops are depicted in the same scale.)

Level 1 of the bounding-volume trees for 6-dops, 14-dops, 18-dops, and 26-dops. (The aircraft and all dops are depicted in the same scale.)

Level 2 of the bounding-volume trees for 6-dops, 14-dops, 18-dops, and 26-dops. (The aircraft and all dops are depicted in the same scale.)

Level 5 of the bounding-volume trees for 6-dops, 14-dops, 18-dops, and 26-dops. (The aircraft and all dops are depicted in the same scale.)

Level 8 of the bounding-volume trees for 6-dops, 14-dops, 18-dops, and 26-dops. (The aircraft and all dops are depicted in the same scale.)

file last modified: Wednesday, 08-Jun-2011 15:22:19 CEST
email address