A literature review of bounding volumes hierarchy focused on collision detection

Abstract

A bounding volume is a common method to simplify object representation by using the composition of geometrical shapes that enclose the object; it encapsulates complex objects by means of simple volumes and it is widely useful in collision detection applications and ray tracing for rendering algorithms. They are popular in computer graphics and computational geometry. Most popular bounding volumes are spheres, Oriented-Bounding Boxes (OBB’s), Axis-Aligned Bounding Boxes (AABB’s); moreover, the literature review includes ellipsoids, cylinders, sphere packing, sphere shells,k-DOP’s, convex hulls, cloud of points, and minimal bounding boxes, among others. A Bounding Volume Hierarchy is usually a tree in which the complete object is represented tighter fitting every level of the hierarchy. Additionally, each bounding volume as a cost associated to construction, update, and interference tests. For instance, spheres are invariant to rotation and translations, then they do not require being updated; their constructions and interference tests are more straightforward then OBB’s; however, their tightness is lower than other bounding volumes. Finally, three comparisons between two polyhedra; seven different algorithms were used, of which five are public libraries for collision detection.