Method, apparatus, and computer program product for geometric warps and deformations

• US 6,608,631 B1
• Filed: 05/02/2000
• Issued: 08/19/2003
• Est. Priority Date: 05/02/2000
• Status: Expired due to Term

• Current Assignee: Pixar Animation Studios Incorporated (The Walt Disney Company)
• Original Assignee: Pixar Amination Studios
• Inventors: Milliron, Timothy S.
• Primary Examiner(s): Brier, Jeffery
• Assistant Examiner(s): Chung, Daniel J
• Application Number:
  US09/563,660
• Time in Patent Office: 1,204 Days
• Field of Search: 345/647, 345/629, 345/639, 345/640, 345/649, 345/660, 345/648, 345/646, 345/619
• US Class Current: 345/647
• CPC Class Codes: G06T 13/00 Animation
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 17/30 Polynomial surface description
• CPC Class Codes: G06T 2210/16 Cloth
• CPC Class Codes: G06T 2210/21 Collision detection, intersection
• CPC Class Codes: G06T 2210/44 Morphing

Abstract

Techniques for geometric deformations in computer graphics are described, including a flexible and general modular methodology for constructing, analyzing, and evaluating geometric warps and deformations. Described techniques include establishing a set of source/target features (and related information) or parameter set for controlling deformation of a graphical model; a set of strength fields are established for controlling how strongly the transformation caused by the mapping of source feature to target feature will be applied to model points. A set of weighting fields modulates the influence of multiple source/target feature mappings on model points. Also described are variations on this technique that allow achieving results similar to conventional methods and additional functionality.

Claims

1. A computer-implemented method for generating graphical warps or deformations through transformation of an undeformed model to a deformed model, said computer-implemented method comprising:

receiving said undeformed model and a set of feature specifications each of said set of feature specifications comprising a source feature, a target feature, and related deformation parameters;

receiving a set of transformations corresponding to said set of feature specifications and for mapping said source feature to said target feature in each of said set of feature specifications;

receiving a set of strength fields corresponding to said set of feature specifications and defined over said undeformed model for scaling the magnitude of each of said set of transformations, establishing a set of scaled transformations;

receiving a set of weighting fields corresponding to said set of feature specifications and defined over said undeformed model for determining the relative influence of said set of scaled transformations;

computing a sum of said set of scaled transformations weighted by said set of weighting fields, for deforming said undeformed model to generate said deformed model; and

returning said deformed model.

2. The computer-implemented method according to claim 1 wherein at least one of said set of feature specifications is continuous and has corresponding parameterized strength field, transformation, and weighting field, and further comprising:

receiving a sampling function for discretizing said parameterized transformation and sampling said strength field and said weighting field;

computing a discretized transformation, a sampled strength field, and a sampled weighting field with said sampling function; and

wherein said step of computing a sum of said set of scaled transformations employs said discretized transformation, said sampled strength field, and said sampled weighting field.

3. The computer-implemented method according to claim 2 wherein said set of feature specifications, said set of transformations, said set of strength fields, said set of weighting fields, and said sampling function are received by a combined function that computes said discretized transformation, said sampled strength field, and said sampled weighting field.

4. The computer-implemented method according to claim 1 wherein:

said set of feature specifications comprises a plurality of line segment features;

said set of transformations corresponding to said plurality of line segment features map source coordinate frames to target coordinate frames; and

said set of weighting fields corresponding said plurality of line segment features fall off with distance.

5. The computer-implemented method according to claim 4 wherein:

said set of weighting fields give influence to line segment features in said plurality of line segment features in relation to their length.

6. The computer-implemented method according to claim 4 wherein:

said source coordinate frames comprise a constrained basis vector and an unconstrained basis vector and wherein said unconstrained basis vector is selected responsive to a weighted sum of the vectors perpendicular to the constrained basis vector for each of said target coordinate frames.

7. The computer-implemented method according to claim 1 wherein:

said set of feature specifications comprises control points in an at least two dimensional lattice;

said at least two dimensional lattice having an associated local coordinate system;

