Collision Detection: A Fundamental Technology for Virtual Prototyping

Collision Detection: A Fundamental Technology for Virtual Prototyping

Gabriel Zachmann (Clausthal University, Germany)
DOI: 10.4018/978-1-61520-631-5.ch003


Collision detection is one of the enabling technologies in many areas, such as virtual assembly simulation, physically-based simulation, serious games, and virtual-reality based medical training. This chapter will provide a number of techniques and algorithms that provide efficient, real-time collision detection for virtual objects. They are applicable to various kinds of objects and are easy to implement.
Chapter Preview


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.

Complete Chapter List

Search this Book: