Construction of minkowski sums and derivatives morphological combinations of arbitrary polyhedra in cad/cam systems

Claim 2

In a CAD/CAM system including a computer for generating an image of a geometric object in a space which simulates a physical object being modeled on said CAD/CAM system, a method of generating said image comprising the computer performed steps of: inputting data to said CAD/CAM system which define first and second general polyhedra as a collection of cells which, when combined, form said geometric object; testing said data to determine the transversality of pairs of said cells; determining from the tested data if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; determining from the tested data if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; forming Minkowski sums of those pairs of respective cells from each of said first and second general polyhedra which are transversal; forming a union of said Minkowski sums of the cells using Boolean operations to form a Minkowski sum of said first and second general polyhedra; and generating and displaying an image of a geometric object represented by said Minkowski sum of said first and second general polyhedra.

Claim 3

The method recited in claim 1 wherein said Minkowski sums are derived from transversal polyhedra in n-space using linear translational sweeps.

Claim 4

The method recited in claim 1 wherein said Minkowski sums 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 5

The method recited in claim 1 wherein one of said general polyhedra is full dimensional and wherein the step of forming said Minkowski sums is performed only on pairs of cells whose dimensions sum to the dimension of the space.

Claim 6

The method recited in claim 1 wherein both said first and second general polyhedra are full dimensional polyhedra and wherein unions of Minkowski sums are formed by 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 7

The method recited in claim 5 wherein only strongly transversal face edge pairs are used in said translations and sweeps.

Claim 8

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 9

The method recited in claim 1 wherein the polyhedron A is expanded by the polyhedron B by the step of computing the Minkowski sum A⊕B to simulate a process of depositing a layer reflecting the characteristics of the polyhedron B on a substrate having the characteristics of the polyhedron A.

Claim 10

The method recited in claim 8 wherein the simulated deposition process represents a step in semiconductor manufacture and the step of generating and displaying an image provides a visual representation of the result of said simulated deposition process.

Claim 11

The method recited in claim 1 wherein the Minkowski sum A⊕B of two polyhedra A and B is formed and the polyhedron A is eroded by the polyhedron B further comprising the steps of: first computing a reflection of the polyhedron B through an origin as B'={-b: bεB}; and then computing the Minkowski sum A⊖B'.

Claim 12

The method recited in claim 10 wherein the process of eroding a polyhedron A by the polyhedron B simulates an etching process in semiconductor manufacture and the step of generating and displaying an image produces a visual representation of said simulated etching process.

Claim 13

The method recited in claim 1 wherein the Minkowski sum A⊕B of two polyhedra A and B is formed and the polyhedron A is opened by the polyhedron B further comprising the steps of: first computing a reflection of the polyhedron B through an origin as B'={-b: bεB}; and next, computing the Minkowski sum of (A⊖B')⊕B.

Claim 14

The method recited in claim 1 wherein the Minkowski sum A⊕B of two polyhedra A and B is formed and the polyhedron A is closed by the polyhedron B further comprising the steps of: first computing a reflection of the polyhedron B through an origin as B'={-b: bεB}; and next, computing the Minkowski sum of (A⊕B')⊖B.

Claim 15

The method recited in claim 1 wherein the Minkowski sum A⊕B of two polyhedra A and B is formed and the process is used to determine a translational free space of the polyhedron B in the polyhedron A further comprising the steps of: first computing a reflection of the polyhedron B through an origin as B'={-b: bεB}; and next, computing the Minkowski sum of A⊖B'.

Claim 16

