Distortion of raster and vector artwork Number:7,385,612 from the United States Patent and Trademark Office (PTO) owispatent Systems and techniques to apply an image distortion to two image objects of different graphic types. In general, in one implementation, the technique includes: receiving an image distortion description to be applied to an image portion including a vector graphic and a raster graphic, the raster graphic being distortable separate from the vector graphic, applying the image distortion description to the vector graphic to produce a distorted vector graphic, and applying the image distortion description to the raster graphic to produce a distorted raster graphic, the distorted vector graphic and the distorted raster graphic together forming a distorted image portion.<H Distortion, artwork, Distortion, of, r, 7385612.html, Patent, pto, 7385612

Title: Distortion of raster and vector artwork

Abstract: Systems and techniques to apply an image distortion to two image objects of different graphic types. In general, in one implementation, the technique includes: receiving an image distortion description to be applied to an image portion including a vector graphic and a raster graphic, the raster graphic being distortable separate from the vector graphic, applying the image distortion description to the vector graphic to produce a distorted vector graphic, and applying the image distortion description to the raster graphic to produce a distorted raster graphic, the distorted vector graphic and the distorted raster graphic together forming a distorted image portion.

Patent Number: 7,385,612 Issued on 06/10/2008 to Peterson

Inventors: Peterson; John (Menlo Park, CA)
Assignee: Adobe Systems Incorporated (San Jose, CA)

Appl. No.: 10/160,574

Filed: May 30, 2002

Current U.S. Class: 345/619 ; 345/581

Field of Search: 345/442,591-594,646-647,441,619,581,474

References Cited [Referenced By]

U.S. Patent Documents


5428728	June 1995	Lung et al.
5481659	January 1996	Nosaka et al.
5539868	July 1996	Hosoya et al.
5598182	January 1997	Berend et al.
5731819	March 1998	Gagne et al.
5731820	March 1998	Broekhuijsen
5736991	April 1998	Tada
5754183	May 1998	Berend et al.
5852447	December 1998	Hosoya et al.
5857067	January 1999	Hassett et al.
5920324	July 1999	Hasegawa et al.
5929867	July 1999	Herbstman et al.
6157390	December 2000	Cheng
6201549	March 2001	Bronskill
6232987	May 2001	Choi et al.
6271864	August 2001	Graham
6300955	October 2001	Zamir
6459439	October 2002	Ahlquist, Jr. et al.
6501475	December 2002	Cheng
6522328	February 2003	Asente
6628295	September 2003	Wilensky
6633300	October 2003	Tomack et al.
6765589	July 2004	Georgiev et al.
6803913	October 2004	Fushiki et al.
6870545	March 2005	Smith et al.
6911980	June 2005	Newell et al.
6919888	July 2005	Perani et al.
6999101	February 2006	Sanborn et al.

Other References

Barry Fowler, Geometric manipulation of tensor product surfaces, Proceedings of the 1992 symposium on Interactive 3D graphics, p. 101-108, Jun. 1992, Cambridge, Massachusetts, United States. cited by examiner .
Venkat Krishnamurthy, Marc Levoy, Fitting smooth surfaces to dense polygon meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p. 313-324, Aug. 1996. cited by examiner .
Frederick W. B. Li , Rynson W. H. Lau, Real-time rendering of deformable parametric free-form surfaces, Proceedings of the ACM symposium on Virtual reality software and technology, p. 131-138, Dec. 20-22, 1999, London, United Kingdom. cited by examiner .
Tony DeRose , Michael Kass , Tien Truong, Subdivision surfaces in character animation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p. 85-94, Jul. 1998. cited by examiner .
Tim Milliron , Robert J. Jensen , Ronen Barzel , Adam Finkelstein, A framework for geometric warps and deformations, ACM Transactions on Graphics (TOG), v. 21 N. 1, p. 20-51, Jan. 2002. cited by examiner .
Steven Schkolne , Michael Pruett , Peter Schroder, Surface drawing: creating organic 3D shapes with the hand and tangible tools, Proceedings of the SIGCHI conference on Human factors in computing systems, p. 261-268, Mar. 2001, Seattle, Washington. cited by examiner .
Karan Singh , Eugene Fiume, Wires: a geometric deformation technique, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p. 405-414, Jul. 1998. cited by examiner .
CorelDraw 9 for Windows: Visual QuickStart Guide, Publisher: Peachpit Press, Jul. 6, 1999, Chapters 4, 14-16. cited by examiner .
CorelDraw 10 for Windows: Visual QuickStart Guide, Publisher: Peachpit Press, Nov. 6, 2001, Chapters 4, 14-16. cited by examiner .
U.S. Appl. No. 09/458,917, filed Dec. 10, 1999, Newell et al. cited by other .
Peterson, John W., "IV.6 Tessellation of NURB Surfaces," Copyright 1994 by Academic Press, Inc. cited by other .
Watkins, M.A. and Worsey, A.J., "Degree reduction of Bezier curves," CAD v20, #7, Sep. 1988. cited by other .
Peterson, John, "Letters to the Editor Degree Reduction of Bezier curves," Computer Aided Design vol. 23, #6 Jul./Aug. 1991. cited by other .
DeRose, Tony D. et al, "Functional Composition Algorithms via Blossoming," May 28, 1992. cited by other .
Heckbert, Paul S., "Fundamentals of Texture Mapping and Image Warping," Master's Thesis, Dept. of Electrical Engineering and Computer Science University of California, Berkeley, CA, Jun. 17, 1989. cited by other .
Richard H. Bartels et al., "A Technique for the Direct Manipulation of Spline Curves", Graphics Interface 1989, pp. 33-37. cited by other .
Barry Fowler, "Geometric Manipulation of Tensor Product Surfaces", ACM 0-89791-471-6/92/0003/0101, 1992, pp. 101-108. cited by other.

