Collision detection

In physical simulations, video games and computational geometry, collision detection covers a range of algorithms ranging from checking for intersection between two given solids, to calculating trajectories, impact times and impact points in a physical simulation.

Overview

In physical simulation, we wish to conduct experiments, such as playing billiards. The physics of bouncing billiard balls are well understood, under the umbrella of rigid body motion and elastic collisions. An initial description of the situation would be given, with a very precise physical description of the billiard table and balls, as well as initial positions of all the balls. Given a certain impulsion on the white ball (probably resulting from a player hitting the ball with his cue), we want to calculate the trajectories, precise motion, and eventual resting places of all the balls with a computer program. A program to simulate this game would consist of several portions, one of which would be responsible for calculating the precise impacts between the billiard balls. This particular example also turns out to be numerically unstable: a small error in any calculation will cause catastrophic changes in the final position of the billiard balls.

Video games have similar requirements, with one crucial difference. While physical simulation needs to simulate real-world physics as precisely as possible, video games need to simulate real-world physics in a believable way. Compromises are allowed, so long as the resulting simulation is satisfying to the game player.

Computational geometers are interested in precise collision detection algorithms (much like physical simulators.) However, computational geometer are more interested in algorithms that have provably good running times. Unfortunately, most algorithms used in physical simulations and video games do not have very satisfying worst-case running times. An example problem is the raytracing problem: given a list of objects in three dimensional space, as well as the initial position and velocity of a particle, find the first solid object the particle will hit. It is very obvious how to do this in time proportional to the number of objects in the scene, however it is very difficult to do better than this, at least in the worst-case (or even expected case) sense.

It turns out that one can do significantly better for the raytracing problem. Using big O notation, the naive algorithm works in $O(n)$ time, without any preprocessing. However, there are algorithms for solving this problem in $O(\log n)$ time. The problem, however, is that a precomputation step needs to be performed. The idea is that the set of objects is first given to the program, the precomputation occurs, and then for each subsequent query of a particle with an initial position and velocity, the time it takes to find the first object hit is of order $O(\log n)$. However, the precomputation generates a data structure of size $O(n^{4+\epsilon })$ for any desired $\epsilon >0$ which makes these algorithms completely unusable in practice. (See, for instance, P.K. Agarwal and J. Matousek. Ray shooting and parametric search. SIAM Journal on Computing, 22(4):794--806, 1993.)

On the other hand, for the purpose of physical simulation, data structures were created which work well in practice. In all cases, these algorithms do not have especially interesting running times in the big O sense, however it is found that in practice they perform very well. The University of North Carolina, Chapel Hill has a group who have investigated this problem extensively, please see http://www.cs.unc.edu/~geom/collide/index.shtml.