In graphics, metamorphosis, or morphing, is the process of gradually changing a source object through intermediate objects into a target object. For example, a person's face can be morphed into another person's face, an animal can be morphed into a human, etc. Morphing can create striking special effects, and has numerous applications—from modeling, computer simulation and video games to generation of animation sequences for the movie and advertising industries.
Past advancements in 3D morphing have tended to concentrate on developing algorithms for morphing geometry between source and target objects. However, modern 3D graphics commonly uses texture mapping to make 3D objects more interesting and apparently more complex. Generally, texture mapping involves taking a 2D image (e.g., a photographic or other digitized picture) and placing it onto a 3D surface. As one example, a brick wall can be imaged by mapping a brick-and-mortar texture onto a simple rectangular surface of a 3D “wall” object. Images of foliage, clouds, and a variety of other complex images can all be created using such texture mapping techniques.
When attempting to morph a textured 3D image, one must morph the texture as well as the geometry. Texture maps can be large, and each texel in the map should be morphed to provide a range of interpolated texture values between source and target textures. Such texture morphing therefore tends to be computationally expensive—effectively preventing resource-constrained real-time graphics systems such as home video game systems and personal computer graphics cards from providing real-time texture morphing functionality. What is needed is a texture morphing procedure that is fast and efficient enough to be performed in real-time within limited resource environments so that texture morphing can be performed “on the fly” in a limited resource graphics system.
The present invention provides a solution to this problem by providing a fast, real-time texture morphing algorithm that is both fast and efficient. The preferred embodiment of the invention provides a number of efficiencies to simplify and reduce the computations required within a texture morphing/blending process, such techniques including off-line texel component decomposition; incremental interpolation; frame counters; interlace morphing; and background low-priority threading. These techniques can be used individually and/or in combination to provide morphing procedures fast enough for real-time computer animation and simulation and video games.
In accordance with one aspect of an exemplary embodiment of the present invention, incremental interpolation techniques are used to reduce repetitive and heavy floating point number calculations/conversions associated with the typical texel blending/morphing process. The preferred embodiment computes an incremental morph parameter t for each texel component based on a previous value(s) and change rate (e.g., image frame rate and the time duration of the morphing process). Initial and incremental morph parameter values can be computed in advance for each texel component during a preliminary morph preparation background process. Then, during a subsequent real-time morphing process, these initial and incremental parameter values are applied incrementally to morph the texel components toward target texel component values.
To save floating-to-fixed point conversion time, the preferred embodiment uses integer addition to apply the incremental morph parameter values to the texel component values. However, to preserve accuracy, incremental and new values should be floating point numbers. The preferred embodiment resolves this inconsistency by using a frame counter concept. The morph parameter preparation process determines, for each texel component value, how many image frames it will take for a fractional portion of the incremental parameter value to change the integer portion of the texel component value. The preferred embodiment carefully chooses the resulting frame counter values to prevent over-runs, and uses them to specify when additional integer correction factors should be applied during the incremental interpolation process. To avoid image artifacts due to mismatch between the morphed texel component values and the actual target texel values, the preferred embodiment “snaps” the texel values to the precise (floating point) target values during the last morph iteration.
In accordance with another aspect of the exemplary preferred embodiment of the invention, incremental interpolation can be applied each frame time or other morphing period to less than all of texels being morphed. For example, some texels can be incrementally interpolated during a particular frame, other texels can be incrementally interpolated during a subsequent frame, etc.—so that all texels are incrementally interpolated across a certain (preferably small) number of frames without requiring each texel to be interpolated every frame. Such interlacing of incremental interpolation can significantly reduce computational load without introducing significant image artifacts.
In accordance with yet another aspect of the invention, the texture buffer data structure is initially decomposed off-line to reduce the number of real-time operations required to separate and manipulate texel component data for morphing. The preferred embodiment decomposes the standard texture map into separate arrays for each of the colors (RGB) and for alpha (transparency). The resulting component arrays (which may be 8-bit integer arrays, for example) can be manipulated directly by real-time software without additional masking/data extraction overhead.
One significant and advantageous application of the present invention is to allow dynamic generation of a virtually infinite number of video game characters and other textured objects “on the fly” using morphing procedures within home video game systems, personal computer graphics cards, and other inexpensive graphics systems. It is possible to pre-construct a number of objects with certain geometry and textures as primary sources and targets (“morph terminals”), and then use the texture morphing features to smoothly transform textures in real time between such objects to generate a sequence of continuous intermediate objects along morphing paths between the morph terminals. Since the preferred embodiment stores each set of intermediate morphed texture values as a texture map, any such intermediate texture map can be used as a source texture map for a further texture morphing operation along the same or different morph path.