A representation scheme for rapid 3D collision detection

A scheme is presented for the representation of objects for the rapid detection of collisions in a dynamic 3D environment, such as when a proposed path for a robot-carried object is tested for collisions with obstacles along the path. The successive spherical approximation (SSA) representation provides a representation scheme which allows rapid collision detection while still providing for the exact representation of dynamic objects. The hierarchy of representation levels is based on the subdivision of a sphere. The degree of approximation of the SSA representation decreases as the scheme traverses down the representation tree. The creation of the SSA representation is illustrated using an object database containing boundary representations. The use of the SSA hierarchical representation for rapid and exact collision detection between 3D objects and the environment is shown by considering the collision detection problem between stationary and moving objects. It is shown that there is little additional cost incurred by allowing changes in position and orientation of the objects. The contribution of the SSA representation is that it leads to a time-efficient, hybrid collision detection scheme