~/imallett (Ian Mallett)

Summary and Hierarchy of Acceleration Datastructures
by Ian Mallett

Keeping all the acceleration datastructures' relative relation to each other is difficult, so I've devised this tree which shows their hierarchy and gives a brief summary of each. Primarily, this list is concerned with graphics-related spatial acceleration datastructures and aims to be exhaustive. If I've left out a structure or organized something incorrectly, do let me know.

• Acceleration Data Structures:
• Regular Grid: The space is divided into a regular grid.
• BSP (Binary Space Partitioning) Trees: Subdivide the space using arbitrary hyperplanes.
• Quadtrees/Octrees: Similar in spirit to (and so often confused with) K-D Trees. Divides space along every axis of the space simultaneously, and divisions are bisections.
• BVHes (Bounding Volume Hierarchies): A hierarchy of bounding volumes. Each node comprises a bounding volume and a list of children, such that the node's children are bounded by the node's bounding volume. Axis-aligned bounding boxes for the bounding volumes is common, as is restricting to having only two children.
• M-Tree: An interesting datastructure I don't know much about. Appears to build some tree structure using a distance metric directly.

Some additional datastructures I didn't have time to look at. R-Trees (including Hilbert R-Trees, R+ Trees, R*-Trees, and X-Trees) seem to be similar to BVHes, but used for non-graphics applications. If that presumption is incorrect, let me know how they apply to graphics. B-Trees (including B+ Trees, B*-Trees, and UB-Trees) seem to be generalizations of Binary Search Trees to multiple children.

I would appreciate some help parsing all the various BVH variants!