efficient collision detection for curved solid objects
The design-for-assembly technique requires realistic physically based simulation algorithms and in particular e?cient geometric collision detection routines. Instead of approximating mechanical parts by large polygonal models, we work with the much smaller original CAD-data directly, thus avoiding precision and tolerance problems. We present a generic algorithm, which can decide whether two solids intersect or not. We identify classes of objects for which this algorithm can be e?ciently specialized, and describe in detail how this specialization is done. These classes are objects that are bounded by quadric surface patches and conic arcs, objects that are bounded by natural quadric patches, torus patches, line segments and circular arcs, and objects that are bounded by quadric surface patches, segments of quadric intersection curves and segments of cubic spline curves. We show that all necessary geometric predicates can be evaluated by ?nding the roots of univariate polynomials of degree at most 4 for the ?rst two classes, and at most 8 for the third class. In order to speed up the intersection tests we use bounding volume hierarchies. With the help of numerical optimization techniques we succeed in calculating smallest enclosing spheres and bounding boxes for a given set of surface patches ful?lling the properties mentioned above.
collision detection manufacturing and assembly planning geometric interrogations and reasoning computational geometry