Fast and Exact Root Parity for Continuous Collision Detection

Bolun Wang, Zachary Ferguson, Xin Jiang, Marco Attene, Daniele Panozzo, Teseo Schneider

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)355-363
Number of pages9
JournalComputer Graphics Forum
Issue number2
StatePublished - May 2022


  • CCS Concepts
  • • Computing methodologies → Collision detection
  • • Mathematics of computing → Mathematical software

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Fast and Exact Root Parity for Continuous Collision Detection'. Together they form a unique fingerprint.

Cite this