Scene graph: Encyclopedia II - Scene graph - Scene-graph and Bounding Volume Hierarchies BVHs

Scene graph - Scene-graph and Bounding Volume Hierarchies BVHs

Bounding Volume Hierarchies (BVHs) are useful for numerous tasks - including efficient culling and speeding up collision detection between objects. A BVH is a spatial structure but doesn't have to partition the geometry (see spatial partitioning, below).

A BVH is a tree of bounding volumes (often spheres, AABBs or/and OBBs). At the bottom of the hierarchy the size of the volume is just large enough to encompass a single object tightly (or possibly even some smaller fraction of an object in high resolution BVHs), as you walk up the hierarchy each node has its own volume which tightly encompasses all the volumes beneath it. At the root of the tree is a volume that encompasses all the volumes in the tree (the whole scene).

BVHs are useful for speeding up collision detection between objects. If an object's bounding volume does not intersect a volume higher in the tree then it cannot intersect any object below that node (so they are all rejected very quickly).

Obviously there are some similarities between BVHs and scene-graphs. A scene-graph can easily be adapted to include/become a BVH - if each node has a volume associated or there's purpose built 'bound node' added in at convenient location in the hierarchy. This may not be the typical view of scene-graph but there are benefits to including a BVH in a scene-graph.

Adapted from the Wikipedia article "Scene-graph and Bounding Volume Hierarchies BVHs", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki