Collision detection is of paramount importance for many applications in computer graphics and visualization. Typically, the input to a collision detection algorithm is a large number of geometric objects comprising an environment, together with a set of objects moving within the environment. In addition to determining accurately the contacts that occur between pairs of objects, one needs also to do so at real-time rates. Applications such as haptic force feedback can require over 1000 collision queries per second. We develop and analyze a method, based on bounding-volume hierarchies, for efficient collision detection for objects moving within highly complex environments. Our choice of bounding volume is to use a discrete orientation polytope (k-DOP), a convex polytope whose facets are determined by halfspaces whose outward normals come from a small fixed set of k orientations. We compare a variety of methods for constructing hierarchies (BV-trees) of bounding k-DOPs. Further, we propose algorithms for maintaining an effective BV-tree of k-DOPs for moving objects, as they rotate, and for performing fast collision detection using BV-trees of the moving objects and of the environment. Our algorithms have been implemented and tested. We provide experimental evidence showing that our approach yields substantially faster collision detection than previous methods.

Two-dimensional image registration estimates how one set of k 2-dimensional points is rotated, scaled, and translated into a second set of 2-dimensional points. We give an exact algorithm to solve the “least-squares” formulation of the problem. On average, the algorithm requires k2 pivots; it can be viewed as a refinement of the O(k3) approximation method proposed by K. Zikan and T. M. Silberberg. The approach can be extended to the registration of images of different cardinalities. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.