Animation system which employs scattered data interpolation and discontinuities for limiting interpolation ranges

• US 5,680,531 A
• Filed: 07/02/1993
• Issued: 10/21/1997
• Est. Priority Date: 07/02/1993
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Chen, Shenchang Eric, Williams, Lance, Litwinowicz, Peter C.
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): Burwell, Joseph R.
• Application Number:
  US08/087,210
• Time in Patent Office: 1,572 Days
• Field of Search: 395/152, 395/136, 395/141-143, 395/128-130, 395/173
• US Class Current: 345/473
• CPC Class Codes: G06T 13/80 2D [Two Dimensional] animation, e.g. using sprites

Abstract

An animation system employs scattered data interpolation to provide fluent animation of still images. Discontinuities, such as cuts and holes, can be established within an image, to limit the range over which interpolation is carried out for a given deformation of a feature in the image, and thereby refine the control exerted by animated features. The amount of computational time and effort required to interpolate the change from one frame of an animation to the next is reduced by concentrating computation of the deformed image on areas of change. Computational requirements are further reduced by taking advantage of frame-to-frame coherence.

Claims

1. A method for producing an animation by generating a sequence of deformed images, comprising the steps of:

displaying an image on a display device;

defining discontinuities on said image;

displacing one or more features on the displayed image in correspondence with desired deformation of the image that is to occur from one image to a subsequent image in the sequence;

interpolating new positions for portions of the displayed image other than the displaced features to produce a deformed image;

limiting the portions of the displayed image that undergo interpolation in correspondence with said discontinuities; and

displaying the deformed image as a subsequent image in the sequence on said display device.

2. The method of claim 1 wherein a scattered data interpolation technique is used in said interpolating step.

3. The method of claim 2 wherein said scattered data interpolation technique employs a thin-plate spline.

4. The method of claim 1 wherein said interpolation is carried out with respect to locations on a grid, and wherein said grid is bounded by said discontinuities.

5. The method of claim 4 wherein said grid has a first resolution, and further including the step of repeating said interpolation with a second grid having a resolution that is different from said first resolution.

6. The method of claim 1 wherein at least one of said features comprises a point on the displayed image.

7. The method of claim 1 wherein at least one of said features comprises a line on the displayed image.

8. The method of claim 7 wherein said line is curved.

9. The method of claim 1, wherein said interpolating step comprises the steps of:

(i) correlating said features to positions on a grid;

(ii) assigning values to the grid positions, with the values for grid positions which correspond to said features being respectively related to the displacements of the features;

(iii) determining residual values for the grid positions which do not correspond to said features;

(iv) identifying the residual value of greatest magnitude;

(v) relaxing the value for the grid position having the greatest magnitude, by adding its residual value to its assigned value;

(vi) updating the residual values for a predetermined number of grid positions near the grid position where said relaxation takes place;

(vii) identifying the updated residual value having the greatest magnitude; and

(viii) iteratively repeating steps (v)-(vii).

10. The method of claim 9 wherein steps (v)-(vii) are repeated a predetermined number of times, and said interpolation includes the further step of iteratively repeating steps (iv)-(viii) a predetermined number of times.

11. The method of claim 10 wherein said grid has a first resolution, and further including the step of repeating said interpolation with a second grid having a resolution that is different from said first resolution.

12. A method for animating an image, comprising the steps of:

displaying one frame of an image on a display device;

defining control features on said image;

correlating said control features to positions on a grid;

defining discontinuities in said image;

determining displaced locations for at least some of said control features in a subsequent frame of animation;

interpolating said image on said grid by means of a thin-plate spline interpolation method, to produce a deformed image;

limiting the positions on said grid over which said interpolation is carried out in accordance with said discontinuities; and

displaying the deformed image on said display device as a subsequent frame of the animation.

13. A method for animating an image, comprising the steps of:

displaying an image on a display device;

defining control features on said image;

correlating said control features to positions on a grid;

determining displaced locations for at least some of said control features, corresponding to desired deformation of the image;

interpolating said image, to produce a deformed image, by;

(i) assigning values to the grid positions, with the values for grid positions which correspond to said control features being respectively related to the displacements of the control features;

(ii) determining residual values for the grid positions which do not correspond to said control features;

(iii) identifying the residual value of greatest magnitude;

(iv) relaxing the value for the grid position having the greatest magnitude, by adding its residual value to its assigned value;

(v) updating the residual values for a predetermined number of grid positions near the grid position where said relaxation takes place;

(vi) identifying the updated residual value having the greatest magnitude; and

(vii) iteratively repeating steps (iv)-(vi); and

displaying the deformed image on said display device as a subsequent frame of the animation.

14. The method of claim 13 wherein steps (iv)-(vi) are repeated a predetermined number of times, and said interpolation includes the further step of iteratively repeating steps (iii)-(vii) a predetermined number of times.

15. The method of claim 14 wherein said grid has a first resolution, and further including the step of repeating said interpolation with a second grid having a resolution that is different from said first resolution.

16. The method of claim 13 further including the steps of defining discontinuities in said image, and limiting the positions on said grid over which said interpolation is carried out to correspond to said defined discontinuities.

17. A system for animating an image, comprising:

means for displaying successive instances of an image to to thereby provide an animation sequence;

means for identifying displacements of features of said image that are to occur during the animation sequence;

means for defining discontinuities in said image;

means for interpolating said image over a limited region of the image defined by said discontinuities to conform the image to the displaced features; and

means for causing the conformed image to be displayed on said display means as a successive instance of the image in said animation sequence.

18. The system of claim 17 wherein said interpolating means employs a thin-plate spline as an interpolant.

19. The system of claim 17 wherein said interpolating means iteratively interpolates said image over a plurality of grids in succession, which have respectively different resolutions.

20. A computer-readable storage medium containing a program which executes the following steps:

displaying an image on a display device;

recording displacement of features of said image that are to occur during animation;

establishing discontinuities in said image;

interpolating said image over a limited region of the image defined by said discontinuities to conform the image to displaced features; and

displaying the interpolated image on the display device.

21. The storage medium of claim 20 wherein said interpolating step is carried out by means of a scattered data interpolation technique.

22. The storage medium of claim 21 wherein said interpolating step is carried out with the use of a thin-plate spline as an interpolant.

23. The storage medium of claim 20 wherein said interpolation is carried out with respect to locations on a grid, and wherein said grid is bounded by said discontinuities.

24. The storage medium of claim 20 wherein said grid has a first resolution, and further including the step of repeating said interpolation with a second grid having a resolution that is different from said first resolution.

25. A computer readable storage medium containing a program which executes the following steps:

displaying a frame of an image on a display device;

recording control features on said image;

correlating said control features to positions on a grid;

defining discontinuities in said image;

recording displaced locations for at least some of said control features in a subsequent frame of animation;

interpolating said image on said grid by means of a thin-plate spline interpolation method, to produce a deformed image;

limiting the positions on said grid over which said interpolation is carried out in accordance with said discontinuities; and

displaying the deformed image on the display device as a subsequent frame of the animation.