Method and apparatus for morphing objects by subdividing and mapping portions of the objects

• US 6,366,282 B1
• Filed: 09/08/1998
• Issued: 04/02/2002
• Est. Priority Date: 09/08/1998
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Trika, Sanjeev N.
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US09/149,533
• Time in Patent Office: 1,302 Days
• Field of Search: 345/473, 345/433, 345/422, 345/420, 345/423, 345/425, 345/427, 345/429
• US Class Current: 345/423
• CPC Class Codes: G06T 13/20 3D [Three Dimensional] animation
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2210/44 Morphing
• CPC Class Codes: G06T 3/18 Image warping, e.g. rearranging pixels individually

Abstract

A method and apparatus for morphing between two objects is disclosed. In one embodiment, a first object and a second object are subdivided into pieces wherein said objects contain an equal number of pieces. With said pieces, a mapping between said first object'"'"'s pieces and said second object'"'"'s pieces is created. A morph sequence is then generated based on said mapping, vertices of said first object'"'"'s pieces and corresponding vertices of said second object'"'"'s pieces.

Claims

1. A method of morphing a first object with a second object, the method comprising:

a. randomly dividing non-triangular sides of said first object into a first number of first pieces and randomly dividing non-triangular sides of said second object into a second number of second pieces;

b. based on values of said first number and said second number, randomly subdividing said first pieces and said second pieces until number of said subdivided first pieces equals to number of said subdivided second pieces;

c. duplicating first vertices that are shared by said subdivided first pieces and duplicating second vertices that are shared by said subdivided second pieces;

d. randomly associating said subdivided first pieces to said subdivided second pieces to create a mapping; and

e. generating a morph sequence based on said mapping, vertices of said subdivided first pieces, said duplicated first vertices, corresponding vertices of said subdivided second pieces, and said duplicated second vertices.

2. The method according to claim 1, wherein said first and said second objects can be two-dimensional or three-dimensional polygons or meshes with divisible faces or edges.

3. The method according to claim 2, wherein said first and said second pieces can be triangles or edges.

4. The method according to claim 1, further comprises:

linearly interpolating between said vertices from said first pieces and said corresponding vertices from said second pieces.

5. The method according to claim 4, further comprises:

linearly interpolating between at least one of color attributes, texture attribute, material attribute or spatial attribute of said first object and said second object.

6. An apparatus for morphing a first object with a second object, the apparatus comprising:

a. means for randomly subdividing said first object into a number of first pieces and said second object into a number of second pieces, wherein the number of said first pieces equals to the number of said second pieces;

b. means for duplicating first vertices that are shared by said first pieces and duplicating second vertices that are shared by said second pieces;

c. means for randomly associating said first pieces to said second pieces to generate a mapping;

d. means for generating a morph sequence based on said mapping, vertices of said first pieces, said duplicated first vertices, corresponding vertices of said second pieces and said duplicated second vertices.

7. The apparatus according to claim 6, wherein said first and said second objects can be two-dimensional or three-dimensional polygons or meshes with divisible faces or edges.

8. The apparatus according to claim 7, wherein said first and said second pieces can be triangles or edges.

9. The apparatus according to claim 8, wherein said subdividing means generates said first and said second pieces by subdividing said first and said second objects'"'"' faces.

10. The apparatus according to claim 6, wherein means for generating a morph sequence further comprises:

means for linearly interpolating between said vertices from said first pieces and said corresponding vertices from said second pieces.

11. The apparatus according to claim 10, wherein means for linearly interpolating is performed on at least one of color attributes, texture attribute, material attribute or spatial attribute of said first object and said second object.

12. An apparatus for morphing a first object with a second object, the apparatus comprising:

a. a piece generator to randomly divide non-triangular sides of said first object into a first number of first pieces and randomly divide non-triangular sides of said second object into a second number of second pieces;

b. a subdivider, coupled to said piece generator, based on values of said first number and said second number to randomly subdivide said first pieces and said second pieces until number of said subdivided first pieces equals to number of said subdivided second pieces;

c. a piece matcher, coupled to said subdivider, to map said subdivided first pieces to said subdivided second pieces; and

d. a morph generator, coupled to said subdivider and said piece matcher, to generate a morph sequence based on outcome of said mapping, vertices of said first pieces and corresponding vertices of said second pieces.

13. The apparatus according to claim 12, wherein said first and said second objects can be two-dimensional or three-dimensional objects with divisible faces or edges.

14. The apparatus according to claim 13, wherein said first and said second pieces can be triangles or edges.

15. The apparatus according to claim 14, wherein said piece generator generates said first and said second pieces by subdividing said first and said second objects'"'"' faces.

16. The apparatus according to claim 15, wherein said morph generator further comprises:

a vertex manager to identify shared vertices between said first and said second objects'"'"' divisible faces and to generate additional vertices in the same positions as said identified shared vertices.

17. The apparatus according to claim 12, wherein said piece matcher randomly associates said first pieces with said second pieces.

18. The apparatus according to claim 12, wherein said morph generator further comprises:

an interpolator to linearly interpolate between said vertices from said first pieces and said corresponding vertices from said second pieces.

19. The apparatus according to claim 18, wherein said interpolator linearly interpolates at one of color attribute, texture attribute, material attribute or spatial attribute of said first object and said second object.

20. A machine readable medium including a plurality of instructions readable therefrom, said instructions, when executed by a machine, cause said machine to morph a first object to a second object, comprising:

a. randomly dividing non-triangular sides of said first object into a first number of first pieces and randomly dividing non-triangular sides of said second object into a second number of second pieces;

b. based on values of said first number and said second number, randomly subdividing said first pieces and said second pieces until number of said subdivided first pieces equals to number of said subdivided second pieces;

c. duplicating first vertices that are shared by said subdivided first pieces and duplicating second vertices that are shared by said subdivided second pieces;

d. randomly associating said subdivided first pieces to said subdivided second pieces to create a mapping; and

e. generating a morph sequence based on said mapping, vertices of said subdivided first pieces, said duplicated first vertices, corresponding vertices of said subdivided second pieces, and said duplicated second vertices.

21. The machine readable medium according to claim 20, wherein said first and said second objects can be two-dimensional or three-dimensional objects with divisible faces or edges.

22. The machine readable medium according to claim 21, wherein said first and said second pieces can be triangles or edges.

23. The machine readable medium according to claim 20, wherein said instructions further comprises:

linearly interpolating between said vertices from said first pieces and said corresponding vertices from said second pieces.

24. The machine readable medium according claim 23, wherein said instructions further comprises linearly interpolating between at least one of color attributes, texture attribute, material attribute or spatial attribute of said first object and said second object.