Primary Examiner: Wang; Jin-Cheng
Attorney, Agent or Firm: Fish & Richardson P.C.

Claims

What is claimed is:

1. A computer-implemented method comprising: receiving an image distortion description to be applied to an image portion including a vector graphic and a raster graphic displayed on the screen of a display device, the raster graphic and the vector graphic being separately distortable and distinct image objects; applying the image distortion description to the vector graphic to produce a distorted vector graphic and independently applying the image distortion description to the raster graphic to produce a distorted raster graphic, the applications being independent in the sense that no result of either application is used as input to the other, the distorted vector graphic and the distorted raster graphic together forming a distorted image portion; wherein independently applying the image distortion description to the raster graphic comprises using the image distortion description as a control structure governing resampling of the raster graphic; wherein receiving the image distortion description comprises: receiving a first input designating the raster graphic to be distorted, receiving a second input designating the vector graphic to be distorted, and receiving a third input defining the image distortion description; and wherein the designated raster graphic and the designated vector graphic define a distortion region, the method further comprising: converting coordinates of the vector graphic into a parameter space of the distortion region; and if the distortion region is larger than the raster graphic, subdividing the image distortion description with respect to the raster graphic before applying the image distortion description to the raster graphic; wherein independently applying the image distortion description to the raster graphic further comprises: tessellating the image distortion description into polygons; checking for any backward facing ones of the polygons; and resampling the raster graphic based on the tessellated image distortion description.

2. The method of claim 1, wherein applying the image distortion description to the vector graphic comprises composing the image distortion description with the vector graphic to retain curve information as curve information and to maintain a resolution independent aspect of the vector graphic; and wherein resampling the raster graphic comprises extending edges of the raster graphic to provide data values for interpolation.

3. The method of claim 1, wherein the raster graphic does not have a mapping association with another image object in the image portion.

4. The method of claim 1, wherein the image portion comprises a full page image stored in a final format electronic document.

5. The method of claim 1, wherein receiving the third input defining the image distortion description comprises receiving inputs specifying a configuration of an adjustable predefined distortion type.

6. The method of claim 1, wherein receiving the first input designating the raster graphic to be distorted comprises receiving inputs defining a selection box to cover a portion of the raster graphic, and wherein receiving the second input designating the vector graphic to be distorted comprises receiving inputs defining the selection box to cover a portion of the vector graphic.

7. The method of claim 1, wherein receiving the third input defining the image distortion description comprises receiving inputs specifying movements of a cursor across the distortion region.

8. The method of claim 1, wherein the image distortion description comprises a tensor-product Bezier mesh, and wherein the vector graphic comprises a cubic Bezier curve.

9. The method of claim 1, wherein receiving the first input designating the raster graphic to be distorted comprises receiving a first input generated by a macro operation, and wherein receiving the second input designating the vector graphic to be distorted comprises receiving a second input generated by the macro operation.

10. A software product, tangibly stored on a computer-readable medium, the software product comprising instructions operable to cause a programmable processor to perform operations comprising: receiving through a single interface tool in a graphical user interface an image distortion description to be applied to an image portion including a vector graphic and a raster graphic displayed on the screen of a display device, the raster graphic and the vector graphic being separately distortable and distinct image objects; applying the image distortion description to the vector graphic to produce a distorted vector graphic and independently applying the image distortion description to the raster graphic to produce a distorted raster graphic, the applications being independent in the sense that no result of either application is used as input to the other, the distorted vector graphic and the distorted raster graphic together forming a distorted image portion; wherein independently applying the image distortion description to the raster graphic comprises using the image distortion description as a control structure governing resampling of the raster graphic; wherein receiving the image distortion description comprises: receiving a first input designating the raster graphic to be distorted, receiving a second input designating the vector graphic to be distorted, and receiving a third input defining the image distortion description; and wherein the designated raster graphic and the designated vector graphic define a distortion region, the operations further comprising: converting coordinates of the vector graphic into a parameter space of the distortion region; and if the distortion region is larger than the raster graphic, subdividing the image distortion description with respect to the raster graphic before applying the image distortion description to the raster graphic; wherein independently applying the image distortion description to the raster graphic further comprises: tessellating the image distortion description into polygons; checking for any backward facing ones of the polygons; and resampling the raster graphic based on the tessellated image distortion description.

11. The software product of claim 10, wherein applying the image distortion description to the vector graphic comprises composing the image distortion description with the vector graphic to retain curve information as curve information and to maintain a resolution independent aspect of the vector graphic; and wherein resampling the raster graphic comprises extending edges of the raster graphic to provide data values for interpolation.

12. The software product of claim 10, wherein receiving the first input designating the raster graphic to be distorted comprises receiving inputs defining a selection box to cover a portion of the raster graphic, and wherein receiving the second input designating the vector graphic to be distorted comprises receiving inputs defining the selection box to cover a portion of the vector graphic.

13. The software product of claim 10, wherein receiving the first input designating the raster graphic to be distorted comprises receiving a first input generated by a macro operation, and wherein receiving the second input designating the vector graphic to be distorted comprises receiving a second input generated by the macro operation.

14. The software product of claim 10, wherein receiving the third input defining the image distortion description comprises receiving inputs specifying movements of a cursor across the distortion region.

15. The software product of claim 10, wherein receiving the third input defining the image distortion description comprises receiving inputs specifying a configuration of an adjustable predefined distortion type.

