Monte-Carlo collision detection

This paper presents a method for detecting collisions between objects under the hard real-time constraints of a virtual reality simulation. A list of potential collision regions is computed and updated over time, using temporal coherence to reduce the cost of this update. New samples are constantly randomly generated on every object in order to discover new interesting regions. The objects are then efficiently tested for collision using a multiresolution layered shell representation, which is locally fitted according to an evaluation of the objects' distance. Amortized algorithms allow the user to trade accuracy for speed, in order to reach real-time performances. Deformable objects and auto-collisions are handled by our algorithm without any change, with a validity that decreases with the amplitude of the deformation. We show how a multiresolution deformable object simulation can be linked with the collision detection process in order to optimize the simulation. We demonstrate our method in a context of virtual reality by simulating realistic dynamic collisions between several and possibly deformable objects, with a guaranteed frame rate. Benchmarks indicate that the method favorably compares to alternative methods, including those which are restricted to (and optimized for) rigid objects collision detection.

@TechReport\{GD04,
  author       = "Guy, St\'ephane and Debunne, Gilles",
  title        = "Monte-Carlo collision detection",
  institution  = "INRIA",
  number       = "RR-5136",
  month        = "March",
  year         = "2004",
  keywords     = "Collision Detection, Stochatic",
  url          = "http://artis.inrialpes.fr/Publications/2004/GD04"
}