Construction of minkowski sums and derivatives morphological

Abstract

A method for constructing the Minkowski sum and derivative morphological combinations of arbitray polyhedra uses operations supported in current CAD/CAM systems. The method has application to three-dimensional modeling of very large scale integrated (VLSI) circuits, their design and simulation of fabrication, and to automated mechanical assembly. The method also has application to n-dimensional modeling in robotics as well as other applications of CAD/CAM systems. In one aspect, an exact Minkowski sum of two polyhedra is obtained by a generalization of sweeping a face along an edge. More generally, according to a second aspect, the Minkowski sum of two polyhedra is computed as the union of linear translational sweeps enabled by the first aspect. The method implements techniques and formulas which greatly reduces the overall cost of the computation of Minkowski sums and, in particular, avoids computations involving non-transversal polyhedra. In a third aspect, the method reduces the difficulty of computing the Minkowski sum of a convex polyhedron and a general polyhedron by using simpler surrogate sets for the convex polyhedron.