Patent US5006218A successfully refreshed from Google Patents.
Patent US5760786A successfully refreshed from Google Patents.
US5760786A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Simultaneous constructive solid geometry (CSG) modeling for multiple objects
Assignee: Benhov GmbH LLC
•
Filing: 1995-12-27
•
Granted: 1998-06-02
•
Expires: 2015-12-27
Abstract
Abstract A system for simultaneously creating similar constructive solid geometry G) representations for multiple objects in bit map or voxel form iteratively creates, mutates and optimizes a population of potential CSG representations of the objects. The system includes a first part which creates and revises two identical populations of CSG representations. Initially, the populations are randomly generated. Thus, each CSG tree includes a random number of primitives of different types, sizes and positions. The primitives are randomly organized in a tree structure which includes randomly selected boolean operators at the nodes. The trees are then modified through an evolutionary process to improve the CSG representations of the objects. Corresponding trees in each population are randomly mutated in the same manner to form new trees. Mutations can include (1) changes in types of primitives, (2) changes in a subtree structure, (3) addition of new subtrees, and (4) deletions of subtrees. If the new trees better represents the objects, then the old trees are replaced with the new trees. Mutations continue until no further improvements are obtained.
Inventors
- 👤 Joseph Marks
- 👤 Sarah Gibson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 08:24
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/10
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
94 words
A method for generating a constructive solid geometry (CSG) representation of multiple objects comprising the steps of: similarly mutating one of each of a set of pluralities of CSG trees to create new CSG trees in each set, each set of CSG trees corresponding to one of the objects; locally optimizing said new trees with respect to each object; and replacing said one of each set of said pluralities of trees with said new trees, if said new trees represent said objects better than said one of each set said plurality of CSG trees.
Claim 2
Independent Claim
94 words
A method for generating a constructive solid geometry (CSG) representation of multiple objects comprising the steps of: similarly mutating one of each of a set of pluralities of CSG trees to create new CSG trees in each set, each set of CSG trees corresponding to one of the objects; locally optimizing said new trees with respect to each object; and replacing said one of each set of said pluralities of trees with said new trees, if said new trees represent said objects better than said one of each set said plurality of CSG trees.
Claim 3
Dependent Claim
23 words
The method of claim 1, wherein said mutating step includes randomly mutating a random one of said sets of pluralities of CSG trees.
Claim 4
Dependent Claim
47 words
The method of claim 1, further comprising before said mutating step, the steps of: generating sets of pluralities of random CSG trees as said sets of pluralities of CSG trees; and locally optimizing each of said plurality of random CSG trees with respect to a corresponding object.
Claim 5
Dependent Claim
49 words
The method of claim 1, wherein said mutating step includes one of changing a type of primitive in said one tree, changing a subtree structure in said one tree, adding a subtree in place of a primitive in said one tree, and deleting a subtree of said one tree.
Claim 6
Dependent Claim
54 words
The method of claim 1, further comprising the step of: replacing a first portion of said sets of pluralities of trees with a second portion of said sets of pluralities of trees, wherein said first portion includes trees which least represent said object, and said second portion includes trees which best represent said object.
Claim 7
Dependent Claim
66 words
The method of claim 1, further comprising the step of determining a degree to which a set of corresponding trees, one tree being from each set of pluralities of trees, represents said objects based upon an area of each object not covered by a respective tree, an area of said respective trees which does not cover said objects, and a number of primitives in the trees.
Claim 8
Dependent Claim
28 words
The method of claim 1, further comprising before said mutating step, the step of scanning at least one object to determine dimensions of said at least one object.
Claim 9
Dependent Claim
37 words
The method of claim 1, wherein said locally optimizing step includes the steps of: adjusting a position of a primitive in said one tree; adjusting a size of said primitive; and adjusting an orientation of said primitive.
Claim 10
Independent Claim
102 words
An apparatus for determining a constructive solid geometry (CSG) representation of a plurality of objects comprising: mutating means for similarly mutating one of each of a set of pluralities of CSG trees to create new CSG trees in each set, each set of CSG trees corresponding to one of the objects; optimizing means for locally optimizing said new trees with respect to each object; and replacement means for replacing said one of each set of said pluralities of trees with said new trees, if said new trees represents said objects better than said one of each set said plurality of CSG trees.
Claim 11
Independent Claim
102 words
An apparatus for determining a constructive solid geometry (CSG) representation of a plurality of objects comprising: mutating means for similarly mutating one of each of a set of pluralities of CSG trees to create new CSG trees in each set, each set of CSG trees corresponding to one of the objects; optimizing means for locally optimizing said new trees with respect to each object; and replacement means for replacing said one of each set of said pluralities of trees with said new trees, if said new trees represents said objects better than said one of each set said plurality of CSG trees.
Claim 12
Dependent Claim
26 words
The apparatus of claim 9, wherein said mutating means randomly mutates a random set of corresponding trees in each set of said pluralities of CSG trees.
Claim 13
Dependent Claim
39 words
The apparatus of claim 10, wherein said optimizing means includes: means for adjusting a position of a primitive in said one tree; means for adjusting a size of said primitive; and means for adjusting an orientation of said primitive.
Claim 14
Dependent Claim
48 words
The apparatus of claim 9, further comprising: tree generation means for generating a plurality of random CSG trees as said sets of pluralities of CSG trees; and initial optimizing means for locally optimizing each set of said pluralities of random CSG trees with respect to a corresponding object.
Claim 15
Dependent Claim
42 words
The apparatus of claim 9, wherein said mutating means includes at least one of: means for changing a primitive in said one tree, means for changing an operator in said one tree, and means for replacing a subtree of said one tree.
Claim 16
Dependent Claim
53 words
The apparatus of claim 9, further comprising means for replacing a first portion of said sets of pluralities of trees with a second portion of said sets of pluralities of trees, wherein said first portion includes trees which least represent said objects, and said second portion includes trees which best represent said objects.
Claim 17
Dependent Claim
64 words
The apparatus of claim 9, further comprising: means for determining a degree to which a set of corresponding trees represents said objects based upon an area of said objects not covered by a respective one of said corresponding trees, an area of a respective one of said corresponding trees which does not cover said respective object, and a number of primitives in the tree.
References Cited (Backward Citations)
US5459829A
Cited
US5561752A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-06-01 | 2001-12-01 | 2002-06-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-06-01 | 2005-12-01 | 2006-06-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-06-01 | 2009-12-01 | 2010-06-02 | $7700.00 | Window Closed / Lapsed |