16. The software product of claim 10, wherein the image distortion description comprises a tensor-product Bezier mesh, and wherein the vector graphic comprises a cubic Bezier curve.

17. The software product of claim 10, wherein the raster graphic does not have a mapping association with another image object in the image portion.

18. The software product of claim 10, wherein the image portion comprises a full page image stored in a final format electronic document.

19. A system for illustrating two dimensional images, the system comprising: means for receiving an image distortion description to be applied to an image including a vector graphic and a raster graphic displayed on the screen of a display device, the raster graphic and the vector graphic being separately distortable and distinct image objects; and means for applying the image distortion description to the vector graphic to produce a distorted vector graphic and independently applying the image distortion description to the raster graphic to produce a distorted raster graphic, the applications being independent in the sense that no result of either application is used as input to the other, wherein the distorted vector graphic and the distorted raster graphic correspond to a consistent distortion as defined by the image distortion description across a distorted image including the distorted vector graphic and the distorted raster graphic; wherein the means for applying the image distortion description to the raster graphic comprises means for resampling the raster graphic using a mathematical control structure; wherein the means for receiving the image distortion description comprises means for receiving a first input designating the raster graphic to be distorted, a second input designating the vector graphic to be distorted, and a third input defining the image distortion description; and wherein the designated raster graphic and the designated vector graphic define a distortion region, the system further comprising: means for converting coordinates of the vector graphic into a parameter space of the distortion region; and means for subdividing the image distortion description with respect to the raster graphic, if the distortion region is larger than the raster graphic, before applying the image distortion description to the raster graphic; wherein the means for applying the image distortion description to the raster graphic comprises: means for tessellating the image distortion description into polygons; means for checking for any backward facing ones of the polygons; and the means for resampling comprising means for resampling the raster graphic based on the tessellated image distortion description.

20. The system of claim 19, wherein the means for applying the image distortion description to the vector graphic comprises means for composing the mathematical control structure with the vector graphic to retain curve information as curve information and to maintain a resolution independent aspect of the vector graphic; and wherein the means for resampling comprises means for extending edges of the raster graphic to provide data values for interpolation.

21. The system of claim 19, wherein the receiving means comprises free-form means for receiving arbitrary user-designed image distortions.

22. The system of claim 19, wherein the raster graphic does not have a mapping association with another image object in the distorted image.

23. The system of claim 19, wherein the distorted image comprises a full page image stored in a final format electronic document.

24. The system of claim 19, wherein the means for receiving the third input defining the image distortion description comprises means for receiving inputs specifying a configuration of an adjustable predefined distortion type.

25. The system of claim 19, wherein the means for receiving the first input designating the raster graphic to be distorted comprises means for receiving inputs defining a selection box to cover a portion of the raster graphic, and wherein the means for receiving the second input designating the vector graphic to be distorted comprises means for receiving inputs defining the selection box to cover a portion of the vector graphic.

26. The system of claim 19, wherein the means for receiving the first input designating the raster graphic to be distorted comprises means for receiving a first input generated by a macro operation, and wherein the means for receiving the second input designating the vector graphic to be distorted comprises means for receiving a second input generated by the macro operation.

27. The system of claim 19, wherein the means for receiving the third input defining the image distortion description comprises means for receiving inputs specifying movements of a cursor across the distortion region.

28. The system of claim 19, wherein the image distortion description comprises a tensor-product Bezier mesh, and wherein the vector graphic comprises a cubic Bezier curve.

Description

BACKGROUND OF THE INVENTION

The present application describes systems and techniques relating to distortion of raster and vector artwork.

Many types of artwork are stored and manipulated in computing machines, and such artwork can be stored digitally in multiple formats. A single artwork image can include multiple distinct image objects, which can also be stored in different formats. For example, a raster graphic is an image object stored as a set of pixel values corresponding to a defined frame (e.g., a rectangular grid). The pixel values can include multiple values for each pixel, including multiple color values, transparency/opacity values, and/or mask values (e.g., an image clipping mask). A raster graphic represents an image as a set of discrete image samples. A vector graphic is an image object stored using a set of two-dimensional coordinates connected by lines or curves (e.g., cubic Bezier curves). Examples of vector graphics include symbols, shapes, and text represented by outline fonts.

Interactive painting and illustration software products, such as Illustrator.RTM., provided by Adobe Systems Incorporated of San Jose, Calif., provide tools to allow a user to distort an image object. Such distortion functionality can be useful for adding creative effects to an image object and/or to integrate an image object with other elements in a finished design (e.g., fitting artwork onto a circular label, or making artwork appear three-dimensional). Image distortions include geometric and optical distortions, as well as image warps and deformations generally (e.g., a deformation and a warp of a two-dimensional image are examples of an image distortion).

Example illustration software products that allow distortions of raster images include Goovie.RTM., provided by MetaCreations Corporation of Carpinteria, Calif., Ampex Video Art, provided by Ampex Corporation of Redwood City, Calif., and Photoshop.RTM., provided by Adobe Systems Incorporated of San Jose, Calif. Example illustration software products that allow distortions of vector artwork include FreeHand.RTM., provided by Macromedia Inc. of San Francisco, Calif., and CorelDraw, provided by Corel Corporation of Ottawa, Ontario, Canada.

SUMMARY OF THE INVENTION

