A Large-scale Benchmark and an Inclusion-based Algorithm for Continuous Collision Detection
- 24 September 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 40 (5), 1-16
- https://doi.org/10.1145/3460775
Abstract
We introduce a large-scale benchmark for continuous collision detection (CCD) algorithms, composed of queries manually constructed to highlight challenging degenerate cases and automatically generated using existing simulators to cover common cases. We use the benchmark to evaluate the accuracy, correctness, and efficiency of state-of-the-art continuous collision detection algorithms, both with and without minimal separation. We discover that, despite the widespread use of CCD algorithms, existing algorithms are (1) correct but impractically slow; (2) efficient but incorrect, introducing false negatives that will lead to interpenetration; or (3) correct but over conservative, reporting a large number of false positives that might lead to inaccuracies when integrated in a simulator. By combining the seminal interval root finding algorithm introduced by Snyder in 1992 with modern predicate design techniques, we propose a simple and efficient CCD algorithm. This algorithm is competitive with state-of-the-art methods in terms of runtime while conservatively reporting the time of impact and allowing explicit tradeoff between runtime efficiency and number of false positives reported.Keywords
Funding Information
- NSF CAREER (1652515)
- NSF (OAC-1835712, OIA-1937043, CHS-1908767, and CHS-1901091)
- National Key Research and Development Program of China (2020YFA0713700)
- EU ERC Advanced (694515)
- Sloan fellowship
- Adobe Research
- nTopology
- Advanced Micro Devices, Inc.
This publication has 33 references indexed in Scilit:
- Interference-aware geometric modelingACM Transactions on Graphics, 2011
- VolCCDACM Transactions on Graphics, 2011
- Star-contours for efficient hierarchical self-collision detectionACM Transactions on Graphics, 2010
- Fast and Scalable CPU/GPU Collision Detection for Rigid and Deformable SurfacesComputer Graphics Forum, 2010
- Robust treatment of simultaneous collisionsACM Transactions on Graphics, 2008
- Continuous collision detection for articulated models using Taylor models and temporal cullingACM Transactions on Graphics, 2007
- Interactive collision detection between deformable models using chromatic decompositionACM Transactions on Graphics, 2005
- Fast Continuous Collision Detection between Rigid BodiesComputer Graphics Forum, 2002
- Collision detection for interactive graphics applicationsIEEE Transactions on Visualization and Computer Graphics, 1995
- Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularityComputer Graphics Forum, 1994