Collision Detection

As noted by Kamat [Kam93], collision detection is essentially a spatial interference problem which has been studied in depth in the computational geometry and robotics fields. It involves detecting interpenetration of one object with another, and is obviously quite an expensive operation to carry out when the simulation involves large numbers of complex objects.

Various methods of collision detection have been used in animation simulation, each depending upon the type of model used to represent the objects. Moore and Wilhelms [MW88] performed collision detection on flexible surfaces modelled by triangles. Testing involved checking for penetration of each vertex point through the planes of any triangle that didn't include the vertex in question (which provided for self-intersection testing). They also presented a method of testing for collisions between convex polyhedra, based upon the 2D Cyrus--Beck clipping algorithm. Convex polyhedra can be viewed as partitioning space into two regions: inside the polyhedron, and outside the polyhedron. Collision detection is carried out by considering pairs of polyhedra, and whether representative points of one lie on the inside of the other (and vice versa).

Hahn [Hah88] also modelled objects using polygons in his rigid body simulation, as did Garcia-Alonso, Serrano, and Flaquer [GASF94] and Bouma [BV93]. Collision detection consisted of checking for interpenetration of polygons.

Duff [Duf92] used interval arithmetic and recursive subdivision on objects modelled using implicit functions and constructive solid geometry (CSG), to detect collisions. Baraff [Bar90] used characteristic functions in determining penetration between curved surfaces modelled as implicit functions or parametric surfaces, and polyhedra. This involved computing extremal points using non-linear equation solvers. Interval arithmetic was also made use of by Snyder, Woodbury, Fleischer, Currin, and Barr [SWF93] in determining collisions between time-dependent curved surfaces (represented implicitly or parametrically). The equations formed for testing collision between two surfaces consisted of a contact constraint and a tangency constraint. The tangency constraint allowed faster convergence to the solutions of the equations (using the interval Newton method).

• Simulator Flow Control
• Efficient Collision Detection
  • Bounding Volumes
  • Spatial Subdivision
  • Miscellaneous Techniques
• Collision Response