BVH Based Methods
Bounding volume hierarchies have proven to be a very efficient data structure for rigid collision detection, and, to some extent, even for deformable objects.
One of the design choices with BV trees is the type of BV. In the past, a wealth of BV types has been explored, such as spheres (Hubbard, 1996; Palmer & Grimsdale, 1995), OBBs (Gottschalk, Lin & Manocha, 1996), DOPs (Klosowski, Held, Mitchell, Sowrizal & Zikan, 1998; Zachmann, 2009), Boxtrees (Bala, Walter & Greenberg, 2003; Zachmann, 2002), AABBs (van den Bergen, 1997; Larsen, Gottschalk, Lin & Monocha, 1999), and convex hulls (Ehmann & Lin, 2001).
Space Subdivision Methods
Another alternative are space-subdivision approaches, for instance by an octree (Kitamura, Smith, Takemura & Kishino, 1998) or a voxel grid (Mcneely, Puterbaugh & Troy, 1999). In general, non-hierarchical data structures seem to be more promising for collision detection of deformable objects (Agarwal, Basch, Guibas, Hershberger & Zhang, 2000; Fisher & Lin, 2001; Huh, Metaxas & Badler, 2001), although some geometric data structures suggest a natural BV hierarchy (Lau, Chan, Luk & Li, 2002). Deformable collision detection is not the focus of our work presented here.