Fast interference detection between geometric models

We present efficient algorithms for interference detection between geometric models described by linear or curved boundaries and undergoing rigid motion. The set of models include surfaces described by rational spline patches or piecewise algebraic functions. In contrast to previous approaches, we first describe an efficient algorithm for interference detection between convex polytopes using coherence and local features. Then an extension using hierarchical representation to concave polytopes is presented. We apply these algorithms along with properties of input models, local and global algebraic methods for solving polynomial equations, and the geometric formulation of the problem to devise efficient algorithms for convex and nonconvex curved objects. Finally, a scheduling scheme to reduce the frequency of interference detection in large environments is described. These algorithms have been successfully implemented and we discuss their performance in various environments.