Skip to content

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

The parity of the roots between a moving triangle and a point (left) and between two moving edges (right), can be computed by counting the parity of the intersections of a ray (red) casted from the origin (red sphere) with the surface of a prism for the vertex-triangle case (left) or a cube for the edge-edge case (right).

Paper

Paper (PDF)       Low res (PDF)

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.

Simulation Videos

We drop three elastic Octocats into a bowl and use our CCD within a filtered line search to keep the meshes intersection-free (simulated using IPC [Li et al. 2020] with a timestep of 0.07s).
We run the mat-twist experiment from [Li et al. 2020] using our CCD method in the filtered line-search and timestep of 0.04 s. The mat is 1m × 1m × 8mm and our algorithm conservatively shifts the world by [11.75, 11.75, 12.24] which results in a rounding error of 2.66e-15.

Source Code

BibTex

@article{Wang:2022:FastRootParity,
    title        = {Fast and Exact Root Parity for Continuous Collision Detection},
    author       = {Bolun Wang and Zachary Ferguson and Xin Jiang and Marco Attene and Daniele Panozzo and Teseo Schneider},
    year         = 2022,
    journal      = {Computer Graphics Forum (Proceedings of Eurographics)},
    volume       = 41,
    number       = 2,
    numpages     = 9
}

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 & Development Program of China Grant No. 2020YFA0713701, Natural Science Foundation of China Grants No.~12171023 & No. 12001028, NSERC DGECR-2021-00461 and RGPIN-2021-03707, 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: 2022-06-06