In general, in one aspect, the invention features application of an image distortion to two image objects of different graphic types. According to an aspect, a single image distortion description can be received, and this image distortion description can be applied to two image objects of different graphic types to distort the image objects, where the image objects are separately distortable. The distortion of the two image objects can create a consistent distortion across the image objects as defined by the image distortion description, while retaining the distinct graphic characteristics of the two image objects. Moreover, the distortion description can be applied to the second image object independently from the application to the first image object. One image object need not be distorted through another image object, and the two image objects can be distorted by the same distortion description even if they are not distorted simultaneously.

Advantageous implementations of the invention include one or more of the following features. An image distortion description to be applied to an image portion can be received through a single interface tool in a graphical user interface. The image portion can be a whole image or part of an image and can include a vector graphic and a raster graphic, where the raster graphic is distortable separate from the vector graphic (i.e., there need not be a predefined mapping association between the raster graphic and the vector graphic). The image distortion description can be applied to the vector graphic to produce a distorted vector graphic, and the image distortion description can be applied to the raster graphic to produce a distorted raster graphic. The distorted vector graphic and the distorted raster graphic together form a distorted image portion.

The image distortion description can be applied to the raster graphic independently from the image distortion description being applied to the vector graphic. The image distortion description can include a mathematical definition of an image distortion in two dimensions. Distorting the raster graphic can involve using the image distortion description as a control structure governing resampling of the raster graphic. Distorting the raster graphic can involve tessellating the image distortion description, and resampling the raster graphic based on the tessellated image distortion description. Distorting the vector graphic can involve composing the image distortion description with the vector graphic to retain curve information as curve information and to maintain a resolution independent aspect of the vector graphic.

The raster graphic need not have a mapping association with another image object in the image portion. The image portion can be part of a final format electronic document. Receiving the image distortion description can involve receiving a first input designating the raster graphic to be distorted, receiving a second input designating the vector graphic to be distorted, and receiving a third input defining the image distortion description. Receiving the first and second inputs designating the raster graphic and vector graphic can involve receiving inputs defining a selection box to cover a portion of the raster graphic and a portion of the vector graphic. Alternatively, receiving the first and second inputs designating the raster graphic and vector graphic can involve receiving inputs generated by a macro operation.

Receiving the third input defining the image distortion description can involve receiving inputs specifying a configuration of an adjustable predefined distortion type, or receiving inputs specifying movements of a cursor across a distortion region. Distorting the vector graphic can involve converting coordinates of the vector graphic into a parameter space of the distortion region. Distorting the raster graphic can involve subdividing the image distortion description before applying the image distortion description to the raster graphic, if the distortion region is larger than the raster graphic. The image distortion description can include a tensor-product Bezier mesh, and the vector graphic can include a cubic Bezier curve.

A system can be provided to implement these features and techniques. The system can be part of a general purpose processing system, or the system can be a special purpose system designed for image processing and manipulation. Implementations of the systems and techniques described here may occur in hardware, firmware, software or a combination of them and may include instructions for causing a machine to perform the operations described.

The invention can be implemented to realize one or more of the following advantages. Multiple types of image objects, such as vector graphics and raster graphics, can be distorted simultaneously using a uniform control interface while retaining the original formats. A graphical user interface can provide a single warping tool that allows both raster and vector artwork to be distorted together. A single distortion description is applied to both vector and raster artwork to produce a consistent distortion across a distorted image, without converting the vector graphic into a raster graphic. Because vector artwork need not be converted into raster form to accomplish the distortion, the advantages of vector artwork (e.g., device independent resolution) are retained. The distortion description can be a free-form distortion or a predefined type of distortion. A user of the distortion tool does not need to consider format differences between the various image objects selected for distortion.

A mathematical control structure (e.g., a tensor product Bezier mesh) can be used to specify an image distortion, and this same mathematical control structure can be applied to both vector graphics and raster graphics, thus allowing a user of a painting and illustration program to distort both vector graphics and raster graphics at the same time with one image distortion description. The geometric result is the same on both types of artwork, and the process is transparent to the user.

The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features and advantages of the invention will become apparent from the description, the drawings, and the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a flowchart showing a process of distorting a group of image objects of different graphic types, including a raster graphic and a vector graphic.

FIG. 2 illustrates designation of a raster graphic and multiple vector graphics to be distorted.

FIG. 3 illustrates results of two predefined image distortions.

FIG. 4 illustrates an image distortion description.

FIG. 5 illustrates a technique for receiving an image distortion description.

FIG. 6 illustrates direct curve manipulation.

FIG. 7 shows response curves.

FIG. 8 shows quadratic response curves.

FIGS. 9 and 10 illustrate sampling to determine surface parameters.

FIG. 11 illustrates curve subdivision.

FIGS. 12 and 13 illustrate subdivision to determine surface parameters.

FIG. 14 illustrates treatment of a surface drag as a series of curve drags.

FIG. 15 illustrates a direct manipulation of an "inflate" distortion.

FIG. 16 illustrates a wave distortion.

FIG. 17 shows linear response curves.

FIG. 18 shows scaled response curves.

FIG. 19 shows linear response curves.

FIG. 20 shows scaled response curves.

FIG. 21 is a flowchart showing a process of distorting a raster graphic and a vector graphic.

FIG. 22 illustrates a technique for distorting vector graphics.

FIGS. 23 and 24 illustrate a technique for distorting a raster graphic.

FIG. 25 is a block diagram illustrating example subdivision of a specified distortion and ordering of vertices.

FIG. 26 illustrates generated edge shards for handling image edges.

FIG. 27 illustrates subdividing a distortion region.

FIG. 28 illustrates a distorted electronic document having multiple image objects of various types.

Like reference symbols in the various drawings indicate like elements.

DETAILED DESCRIPTION

