@article{a8188a491a034365a65a47f9b0e67bf3,
title = "Fast and Exact Root Parity for Continuous Collision Detection",
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.",
keywords = "CCS Concepts, • Computing methodologies → Collision detection, • Mathematics of computing → Mathematical software",
author = "Bolun Wang and Zachary Ferguson and Xin Jiang and Marco Attene and Daniele Panozzo and Teseo Schneider",
note = "Funding Information: 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. Publisher Copyright: {\textcopyright} 2022 The Author(s) Computer Graphics Forum {\textcopyright} 2022 The Eurographics Association and John Wiley & Sons Ltd. Published by John Wiley & Sons Ltd.",
year = "2022",
month = may,
doi = "10.1111/cgf.14479",
language = "English (US)",
volume = "41",
pages = "355--363",
journal = "Computer Graphics Forum",
issn = "0167-7055",
publisher = "Wiley-Blackwell",
number = "2",
}