Given two objects we define the minimal translational distance (MTD) between them to be the length of the shortest relative translation that results in the objects being in contact. MTD is equivalent to the distance between two objects if the objects are not intersecting; however MTD is also defined for intersecting objects and it then gives a measure of penetration. We show that the computation of MTD can be recast as a configuration space problem, and describe an algorithm for computing MTD for convex polyhedra. This research was conducted under the McDonnell Douglas Independent Research and Development Program.

The collision detection problem is encountered whenever objects are to be manipulated in the real world. Efficient solutions to this problem must intelligently decide when in time and where in space to check for interference among the objects. Complete solutions must guarantee that no collision can be overlooked. Useful solutions should also report the precise space/time points at which colliding objects begin and end contact. An algorithm based on velocity and distance bounds is described which is both useful and complete. Experiments are presented which measure the efficiency of the algorithm on a variety of test cases. The algorithm is contrasted with existing collision detection methods.