A Large-scale Benchmark and an Inclusion-based Algorithm for Continuous Collision Detection

We introduce a large-scale benchmark for continuous collision detection(CCD) algorithms, composed of queries manually constructed to highlightchallenging degenerate cases and automatically generated using existingsimulators to cover common cases. We use the benchmark to evaluatethe accuracy, correctness, and efficiency of state-of-the-art continuous collisiondetection algorithms, both with and without minimal separation.We discover that, despite the widespread use of CCD algorithms, existingalgorithms 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 positivesthat might lead to inaccuracies when integrated in a simulator.By combining the seminal interval root finding algorithm introducedby Snyder in 1992 with modern predicate design techniques, we proposea simple and efficient CCD algorithm. This algorithm is competitivewith state-of-the-art methods in terms of runtime while conservativelyreporting the time of impact and allowing explicit tradeoff betweenruntime efficiency and number of false positives reported.