TightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Bounds
No Thumbnail Available
Date
2015
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and John Wiley & Sons Ltd.
Abstract
We present a realtime and reliable continuous collision detection (CCD) algorithm between triangulated models that exploits the floating point hardware capability of current CPUs and GPUs. Our formulation is based on Bernstein Sign Classification that takes advantage of the geometry properties of Bernstein basis and Bézier curves to perform Boolean collision queries. We derive tight numerical error bounds on the computations and employ those bounds to design an accurate algorithm using finite-precision arithmetic. Compared with prior floatingpoint CCD algorithms, our approach eliminates all the false negatives and 90-95% of the false positives. We integrated our algorithm (TightCCD) with physically-based simulation system and observe speedups in collision queries of 5-15X compared with prior reliable CCD algorithms. Furthermore, we demonstrate its benefits in terms of improving the performance or robustness of cloth simulation systems.
Description
@article{10.1111:cgf.12767,
journal = {Computer Graphics Forum},
title = {{TightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Bounds}},
author = {Wang, Zhendong and Tang, Min and Tong, Ruofeng and Manocha, Dinesh},
year = {2015},
publisher = {The Eurographics Association and John Wiley & Sons Ltd.},
DOI = {10.1111/cgf.12767}
}