Root Parity

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¶

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.

Fast Forward¶

Presentation¶

Watch our full Eurographics 2022 presentation on Bilibili (English)!

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 and Data¶

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: 2024-04-01