Fast and Exact Root Parity for Continuous Collision Detection
Loading...
Date
2022
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and John Wiley & Sons Ltd.
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.
Description
CCS Concepts: Computing methodologies --> Collision detection; Mathematics of computing --> Mathematical software
@article{10.1111:cgf.14479,
journal = {Computer Graphics Forum},
title = {{Fast and Exact Root Parity for Continuous Collision Detection}},
author = {Wang, Bolun and Ferguson, Zachary and Jiang, Xin and Attene, Marco and Panozzo, Daniele and Schneider, Teseo},
year = {2022},
publisher = {The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {10.1111/cgf.14479}
}