As used herein, the terms "artwork", "image object" and "graphic" are used interchangeably. Thus, a raster graphic is also referred to as a raster image object and raster artwork (with no intended suggestion that the graphic is in fact art). A graphic is a set of data defining an image or image portion that can be displayed.

FIG. 1 is a flowchart showing a process of distorting a group of image objects of different graphic types, including a raster graphic and a vector graphic. A first input designating a raster graphic to be distorted is received at 100. A second input designating a vector graphic to be distorted is received at 105. The manner and order of the designations can be varied, but in general, a vector graphic and a raster graphic are separately designated by a user. Moreover, additional raster and vector graphics and/or portions of raster and vector graphics can be designated (e.g., selected, or defined) for the same distortion to be applied.

Once a group of image objects have been designated, a third input defining an image distortion description is received at 110. The image distortion description can describe a free-form distortion or a predefined type of distortion, such as a twist, squeeze, twirl, wave, flag, arc, zig-zag, ripple, spherify, pucker, bloat, or reflection distortion. The third input can be received from a distortion tool interface that can be a simple button or a more detailed interface that allows a user to adjust distortion parameters before application and/or to paint a distortion directly onto the designated raster and vector graphics. Detailed interfaces can be provided for free-form distortion tools and/or predefined-type distortion tools.

The image distortion description is a mathematical definition of an image distortion in two dimensions. This mathematical definition can include higher dimensional components, but in general, the mathematical definition represents a mapping of a first two-dimensional image to a second two-dimension image. The image distortion description is applied to the vector graphic to produce a distorted vector graphic at 115. Straight lines in the vector graphic can be converted into curves as needed, and curves in the vector graphic can be distorted by modifying their control points and/or subdividing them into additional curves.

The same image distortion description is applied to the raster graphic to produce a distorted raster graphic at 120. The frame of the raster graphic can be warped by the image distortion description into a distorted frame, and the image distortion description (e.g., a distortion surface such as a Bezier tensor product mesh) can be converted into small polygons (e.g., triangles) that cover the distorted frame. For each polygon, the portion of the original raster graphic can be mapped onto the corresponding polygon.

The same distortion can thus be applied to both raster image objects and vector image objects at essentially the same time. A user of an interactive painting and illustration program need not be aware of which objects in a piece of artwork are vector graphics and which are raster graphics. A uniform set of user interface controls for image distortion can be provided. Such uniform interface controls can allow deformation and warping of selected artwork without changing the underlying fundamental nature of the artwork. Raster artwork remains raster artwork, and vector artwork remains vector artwork, but both are distorted in a visually consistent manner across a distortion region as defined by the image distortion description.

FIG. 2 illustrates designation of a raster graphic and multiple vector graphics to be distorted. An image 200 is a piece of artwork that includes an image portion 205, which itself is another image. The image 205 includes multiple image objects: a raster graphic 210, which is a picture of a cat, an arrow vector graphic 215, a box vector graphic 220, a border vector graphic 225, and a text vector graphic 230. The image objects have coordinates associated with the image 200 but not necessarily with each other. The image objects can be selected and/or portions of the image objects can be defined for distortion. Text objects that are not vector graphics can be dynamically converted to vector graphics (e.g., converted to outline fonts, or an alternative vector graphic format that includes text data, such as Unicode or ASCII (American Standard Code for Information Interchange) data) before being distorted. Such conversion of text objects can be performed by a user or automatically by the distortion control interface. Additionally, a distortion operation can be applied directly using a graphical painting tool, such as a brush tool of variable shapes and sizes.

When a portion of a raster graphic is defined for distortion (e.g., a selection box is drawn over a portion of the raster graphic), that portion can be separated and treated as a distinct raster graphic for distortion. A distortion region of the raster graphic and a slightly larger sampling region can be defined. When a portion of a vector graphic is defined for distortion, that portion can be carved off and treated as a distinct vector graphic for distortion. The non-distortion portion of the vector graphic can either be separated from the distortion portion, or remain connected (e.g., with a straight line). Carving off the distortion portion can involve finding a parametric point along a curve (e.g., the point at which the curve intersects an edge of the distortion region) and creating two curves that intersect at this parametric point.

Image objects can be designated for distortion using a point-and-click-interface, a selection box drawing interface, or other interfaces. For example, a selection box 240 can be drawn over the image 205 to select the image objects and define a distortion region. The box 240 can define a distortion region directly, in which case the box 240 designates a portion of the raster graphic 210, the entire arrow vector graphic 215, a portion of the box vector graphic 220, a portion of the border vector graphic 225, and a portion of the text vector graphic 230. In this case, the box 240 represents the distortion region.

Alternatively, the box 240 can define the distortion region indirectly by selecting all image objects that the box 240 either contains or intersects. In this case, the box 240 defines a distortion region 260 that includes all of the image objects in the image 205. The selection box interface of this example provides the first and second inputs described above. Thus, drawing the box 240 to cover an upper left corner of the border vector graphic 225 represents the first input designating the vector graphic, and drawing the box 240 over an upper left corner of the raster graphic 210 represents the second input designating the raster graphic. Alternative image object designation techniques are also possible, including macro operations, such as pressing Ctrl-A to designate all image objects on a page or pressing a mouse button with a cursor within a predefined distance of two or more image objects, that cause the separate inputs designating the vector graphic and the raster graphic to be generated.

FIG. 3 illustrates results of two predefined image distortions. A first distortion shows the artwork image 200 as modified by a predefined flag distortion to create a flag image 300. A second distortion shows the artwork image 200 as modified by a predefined arc distortion to create an arc image 350.

