# 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

## 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.

## 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