US5850229A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for geometric morphing
Assignee: 3D Systems Inc
•
Filing: 1995-12-15
•
Granted: 1998-12-15
•
Expires: 2015-12-15
Abstract
Abstract A method of geometric morphing between a first object having a first shape and a second object having a second shape. The method includes the steps of generating a first Delaunay complex corresponding to the first shape and a second Delaunay complex corresponding to the second shape and generating a plurality of intermediary Delaunay complexes defined by a continuous family of mixed shapes corresponding to a mixing of the first shape and the second shape. The method further includes the steps of constructing a first skin corresponding to the first Delaunay complex and a second skin corresponding to the second Delaunay complex and constructing a plurality of intermediary skins corresponding to the plurality of intermediary Delaunay complexes. The first skin, second skin and plurality of intermediary skins may be visually displayed on an output device.
Inventors
- 👤 Herbert Edelsbrunner
- 👤 Ping Fu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:41
CPC Classifications
G; G06; G06T; G06T13/00; G06T13/20; G06T2210/00; G06T2210/44; Y; Y10; Y10S; Y10S345/00; Y10S345/949; Y10S345/953; Y10S345/955
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
163 words
A method of geometric morphing between a first object having a first shape and a second object having a second shape comprising the steps in combination: generating a first Delaunay complex corresponding to said first shape and a second Delaunay complex corresponding to said second shape; generating a plurality of intermediary Delaunay complexes defined by a continuous family of mixed shapes corresponding to a mixing of said first shape and said second shape; extracting a plurality of alpha complexes corresponding to said plurality of intermediary Delaunay complexes: generating a first alpha complex corresponding to said first shape and a second alpha complex corresponding to said second shape; constructing a first skin corresponding to said first alpha complex and a second skin corresponding to said second alpha complex; constructing a plurality of intermediary skins corresponding to said plurality of alpha complexes; and visually displaying said first skin, said second skin and one or more of said plurality of intermediary skins on an output device.
Claim 2
Independent Claim
163 words
A method of geometric morphing between a first object having a first shape and a second object having a second shape comprising the steps in combination: generating a first Delaunay complex corresponding to said first shape and a second Delaunay complex corresponding to said second shape; generating a plurality of intermediary Delaunay complexes defined by a continuous family of mixed shapes corresponding to a mixing of said first shape and said second shape; extracting a plurality of alpha complexes corresponding to said plurality of intermediary Delaunay complexes: generating a first alpha complex corresponding to said first shape and a second alpha complex corresponding to said second shape; constructing a first skin corresponding to said first alpha complex and a second skin corresponding to said second alpha complex; constructing a plurality of intermediary skins corresponding to said plurality of alpha complexes; and visually displaying said first skin, said second skin and one or more of said plurality of intermediary skins on an output device.
Claim 3
Dependent Claim
27 words
A method as in claim 1 wherein said first Delaunay complex and said second Delaunay complexes and said plurality of intermediary Delaunay complexes are three dimensional complexes.
Claim 4
Dependent Claim
56 words
A method as in claim 1 further including the steps of: receiving from a measuring device a first point set corresponding to said first object and a second point set corresponding to said second object; and generating said first Delaunay complex from said first point set and said second Delaunay complex from said second point set.
Claim 5
Dependent Claim
49 words
A method as in claim 1 wherein said first shape defines a first 4-dimensional convex polytope, said second shape defines a second 4-dimensional convex polytope, and said plurality of intermediary Delaunay complexes correspond to Minkowksi sums formed between said first 4-dimensional convex polytope and said second 4-dimensional convex polytope.
Claim 6
Dependent Claim
29 words
A method as in claim 1 further including the step of continuously varying the scale degree of detail in said plurality of intermediary skins produced by variable morphing paths.
Claim 7
Dependent Claim
21 words
A method as in claim 1 wherein said continuous family of mixed shapes further depends on at least a third object.
Claim 8
Dependent Claim
18 words
A method as in claim 1 wherein said morphing proceeds with different speed at different parts of space.
Claim 9
Dependent Claim
21 words
A method as in claim 1 wherein said method is carried out by a computer program embodied in a tangible medium.
Claim 10
Dependent Claim
28 words
A method as in claim 8 wherein said tangible medium is selected from the group consisting of a floppy diskette, a hard disk, a CD-ROM and a network.
Claim 11
Dependent Claim
62 words
A method as in claim 1 wherein said method is a machine-executable method in a computer system which executes a computer program, the computer system including a storage unit, a central processing unit, input means for providing input data to the storage unit and central processing unit, and output means for providing discernible indications of actions performed by the central processing unit.
Claim 12
Independent Claim
130 words
A method of transforming a source shape corresponding to a source object to a target shape corresponding to a target object comprising the steps in combination: storing in a memory a first set of data points corresponding to said source shape and a second set of data points corresponding to said target shape; generating a four dimensional simplical complex corresponding to said source shape and said target shape; and extracting one or more mixed shapes from one or more cross-sections of said four dimensional simplical complex, each of said mixed shapes depending on said source shape and said target shape; constructing one or more skins, each of said skins corresponding to one or more of said mixed shapes; and displaying one or more of said skins on an output device.
Claim 13
Independent Claim
130 words
A method of transforming a source shape corresponding to a source object to a target shape corresponding to a target object comprising the steps in combination: storing in a memory a first set of data points corresponding to said source shape and a second set of data points corresponding to said target shape; generating a four dimensional simplical complex corresponding to said source shape and said target shape; and extracting one or more mixed shapes from one or more cross-sections of said four dimensional simplical complex, each of said mixed shapes depending on said source shape and said target shape; constructing one or more skins, each of said skins corresponding to one or more of said mixed shapes; and displaying one or more of said skins on an output device.
Claim 14
Dependent Claim
60 words
A method as in claim 11 wherein said four dimensional simplical complex is a weighted Delaunay complex, and said generating step comprises, in combination: constructing a source Delaunay complex corresponding to said source shape; constructing a target Delaunay complex corresponding to said target shape; generating a collection of 4-simplices corresponding to predetermined simplice types; and adding 3-simplices connecting said 4-simplices.
Claim 15
Dependent Claim
153 words
A method as in claim 11 wherein said four dimensional simplical complex is a weighted Delaunay complex, and said generating step comprises, in combination: constructing a source Delaunay complex corresponding to said source shape; storing said source Delaunay complex in a memory; constructing a target Delaunay complex corresponding to said target shape; storing said target Delaunay complex in said memory; determining connecting simplices of said weighted Delaunay complex that connect said source Delaunay complex and said target Delaunay complex; generating a collection of 4-simplices corresponding to said connecting simplices; storing said collection of 4-simplices in a first and a second data structure, said first data structure representing said collection of said connecting simplices and used for determining adjacancies in said collection of 4-simplices, and said second data structure storing a first, second, third and fourth table corresponding to each dimension and used for generating size curves and unattachment intervals corresponding to said 4-simplices.
Claim 16
Dependent Claim
96 words
A method as in claim 11 wherein said step of extracting a mixed shape comprises, in combination: generating a plurality of tables of k-simplices each containing table items; detecting whether at least one of said k-simplices in said tables is unattached; detecting whether at least one of said k-simplices in said tables has a coface in said mixed shape; detecting whether at least one of said k-simplices in said tables has size less than or equal to a predetermined value; and adding a cross section of at least one of said k-simplices to said mixed shape.
Claim 17
Dependent Claim
20 words
A method as in claim 11 wherein said method is an encoded machine-readable computer program stored on a storage medium.
Claim 18
Dependent Claim
39 words
A method as in claim 11 further including the step of measuring with a measuring device a first set of data points corresponding to said source shape and a second set of data points corresponding to said target shape.
Claim 19
Dependent Claim
28 words
A method as in claim 11 wherein said output device is selected from the group consisting of a video display, a graphic monitor and a virtual reality system.
Claim 20
Dependent Claim
153 words
Apparatus for graphically transforming a source shape to a target shape comprising, in combination: a storage device for storing a first data point set corresponding to said source shape and a second data point set corresponding to said target shape; a memory for storing a series of computer instructions and data structures; a microprocessor for executing said series of computer instructions, said microprocessor generating a first Delaunay complex and a first skin corresponding to said first data point set, said microprocessor generating a second Delaunay complex and a second skin corresponding to said second data point set, said microprocessor generating a plurality of alpha complexes corresponding to the transformation of said source shape to said target shape, and said microprocessor generating a plurality of skins corresponding to said plurality of alpha complexes; an output device for graphically depicting said first skin, said second skin, and one or more of said plurality of skins.
Claim 21
Dependent Claim
153 words
Apparatus for graphically transforming a source shape to a target shape comprising, in combination: a storage device for storing a first data point set corresponding to said source shape and a second data point set corresponding to said target shape; a memory for storing a series of computer instructions and data structures; a microprocessor for executing said series of computer instructions, said microprocessor generating a first Delaunay complex and a first skin corresponding to said first data point set, said microprocessor generating a second Delaunay complex and a second skin corresponding to said second data point set, said microprocessor generating a plurality of alpha complexes corresponding to the transformation of said source shape to said target shape, and said microprocessor generating a plurality of skins corresponding to said plurality of alpha complexes; an output device for graphically depicting said first skin, said second skin, and one or more of said plurality of skins.
Claim 22
Dependent Claim
27 words
Apparatus as in claim 18 wherein said output device is selected from the group consisting of a video display, a graphic monitor and a virtual environment apparatus.
Claim 23
Dependent Claim
23 words
Apparatus as in claim 18 further comprising a measuring device for generating said first data point set and said second data point set.
Claim 24
Dependent Claim
33 words
Apparatus as in claim 20 wherein said measuring device is selected from the group consisting of a nuclear magnetic resonance apparatus, a cat scan apparatus, a digital scanner and a laser range finder.
Claim 25
Dependent Claim
123 words
Apparatus for graphically transforming a first geometric object to a second geometric object comprising, in combination: measuring means for generating a first point set corresponding to said first object and generating a second point set corresponding to said second object; storage means for storing said first data point set and said second data point set; generating means for: (a) generating a first combinatorial representation of said first data point set; (b) generating a second combinatorial representation of said second data point set; (c) defining a motion between said first point set and said second point set and between said first combinatorial representation and said second combinatorial representation; and transforming said first combinatorial representation into said second combinatorial representation in response to said motion.
Claim 26
Dependent Claim
123 words
Apparatus for graphically transforming a first geometric object to a second geometric object comprising, in combination: measuring means for generating a first point set corresponding to said first object and generating a second point set corresponding to said second object; storage means for storing said first data point set and said second data point set; generating means for: (a) generating a first combinatorial representation of said first data point set; (b) generating a second combinatorial representation of said second data point set; (c) defining a motion between said first point set and said second point set and between said first combinatorial representation and said second combinatorial representation; and transforming said first combinatorial representation into said second combinatorial representation in response to said motion.
Claim 27
Dependent Claim
25 words
Apparatus as in claim 22 wherein said first combinatorial representation is a first alpha complex and said second combinatorial representation is a second alpha complex.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-14 | 2002-06-15 | 2002-12-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-14 | 2006-06-15 | 2006-12-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-14 | 2010-06-15 | 2010-12-15 | $7700.00 | Window Closed / Lapsed |