TightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Bounds

Simple item page
dc.contributor.authorWang, Zhendongen_US
dc.contributor.authorTang, Minen_US
dc.contributor.authorTong, Ruofengen_US
dc.contributor.authorManocha, Dineshen_US
dc.contributor.editorStam, Jos and Mitra, Niloy J. and Xu, Kunen_US
dc.date.accessioned2015-10-07T05:12:46Z
dc.date.available2015-10-07T05:12:46Z
dc.date.issued2015en_US
dc.description.abstractWe 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.en_US
dc.description.number7en_US
dc.description.sectionheadersCollision Detectionen_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume34en_US
dc.identifier.doi10.1111/cgf.12767en_US
dc.identifier.pages289-298en_US
dc.identifier.urihttps://doi.org/10.1111/cgf.12767en_US
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectI.3.7 [Computer Graphics]en_US
dc.subjectThree Dimensional Graphicsen_US
dc.subjectAnimationen_US
dc.titleTightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Boundsen_US
Files
Collections
34-Issue 7