| In the past, even while modeling, most solid modelers have used faceted approximations for representing the curved boundaries of solids. Therefore, most collision detection algorithms known and practiced today are performed with models bounded by flat surfaces. Often, objects with curved boundaries are approximated by polyhedra and then a collision detection algorithm for polyhedral objects is applied to them. Approximating curved surfaces by planar facets limits the exactness of a collision detection algorithm to the accuracy of the tessellation and may cause accuracy problems. Today most CAD and solid modeling systems represent curved surfaces by piecewise spline rational functions. This type of representation has more recently become the standard in many applications of geometric and solid modeling.; This research presents an algorithm for exact contact prediction between moving curved objects. Objects are, generally, non-convex and are described using the 13-rep scheme. The bounding faces are represented by non-uniform rational B-splines (NURBS).; The collision time is sought in short time spans during the motion, in which time is one of the problem's variables to be found. Hierarchies of oriented bounding boxes (HOBBs) are used identify the parts of objects that may collide with each other. HOBBs of surfaces are computed based on curvature regions. This criterion ensures that the local numerical methods will converge to the contact points if they exist. Given an object, the HOBBs of each of its surfaces is first computed in a top-down scheme and then the root nodes of the resulting HOBBs are combined by repeated merges using a bottom-up approach to form the HOBB of the whole object.; The collision test is performed in two stages: a broad phase and a narrow phase. In the broad phase, collision detection is performed between the HOBBs. In the narrow phase, the patches enclosed in overlapping leaf nodes are tested for contact, by solving a system of non-linear equations, based on the type of collision expected. The types of collision studied in this research are: cusp-cusp, cusp-ridge, cusp-face, ridge-ridge, ridge-face, and face-face collisions. The current algorithm is implemented and compared to an efficient collision package for polygonal models (RAPID) and the result indicates that the current algorithm appears promising. |
