Construction of Minkowski sums and derivatives morphological combinations of arbitrary polyhedra in CAD/CAM systems
US5159512A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jul 5, 1991 |
| Grant date | Oct 27, 1992 |
| Priority date | — |
| Expiry date | Jul 5, 2011 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY02P90/02
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.