Computing rotation distance between contacting polyhedra

Abstract

Distance computation is essential for collision prediction and/or detection in real-world robotic tasks, computer simulation and animation, and CAD/CAM. This paper addresses distance computation to deal with a rarely researched type of collision prediction/detection problem: Given two objects in certain contact, determine if and when a relative rotation constrained by contact will cause a collision (which results in a new contact state) between the two objects. The authors use the positive angle of rotation as the measure of rotation distance and present a method to compute, given two contacting convex polyhedra G and H and a rotation axis containing contact point(s) between them, the shortest rotation distance (SRD) of G which will cause new collision between G and H. The method is fully implemented and used in a computer simulation system for a contact-based fine motion planning scheme. The algorithm is also efficient. If each vertex of G or H is the intersection of n/sub e//spl nu// edges, the worst-case time complexity of the algorithm is O(n/sup 2//sub e//spl nu//). This means that for two arbitrary trihedral polyhedra, the algorithm has a constant worst-time complexity.