EP0405106A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Construction of Minkowski sums and derivative morphological combinations of arbitrary polyhedra in CAD/CAM systems
Assignee: International Business Machines Corp
•
Filing: 1990-05-12
•
Granted: —
•
Expires: 2010-05-12
Abstract
Abstract A method for constructing the Minkowski sum and derivative morphological combinations of arbitrary 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.
Inventors
- 👤 Roger Clinton Evans
- 👤 Michael Andrew O'conner
- 👤 Jaroslaw Roman Rossignac
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-03 12:22
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/10; G06F; G06F30/00; G06F30/20; Y; Y02; Y02P; Y02P90/00; Y02P90/02
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
63 words
In a CAD/CAM system including a computer for modeling geometric objects in n-space, a method for computing Minkowski sums of general polyhedra comprising the computer performed steps of: using Boolean operations and Minkowski sums of simpler polyhedra to form the Minkowski sum of said general polyhedra; and generating an image or internal computer representation of a geometric object represented by said Minkowski sum.
Claim 2
Dependent Claim
63 words
In a CAD/CAM system including a computer for modeling geometric objects in n-space, a method for computing Minkowski sums of general polyhedra comprising the computer performed steps of: using Boolean operations and Minkowski sums of simpler polyhedra to form the Minkowski sum of said general polyhedra; and generating an image or internal computer representation of a geometric object represented by said Minkowski sum.
Claim 3
Dependent Claim
53 words
The method recited in claim 1 wherein the step of using Boolean operations and Minkowski sums of simpler polyhedra to form the Minkowski sum of said general polyhedra comprises the steps of: decomposing said general polyhedra into cells; and forming the union of the Minkowski sums of the cells of said general polyhedra.
Claim 4
Dependent Claim
42 words
The method recited in claim 2 further comprising the step of testing transversality of said cells of general polyhedra in n-space in order to enable the step of using Boolean operations and Minkowski sums of simpler polyhedra to form said Minkowski sum.
Claim 5
Dependent Claim
21 words
The method recited in claim 2 further including the step of testing transversality between said cells of general polyhedra in n-space.
Claim 6
Dependent Claim
27 words
The method recited in claim 2 wherein said Minkowski sums of simpler polyhedra are formed of transversal polyhedra in n-space using a generalization of linear translational sweeps.
Claim 7
Dependent Claim
37 words
The method recited in claim 2 wherein said Minkowski sums of simpler polyhedra are formed by processing cells starting from a lowest dimension and ending with highest dimensional cells, thereby eliminating a large fraction of redundant calculations.
Claim 8
Dependent Claim
26 words
The method recited in claim 2 further comprising the step of propagating information on the transversality of cells, thereby reducing the need to compute this information.
Claim 9
Dependent Claim
55 words
The method recited in claim 7 wherein said step of propagating comprises the steps of: determining if two cells are nontransversal, and if so, declaring pairs of cells that they bound cannot be transversal; and determining if two cells are transversal, and if so, declaring all pairs of cells in their respective boundary are transversal.
Claim 10
Dependent Claim
38 words
The method recited in claim 2 further comprising the step of determining if two cells are not strongly transversal, and if so, not calculating the Minkowski sums of these two cells, thereby avoiding unnecessary calculation of Minkowski sums.
Claim 11
Dependent Claim
28 words
The method recited in claim 9 further comprising the step of establishing sufficient conditions for cells that are not strongly transversal to any other cell of particular dimensions.
Claim 12
Dependent Claim
27 words
The method recited in claim 10 wherein one of said conditions is that concave edges in 3-space are never strongly transversal to solids or faces in 3-space.
Claim 13
Dependent Claim
27 words
The method recited in claim 2 wherein one of said general polyhedra is convex, further comprising the step of using surrogate cells to compute said Minkowski sums.
Claim 14
Dependent Claim
30 words
The method recited in claim 12 wherein the process of computing said Minkowski sums comprises the step of computing a surrogate of said complex polyhedron with respect to a cell.
Claim 15
Dependent Claim
25 words
The method recited in claim 13 wherein the surrogate of a convex three dimensional polyhedron is computed with respect to a face or an edge.
Claim 16
Dependent Claim
44 words
The method recited in claim 2 wherein one of said general polyhedra is full dimensional and wherein the step of forming said Minkowski sums of simpler polyhedra is performed by considering only pairs of cells whose dimensions sum to the dimension of the space.
Claim 17
Dependent Claim
50 words
The method recited in claim 15 wherein both said general polyhedra are full dimensional polyhedra in 3-space and wherein unions of Minkowski sums are reduced to translations of each polyhedron by vertices of the other polyhedron and of sweeps of faces of each polyhedron by edges of the other polyhedron.
Claim 18
Dependent Claim
22 words
The method recited in claim 16 wherein only strongly transversal face-edge pairs are used in the process of said translations and sweeps.
Claim 19
Dependent Claim
31 words
The method recited in claim 17 wherein the Minkowski sum is formed in 3-space as the union of linear translational sweeps of each polyhedron along non-concave edges of the other polyhedron.
Claim 20
Dependent Claim
30 words
The method recited in claim 1 further comprising the step of reducing unbounded polyhedra to a union of a finite number of polyhedra, each of which contains no affine line.
Claim 21
Dependent Claim
110 words
In a CAD/CAM system including a computer for modeling geometric objects in three-dimensions, a method for computing Minkowski sum of general polyhedra comprising the computer performed steps of: computing the Minkowski sum A ⊕ B of two polyhedra A and B, at least one of which bounded, as the union of linear translational sweeps wherein said Minkowski sum is expressed as A⊕B = (A⊕V B )U(F A ⊕E B )U(E A ⊕F B )U(V A ⊕B), where V A , E A and F A , respectively, and V B , E B and F B , respectively, denote the unions of vertices, edges and faces of A and B;
Claim 22
Dependent Claim
110 words
In a CAD/CAM system including a computer for modeling geometric objects in three-dimensions, a method for computing Minkowski sum of general polyhedra comprising the computer performed steps of: computing the Minkowski sum A ⊕ B of two polyhedra A and B, at least one of which bounded, as the union of linear translational sweeps wherein said Minkowski sum is expressed as A⊕B = (A⊕V B )U(F A ⊕E B )U(E A ⊕F B )U(V A ⊕B), where V A , E A and F A , respectively, and V B , E B and F B , respectively, denote the unions of vertices, edges and faces of A and B;
Claim 23
Dependent Claim
51 words
The method recited in claim 20 wherein said step of computing is performed by the steps of: sweeping each polyhedron along the edges of the other polyhedron that are not concave, thereby forming first and second intermediate polyhedra; and forming the polyhedral union of the said first and second intermediate polyhedra.
Claim 24
Dependent Claim
83 words
The method recited in claim 20 wherein the said polyhedron B is convex and wherein the step of computing is performed by the steps of: sweeping the polyhedron B along the edges of the polyhedron A to form a first intermediate polyhedron; sweeping the faces of the polyhedron A along a surrogate edge of B, thereby raising the faces of polyhedron A by the polyhedron B and forming a second intermediate polyhedron; and forming the polyhedral union of the first and second polyhedra.
Claim 25
Dependent Claim
50 words
The method recited in claim 20 wherein the polyhedron A is expanded by the polyhedron B by the step of computing the Minkowski sum A⊕B to simulate the process of depositing a layer reflecting the characteristics of the polyhedron B on a substrate having the characteristics of the polyhedron A.
Claim 26
Dependent Claim
38 words
The method recited in claim 23 wherein the simulated deposition process represents a step in semiconductor manufacture and the step of generating an image provides a visual or internal computer representation of the result of said deposition process.
Claim 27
Dependent Claim
43 words
The method recited in claim 20 wherein the polyhedron A is eroded by the polyhedron B comprising the steps of: first computing the reflection of the polyhedron B through an origin as B′ = {-b: bεB}; and then computing the Minkowski sum A⊖B′.
Claim 28
Dependent Claim
43 words
The method recited in claim 25 wherein the process of eroding the polyhedron A by the polyhedron B simulates and etching process in semiconductor manufacture and the step of generating an image produces a visual or internal computer representation of said etching process.
Claim 29
Dependent Claim
44 words
The method recited in claim 20 wherein the polyhedron A is opened by the polyhedron B comprising the steps of: first computing the reflection of the polyhedron B through an origin as B′ = {-b: bεB}; and next, computing the Minkowski sum of (A⊖B′)⊕B.
Claim 30
Dependent Claim
44 words
The method recited in claim 20 wherein the polyhedron A is closed by the polyhedron B comprising the steps of: first computing the reflection of the polyhedron B through an origin as B′ = {-b: bεB}; and next, computing the Minkowski sum of (A⊕B′)⊖B.
Claim 31
Dependent Claim
52 words
The method recited in claim 20 wherein the process is used to determine the translational free space of a polyhedron B in a polyhedron A further comprising the steps of: first computing the reflection of B through an origin as B′ = {-b: bεB}; and next, computing the Minkowski sum of A⊖B′.
Claim 32
Dependent Claim
46 words
The method recited in claim 29 wherein the polyhedron B is a robotic gripper and the polyhedron A is a workcell containing the gripper and the step of generating a image produces a visual representation of the translational free space of the gripper within the workcell.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.