Computer graphics processing and selective visual display system – Computer graphics processing – Animation
Reexamination Certificate
2000-12-11
2003-06-03
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Animation
C345S467000
Reexamination Certificate
active
06573899
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method for morphing, in an object space, the outlines of characters or figures consisting of straight lines and curves.
BACKGROUND ART
Morphing, which is short for metamorphosing, is an animation technique involving moving a control point set on an image, so that image can be smoothly and seamlessly transformed into another.
A conventional technique for using morphing to transform a character on a display is disclosed in reference document 1, “Advanced Animation and Rendering Techniques,” Alan Watt and Mark Watt, Addison-Wesley, 1992, pp. 413. In reference document 1, a method is described whereby characters defined using Bezier curves are transformed by linearly interpolating control points on the curves. As an actual operating example, in the document the transformation of the character “E” into the character “Z” is described.
However, the technique disclosed in reference document 1 is not generally applicable. It cannot be applied for a general outline font, such as a True Type font, that consists of line segments and Bezier curves. Furthermore, the technique presented in the document handles only characters for which the outline consists of a single line, such as “E” or “Z.” That is, the technique in reference document 1 cannot be applied for characters for which the outlines consist of multiple lines, including characters containing internal spaces, such as “A” or B,” or characters, such as Chinese characters, for which many strokes are used.
Techniques for using morphing to transform two-dimensional outline curves are also disclosed in: reference document 2, “A Physically Based Approach to 2-D Shape Blending,” T. W. Sederberg, et al., SIGGRAPH Proceeding, 1992, pp. 25-34; reference document 3, “2-D Shape Blending: An Intrinsic Solution to the Vertex Path Problem,” T. W. Sederberg, et al., SIGGRAPH Proceeding, 1993, pp. 15-18; reference document 4, “A Fuzzy Approach to Digital Image Warping,” Y. Zhang, 1996, July, pp. 34-41; and reference document 5, “Self-intersection Elimination In Metamorphosis of Two-dimensional Curves,” T. Samoilov and G. Elber, The Visual Computer, 1988, Vol. 14, pp. 415-428.
The technique disclosed in reference documents 2 and 3 employs an algorithm whereby an outline consisting of straight lines (sides), such as linear lines or polylines, is transformed by using, as parameters, angles formed by adjacent sides and the lengths of these sides. However, it is difficult for this technique to perform the morphing of a figure, such as a character, having many raised and recessed portions.
The technique disclosed in reference document 4 is a method for distorting a two-dimensional polygonal image to perform morphing in an image space. However, since this technique processes an image in the image space, the outline has jaggy contours. Furthermore, the size of a figure cannot be enlarged or reduced (morphing cannot be performed using an arbitrary scale).
Reference document 5 discloses two algorithms to prevent self-intersection during the morphing process. However, the premise is that two two-dimensional closed curves are similar in phase so that figures that can avoid self-intersection during transformation are limited.
As is described above, it is difficult to employ the known morphing techniques to transform the outlines of complicated figures, such as characters.
When the process is performed in an image space, as disclosed in the referenced document 4, the outline of the image is jaggy, and a satisfactory appearance cannot be obtained. Further, since an arbitrary scale cannot be used only limited visual effects are possible.
When the image processing is performed in object space using vectors, the types and shapes of target figures for which the processing can be performed are limited. In the method of reference document 1 only figures that have outlines consisting of single lines can be handled. With the method of reference documents 2 and 3, figures having many raised and recessed portions cannot be handled.
In addition, it is important self-intersection in an outline be avoided because the internal space of the outline may not satisfactorily be solidly painted with a specific color. The technique disclosed in reference document 5 is not generally applicable because the figures for which self-intersection can be avoided are limited.
Therefore it is one object of the present invention to perform morphing, in a vector space, for the outlines for various types and shapes of figures.
It is a further object of the present invention to perform morphing for a figure that consists of a plurality of outlines.
It is still a further object of the present invention to perform morphing for a figure having raised and recessed portions, while preventing self-intersection.
It is another object of the present invention to perform morphing for a character or for a character string on a computer display device.
SUMMARY OF THE INVENTION
According to the present invention, a morphing processing apparatus, which performs a morphing process for the smooth transformation of one figure into another, comprises: an outline extractor, for receiving two target figures for the morphing process and for extracting a set of outlines for each of the target figures; an outline arrangement unit, for retaining one specific outline of each of the two sets of outlines extracted for the target figures and for deleting the other outlines; a smoothing processor, for performing a smoothing process for the two outlines for the target figures that are retained by the outline arrangement unit in order to prevent self-intersection during the morphing process; and a morphing execution unit, for performing the morphing process in response to the progress made by the smoothing process performed by the smoothing processor.
The outline arrangement unit includes: an outline tree generator, for generating an outline tree having nodes that correspond to the outlines that are extracted for the two target figures by the outline extractor and that reflect the relationship of the outlines; and an outline tree arrangement unit, for retaining only one specific node, of those nodes of the outline tree that are generated by the outline tree generator, for each of the figures and for deleting the other nodes in accordance with a predetermined rule, wherein the smoothing processor performs the smoothing process for each outline that corresponds to one of the nodes that are retained as a result of the process performed by the outline arrangement unit. This arrangement is preferable because a desired outline can be retained by designating the node of the outline tree, while taking the structure of the outline tree into account. Further, as will be described later, information concerning a bounding box that encloses an outline is stored in the node of the outline tree. In this case, a node for which the size of the bounding box is the maximum may be retained.
Furthermore, the outline tree generator receives the outlines of the target figures that are extracted by the outline extractor, designates, for each of the outlines, a bounding box that encloses the pertinent outline, and generates an outline tree based on the relationship existing between the bounding boxes. This arrangement is preferable because the relationship of the outlines that constitute the target figure will be readily apparent. While an arbitrary shape can be selected for a bounding box, a rectangular shape is easy to handle when a target figure is a character.
In addition, when a curve is included in the outlines of the target figures, the outline extractor divides the curve into line segments and performs segment approximation. Therefore, the outline can be treated as a polygon, and the process can be generalized so that it can be performed regardless of the shape of the target figure.
Further, the outline extractor receives, as a target figure, an outline font character and extracts the outline of the character. As a result, excellent visual effects can be provided for the display of a tex
International Business Machines - Corporation
Murray James E.
Nguyen Phu K.
Wojnicki, Jr. Andrew J.
LandOfFree
Morphing processing apparatus, method, storage medium,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Morphing processing apparatus, method, storage medium,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Morphing processing apparatus, method, storage medium,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3163815