University Information Service: Contents | Index | Search

Collision Detection for Animation

In a dynamic environment consisting of multiple, simulated 3D objects, the detection of collisions between objects is a computational intensive task. The problem has been the focus of much research in the computer animation area for some time, and is currently an equally important area of study for those interested in virtual environments.

To accelerate the detection of collisions, both the REALISM and ACE systems use a three-stage scheme.

Since the objects in the system are strictly encapsulated, only the objects themselves can perform the collision detection process. Each object is assigned a set of other objects of which it is responsible for carry out the test processes. This distribution of work ensures that no object carries out more work than the pre-defined limit. Some frames from an animation with graphs monitoring the object workloads is given below.

Object workloads during animation

MPEG, 336K

The use of `sphere-trees'

After an intial bounding volume test, inter-object collision detection is carried out using a geometry approximation consisting of a tree of spheres. This allows rapid rejection of non-colliding objects and identification of regions of potential collisions. Finally, a test using the actual geometry of the object is performed in the regions identified.

Some images showing the various levels of a sphere-tree object approximation are shown below, together with an image showing the stages in a collision search.