Fast Continuous Collision Detection between Rigid Bodies

By S. Redon, A. Kheddar, S. Coquillart. Computer graphics forum (Print), 2002

329 citations recorded by the source corpus.

This paper introduces a fast continuous collision detection technique for polyhedral rigid bodies. As opposed to most collision detection techniques, the computation of the first contact time between two objects is inherently part of the algorithm. The method can thus robustly prevent objects interpenetrations or collisions misses, even when objects are thin or have large velocities. The method is valid for general objects (polygon soups), handles multiple moving objects and acyclic articulated bodies, and is efficient in low and high coherency situations. Moreover, the method can be used to speed up existent continuous collision detection methods for parametric or implicit rigid surfaces. The collision detection algorithms have been successfully coupled to a real‐time dynamics simulator. Various experiments are conducted that show the method's ability to produce high‐quality interaction (precise objects positioning for example) between models up to tens of thousands of triangles, which couldn't have been performed with previous continuous methods.

Subfields: Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition, Mechanical Engineering

View Paper: https://www.semanticscholar.org/paper/091d73bc9f3ca617d2af245927731489e3ef9582

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Graphics and Computer-Aided Design

1. Yuanming Hu
2. Jonathan Ragan-Kelley
3. Luke Anderson
4. Nathan A. Carr
5. Frédo Durand
6. Tzu-Mao Li
7. Qi Sun

In Computer Vision and Pattern Recognition

1. Jonathan Ragan-Kelley
2. Yuanming Hu
3. Mark Moll
4. Frédo Durand
5. Tzu-Mao Li
6. Lydia E. Kavraki
7. Ioan Alexandru Sucan
8. Pieter Abbeel

In Mechanical Engineering

1. Mark Moll
2. Lydia E. Kavraki
3. Ioan Alexandru Sucan

Citations in the corpus

• DiffTaichi: Differentiable Programming for Physical Simulation (2019, methodology): “We propose a simple solution of adding continuous collision resolution (see, for example, Redon et al. (2002)), which considers precise time of impact (TOI), to the forward program (Fig.”
• The Open Motion Planning Library (2012, background): “For example, one might want to add support for continuous collision checking, which can adaptively check for collisions and provide exact guarantees for state validity [31].”