Method and apparatus for differential object modeling using automatically generated constructive solid geometry (CSG) through an evolutionary process
US5729254A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Dec 27, 1995 |
| Grant date | Mar 17, 1998 |
| Priority date | — |
| Expiry date | Dec 27, 2015 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T17/10
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A system for creating a constructive solid geometry (CSG) representation of bjects in bit map or voxel form iteratively creates, mutates and optimizes a population of potential CSG representations of the object. The system includes a first part which randomly generates and revises a population of CSG representations. 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 modified through an evolutionary process to improve the CSG representation of the object. Trees are randomly mutated 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 tree better represents the object, then the old tree is replaced with the new tree. Mutations continue until no further improvements are obtained. The population may be periodically reinitialized by replacing the worst trees with the best trees. A second part of the system locally optimizes each tree upon creation or mutation. Optimization includ…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.