Skip to content

Tight Inclusion

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

An overview of the results of our study of different CCD methods run on 60 million queries (both vertex-face and edge-edge). For each method, we show the number of false positives (i.e., the method detects a collision where there is none), the number of false negatives (i.e., the method misses a collision), and the average run time. Each plot reports results in a logarithmic scale. False positives and negatives are computed with respect to the ground truth computed using Mathematica [Wolfram Research Inc. 2020].

Paper

Paper (PDF)       Low res (PDF)      

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 Forward

Presentation

Video

Inaccurate collision detection can lead to unnatural "sticking" and eventual failure when integrated into simulators (show here using IPC [Li et al. 2020]) because part of the geometry gets stuck inside. Here we show a false negative reported by the Root-Parity method of Brochu et al. [2012] causes the ball to get stuck inside the rollers. Our conservative CCD never misses collisions and so the ball can pass through the rollers without problems.

Source Code and Data

Build status License

BibTex

@article{Wang:2021:Benchmark,
    title        = {A Large Scale Benchmark and an Inclusion-Based Algorithm for Continuous Collision Detection},
    author       = {Bolun Wang and Zachary Ferguson and Teseo Schneider and Xin Jiang and Marco Attene and Daniele Panozzo},
    year         = 2021,
    month        = oct,
    journal      = {ACM Transactions on Graphics},
    volume       = 40,
    number       = 5,
    articleno    = 188,
    numpages     = 16
}

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, CHS-1901091, National Key Research and Development Program of China No. 2020YFA0713700, EU ERC Advanced Grant CHANGE No. 694515, a Sloan Fellowship, a gift from Adobe Research, a gift from nTopology, and a gift from Advanced Micro Devices, Inc.

Last update: 2024-04-01