Large Scale Benchmarks for Continuous Collision Detection

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 either: (1) correct but impractically slow, (2) efficient but incorrect, introducing false negatives which will lead to interpenetration, or (3) correct but over conservative, reporting a large number of false positives which 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 an explicit trade-off between runtime efficiency and the number of false positives reported.

We introduce the first exact root parity counter for continuous collision detection (CCD) in follow-up work. That is, our algorithm computes the parity (even or odd) of the number of roots of the cubic polynomial arising from a CCD query. We note that the parity is unable to differentiate between zero (no collisions) and the rare case of two roots (collisions). Our method does not have numerical parameters to tune, has a performance comparable to efficient approximate algorithms, and is exact. We test our approach on a large collection of synthetic tests and real simulations, and we demonstrate that it can be easily integrated into existing simulators..

The full CCD article is available here.
The full Root-Parity article is available here.
The github organization to run all experiments can be found here.
Our novel inclusion-based CCD algorithm can be foud here.
If you just want to use our wrapper to use CCD inside your application, go here.
Our novel root-parity CCD algorithm can be foud here.

We thank the NYU IT High Performance Computing for resources, services, and staff expertise. This work was partially supported by the NSF CAREER award under Grant No. 1652515; the NSF grants OAC-1835712, OIA-1937043, CHS-1908767, and CHS-1901091; National Key Research and Development Program of China No. 2020YFA0713700; Natural Science Foundation of China Grants No. 12171023 and 12001028; NSERC DGECR-2021-00461 and RGPIN-2021-03707; KAUST baseline funding (grant BAS/1/1679-01-01); EU ERC Advanced Grant CHANGE No. 694515 and EU project DIGITbrain/ProMED (952071); a Sloan Fellowship; a gift from Adobe Research; a gift from nTopology; and a gift from Advanced Micro Devices, Inc.