Collision detection for interactive graphics applications.

摘要

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, such as vehicle simulators and virtual realities. These applications use a collision-detection algorithm to enforce the solidness of objects. Unfortunately, previous collision-detection algorithms cannot 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. By approximating how objects move through time, space-time bounds let the algorithm focus on likely collisions. The second geometric approximation is a sphere-tree. This hierarchy of spheres approximates the three-dimensional shape of an object at multiple levels of detail. Sphere-trees allow the algorithm to quickly find approximate contacts between objects, with the application controlling the level of accuracy.; Automatically building sphere-trees is an interesting problem in itself, and this dissertation describes several approaches. The simplest approach uses octrees, and more sophisticated approaches use simulated annealing and approximate medial-axis surfaces. Several steps in these algorithms are themselves significant. One is a simple algorithm for checking whether a union of two-dimensional shapes cover a polygon. Another builds Voronoi diagrams for three-dimensional data more robustly and accurately than previous approaches.; An implementation of the collision-detection algorithm allows real-time performance in a sample application which is too slow with previous algorithms. In some cases, performance improves by more than two orders of magnitude. Experience with this sample application suggests that time-critical computing is not trivial to apply, but it provides enough benefits that it deserves further exploration in other contexts.