Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
1998-04-08
2002-03-26
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S619000, C345S629000, C345S419000, C345S418000, C345S672000
Reexamination Certificate
active
06362833
ABSTRACT:
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, a s it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND
1. Field
The present invention relates generally to computer graphics and, more specifically, to shape transformation of two-dimensional and three-dimensional objects on a computer display.
2. Description of Related Art
In recent years, image processing techniques, popularly known as “morphing,” have achieved widespread use in the entertainment industry. Morphing involves the transformation of one image into another image or from one model into another model. Morphing operations can be performed to transform one two-dimensional (2-D) image into another 2-D image, to transform one 2-D model into another 2-D model, or to transform one three-dimensional (3-D) model into another 3-D model. These techniques specify some operation that maps points from one image or model onto points of the other image or model, and then simultaneously interpolate the color and position of corresponding points to generate intermediate images or models. When viewed in sequence, these intermediate images produce an animation of the first image or model changing into the second image or model. Variations of these techniques have been used to create special effects for television commercials, music videos, movies, and web pages on the World Wide Web.
Morphs are typically restricted to 2-D images, primarily because a realistic transition between two-dimensional (2-D) and three-dimensional (3-D) models is difficult to specify. However, such specifications might be valuable because the resulting morph can be viewed from arbitrary viewpoints in arbitrary settings, can be arbitrarily scaled and placed, and provides greater compression and realism.
There are at least two existing approaches for defining a morph between two 3-D models, each of which may be adapted for 2-D models. The first approach is described in “Shape Transformation For Polyhedral Objects”, by James R. Kent, et al., Computer Graphics, Vol. 26, No. 2, July, 1992. Kent, et al. describes a process that, given two 3-D polyhedral models, generates two new models that have the same or similar shape as the original ones, but that allow transformations from one to another to be easily computed. This process assumes the morphing of star-shaped objects only. If the objects are not star-shaped, then externally supplied information is employed to divide the non-star-shaped objects into several star-shaped objects for morphing. Star-shaped refers to models for which at least one interior point p exists such that any semi-infinite ray originating at p intersects the surface of the object at exactly one point. The second approach is discussed in “Solid-Interpolating Deformations: Construction and Animation of PIPs”, by Anil Kaul and Jarek Rossignac, Eurographics '91, Proceedings of the European Computer Graphics Conference, September 1991, pp. 493-505. Kaul and Rossignac describe a process using an animation primitive called a Parameterized Interpolating Polyhedron (PIP), which may be animated on widely used graphic hardware because a PIP is a smoothly varying family of polyhedra representations bounded by faces that evolve with time. The faces have constant orientation and vertices that each move on a straight line between the vertex of the initial shape and a vertex of the final one. This process uses Minkowski sum operations for computing the PIPs.
There are several drawbacks to the above approaches. Both approaches exhibit a quadratic computational complexity, so they are impractical for some models. Furthermore, if two models to be morphed have N
1
and N
2
vertices, respectively, both approaches use O(N
1
*N
2
) storage units for storing the intermediate representations. Hence, as the models grow more complex, the storage used becomes very large. With the existing approaches, content developers cannot easily adjust or guide the construction of the morph at low resolutions. Further, content developers do not have control over the morphing process through exposable parameters or alternative sub-algorithms.
Thus, an improved method of morphing 2-D and 3-D models is desired that reduces the deficiencies and limitations of the prior art.
SUMMARY
An embodiment of the present invention is a method of constructing morphs between a first model having a first resolution and a second model having a second resolution. The method includes determining a first morph between the first model and the second model, increasing resolution of at least one of the first and second models, and determining a subsequent morph between the first model and the second model.
REFERENCES:
patent: 5448686 (1995-09-01), Borrel et al.
patent: 5590261 (1996-12-01), Sclaroff et al.
patent: 5886702 (1999-03-01), Migdal
patent: 5945996 (1999-08-01), Migdal et al.
patent: 5963209 (1999-10-01), Hoppe
patent: 5966140 (1999-10-01), Popovic et al.
patent: 5969722 (1999-10-01), Palm
patent: 5990901 (1999-11-01), Dawton et al.
patent: 6009435 (1999-12-01), Taubin et al.
patent: 6031548 (2000-02-01), Gueziec et al.
patent: 6057849 (2000-05-01), Haubner et al.
patent: 6094199 (2000-07-01), Turkiyyah et al.
patent: 6147692 (2000-11-01), Shaw et al.
patent: 6285372 (2001-09-01), Cowsar et al.
patent: 6285794 (2001-09-01), Georgiev et al.
Arthur Gregory, et al., “Feature-based Surface Decomposition for Correspondence and Morphing between Polyhedra”, Department of Computer Science, University of North Carolina at Chapel Hill, pp. 1-4.
John F. Hughes, “Scheduled Fourier Volume Morphing”, Computer Graphics, 26.2, Jul. 1992, 1992. pp. 43-46.
Apostolos Lerios, et al., “Feature-Based Volume Metamorphosis”, Computer Science Department; Standford University, pp. 1-7.
Kartik Venkataraman, et al., “Piece-wise Linear Morphing and Rendering with 3D Textures”, Microprocessor Reasearch Labs, Intel Corporation; Santa Clara, USA. pp. 1-10.
Charles S. Stein and Lewis E. Hitchner, “The Multiresolution Dissolve”, SMPTE Journal, Dec. 1998, pp. 977-982 and p. 984.
Hugues Hoppe, “Progressive Meshes”, Microsoft Research, 8 pgs.
Hugues Hoppe, “View-dependent Refinement of Progressive Meshes”, Microsoft Research, 10 pgs.
James R. Kent, Wayne E. Carlson and Richard E. Parent, “Shape Transformation for Polyhedral Objects”, Dept of Computer and Information Science Advanced Computing Center for the Arts and Design, The Ohio State University, pp. 47-53.
Anil Kaul and Jarek Rossignac, “Solid-Interpolating Deformations: Construction and animation of PIPs”, Proceedings of Eurographics '91 inComputers and Graphics(1991), pp. 443-505.
Costa, et al., “Warping and Morphing of Graphical Objects”, Siggraph '97 24th International Conference on Computer Graphics and Interactive Techniques, Aug. 3-8, 1997, pp. 35-59 and pp. 135-149.
Cohen-Or, Daniel, et al., “Three-Dimensional Distance Field Metamorphosis,” ACM Transactions of Graphics, vol. 17, No. 2, Apr. 1998, pp. 116-141.
Goldstein, Eli, et al., “Polygon Morphing Using a Multiresolution Representation,” Proceedings of Graphics Interface '95, pp. 247-254 (1995).
Sun, Yue Man,, et al., “Interpolating Polyhedral Models Using Intrinsic Shape Parameters,” Proceedings of the Third Pacific Conference on Computer Graphics and Applications, Pacific Graphics '95, pp.133-147. (1995).
Chung Daniel J
Intel Corporation
Luu Matthew
Skabrat Steven P.
LandOfFree
Method and apparatus for progressively constructing a series... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for progressively constructing a series..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for progressively constructing a series... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2882473