FIG. 4 illustrates an image distortion description. The image distortion description is a mathematical definition of an image distortion in two dimensions. This mathematical definition can be parameterized using a grid of control points. When a distortion region is defined, a uniform surface (e.g., a rectangular surface) can be created over the artwork in the distortion region. By distorting the shape of the uniform surface, the artwork in the distortion region can be distorted in a manner corresponding to the distorted surface.

For example, a piece of artwork 400 has an associated distortion surface 410, which can be a tensor product surface. The distortion surface 410 has nine control points 420 that define the shape of the surface and thus the mapping of the artwork 400 from a undistorted two-dimensional image to a distorted two-dimensional image. Additional control points can be used, and the distortion surface can be a Bezier bicubic surface, which has sixteen control points.

These control points can be moved individually to reshape the distortion surface, or a more intuitive control interface can be provided. Additional control handles can be provided that have predefined effects on the control points of the distortion surface to create an adjustable predefined type of distortion (e.g., symmetrical distortions such as those mentioned previously). Alternatively, a free-form type of distortion control interface can be provided, such as a control interface that draws an envelope around a distortion region and allows dragging of the envelope, or a control interface that causes movements of a cursor across the distortion region to have predefined effects on the distortion surface such as allowing dragging of arbitrary points within the distortion region.

FIG. 5 illustrates a technique for receiving an image distortion description. A piece of artwork 450 has an associated distortion surface with control points such as control points 455. A cursor 460 can be used to select and drag an arbitrary target point on the distortion surface and the software determines how the control points, and thus the distortion surface, are distorted. The distortion surface behaves as a flexible or pliable sheet, which can be stretched and pulled using the cursor 460. Thus, movement of the cursor 460 causes movement of the control points, where the amount of movement of a control point depends on that control point's relation to an arbitrary point on the distortion surface being dragged. The distortion surface can have many control points creating a mesh. For example, the distortion surface can be a tensor product Bezier mesh.

Manipulation of curves forms the basis of the flexible sheet method of distortion manipulation described above. Moreover, the notation for curves is simpler than for surfaces, thus curve manipulation is described first.

A Bezier curve is defined as:

.function..times..times..times..function. ##EQU00001## Where P.sub.i are the control points, and B.sub.i.sup.d(t) are the Bezier basis functions, defined as:

.function..times..function. ##EQU00002## d is the degree of the curve (e.g., for a cubic curve, d=3) and the curve has d+1 control points. In order to manipulate the curve, we wish to drag a particular point on the curve C(t.sub.drag) to a point P.sub.drag such that the curve is adjusted in a natural way. Doing this involves first determining t.sub.drag, which is the parameter of the curve that corresponds to the point on the curve to be moved to the new location.

One method for directly manipulating curves developed by Bartels and Beatty is based on the Householder equations. As shown in FIG. 6, a point on a curve 500 is dragged, and the curve 500 moves accordingly. The control points P.sub.i are modified to create a new set of points according to:

.DELTA..function..DELTA..times..function..times..times..function. ##EQU00003##

The circumflex ^ is added to curves or points modified by a dragging operation. While the Bartels and Beatty method produces a smooth change in the curve, it also produces artifacts. The length of the curve is often preserved, making it difficult to flatten a curved shape. The entire curve segment is adjusted, making local changes difficult. And either the end points are left fixed, producing a large change in the overall curve near the fixed point when a small change is made, or the endpoints are allowed to move, making it difficult to constrain changes.

Based on a consideration of how the curve should behave when a target point is dragged, the following criteria work well (in the case of a cubic curve) in defining how certain canonical points on the curve should move. An equivalent set can be written for, e.g., the quadratic case. For t.sub.drag>1/3, C(0) does not move. For t.sub.drag<2/3, C(1) does not move Dragging at t.sub.drag=0 behaves just like moving the P.sub.0 control point. Dragging at t.sub.drag=1 behaves just like moving the P.sub.3 control point. Dragging at t.sub.drag=1/3 or t.sub.drag=2/3 maximally effects that point on the curve.

Given end points A and B (end points A and B are two of the canonical points, and also happen, in this case, to be control points) and intermediate division points X and Y, the three sections of the Bezier are denoted AX (section 1), XY (section 2) and YB (section 3). When dragging a target point located in section 1, end point B will not move, and A, X, and Y will each move based on the position of the target point between A and X. When dragging a target point located in section 2, end points A and B will not move, and X and Y will each move based on the position of the target point between X and Y. When dragging a target point within section 3, end point A will not move, and X, Y, and B will each move based on the position of the target point between Y and B.

FIG. 7 shows how these constraints translate into adjustments of the canonical points on the Bezier curve in a graph of response curves 550. Each of the four response curves R.sub.i(t.sub.drag) shows the extent of motion of one of the canonical points (denoted 0, 1, 2, 3) as a percentage of the dragged position change of any arbitrary drag point along the curve C, where the t.sub.drag value of the selected point on the curve is on the horizontal axis, and the vertical axis shows the amount by which the end points and the section dividing points C(i/3), i=0, 1, . . . , 3, on the curve (i.e., the canonical points) are affected by dragging the curve at point C(t.sub.drag) to P.sub.drag.

Consider the case of dragging the curve at the first end point, t.sub.drag=0. Because (according to the third constraint above) this is the same as dragging P.sub.0, the response curve R.sub.0 for curve point C(0) has a value of 1 at that point, which means that the point at the first end of the curve (which is the same as the target point) moves as much as the target point is dragged. The response curve R.sub.1 for curve point C(1/3) has a value of 8/27 at t.sub.drag=0, because the Bezier basis function for the zeroth control point for a 3 degree curve is 8/27 evaluated at t.sub.drag=0. Thus, when the section dividing point that is 1/3 of the way along the curve is moved by a unit, the first end point of the curve moves by 8/27 of a unit. In a similar way, the response curve R.sub.2 for C(2/3) has a value (of the basis function) of 1/27 at the first end point of the curve, and the response curve R.sub.3 for C(1) has a value (of the basis function) of zero at the first end point as required by the constraint above that, for t<2/3, C(1) does not move.

