Tech Report CS-93-04

Space-Time Bounds for Collision Detection

Philip M. Hubbard

February 1993

Abstract:

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.

(complete text in pdf or gzipped postscript)