In physical simulations, video games and computational geometry,

**collision detection**includes algorithms 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 some crucial differences. 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, in real time and robustly. 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 ray tracing 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 time, without any preprocessing. However, there are algorithms for solving this problem in 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 . However, the precomputation generates a data structure of size for any desired 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.

## Collision detection in physical simulation

### A posteriori vs a priori

Given that exact numbers are impossible to obtain, one can also use a simple *a posteriori* algorithm, and then use a binary search to attempt to compute the first moment of collision, if any. However, aside from the fact that this approach may miss some collisions, binary search is known to be relatively inefficient compared to other root-finding algorithms such as Newton's method.

Some objects are in *resting contact*, that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment, however, some believe that it poses special problems in *a posteriori* algorithms.

*n*-body pruning

The problem of course is that for large objects very close to one another, it is not necessarely easy to find a line (such as in the billiards example) which separates the objects into two sets that don't intersect. This can be appeased somewhat, and the algorithm can be made recursive, and one obtains a program which seems to work faster than the naive algorithm for certain data when is large.

From the point of view of worst-case behavior, we note that if all objects occupy the same point in space, then necessarely there will be pairs to check. Instead, we're interested in *output sensitive* algorithms: algorithms whose running time is appealing if written in terms of the size of their *output*. In our case, these are algorithms which will run faster when the actual number of collisions is small.

### Temporal coherence

So we reduce the problem to that of tracking, from frame to frame, which intervals do intersect. We have three lists of intervals (one for each axis) and all lists are the same length (since each since has length , the number of bounding boxes.) In each list, each interval is allowed to intersect all other intervals in the list. So for each list, we will have an matrix of zeroes and ones: is 1 if intervals and intersect, and 0 if they do not intersect.

By our assumption, the matrix associated to a list of intervals will remain essentially unchanged from one time step to the next. To exploit this, the list of intervals is actually maintained as a list of labeled endpoints. Each element of the list has the coordinate of an endpoint of an interval, as well as a unique integer identifying that interval. Then, we bubble sort the list by coordinates, and update the matrix as we go. It's not so hard to believe that this algorithm will work relatively quickly if indeed the configuration of bounding boxes does not change significantly from one time step to the next.

In the case of deformable bodies such as cloth simulation, it may not be possible to use a more specific pairwise pruning algorithm as discussed below, and an *n*-body pruning algorithm is the best that can be done.

### Physically based temporal coherence

### Pairwise pruning

As a precomputation, we can take each physical body (represented by a set of triangles) and recursively decompose it into a binary tree, where each node represents a set of triangles, and its two children represent and . At each node in the tree, as a we can precompute the bounding sphere .

When the time comes for testing a pair of objects for collision, their bounding sphere tree can be used to eliminate many pairs of triangles.

Many variants of the algorithms are obtained by choosing something other than a sphere for . If one chooses axis-aligned bounding boxes, one gets AABBTrees. Oriented bounding box trees are called OBBTrees. Some trees are easier to update if the underlying object changes. Some trees can accommodate higher order primitives such as splines instead of simple triangles.

### Exact pairwise collision detection

A basic observation is that for any two convex objects which are disjoint, one can find a plane in space so that one object lies completely one one side of that plane, and the other object lies on the opposite side of that plane.

To turn this into a triangle-triangle intersection check, one further observes that two triangles collide essentially only when they can not be separated by a plane going through three vertices. That is, if the triangles are and where each is a vector in , then we can take three vertices, , find a plane going through all three vertices, and check to see if this is a separating plane. If any such plane is a separating plane, then the triangles are deemed to be disjoint. On the other hand, if none of these planes are separating planes, then the triangles are deemed to intersect. There are twenty such planes.

If the triangles are coplanar, this test is not entirely succesful. One can either add some extra planes, for instance, planes that are normal to triangle edges, to fix the problem entirely. In other cases, objects that meet at a flat face must necessarely also meet at an angle elsewhere, hence the overall collision detection will be able to find the collision.

For many more sophisticated primitives, it is impossible to find a closed-form solution to the intersection problem. To complicate matters further, many have found that using a black-box root finder to locate intersections often leads to numerical catastrophe. Some have suggested that replacing a high-order surface with a triangulation is the most numerically stable approach.

### A priori collision detection

### Spatial partitioning, miscellania

M. C. Lin also proposed in her Ph.D. thesis an exact pairwise algorithm for convex polyhedra that exploited temporal coherence. She noted that it is very easy to track, from one time step to the next, the closest features of a pair of convex object, using a variant of a Voronoi diagram. This algorithm is tricky to implement, and only works on convex polyhedra. Since concave polyhedra are very interesting in practice, attempts were made to adapt M. C. Lin's algorithm to concave situations. The natural approach is to write each concave polyhedron as a (not necessarely disjoint) union of convex polyhedra. However, in theory of computation and computational geometry, this is known as the *minimal convex cover* problem, and it is known to be NP-hard.

As if that were not enough, there are examples of very useful concave polyhedra typically approximating curved surfaces (for instance, a torus) which can only be written as a degenerate union of an extremely large number of convex polyhedra. Hence, this algorithm is not used for more general scenes.