hide
Free keywords:
-
Abstract:
The design-for-assembly technique requires realistic physically based
simulation algorithms and in particular efficient 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
efficiently 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 finding the roots of univariate polynomials of
degree at most $4$ for the first 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 fulfilling the properties
mentioned above.