Shaping geometric objects by cumulative translational sweeps

• US 4,785,399 A
• Filed: 03/03/1987
• Issued: 11/15/1988
• Est. Priority Date: 03/03/1987
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rajan, Vadakkedathu T., Koppelman, George M., Evans, Roger C.
• Primary Examiner(s): NOT, DEFINED
• Application Number:
  US07/021,388
• Time in Patent Office: 623 Days
• Field of Search: 364/200, 364/300, 364/900, 364/419, 364/512
• US Class Current: 715/810
• CPC Class Codes: B29C 64/129 characterised by the energy source therefor, e.g. by global irradiation combined with a mask
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

Cumulative translational sweeps are used to shape geometric objects in a computer model, and they permit display of the resulting changes in shape in the object modelled, and control of processes involving the object modelled. If the geometric object is polyhedral, the cumulative translational sweeps, by creating additional facets, effect selective rounding along model edges and around model vertices. This permits computer modelling of the growth of layers, encompassing in addition to flat surface growth, growth with rounding around corners and over obstacles. Such growth occurs in the manufacture of semiconductors. Modelling a change in a solid structure in stages of growth (or shrinking) and of rounding, as might take place during processing of integrated circuits is achieved by controlled sweep sequences that sweep the structure a finite number of times in accordance with a rayset and stipulated parameters of shape, balance, convexity/concavity, degree of faceting, and memory limitation. The cumulative translational sweep (CTS) is applied in combination with Boolean operations to simulate growth and shrinking over the boundary regions of polyhedral models. By creating additional facets, it effects stipulated selective or global rounding effects along model edges and around model vertices. Such sweeps are examined in terms of Minkowski sums--of the geometric objects that are swept, with structuring geometric shapes that are convex polyhedron from the zonotope subclass of the mathematical family of objects known as polytopes.

Claims

1. A method for shaping a geometric model, comprising the following steps performed by a computer of:

(a) providing for entry of a parameterized operational rayset of n rays, which rays determine a structuring geometric shape;

(b) applying to the geometric model a translational sweep corresponding to a first ray of said parameterized operational rayset, resulting in a sweptspace for the sweep;

(c) iteratively applying to the sweptspace of the respectively preceding sweep a translational sweep corresponding to a next ray of said parameterized operational rayset, until a sweep corresponding to ray n has been applied, resulting in a final sweptspace which is a desired shaped geometric model; and

(d) providing the shaped geometric model to a utilization device.

2. A method for shaping a geometric model, comprising the following steps performed by a computer of:

(a) providing for entry of an operational rayset of n rays, which rays determine a structuring geometric shape;

(b) providing for entry of at least one of initializing parameters scale, balance, convexity/concavity (CMODE), degree of faceting, and memory limitation, for said operational rayset;

(c) combining said operational rayset and said parameters, resulting in a parameterized operational rayset;

(d) applying to the geometric model a translational sweep corresponding to a first ray of said parameterized operational rayset, resulting in a sweptspace for the sweep;

(e) iteratively applying to the sweptspace of the respectively preceding sweep a translational sweep corresponding to a next ray of said parameterized operational rayset, until a sweep corresponding to ray n has been applied, resulting in a final sweptspace which is a desired shaped geometric model; and

(f) providing the shaped geometric model to a utilization device.

3. A method for shaping a geometric model, according to claim 2, in which said providing for entry of initializing parameters includes providing for user entry of scaling values that control directional extent of swell (growth or shrinkage) of said operational rayset in independent directions.

4. A method for shaping a geometric model, according to claim 2, in which said providing for entry of initializing parameters provides for user entry of a balance parameter that determines relative positioning between an unshaped geometric model and the shaped geometric model corresponding to said operational rayset.

5. A method for shaping a geometric model, according to claim 2, in which said providing for entry of initializing parameters includes providing for user entry of a convexity/concavity (CMODE) that controls whether shaping produced by said operational rayset effects rounding or retains sharpness in regions of the geometric model which are locally convex or locally concave.

6. A method for shaping a geometric model, according to claim 2, in which said providing for entry of initializing parameters includes providing for user entry of parameters to control degree of faceting of the geometric model.