In a computer modeling system including a computer for generating images of geometric objects in three-dimensions, said image generating computer receiving as inputs data generated by a computer based simulation system programmed to simulate a deposition process in semiconductor manufacture, a method for displaying said deposition process in semiconductor manufacture wherein a polyhedron A is expanded by a polyhedron B, said method comprising the computer performed steps of: inputting data from said simulation system to said computer modeling system which data define said polyhedrons A and B as a collection of cells which, when combined, form a geometric object; testing said data to determine the transversality of pairs of said cells; determining from the tested data if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; determining from the tested data if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; forming Minkowski sums of those respective cells from each of said polyhedra A and B which are transversal; forming a union of said Minkowski sums of the cells using Boolean operations to form the Minkowski sum A⊕B of the two polyhedra A and B, at least one of which is bounded, as the union of linear translational sweeps wherein said Minkowski sum is expressed as A⊕B=(A⊕V.sub.B)∪(F.sub.A ⊕E.sub.B)∪(E.sub.A ⊕F.sub.B)∪(V.sub.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 the polyhedrons A and B; generating and displaying an image of a geometric object represented by said Minkowski sum, said image simulating said deposition process.

Claim 17

In a computer modeling system including a computer for generating images of geometric objects in three-dimensions, said image generating computer receiving as inputs data generated by a computer based simulation system programmed to simulate a deposition process in semiconductor manufacture, a method for displaying said deposition process in semiconductor manufacture wherein a polyhedron A is expanded by a polyhedron B, said method comprising the computer performed steps of: inputting data from said simulation system to said computer modeling system which data define said polyhedrons A and B as a collection of cells which, when combined, form a geometric object; testing said data to determine the transversality of pairs of said cells; determining from the tested data if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; determining from the tested data if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; forming Minkowski sums of those respective cells from each of said polyhedra A and B which are transversal; forming a union of said Minkowski sums of the cells using Boolean operations to form the Minkowski sum A⊕B of the two polyhedra A and B, at least one of which is bounded, as the union of linear translational sweeps wherein said Minkowski sum is expressed as A⊕B=(A⊕V.sub.B)∪(F.sub.A ⊕E.sub.B)∪(E.sub.A ⊕F.sub.B)∪(V.sub.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 the polyhedrons A and B; generating and displaying an image of a geometric object represented by said Minkowski sum, said image simulating said deposition process.

Claim 18

In a computer modeling system including a computer for generating images of geometric objects in three-dimensions, said image generating computer receiving as inputs data generated by a computer based simulation system programmed to simulate an etching process in semiconductor manufacture, a method for displaying said etching process in semiconductor manufacture wherein a polyhedron A is eroded by a polyhedron B, said method comprising the computer performed steps of: inputting data from said simulation system to said computer modeling system which data define said polyhedrons A and B as a collection of cells which, when combined, form a geometric object; testing said data to determine the transversality of pairs of said cells; determining from the tested data if two cells are nontranversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; determining from the tested data if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; computing the reflection of the polyhedron B through an origin as B'={-b: bεB}; forming Minkowski sums of those respective cells from each of said polyhedra A and B' which are transversal; forming a union of said Minkowski sums of the cells using Boolean operations to form the Minkowski sum A⊕B' of the 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.sub.B')∪(F.sub.A ⊕E.sub.B')∪(E.sub.A ⊕F.sub.B')∪(V.sub.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 the polyhedron A and the reflection B' of the polyhedron B; and generating and displaying an image of a geometric object represented by said Minkowski sum, said image simulating said etching process.

Claim 19

In a computer modeling system including a computer for generating images of geometric objects in three-dimensions, said image generating computer receiving as inputs data generated by a computer based simulation system programmed to simulate an etching process in semiconductor manufacture, a method for displaying said etching process in semiconductor manufacture wherein a polyhedron A is eroded by a polyhedron B, said method comprising the computer performed steps of: inputting data from said simulation system to said computer modeling system which data define said polyhedrons A and B as a collection of cells which, when combined, form a geometric object; testing said data to determine the transversality of pairs of said cells; determining from the tested data if two cells are nontranversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; determining from the tested data if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; computing the reflection of the polyhedron B through an origin as B'={-b: bεB}; forming Minkowski sums of those respective cells from each of said polyhedra A and B' which are transversal; forming a union of said Minkowski sums of the cells using Boolean operations to form the Minkowski sum A⊕B' of the 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.sub.B')∪(F.sub.A ⊕E.sub.B')∪(E.sub.A ⊕F.sub.B')∪(V.sub.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 the polyhedron A and the reflection B' of the polyhedron B; and generating and displaying an image of a geometric object represented by said Minkowski sum, said image simulating said etching process.

Claim 20

In a computer modeling system including a computer for generating images of geometric objects in three-dimensions, a method for simulating translational free space of a robotic gripper within a workcell, said workcell being represented by a polyhedron A and said robotic gripper being represented by a polyhedron B, said method comprising the computer performed steps of: inputting data to said computer modeling system which define said polyhedrons A and B as a collection of cells which, when combined, form a geometric object; testing said data to determine the transversality of pairs of said cells; determining from the tested data if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; determining from the tested data if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; computing the reflection of B through an origin as B'={-b: bεB}; forming Minkowski sums of those respective cells from each of said polyhedra A and B' which are transversal; forming a union of said Minkowski sums of the cells using Boolean operations to form the Minkowski sum A⊕B' of the 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.sub.B')∪(F.sub.A ⊕E.sub.B')∪(E.sub.A ⊕F.sub.B')∪(V.sub.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 the polyhedron A and the reflection B' of the polyhedron B; and generating and displaying an image of a geometric object represented by said Minkowski sum, said image simulating the translational free space of the gripper within the workcell.

Claim 21

In a computer modeling system including a computer for generating images of geometric objects in three-dimensions, a method for simulating translational free space of a robotic gripper within a workcell, said workcell being represented by a polyhedron A and said robotic gripper being represented by a polyhedron B, said method comprising the computer performed steps of: inputting data to said computer modeling system which define said polyhedrons A and B as a collection of cells which, when combined, form a geometric object; testing said data to determine the transversality of pairs of said cells; determining from the tested data if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; determining from the tested data if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; computing the reflection of B through an origin as B'={-b: bεB}; forming Minkowski sums of those respective cells from each of said polyhedra A and B' which are transversal; forming a union of said Minkowski sums of the cells using Boolean operations to form the Minkowski sum A⊕B' of the 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.sub.B')∪(F.sub.A ⊕E.sub.B')∪(E.sub.A ⊕F.sub.B')∪(V.sub.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 the polyhedron A and the reflection B' of the polyhedron B; and generating and displaying an image of a geometric object represented by said Minkowski sum, said image simulating the translational free space of the gripper within the workcell.

Claim 22

The method recited in claim 17 wherein the polyhedron B is a robotic gripper and the polyhedron A is a workcell containing the gripper and the step of generating and displaying a image produces a visual representation of the translational free space of the gripper within the workcell.

Claim 23

A CAD/CAM system including a computer for generating an image of a geometric object in a space which simulates a physical object being modeled on said CAD/CAM system comprising: data input means for inputting data which defines first and second general polyhedra as a collection of cells which, when combined, form said geometric object; testing means for testing said data to determine transversality of pairs of said cells; means responsive to said testing means for determining if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; means responsive to said testing means for determining if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; summing means comprising first means for forming Minkowski sums of those pairs of respective cells from each of said first and second general polyhedra which are transversal and second means for forming a union of said Minkowski sums of the cells using Boolean operations to form a Minkowski sum of said first and second general polyhedra; and image generating means for generating and displaying on said display device an image of a geometric object represented by said Minkowski sum of said first and second general polyhedra.

Claim 24

A CAD/CAM system including a computer for generating an image of a geometric object in a space which simulates a physical object being modeled on said CAD/CAM system comprising: data input means for inputting data which defines first and second general polyhedra as a collection of cells which, when combined, form said geometric object; testing means for testing said data to determine transversality of pairs of said cells; means responsive to said testing means for determining if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; means responsive to said testing means for determining if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; summing means comprising first means for forming Minkowski sums of those pairs of respective cells from each of said first and second general polyhedra which are transversal and second means for forming a union of said Minkowski sums of the cells using Boolean operations to form a Minkowski sum of said first and second general polyhedra; and image generating means for generating and displaying on said display device an image of a geometric object represented by said Minkowski sum of said first and second general polyhedra.

Claim 25

The CAD/CAM system recited in claim 19 wherein said means for forming Minkowski sums derives said Minkowski sums from transversal polyhedra in n-space using linear transversal sweeps.

Claim 26

The CAD/CAM system recited in claim 19 wherein said means for forming Minkowski sums forms sums by processing cells starting from a lowest dimension and ending with highest dimensional cells, thereby eliminating a large fraction of redundant calculations.

Claim 27

The CAD/CAM system recited in claim 19 wherein one of said general polyhedra is full dimensional and wherein said means for forming said Minkowski sums operates on only pairs of cells whose dimensions sum to the dimension of the space.

Claim 28

The CAD/CAM system recited in claim 19 wherein both said first and second general polyhedra are full dimensional polyhedra and wherein said means for forming a union of said Minkowski sums translates each polyhedron by vertices of the other polyhedron and sweeps faces of each polyhedron by edges of the other polyhedron.

Claim 29

The CAD/CAM system recited in claim 23 wherein only strongly transversal face-edge pairs are used by said means for forming a union of Minkowski sums in translating and sweeping.

Claim 30

The CAD/CAM system recited in claim 19 wherein said computer further comprises means for reducing unbounded polyhedra to a union of a finite number of polyhedra, each of which contains no affine line.

Claim 31

The CAD/CAM system recited in claim 19 wherein said means for forming Minkowski sums forms the Minkowski sum A⊕B of two polyhedra A and B and the polyhedron A is expanded by the polyhedron B to simulate a process of depositing a layer reflecting the characteristics of the polyhedron B on a substrate having the characteristics of the polyhedron A.

Claim 32

The CAD/CAM system recited in claim 26 wherein the simulated deposition process represents a step in semiconductor manufacture and the generation and display of an image by said computer provides a visual representation of the result of said simulated deposition process.

Claim 33

The CAD/CAM system recited in claim 19 wherein said means for forming Minkowski sums forms the Minkowski sum A⊕B of two polyhedra A and B and the polyhedron A is eroded by the polyhedron B, said computer further comprising: first computing means for computing a reflection of the polyhedron B through an origin as B'={-b: bεB}; and second computing means for computing the Minkowski sum A⊕B'.

Claim 34

The CAD/CAM system recited in claim 28 wherein the process of eroding the polyhedron A by the polyhedron B simulates an etching process in semiconductor manufacture and the generation and display of an image by said computer produces a visual representation of said simulated etching process.

Claim 35

The CAD/CAM system recited in claim 19 wherein said means for forming Minkowski sums forms the Minkowski sum A⊕B of two polyhedra A and B and the polyhedron A is eroded by the polyhedron B, said computer further comprising: first computing means for computing a reflection of the polyhedron B through an origin as B'={-b: bεB}; and second computing means for computing the Minkowski sum (A⊕B')⊕B.

Claim 36

The CAD/CAM system recited in claim 19 wherein said means for forming Minkowski sums forms the Minkowski sum A⊕B of two polyhedra A and B and the polyhedron A is closed by the polyhedron B, said computer further comprising: first computing means for computing a reflection of the polyhedron B through an origin as B'={-b: bεB}; and second computing means for computing the Minkowski sum of (A⊕B')⊖B.

