Tech Report CS-93-04
Space-Time Bounds for Collision Detection
Philip M. Hubbard
Collision detection and response is an important but costly component of computer animation. We identify three basic reasons why collision-detection algorithms can be slow. We present a new collision-detection algorithm that directly addresses two of these problems and prepares us for future work on the third. Our algorithm is based on a four-dimensional structure that puts a conservative bound on motion through time, even if that motion is specified interactively by a user. The empirical results we present suggest that our algorithm performs significantly better than previous algorithms.