When a target point C(t.sub.drag) is dragged to P.sub.drag, first compute the new positions of the end points and the section dividing points of the new curve C by applying the response curve to the original curve at: C(i/3)=.DELTA.R.sub.i(t.sub.drag)+C(i/3), i=0, . . . , 3 Then, the new control points for the curve are determined by writing the calculation of the Bezier curve points C(i/3), i=0, . . . , 3 in matrix form: C.sup.T=BP where B is the basis coefficient matrix:

.function..function..function..function..function..times..times..function.- .times..times..function..times..times..function..times..times..function..t- imes..times..function..times..times..function..times..times..function..tim- es..times..function..function..function..function. ##EQU00004## To find the new control points, C(i/t) is substituted for C(i/t) in the equation above, which is then solved for the new control points: {circumflex over (P)}=CB.sup.-1 Because the basis coefficient matrix is constant, it can be pre-computed. The new curve rendered from the control points will move towards P.sub.drag but may not actually reach it. In an interactive program, this is often not noticeable, because the constraint will be satisfied on the next iterations of the mouse tracking loop. However, it is possible to avoid this behavior in a manner described later.

The curve dragging method is extended to non-cubic curves by creating new response curves R.sub.i for points on the curve at C(i/d), i=0, . . . , d. For example, in FIG. 8, response curves 600 for a quadratic curve are shown. When the curve dragged is part of a multiple-segment Bezier curve, the curve continuity should be maintained by keeping the control points on the adjoining segments co-linear with the ones on the dragged segment, and at the same distance.

Extending the methods described above to surfaces provides an intuitive, natural way to edit the distortion surfaces described previously. A distortion surface of the kind shown in FIG. 5 can be described as:

.function..times..times..times..times..times..function..times..function. ##EQU00005## where u, v are the parameters of the surface, V.sub.i,j is the (n+1) X (m+1) mesh of control points, and B.sub.j.sup.m(u)B.sub.i.sup.n(v) are the Bezier basis functions of degree m, n as described above. The goal of the free-form manipulation is to drag an arbitrary point on the surface S(u.sub.drag, v.sub.drag) to P.sub.drag in a similar fashion to the curve manipulation method described above.

To drag a point on the surface, the parameters u.sub.drag, v.sub.drag of the selected point on the surface should be determined, given the selected target point P.sub.sel, so that S(u.sub.drag, v.sub.drag) is approximately equal to P.sub.sel. As shown in FIGS. 9 and 10, to accomplish this, a distortion surface 630 can be first coarsely sampled in uniform steps in u and v. A typical sampling rate of 4(n+1).times.4(m+1) can be used across the entire surface 630. By connecting points adjacent to each other in the parameter space, the resulting sample points form a mesh of quadrilaterals covering the surface. Each quadrilateral is checked to see if it contains P.sub.sel, by checking P.sub.sel against the line equations of the four borders of the quadrilateral (the lines are formed by proceeding around the quadrilateral in a consistent direction, e.g., clockwise). If P.sub.sel is on the same side of all four lines, then it lies inside. If P.sub.sel is found to lie inside one of the quadrilaterals 650, then the process is repeated, except this time the sampling is done over the parameter range for just that quadrilateral 655 rather than the entire surface. The indices of the sample points containing P.sub.sel, are used to determine the parameters u.sub.drag, v.sub.drag. While this process can be repeated indefinitely to improve accuracy, in practice two iterations are sufficient for interactive manipulation.

An alternative technique for determining the parameters of a drag point corresponding to a user-selected point on the surface is illustrated in FIGS. 11-13. FIG. 11 illustrates curve subdivision. A Bezier curve C(t) 700 can be subdivided into two joined curves L(t) 710 and R(t) 715 by computing two new sets of control points from the original set using the following:

.function..times..times..function. ##EQU00006##

.function..times..times..function. ##EQU00007## The two new curves are the same shape as the original, and L.sub.d and R.sub.0 have the same value. To split a Bezier surface, the same technique can be applied to each row of control points to split along the u parameter or each column of control points to split along the v parameter.

FIGS. 12 and 13 illustrate subdivision to determine surface parameters. To find the parameters u and v corresponding to a user-selected point on a surface 750, the surface can be recursively subdivided. A test can be made to see if the user-selected point is within the bounding box of the control points of each subdivided surface half. If it is, the subdivision continues recursively on that half. At each subdivision, the parametric bounds of the subsurface is recorded. This process continues until the size of the bounding box 755 becomes approximately the same size as a single pixel of the display device. At this point, the center of the parametric bounds of the subsurface provide a good approximation to the parametric coordinates of the selected point.

Applying the drag method to the surface proceeds in two steps as shown in FIG. 14. First the drag is applied to the iso-curve 800 at v.sub.drag. Then, each of the control points of this iso-curve 800, such as a control point 805, is used as a P.sub.drag for modifying the curves formed by the columns of control points in the surface. Because the surface drag is developed as a series of curve drags, it is useful to express the curve manipulation method described above for dragging the point C(t.sub.drag) to P.sub.drag as a function that generates a new set of curve control points from the original control points P: P=Drag(P,t.sub.drag,.DELTA.) where .DELTA.=P.sub.drag-C(t.sub.drag) he iso-curve at v.sub.drag C.sup.v is formed by control points P.sup.v computed via:

.times..times..times..function..times..times..times..times. ##EQU00008## A new set of control points for this iso-curve is computed with: {circumflex over (P)}=Drag(P.sup.v,u.sub.drag,P.sub.drag-S(u.sub.drag,v.sub.drag)) The control points for this new curve are used to drag the columns of the control points by applying them to the surface control points:

for j=0 . . . m P.sub.i.sup.u=V.sub.i,j, i=0 . . . n {circumflex over (P)}.sup.u=Drag(P.sup.u, v.sub.drag, {circumflex over (P)}.sub.j.sup.v-P.sub.j.sup.v) V.sub.i,j={circumflex over (P)}.sub.i.sup.u, i=0 . . . n

The methods described above are useful for free-form manipulation of the distortion surface to produce an arbitrary shape. However, there are many cases where it is useful to produce distortions with a symmetric shape, where the manipulation is confined to a single parameter. Consider an inflate pre-defined distortion as shown in FIG. 15. In this case, as the parameter is changed, the edges of the distortion move in or out. The inflate distortion is a bi-quadratic. The amount of distortion is controlled by a single parameter, which moves the control points on the center of each edge towards (or away from) the center of the mesh. While this manipulation can be done with a traditional user interface tool such as a slider control, another approach is to provide a handle 850 oh the surface that the user drags to the desired shape, subject to the constraints of the symmetry. This closely matches the free-form dragging behavior described above, and makes the surface editing more precise, easier to learn, and easier to use.

To provide this control, a method is needed to convert the movement of the mouse (in one dimension) into a corresponding movement amount for the symmetric movement of the control points in the distortion. This generally involves modifying the surface equation (see above) to incorporate the desired symmetric movement, and then solving that equation for the amount to move the control points.

Continuing with the inflate distortion example, a handle is placed at S(1/2,0). This handle is constrained to move only vertically and should track the top of the distortion. To simplify the problem, consider just the top iso-curve of the surface (v=0, V.sub.0,0 .2). As the handle is dragged, the control point V.sub.0,1 should move so that the point on the curve S(1/2,0) tracks the mouse as it moves. To find out how far V.sub.0,1 should move so that the handle tracks the curve, consider the formulation of the curve (with u=1/2, and ignoring v for the moment):

.function..times..times..times..times..times. ##EQU00009## With V.sub.0,0 and V.sub.0,2 fixed, we can see that V.sub.0,1 moves twice as far as the point on the curve S(1/2,0). Thus, when the handle at S(1/2,0) is dragged, the four control points on the edges are moved twice the distance the handle was moved, giving the illusion that the handle is fixed onto the edge of the distortion.

As a second, more complex example, consider the wave distortion shown in FIG. 16. When the single parameter of this distortion is changed, a left interior control point 900 moves up, and a right interior control point 905 moves down in equal amounts. If y is the wave amount, then the distortion is determined by: V.sub.1,1=c+y V.sub.1,2=c-y where c is the vertical coordinate of the center of the distortion's bounding box. (V.sub.i,j, refers to just they coordinate V.sub.i,j; because the x coordinates are not affected they may be ignored). To give maximum control, the handle should start out at S(1/4,1/2). As this handle is dragged up or down, we want it to track the surface, with V.sub.1,1 moving in the same direction as the handle and V.sub.1,2 moving in the opposite direction. To do this, we need to find the value corresponding to the difference between the original handle location at S(1/4,1/2) and P.sub.drag. If we call this difference d, and the corresponding distance the control points V.sub.1,1 and V.sub.1,2 each move y, we find d is related to y via the equation:

.function..function..times..times..times..times..function..function..times- ..times..function. .times..times..function..times..times..function..times..times..times..fun- ction..function..times..times..times..times..function. ##EQU00010## Solving for y gives:

.function..times..times..times..times..function..function..times..times..t- imes..times..function..times..function..times..function..times..function..- times..function..function..times..function..function. ##EQU00011## Collecting terms and substituting u=1/4, v=1/2 gives:

.times..times..times..times..times..times..times..times..times..times. ##EQU00012## This is the equation relating the mouse movement d to the control point movement y.

Other direct controls for pre-defined distortions can follow the same general strategy of relating the mouse movement to a point on the surface. Distortions can also have multiple handles (e.g., one for a vertical stretch and another for horizontal) with the implementation strategy being applied to each handle.

As mentioned, the method described above for free-form manipulation of the distortion of the surface using a point on the surface does not adjust a curve sufficiently in a single iteration to move a target point by an amount indicated by dragging. However, the method can be enhanced to move the point by the required amount in a single step. Below we discuss how this is done for the cubic case. The same approach can be applied to the quadratic case.

In the basic method the desired displacements of four canonical points on the curve, at t=0, 1/3, 2/3, and 1, are specified by the response curves for four specific choices of the dragged point, t.sub.drag=0, 1/3, 2/3, and 1. The behavior of the four on-curve canonical points for other values of t.sub.drag was derived by linear interpolation as shown by the linear segments of the response curves. Although linear functions are easy to compute, the result of the choice of linear interpolation is that the dragged point may not be displaced by the correct amount.

Among the possible methods for interpolating behavior for intermediate values of t.sub.drag, a set of scaled response curves, S.sub.1 derived in a manner explained below, works well. Starting with the response curves, R.sub.i, of the basic method, we find the resulting displacement of the Bezier control points, and of the point, t.sub.drag. The point, t.sub.