Claim 37

The CAD/CAM system recited in claim 19 wherein said means for forming Minkowski sums forms the Minkowski sum A⊕B of two polyhedra A and B and the system determines the translational free space of a polyhedron B in a polyhedron A, said computer further comprising: first computing means for computing a reflection of B through an origin as B'={-b: bεB}; and second computing means for computing the Minkowski sum of A⊖B'.

Claim 38

A computer modeling system including a computer for generating images of geometric objects in three-dimensions, said image generating computer receiving as inputs data generated by a computer based simulation system programmed to simulate a deposition process in semiconductor manufacture, said image generating computer generating an image of said deposition process in semiconductor manufacture wherein a polyhedron A is expanded by a polyhedron B where polyhedron A and polyhedron B are defined as collections of cells, said computer modeling system comprising: data input means for inputting data to said image generating computer from said simulation system which data defines said polyhedrons A and B as a collection of cells which, when combined, form a geometric object; testing means for testing said data to determine transversality of pairs of said cells; means responsive to said testing means for determining if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; means responsive to said testing means for determining if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; summing means comprising first means for forming Minkowski sums of those respective cells from each of said polyhedra A and B which are transversal and second means for forming a union of said Minkowski sums of the cells using Boolean operations to form the Minkowski sum A⊕B of the two polyhedra A and B, at least one of which is bounded, as the union of linear translational sweeps wherein said Minkowski sum is expressed as A⊕B=(A⊕V.sub.B)∪(F.sub.A ⊕E.sub.B)∪(E.sub.A ⊕F.sub.B)∪(V.sub.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 the polyhedrons A and B; and image generating means for generating and displaying on a display device an image of a geometric object represented by said Minkowski sum, said image simulating said deposition process.

Claim 39

A computer modeling system including a computer for generating images of geometric objects in three-dimensions, said image generating computer receiving as inputs data generated by a computer based simulation system programmed to simulate a deposition process in semiconductor manufacture, said image generating computer generating an image of said deposition process in semiconductor manufacture wherein a polyhedron A is expanded by a polyhedron B where polyhedron A and polyhedron B are defined as collections of cells, said computer modeling system comprising: data input means for inputting data to said image generating computer from said simulation system which data defines said polyhedrons A and B as a collection of cells which, when combined, form a geometric object; testing means for testing said data to determine transversality of pairs of said cells; means responsive to said testing means for determining if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; means responsive to said testing means for determining if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; summing means comprising first means for forming Minkowski sums of those respective cells from each of said polyhedra A and B which are transversal and second means for forming a union of said Minkowski sums of the cells using Boolean operations to form the Minkowski sum A⊕B of the two polyhedra A and B, at least one of which is bounded, as the union of linear translational sweeps wherein said Minkowski sum is expressed as A⊕B=(A⊕V.sub.B)∪(F.sub.A ⊕E.sub.B)∪(E.sub.A ⊕F.sub.B)∪(V.sub.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 the polyhedrons A and B; and image generating means for generating and displaying on a display device an image of a geometric object represented by said Minkowski sum, said image simulating said deposition process.

Claim 40

A computer modeling system including a computer for generating images of geometric objects in three-dimensions, said image generating computer receiving as inputs data generated by a computer based simulation system programmed to simulate an etching process in semiconductor manufacture, said image generating computer generating an image of said etching process in semiconductor manufacture wherein a polyhedron A is eroded by a polyhedron B where polyhedron A and polyhedron B are defined as collections of cells, said computer modeling system comprising: data input means for inputting data to said image generating computer from said simulation system which data defines said polyhedrons A and B as a collection of cells which, when combined, form a geometric object; testing means for testing said data to determine transversality of pairs of said cells; means responsive to said testing means for determining if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; means responsive to said testing means for determining if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; computing means for computing the reflection of the polyhedron B through an origin as B'={-b: bεB}; summing means comprising first means for forming Minkowski sums of those respective cells from each of said polyhedra A and B' which are transversal and second means for forming a union of said Minkowski sums of the cells using Boolean operations to form the Minkowski sum A⊕B' of the 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.sub.B')∪(F.sub.A ⊕E.sub.B')∪(E.sub.A ⊕F.sub.B')∪(V.sub.A ⊕B'), where V A , E A and F A , respectively, and V B' , E B' and F B' , respectively, denote the unisons of vertices, edges and faces of the polyhedron A and the reflection B' of the polyhedron B; and image generating means for generating and displaying on a display device an image of a geometric object represented by said Minkowski sum, said image simulating said etching process.

Claim 41

A computer modeling system including a computer for generating images of geometric objects in three-dimensions, said image generating computer receiving as inputs data generated by a computer based simulation system programmed to simulate an etching process in semiconductor manufacture, said image generating computer generating an image of said etching process in semiconductor manufacture wherein a polyhedron A is eroded by a polyhedron B where polyhedron A and polyhedron B are defined as collections of cells, said computer modeling system comprising: data input means for inputting data to said image generating computer from said simulation system which data defines said polyhedrons A and B as a collection of cells which, when combined, form a geometric object; testing means for testing said data to determine transversality of pairs of said cells; means responsive to said testing means for determining if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; means responsive to said testing means for determining if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; computing means for computing the reflection of the polyhedron B through an origin as B'={-b: bεB}; summing means comprising first means for forming Minkowski sums of those respective cells from each of said polyhedra A and B' which are transversal and second means for forming a union of said Minkowski sums of the cells using Boolean operations to form the Minkowski sum A⊕B' of the 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.sub.B')∪(F.sub.A ⊕E.sub.B')∪(E.sub.A ⊕F.sub.B')∪(V.sub.A ⊕B'), where V A , E A and F A , respectively, and V B' , E B' and F B' , respectively, denote the unisons of vertices, edges and faces of the polyhedron A and the reflection B' of the polyhedron B; and image generating means for generating and displaying on a display device an image of a geometric object represented by said Minkowski sum, said image simulating said etching process.

Claim 42

A computer modeling system including a computer for generating images of geometric objects in three-dimensions, said computer simulating translational free space of a robotic gripper within a workcell, said workcell being represented by a polyhedron A and said robotic gripper being represented by a polyhedron B where polyhedron A and polyhedron B are defined as collections of cells, said computer modeling system comprising: data input means for inputting data which defines said polyhedrons A and B as a collection of cells which, when combined, form a geometric object; testing means for testing said data to determine transversality of pairs of said cells; means responsive to said testing means for determining if two cells are nontransversal, and if so, declaring parts of cells in the respective boundaries of said two cells cannot be transversal; means responsive to said testing means for determining if two cells are transversal, and if so, declaring all parts of cells in their respective boundaries are transversal; computing means for computing the reflection of B through an origin as B'={-b: bεB}; summing means comprising first means for forming Minkowski sums of those respective cells from each of said polyhedra A and B' which are transversal and second means for forming a union of said Minkowski sums of the cells using Boolean operations to form the Minkowski sum A⊕B' of the 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.sub.B')∪(F.sub.A ⊕E.sub.B')∪(E.sub.A ⊕F.sub.B')∪(V.sub.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 the polyhedron A and the reflection B' of the polyhedron B; and image generating means for generating and displaying on a display device an image of a geometric object represented by said Minkowski sum, said image simulating the translational free space of the gripper within the workcell.

Claim 43

A computer modeling system including a computer for generating images of geometric objects in three-dimensions, said computer simulating translational free space of a robotic gripper within a workcell, said workcell being represented by a polyhedron A and said robotic gripper being represented by a polyhedron B where polyhedron A and polyhedron B are defined as collections of cells, said computer modeling system comprising: data input means for inputting data which defines said polyhedrons A and B as a collection of cells which, when combined, form a geometric object; testing means for testing said data to determine transversality of pairs of said cells; means responsive to said testing means for determining if two cells are nontransversal, and if so, declaring parts of cells in the respective boundaries of said two cells cannot be transversal; means responsive to said testing means for determining if two cells are transversal, and if so, declaring all parts of cells in their respective boundaries are transversal; computing means for computing the reflection of B through an origin as B'={-b: bεB}; summing means comprising first means for forming Minkowski sums of those respective cells from each of said polyhedra A and B' which are transversal and second means for forming a union of said Minkowski sums of the cells using Boolean operations to form the Minkowski sum A⊕B' of the 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.sub.B')∪(F.sub.A ⊕E.sub.B')∪(E.sub.A ⊕F.sub.B')∪(V.sub.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 the polyhedron A and the reflection B' of the polyhedron B; and image generating means for generating and displaying on a display device an image of a geometric object represented by said Minkowski sum, said image simulating the translational free space of the gripper within the workcell.

Claim 44

The computer recited in claim 35 wherein the polyhedron B is a robotic gripper and the polyhedron A is a workcell containing the gripper and the generation of an image by the computer produces a visual representation of the translational free space of the gripper within the workcell.

Claim 45

In a CAD/CAM system including a computer for generating an image of a geometric object in a space which simulates a physical object being modeled on said CAD/CAM system, a method of generating said image comprising the computer performed steps of: inputting data to said CAD/CAM system which define first and second general polyhedra as a collection of cells which, when combined, form said geometric object, one of said first or second general polyhedra being nontransversal to the other of said first or second polyhedra; testing said data to determine transversality of pairs of said cells; determining from the tested data if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; determining from the tested data if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; computing surrogate cells of the convex polyhedron; using said surrogate cells computed for the convex polyhedron to form Minkowski sums of those pairs of respective cells from each of said first and second general polyhedra which are transversal; forming a union of said Minkowski sums of the cells using Boolean operations to form a Minkowski sum of said first and second general polyhedra; and generating and displaying an image of a geometric object represented by said Minkowski sum of said first and second general polyhedra.

Claim 46

In a CAD/CAM system including a computer for generating an image of a geometric object in a space which simulates a physical object being modeled on said CAD/CAM system, a method of generating said image comprising the computer performed steps of: inputting data to said CAD/CAM system which define first and second general polyhedra as a collection of cells which, when combined, form said geometric object, one of said first or second general polyhedra being nontransversal to the other of said first or second polyhedra; testing said data to determine transversality of pairs of said cells; determining from the tested data if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; determining from the tested data if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; computing surrogate cells of the convex polyhedron; using said surrogate cells computed for the convex polyhedron to form Minkowski sums of those pairs of respective cells from each of said first and second general polyhedra which are transversal; forming a union of said Minkowski sums of the cells using Boolean operations to form a Minkowski sum of said first and second general polyhedra; and generating and displaying an image of a geometric object represented by said Minkowski sum of said first and second general polyhedra.

Claim 47

The method recited in claim 37 wherein the step of forming said Minkowski sums comprises the step of computing a surrogate of said convex polyhedron with respect to a cell.

Claim 48

In a CAD/CAM system including a computer for generating an image of a geometric object in a space which simulates a physical object being modeled on said CAD/CAM system, a method of generating said image comprising the computer performed steps of: inputting data to said CAD/CAM system which define first and second general polyhedra as a collection of cells which, when combined, form said geometric object; testing said data to determine transversality of pairs of said cells; determining from tested data if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; determining from tested data if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; forming Minkowski sum of two polyhedra A and B, the polyhedron B being convex, by forming Minkowski sums of those pairs of respective cells from each of said first and second general polyhedra which are transversal by first sweeping the polyhedron B along edges of polyhedron A to form a first intermediate polyhedron and then sweeping the faces of the polyhedron A along surrogate edges of the polyhedron B, thereby raising the faces of polyhedron A by the polyhedron B and forming a second intermediate polyhedron; forming a polyhedral union of said first and second intermediate polyhedra by forming a union of said Minkowski sums of the cells using Boolean operations to thereby form a Minkowski sum of said first and second general polyhedra; and generating and displaying an image of a geometric object represented by said Minkowski sum of said first and second general polyhedra.

Claim 49

In a CAD/CAM system including a computer for generating an image of a geometric object in a space which simulates a physical object being modeled on said CAD/CAM system, a method of generating said image comprising the computer performed steps of: inputting data to said CAD/CAM system which define first and second general polyhedra as a collection of cells which, when combined, form said geometric object; testing said data to determine transversality of pairs of said cells; determining from tested data if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; determining from tested data if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; forming Minkowski sum of two polyhedra A and B, the polyhedron B being convex, by forming Minkowski sums of those pairs of respective cells from each of said first and second general polyhedra which are transversal by first sweeping the polyhedron B along edges of polyhedron A to form a first intermediate polyhedron and then sweeping the faces of the polyhedron A along surrogate edges of the polyhedron B, thereby raising the faces of polyhedron A by the polyhedron B and forming a second intermediate polyhedron; forming a polyhedral union of said first and second intermediate polyhedra by forming a union of said Minkowski sums of the cells using Boolean operations to thereby form a Minkowski sum of said first and second general polyhedra; and generating and displaying an image of a geometric object represented by said Minkowski sum of said first and second general polyhedra.

Claim 50

A CAD/CAM system including a computer for generating an image of a geometric object in a space which simulates a physical object being modeled on said CAD/CAM system, said computer generating said image on a display device and comprising: input means for inputting data which define first and second general polyhedra as a collection of cells which, when combined, form said geometric object, one of said first or second general polyhedra being convex, the convex polyhedron being nontransversal to the other of said first or second polyhedron; testing means for testing the data to determine transversality of pairs of said cells; means responsive to said testing means for determining if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; means responsive to said testing means for determining if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; means for computing surrogate cells of the convex polyhedron; summing means comprising first means using computed surrogate cells for forming Minkowski sums of those pairs of respective cells from each of said first and second general polyhedra which are transversal and second means for forming a union of said Minkowski sums of the cells using Boolean operations to form a Minkowski sum of said first and second general polyhedra; and image generating means responsive to said summing means for generating and displaying on said display device an image of a geometric object represented by said Minkowski sum of said first and second general polyhedra.

Claim 51

A CAD/CAM system including a computer for generating an image of a geometric object in a space which simulates a physical object being modeled on said CAD/CAM system, said computer generating said image on a display device and comprising: input means for inputting data which define first and second general polyhedra as a collection of cells which, when combined, form said geometric object, one of said first or second general polyhedra being convex, the convex polyhedron being nontransversal to the other of said first or second polyhedron; testing means for testing the data to determine transversality of pairs of said cells; means responsive to said testing means for determining if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; means responsive to said testing means for determining if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; means for computing surrogate cells of the convex polyhedron; summing means comprising first means using computed surrogate cells for forming Minkowski sums of those pairs of respective cells from each of said first and second general polyhedra which are transversal and second means for forming a union of said Minkowski sums of the cells using Boolean operations to form a Minkowski sum of said first and second general polyhedra; and image generating means responsive to said summing means for generating and displaying on said display device an image of a geometric object represented by said Minkowski sum of said first and second general polyhedra.

Claim 52

The CAD/CAM system recited in claim 40 wherein said means for computing surrogate cells computes a surrogate of said convex polyhedron with respect to a cell.

Claim 53

A CAD/CAM system including a computer for generating an image of a geometric object in a space which simulates a physical object being modeled on said CAD/CAM system comprising: input means for inputting data defining first and second general polyhedra as a collection of cells which, when combined, form said geometric object; testing means for testing the data to determine transversality of pairs of said cells; means responsive to said testing means for determining if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; means responsive to said testing means for determining if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; summing means for forming the Minkowski sum A⊕B of two polyhedra A and B, the polyhedron B being convex, said summing means comprising first means for forming Minkowski sums of those pairs of respective cells from each of said first and second general polyhedra which are transversal, said first means including: first sweep means for sweeping the polyhedron B along edges of the polyhedron A to form a first intermediate polyhedron, second sweep means for sweeping faces of the polyhedron A along a surrogate edge of the polyhedron B, thereby raising the faces of polyhedron A by the polyhedron B and forming a second intermediate polyhedron, and second means for forming the polyhedral union of the first and second intermediate polyhedra by forming a union of said Minkowski sums of the cells using Boolean operations to thereby form a Minkowski sum of said first and second general polyhedra; and image generating means responsive to said summing means for generating and displaying on a display device an image of a geometric object represented by said Minkowski sum of said first and second general polyhedra.

Claim 54

A CAD/CAM system including a computer for generating an image of a geometric object in a space which simulates a physical object being modeled on said CAD/CAM system comprising: input means for inputting data defining first and second general polyhedra as a collection of cells which, when combined, form said geometric object; testing means for testing the data to determine transversality of pairs of said cells; means responsive to said testing means for determining if two cells are nontransversal, and if so, declaring pairs of cells in the respective boundaries of said two cells cannot be transversal; means responsive to said testing means for determining if two cells are transversal, and if so, declaring all pairs of cells in their respective boundaries are transversal; summing means for forming the Minkowski sum A⊕B of two polyhedra A and B, the polyhedron B being convex, said summing means comprising first means for forming Minkowski sums of those pairs of respective cells from each of said first and second general polyhedra which are transversal, said first means including: first sweep means for sweeping the polyhedron B along edges of the polyhedron A to form a first intermediate polyhedron, second sweep means for sweeping faces of the polyhedron A along a surrogate edge of the polyhedron B, thereby raising the faces of polyhedron A by the polyhedron B and forming a second intermediate polyhedron, and second means for forming the polyhedral union of the first and second intermediate polyhedra by forming a union of said Minkowski sums of the cells using Boolean operations to thereby form a Minkowski sum of said first and second general polyhedra; and image generating means responsive to said summing means for generating and displaying on a display device an image of a geometric object represented by said Minkowski sum of said first and second general polyhedra.