7. A method for shaping a geometric model, according to claim 2, in which at least one of said providing for entry steps comprises providing for entry of default values.

8. A method for shaping a geometric model according to claim 2, wherein said iteratively applying a translational sweep includes canvassing direction-of-face indicators to develop a sweep-direction-facecount along the direction of sweep and to develop a contra-sweep-facecount along a direction opposite the direction of sweep, comparing the sweep-direction-facecount and contra-sweep-facecount, selectively reversing the direction of sweep if the sweep-direction-facecount is greater than the contra-sweep-facecount, resulting in a congruent-but-translated sweptspace from a simpler procedure;

and performing a translation operation to correct for the translated sweptspace.

9. A method for shaping a geometric model, according to claim 2, wherein said iteratively applying a translational sweep includes limited memory of the sweptspace of the respectively preceding sweep, and said providing for entry of initializing parameters includes providing for user entry of values for memory limitation.

10. A user-interactive computer method for developing a parameterized operational rayset for shaping a geometric model, comprising the following steps performed by a computer of:

(a) providing an initial rayset entry menu including user stipulation of at least one of entry of rayset from library, entry of rayset by defaults, and entry of rayset by user, to provide a rayset of n rays that determines a structuring geometric shape;

(b) providing a parameters stipulation menu including user stipulation of at least one of entry of parameters by default, and entry of parameters by user, to provide parameters of at least one of scale, balance, convexity/concavity (CMODE), degree of faceting and memory limitation for said operational rayset;

(c) combining said operational rayset and said parameters, resulting in a parameterized operational rayset;

(d) providing a demonstration stipulation menu including user stipulation of at least one of selection of a demonstration geometric model by defaults and selection of a demonstration geometric model by the user;

(e) applying to said demonstration geometric model a translational sweep corresponding to a first ray of said parameterized operational rayset, resulting in a sweptspace for the sweep;

(f) iteratively applying to the sweptspace of the respectively preceding sweep a translational sweep corresponding to a next ray of said parameterized operational rayset, until a sweep corresponding to ray n has been applied, resulting in a final sweptspace which is the demonstration geometric model shaped in accordance with a currently developed parameterized operational rayset;

(g) displaying said shaped demonstration geometric model for user acceptance; and

(h) providing an acceptance stipulation menu including user stipulation of at least one of forwarding the developed parameterized operational rayset to a utilization device, and of continuing rayset development by return to a previous step (a-e) for repeating menu steps with changes of user stipulations.

11. A method for developing a parameterized operational rayset for shaping a geometric model, according to claim 10, in which said providing an initial rayset entry menu includes user stipulations for selecting a structuring zonotope and collapsing said zonotope to provide defined rays.

12. A method for developing a parameterized operational rayset for shaping a geometric model, according to claim 10, in which said providing a parameters stipulation menu includes user stipulations for selection of a balance parameter.

13. A method for developing a parameterized operational rayset for shaping a geometric model, according to claim 10, in which said providing a parameters stipulation menu includes user stipulations for selection of scaling values that control directional extent of swell (growth or shrinkage) of said operational rayset in independent directions.

14. A method for developing a parameterized operational rayset for shaping a geometric model, according to claim 10, in which said providing a parameters stipulation menu includes user stipulations for selection of CMODE.

15. A method for developing a parameterized operational rayset for shaping a geometric model, according to claim 10, in which said providing a parameters stipulation menu includes user stipulations for selection of degree of faceting.

16. A method for developing a parameterized operational rayset for shaping a geometric model, according to claim 10, in which said providing a parameters stipulation menu includes user stipulations for selection of memory limitation.

17. A method for developing a parameterized operational rayset for shaping a geometric model according to claim 10, in which said providing a demonstration stipulation menu includes user stipulations for selection from a series of simple objects of increasing number of dimensions.

18. A method for developing a parameterized operational rayset for shaping a geometric model, according to claim 17, in which said providing a demonstration stipulation menu includes user stipulations for selection from a series of simple objects of increasing number of dimensions, including point, line segment, rectangle, and rectangular right prism.

19. A method for developing a parameterized operational rayset for shaping a geometric model, according to claim 10, in which said providing an initial rayset entry menu includes automatic combination of colinear rays.