Fast and Exact Root Parity for Continuous Collision Detection. (24th May 2022)

• Record Type: Journal Article
• Authors: Wang, Bolun; Ferguson, Zachary; Jiang, Xin; Attene, Marco; Panozzo, Daniele; Schneider, Teseo
• Is Part Of: Computer graphics forum. Volume 41:Number 2(2022)
• Page Start: 355
• Page End: 363
• Publication Date: 2022-05-24
• Subjects: CCS Concepts -- Computing methodologies → Collision detection -- Mathematics of computing → Mathematical software; Computer graphics -- Periodicals; 006.605
• DOI: 10.1111/cgf.14479
• Languages: English
• ISSNs: 0167-7055

Abstract

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.