Apparatus and method for geometric morphing

• US 5,850,229 A
• Filed: 12/15/1995
• Issued: 12/15/1998
• Est. Priority Date: 12/15/1995
• Status: Expired due to Term

• Current Assignee: 3D Systems, Inc. (3D Systems Corporation)
• Original Assignee: Raindrop Geomagic, Inc. (3D Systems Corporation)
• Inventors: Edelsbrunner, Herbert, Fu, Ping
• Primary Examiner(s): Feild, Joseph H.
• Application Number:
  US08/570,614
• Time in Patent Office: 1,096 Days
• Field of Search: 395/123, 395/125, 395/127, 395/128, 395/139, 395/173, 395/175, 395/955, 395/953, 395/952, 345/122, 345/423, 345/425, 345/427, 345/428, 345/439, 345/473, 345/475, 345/474, 345/952, 345/953, 345/955, 382/190, 382/199, 382/201, 382/205, 382/206, 382/215, 382/216, 382/256, 382/285, 382/286, 382/288, 382/291, 382/294, 382/299, 382/276
• US Class Current: 345/473
• CPC Class Codes: G06T 13/20 3D [Three Dimensional] animation
• CPC Class Codes: G06T 2210/44 Morphing
• CPC Class Codes: Y10S 345/953 Geometric processing
• CPC Class Codes: Y10S 345/955 Morphing

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. A method as in claim 1 wherein said continuous family of mixed shapes further depends on at least a third object.

7. A method as in claim 1 wherein said morphing proceeds with different speed at different parts of space.

8. A method as in claim 1 wherein said method is carried out by a computer program embodied in a tangible medium.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. A method as in claim 11 wherein said method is an encoded machine-readable computer program stored on a storage medium.

16. 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.

17. 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.

18. 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.

19. 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.

20. Apparatus as in claim 18 further comprising a measuring device for generating said first data point set and said second data point set.

21. 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.

22. 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.

23. 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.