Continuous Collision Detection¶
Welcome! This is the website for the Continuous Collision Detection (CCD) projects started at the Geometric Computing Lab @ NYU. The goal of this work is to provide provably correct and efficient algorithms for continuous collision detection and to provide large-scale benchmarks for evaluating the correctness and efficiency of future developments.
We have three papers on this topic, and the code for the algorithms and the benchmarks are available on GitHub. Below you can find the abstracts for the papers, links to the papers, and links to the code repositories.
Papers¶
A Large Scale Benchmark and an Inclusion-Based Algorithm for Continuous Collision Detection¶
Bolun Wang*, Zachary Ferguson*, Teseo Schneider, Xin Jiang, Marco Attene, Daniele Panozzo (*Joint first authors)
ACM Transactions on Graphics, 2021
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 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 into 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.
Fast and Exact Root Parity for Continuous Collision Detection¶
Bolun Wang, Zachary Ferguson, Xin Jiang, Marco Attene, Daniele Panozzo, Teseo Schneider
Computer Graphics Forum (Eurographics), 2022
Abstract¶
We introduce the first exact root parity counter for continuous collision detection (CCD). 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.
Time of Impact Dataset for Continuous Collision Detection and a Scalable Conservative Algorithm¶
David Belgrod, Bolun Wang, Zachary Ferguson, Xin Zhao, Marco Attene, Daniele Panozzo, Teseo Schneider
In submission
Abstract¶
We introduce a large-scale benchmark for broad- and narrow-phase continuous collision detection (CCD) over linearized trajectories with exact time of impacts and use it to evaluate the accuracy, correctness, and efficiency of 13 state-of-the-art CCD algorithms. Our analysis shows that several methods exhibit problems either in efficiency or accuracy.
To overcome these limitations, we introduce an algorithm for CCD designed to be scalable on modern parallel architectures and provably correct when implemented using floating point arithmetic. We integrate our algorithm within the Incremental Potential Contact solver [Li et al. 2020] and evaluate its impact on various simulation scenarios. Our approach includes a broad-phase CCD to quickly filter out primitives having disjoint bounding boxes and a narrow-phase CCD that establishes whether the remaining primitive pairs indeed collide. Our broad-phase algorithm is efficient and scalable thanks to the experimental observation that sweeping along a coordinate axis performs surprisingly well on modern parallel architectures. For narrow-phase CCD, we re-design the recently proposed interval-based algorithm of Wang et al. [Wang et al. 2021] to work on massively parallel hardware.
To foster the adoption and development of future linear CCD algorithms, and to evaluate their correctness, scalability, and overall performance, we release the dataset with analytic ground truth, the implementation of all the algorithms tested, and our testing framework.
Code¶
- GitHub Organization
- Wrapper and Benchmark
- Tight Inclusion CCD
- Exact Root Parity CCD
- Scalable CCD
- Symbolic CCD
- Queries:
Data¶
All the data used in the papers is available on the NYU Faculty Digital Archive.
This includes the handcrafted queries, simulation queries, rounded queries, and full scene and time of impact dataset.
Acknowledgments¶
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.