Tech Report CS-95-08

Collision Detection for Interactive Graphics Applications

Philip M. Hubbard

March 1995


Solid objects in the real world do not pass through each other when they collide. Enforcing this property of ``solidness'' is important in many interactive graphics applications; for example, solidness makes virtual reality more believable, and solidness is essential for the correctness of vehicle simulators. These applications use a collision-detection algorithm to enforce the solidness of objects. Unfortunately, previous collision-detection algorithms do not adequately address the needs of interactive applications. To work in these applications, a collision-detection algorithm must run at real-time rates, even when many objects can collide, and it must tolerate objects whose motion is specified ``on the fly'' by a user.

This dissertation describes a new collision-detection algorithm that meets these criteria through approximation and graceful degradation, elements of ``time-critical computing.'' The algorithm is not only fast but also interruptible, allowing an application to trade accuracy for speed as needed. The algorithm uses two forms of approximate geometry. The first is a four-dimensional structure called a ``space-time bound.'' This structure provides a conservative estimate of where an object may be in the immediate future based on estimates of the object's acceleration. The algorithm uses space-time bounds to focus its attention on objects that are likely to collide. The second form of approximate geometry is a ``sphere-tree.'' This structure contains a hierarchy of unions of spheres, each union approximating the three-dimensional surface of an object at a different level of detail. Sphere-trees allow the algorithm to quickly find approximate contacts between objects, and they allow the application to interrupt the algorithm in order to meet real-time performance goals.

Automatically building sphere-trees is an interesting problem in itself, and this dissertation describes several approaches. The simplest approach is based on octrees, and more sophisticated approaches use simulated annealing and approximate medial-axis surfaces. Several of the steps in these algorithms are themselves significant. One step is a simple algorithm for checking whether a union of two-dimensional shapes covers a polygon. Another step builds Voronoi diagrams for three-dimensional data points, and does so more robustly and accurately than previous algorithms.

An implementation of the collision-detection algorithm runs significantly faster than a previous algorithm in empirical tests. In particular, this implementation allows real-time performance in a sample application (a simple flight simulator) that is too slow with the previous algorithm; in some cases, the performance improves by more than two orders of magnitude. Experience with this sample application suggests that time-critical computing is not always simple to apply, but it provides enough benefits that it deserves further exploration in other contexts.

(complete text in pdf or gzipped postscript)