Defending Continuous Collision Detection against Errors

摘要

Numerical errors and rounding errors in continuous collision detectionrn(CCD) can easily cause collision detection failures if theyrnare not handled properly. A simple and eu000bective approach is to usernerror tolerances, as shown in many existing CCD systems. Unfortunately,rnfinding the optimal tolerance values is a diu000ecult problemrnfor users. Larger tolerance values will introduce false positive artifacts,rnwhile smaller tolerance values may cause collisions to bernundetected. The biggest issue here is that we do not know whetherrnor when CCD will fail, even though failures are extremely rare. Inrnthis paper, we demonstrate a set of simple modifications to make arnbasic CCD implementation failure-proof. Using error analysis, wernprove the safety of this method and we formulate suggested tolerancernvalues to reduce false positives. The resulting algorithms arernsafe, automatic, eu000ecient, and easy to implement.