Programming Research Group Technical Monograph PRG-86

Stephen Cameron

July 1990, 30 pages, ISBN 0-902928-65-1

The collision detection problem is easily stated: "Given two objects and desired motions, decide whether the objects will come into collision over a given time span". The solution of this problem is useful, both in robotics and other problem domains. We describe a method for solving collision detection that involves transforming the problem into an intersection detection problem over space-time. We give the theoretical basis for the solution, and describe an efficient implementation based on describing the objects and motions constructively. We also consider the related problems of describing the collision region, and of detecting collisions when there are more than two moving objects.