said set of weighting fields corresponding to said control points comprise Bernstein polynomials with arguments comprising points of said undeformed model represented in said local coordinate system.

8. The computer-implemented method according to claim 1 wherein:

said set of feature specifications comprises an oriented point in an least two dimensional lattice;

said at least two dimensional lattice having an associated local coordinate system;

the transformation in said set of transformations corresponding to said oriented maps a source coordinate frame to a target coordinate frames; and

said set of weighting fields corresponding to said oriented points comprise Bernstein polynomials with arguments comprising points of said undeformed model represented in said local coordinate system.

9. The computer-implemented method according to claim 1 wherein:

said set of transformations comprises a geometrically parameterized transformation.

10. The computer-implemented method according to claim 9 wherein:

said set of transformations comprises plural geometrically parameterized transformations; and

said set of strength fields modulate said plural geometrically parameterized transformations.

11. The computer-implemented method according to claim 10 wherein:

said set of weighting fields blend said plural geometrically parameterized transformations.

12. The computer-implemented method according to claim 1 wherein:

at least one of said set of feature specifications comprises a source curve and a target curve;

corresponding members of said set of transformations comprise a composition of a translation from points along said source curve to points along said target curve, a rotation taking the tangent at said points along said source curve to the tangent at said points along said target curve, and a scale centered at said points along said source curve;

corresponding members of said set of strength fields comprise a falloff function having a domain and a range and monotonically decreasing over said range, and wherein over at least a portion of said domain arguments of said falloff function comprise a distance between points of said undeformed model and point along said source curve and a rate of falloff for said distance;

corresponding members of said set of weighting fields comprise a scaled displacement function having a domain and a range, wherein for at least a portion of said domain said scaled displacement function comprises a power of the displacement of elements of said undeformed model by said corresponding members of said set of transformations.

13. The computer-implemented method according to claim 12 wherein said scaled displacement function comprises a power of the displacement of elements of said undeformed model by said corresponding members of said set of transformations for the entirety of said domain.

14. The computer-implemented method according to claim 1 wherein:

said undeformed model comprises control vertices of a fine surface model; and

at least one of said set of feature specifications comprise;

a source position and a target position of one or more vertices of a coarse deformation mesh configured for deformation of said fine surface model, and

a set of edges incident on said one or more vertices.

15. The computer-implemented method according to claim 14 wherein:

corresponding members of said set of transformations comprise a composition of;

a translation mapping said source position to said target position, and

at least an approximation of a mapping of said set of edges in said undeformed model to said deformed model.

16. The computer-implemented method according to claim 15 wherein:

corresponding members of said set of weighting fields comprise a falloff function, said falloff function substantially zero at a distal end of each of said set edges incident on said one or more vertices, and said falloff function substantially at its maximum value for arguments proximate to said source positions of said control vertices.

17. The computer-implemented method according to claim 1 wherein:

said undeformed model comprises control vertices of a surface for deformation, wherein source and target features are parameterized as a function that returns a tuple comprising a point and a vector normal to said point;

at least one of said set of feature specifications comprises a source region and a target region;

corresponding members of said set of transformations comprise a composition of;

a translation mapping points on said source region to points on said target region, and

a rotation taking said vector normal to said points on said source region to said vector normal to said points on said target region of said surface.

18. The computer-implemented method according to claim 17 wherein corresponding members of said set of strength fields localize the effect of said set of transformations around said source surface region.

19. The computer-implemented method according to claim 18 wherein:

corresponding members of said set of weighting fields decrease monotonically with corresponding members of said set of strength fields and wherein said set of weighting fields decrease responsive to;

a distance between control vertices of said surface for deformation and said point on said surface, and

a range for limiting the region of said weighting field, and

a rate for controlling the rate of decrease of said weighting field.

20. The computer-implemented method according to claim 1 wherein:

one of said set of feature specifications act with substantially full strength across said undeformed model and corresponding the member of said set of weighting fields dominates weighting contributions of other members of said set of weighting fields.