Method and Apparatus for Generating and Displaying Freeform Strokes of Varying or Constant Width Using Adaptive Forward Differencing

The present invention relates to a method and apparatus for generating and displaying freeform strokes of varying or constant width and, more specifically, to a method and apparatus for generating and displaying points along a centerline curve and right and left offset curves of a freeform stroke of varying or constant width using an adaptive forward differencing technique.

Freeform curves, which have no width, have useful applications in, for example, computer aided design and manufacturing systems, computer graphics, graphic arts, and typesetting for creating curved surfaces (see, e.g., U.S. Pat. No. 4,943,935 issued to Sato, which discloses a method and apparatus for expressing curved surfaces using curves of an nth order such as Bezier cubic curves). Freeform strokes, which have widths, also have useful applications in, for example, computer aided design and manufacturing systems, computer graphics, graphic arts, and typesetting for creating both uniform and variable width shapes and figures (see, e.g., U.S. Pat. No. 4,674,058 issued to Lindbloom et al., which discloses a method and apparatus for representing and recreating two dimensional arbitrary shapes using Bezier curves).

In particular, U.S. Pat. No. 4,855,935 issued to Lien et al, and S-L Lien, M. Shantz, and V. Pratt, Adaptive Forward Differencing for Rendering Curves and Curved Surfaces, Computer Graphics Vol. 21 No. 4 (July 1987) disclose an adaptive forward differencing technique for rendering curves and curved surfaces on display device, such as a CRT, by actuating display elements defining the curve. A plurality of data points representative of display elements are used to render the curve in substantially form single pixel steps using the adaptive forward differencing technique.

Accordingly, it is an object of the present invention to provide a method and apparatus for generating and displaying a freeform stroke of varying or constant width.

Another object of the present invention is to provide a method and apparatus for generating and displaying points along a centerline curve and right and left offset curves of a freeform stroke of varying or constant width using an adaptive forward differencing technique.

Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out in the appended claims.

To achieve the foregoing objects, and in accordance with the purposes of the invention as embodied and broadly described herein, a method of generating and displaying a freeform stroke of varying or constant width is provided, comprising the steps of generating, using an adaptive forward differencing technique in accordance with a step size of a parameter t, points along a centerline curve of the freeform stroke, the centerline curve being a spline curve varying as a function of the parameter t, and each of the points along the centerline curve being associated with a horizontal coordinate defined by a function x(t), a vertical coordinate defined by a function y(t), and a width defined by a function w(t); generating a normal vector associated with each of the points along the centerline curve; generating points along a right offset curve and a left offset curve for corresponding ones of the points along the centerline curve, each of the points along the right and left offset curves being associated with a horizontal coordinate and a vertical coordinate generated in accordance with the horizontal coordinate, vertical coordinate, width, and normal vector associated with a corresponding point along the centerline curve; and displaying graphical representations of the points along the right and left offset curves to display an outer boundary of the freeform stroke.

Also in accordance with the purposes of the invention as embodied and broadly described herein, an apparatus for generating and displaying a freeform stroke of varying or constant width is provided, comprising a circuit for generating, using an adaptive forward differencing technique in accordance with a step size of a parameter t, points along a centerline curve of the freeform stroke, the centerline curve being a spline curve varying as a function of the parameter t, and each of the points along the centerline curve being associated with a horizontal coordinate defined by a function x(t), a vertical coordinate defined by a function y(t), and a width defined by a function w(t); a circuit for generating a normal vector associated with each of the points along the centerline curve; a circuit for generating points along a right offset curve and a left offset curve for corresponding ones of the points along the centerline curve, each of the points along the right and left offset curves being associated with a horizontal coordinate and a vertical coordinate generated in accordance with the horizontal coordinate, vertical coordinate, width, and normal vector associated with a corresponding point along the centerline curve; and a circuit for displaying graphical representations of the points along the right and left offset curves to display an outer boundary of the freeform stroke.

The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate a presently preferred embodiments of the invention and, together with the general description given above and the detailed description of the preferred embodiments given below, serve to explain the principles of the invention. In the drawings:

FIG. 1 is a block diagram illustrating a freeform stroke generation and display system in accordance with one embodiment of the present invention;

FIG. 2 is a block diagram illustrating a forward differencing unit of the freeform stroke generation and display system of FIG. 1;

FIG. 3 is a block diagram illustrating a forwarding circuit of the forward differencing unit of FIG. 2;

FIG. 4 is a flow diagram illustrating an operation of the freeform stroke generation and display system of FIG. 1;

FIG. 5 illustrates a technique for transmitting horizontal coordinates, vertical coordinates, and widths associated with control points to a processor of the freeform stroke generation and display system of FIG. 1; and

FIG. 6 is a block diagram of a data processing system for generating and displaying freeform strokes in accordance with another embodiment of the present invention.

Reference will now be made in detail to the presently preferred embodiments of the invention as illustrated in the accompanying drawings, in which like reference characters designate like or corresponding parts throughout the several drawings.

In the present invention, a freeform stroke is defined by a centerline curve and a right and left offset curve. The right and left offset curves are each a distance w from the centerline curve, the distance w being defined along a normal to each point along the centerline curve. In the absence of a sign convention for the normal, an offset curve is defined on both sides of the centerline curve. Generally, the term "left offset curve" designates the offset curve based upon a normal given by a positive sign, while the term "right offset curve" designates the offset curve based upon a normal by the negative sign. Further, the term "offset curve" is used to refer to one or the other of the left and right offset curves, while the term "offset curve pair" indicates both the left and right offset curves. Still further, the term "offset point" is used to refer to a point along an offset curve. As a preliminary note, it should be understood that the centerline curve of the freeform stroke is a spline curve, i.e., a curve whose shape can be defined by a series of control points, as is known to those of ordinary skill in the art. Examples of spline curves are Bezier curves and B-spline curves.

As shown in FIG. 1, there is provided a freeform stroke generation and display system 10 for generating and displaying a freeform stroke of constant or varying width in accordance with a first embodiment of the present invention. The system 10 comprises an input device 20, a processor 30, a forward differencing ("FD") unit 40, an adjustment unit 50, an offset generator 60, a display 70, and data/control busses 80, 90, and 100.

The input device 20 comprises, for example, any of a keyboard, mouse, touchscreen panel, and digitizer for enabling an operator of the system 10 to transmit to the processor 30 parameters associated with a plurality of control points which define a centerline curve of a freeform stroke to be generated and displayed.

The processor 30 comprises, for example, any standard CPU capable of initializing the FD unit 40 by determining forward differencing coefficients from the parameters transmitted by the input device 20, and capable of generating points along a right offset curve and a left offset curve for corresponding ones of the control points using the parameters associated with the control points and respective tangent vectors. For example, a Motorola 680x0, Intel/IBM R6000, or SPARC can be used as the processor 30. The processor 30 executes a software program stored in a memory (not shown) to perform the functions described below in connection with the processor 30.

The FD unit 40 comprises, for example, circuitry for generating, using a forward differencing technique in accordance with a step size of a parameter t, points along a centerline curve of the freeform stroke, wherein the centerline curve varies as a function of the parameter t, and wherein each point along the centerline curve is associated with a horizontal coordinate defined by a function x(t), a vertical coordinate defined by a function y(t), and a width defined by a function w(t).

As shown in FIG. 2, preferably, the FD unit 40 comprises FD circuits 100, 110, 120, 130, and 140 corresponding to the parameters x, y, w, dx/dt, and dy/dt, respectively. As also shown in FIG. 2, preferably, each FD circuit includes four forwarding circuits F.sub.0 through F.sub.3, each of which includes a data latch, an adder, and control logic (not shown).

As shown in FIG. 3, each forwarding circuit has an input line, an output line, a clock line, a latch control line, and a data line, all of which are connected to the data/control busses 80 and 90. It should be understood that, when the latch control line is high, data on the data line is loaded into the data latch on a next clock cycle. When the latch control line is low, data on the input line is added to the data stored in the data latch on the next clock cycle. Further, the output line, preferably, always transmits the data stored in the latch. It should also be understood that the input line of the leftmost forwarding circuit of each FD circuit of FIG. 2 is fed with the constant zero.

The adjustment unit 50 of FIG. 1 comprises, for example, circuitry for updating coefficients stored in the forwarding circuits of the FD unit 40 in accordance with instructions from the offset generator 60. Preferably, the adjustment unit 50 comprises a plurality of registers, each corresponding to one of the FD circuits 100, 110, 120, 130, and 140, for storing the differencing coefficients. The step adjustment circuit 50, preferably, also comprises control logic for updating the coefficients stored in its registers in accordance with a step size adjustment indicated by the offset generator 60, and for loading the updated coefficients, via the data/control bus 90, into corresponding ones of the forwarding circuits of the FD circuits 100, 110, 120, 130, and 140.

The offset generator 60 comprises, for example, circuitry for generating a unit normal vector associated with each point along the centerline curve generated by the FD unit 40, and for generating points along a right offset curve and a left offset curve for corresponding ones of the points along the centerline curve. Each of the points along the right and left offset curves is associated with a horizontal coordinate and a vertical coordinate generated in accordance with the horizontal coordinate, vertical coordinate, width, and unit normal vector associated with a corresponding point along the centerline curve. Preferably, the offset generator 60 also comprises, for example, circuitry for specifying a step size adjustment in accordance with the screen coordinates of adjacent right and left offset points.

The display 70 of FIG. 1 comprises, for example, a color or monochrome visual display capable of displaying graphical representations of points along the centerline curve and the right and left offset curves generated by the offset generator 60. Likewise, the display 70 can comprise a printing device such as a laser printer or plotter.

An operation of the system 10 of FIG. 1 will now be described, in detail, with reference to the flow diagram 1000 of FIG. 4.

In step S1010, an operator transmits to the processor 30, via the input device 20, horizontal coordinates, vertical coordinates, and widths associated with a plurality of control points. As described above, the control points define the shape of a centerline curve of a freeform stroke which is to be generated and displayed. The parameters associated with each control point include a horizontal coordinate, a vertical coordinate, and a width.

For the sake of simplicity, it will be assumed that the operator inputs horizontal and vertical coordinates and widths associated with only four control points. For example, as shown in FIG. 5, in step S1010, the operator inputs horizontal coordinates V0.sub.x through V3.sub.x, vertical coordinates V0.sub.y through V3.sub.y, and widths VO.sub.w through V3.sub.w which are associated with control points V0 through V3, respectively. It should be understood by those of ordinary skill in the art that control point V0 and control point V3 are known to be points along the centerline curve and that control points V1 and V2 determine the shape of the centerline curve between the control points V0 and V3.

Step S1010 can be performed in many ways. For example, assuming that the input device 20 includes a floppy disk drive, the horizontal and vertical coordinates and widths associated with each control point can be stored on a floppy disk and transmitted directly to the processor 30. Alternatively, if the input device 20 includes a keyboard, the operator can transmit the coordinates and widths into the processor 30 by typing them on the keyboard. Preferably, however, the input device includes a mouse (not shown) and, as shown in FIG. 5, the operator controls the mouse to move a pointer 110 along the display 70' to a position on the display 70' corresponding to the desired coordinates associated with a control point. To transmit the coordinates to the processor 30, the operator, for example, "clicks" the mouse, whereupon the control point is displayed on the display 70'. To enter the widths, the described embodiment provides a circle on the display 70', having a radius R, centered around each control point, as also shown in FIG. 5. The radius R corresponds to the width associated with the respective control point. To set the width associated with a control point, the operator uses the mouse to place the pointer 110 on the perimeter of a circle surrounding the control point. By "pulling" the perimeter of the circle either "in" or "out," the operator can vary the radius R of the circle and, thereby, vary the width associated with the respective control point. Preferably, the width of a control point is automatically transmitted to the processor 30 each time the radius R of the corresponding circle is changed. A type of software required to control the screen display of the display 70' is well known to persons of ordinary skill in the art. After completion of step S1010, control passes to step S1020.

In step S1020, the processor 30 generates initial forward differencing coefficients .delta..sub.0x through .delta..sub.3x, .delta..sub.0y through .delta..sub.3y, and .delta..sub.0w through .delta..sub.3w from each the coordinates and widths transmitted by the input device 20 in step S1010, as follows: ##EQU1##

Also in step S1020, the processor 30 generates initial forward differencing coefficients .delta..sub.0dx/dt through .delta..sub.3dx/dt and .delta..sub.0dy/dt through .delta..sub.3dy/dt from each the coordinates and widths transmitted by the input device 20 in step S1010, as follows: ##EQU2## It should be understood that the term dt in the above equation represents an initial step size which is adjusted automatically. Good initial estimates are known to those of ordinary skill in the art.

In step S1030, the processor 30 initializes the FD unit 40 by loading, via the data/control bus 80, each of the initial forward differencing coefficients into a corresponding forwarding circuit of a corresponding one of the FD circuits 100, 110, 120, 130, and 140. For example, the processor 30 loads the initial coefficients .delta..sub.0x through .delta..sub.3x into the forwarding circuits F.sub.0x through F.sub.3x, respectively, of the FD circuit 100; loads the initial coefficients .delta..sub.0y through .delta..sub.3y into the forwarding circuits F.sub.0y through F.sub.3y, respectively, of the FD circuit 110; loads the initial coefficients .delta..sub.0w through .delta..sub.3w into the forwarding circuits F.sub.0w through F.sub.3w, respectively, of the FD circuit 120; loads the initial coefficients .delta..sub.dx/dt through .delta..sub.3dx/dt into the forwarding circuits F.sub.0dx/dt through F.sub.3dx/dt, respectively, of the FD circuit 130; and loads the initial coefficients .delta..sub.0dy/dt through .delta..sub.3dy/dt into the forwarding circuits F.sub.0dy/dt through F.sub.3dy/dt, respectively, of the FD circuit 140.

The loading of the initial coefficients into the forwarding circuits by the processor 30 can be accomplished by appropriate control of the clock lines, data lines, and latch control lines of each forwarding circuit. Specifically, the processor 30 places the initial coefficients on the corresponding data lines of the forwarding circuits, places a high signal on each of the latch control lines, and sends a clock pulse to each of the clock lines. Also in step S1030, the processor 30 stores the initial coefficients into corresponding registers of the adjustment unit 50 via data/control bus 100. After completion of step S1020, control passes to step S1040.

In step S1040, the processor 30 generates right and left offset points corresponding to each of the control points V0 and V3. AS described above, both V0 and V3 are known to be points along the centerline curve and, accordingly, the corresponding right and left offset points can be generated by the processor 30 using the coordinates and widths associated with the control points V0 and V3 and their respective tangent vectors.

For example, the processor 30 generates a right offset point V0.sub.ro =(V0.sub.rox, V0.sub.roy) and left offset point V0.sub.lo =(V0.sub.lox, V0.sub.loy) corresponding to the control point V0, and generates a right offset point V3.sub.ro =(V3.sub.rox, V3.sub.roy) and left offset point V3.sub.lo =(V3.sub.lox, V3.sub.loy) corresponding to the control point V3, as follows: ##EQU3## It should be evident from the foregoing that each right and left offset point generated by the processor 30 is associated with a horizontal coordinate and a vertical coordinate.

Once the processor 30 has generated the right and left offset points corresponding to each of the control points V0 and V3, the processor 30 transmits, via the data/control bus 80, the horizontal and vertical coordinates to the offset generator 60. Upon completion of step S1040, control passes to step S1050.

In step S1050, the offset generator 60 converts the horizontal and vertical coordinates associated with the offset points corresponding to the control points V0 and V3 into horizontal and vertical screen coordinates, respectively. Preferably, the horizontal and vertical screen coordinates correspond to horizontal and vertical positions, respectively, of pixels on the display 70. To perform the conversion process, the offset generator 60, preferably, selects the high order bits of the internal representations for converting the horizontal coordinates into horizontal screen coordinates and for converting the vertical coordinates into vertical screen coordinates. Upon completion of step S1050, control passes to step S1060.

In step S1060, the offset generator 60 designates the right and left offset points corresponding to the control point V0 as "current" right and left offset points, respectively. Also in step S1060, the offset generator 60 designates the right and left offset points corresponding to the control point V3 as "end" right and left offset points, respectively. Control then passes to step S1070.

In step S1070, the offset generator 60 transmits the horizontal and vertical screen coordinates associated with the "current" offset points to the display 70, wherein the display 70 displays graphical representations of the "current" offset points to display a portion of, i.e., two points along, the outer boundary of the freeform curve. Upon completion of step S1070, control passes to step S1080.

In step S1080, the offset generator 60 determines whether the screen coordinates associated with the "current" offset points are the same as the screen coordinates associated with the "end" offset points. If the offset generator 60 determines that the screen coordinates associated with the "current" offset points are the same as the screen coordinates associated with the "end" offset points, operation of the system 10 is stopped. Otherwise, control passes to step S1090.

In step S1090, the offset generator 60 determines whether to instruct the adjustment unit 50 to update the forward differencing coefficients stored in the latches of the FD unit 40. Specifically, if the x and y coordinates of both of the new offset points are in the same pixel as the corresponding current offset points, it instructs the adjustment unit 50 to double the step size, in which case the adjustment unit 50 uses the values of the coefficients before the step was taken to compute new coefficients corresponding to a step size twice as large, and loads them into the latches of the FD unit 40. If, however, the x or y coordinate of either new offset point is more than one pixel away from the corresponding coordinate of the corresponding current offset point, the offset generator 60 instructs the adjustment unit 50 to halve the step size, in which case the adjustment unit 50 uses the values of the coefficients before the step was taken to compute new coefficients corresponding to a step size half as large and loads them into the latches of the FD unit 40. Upon completion of step S1090, control passes to step S1100,

In step S1100, the processor 30 controls the FD unit 40, via the data/control bus 80, to perform one "step" of a forward differencing technique on the updated coefficients that were loaded into its forwarding circuits by the adjustment unit 50 in step S1090. In particular, the processor 30 places a low signal on the latch control lines of each forwarding circuit in the FD unit 40 and sends one clock pulse along each clock line. As explained above, this action by the processor 30 causes the coefficient loaded in each forwarding circuit to be added to the coefficient loaded in a subsequent forwarding circuit, the result being that each FD circuit of the FD unit 40 produces a new output value. It should be understood that these new output values describe a "new" point p along the centerline curve of the freeform stroke.

For example, upon completion of step S1100, the FD circuit 110 produces a "new" horizontal coordinate P.sub.x, the FD circuit 120 produces a "new" vertical coordinate p.sub.y, and the FD circuit 130 produces a "new" width P.sub.w, each of which is associated with the "new" point p. In addition, the FD circuit 130 produces a "new" value P.sub.dx/dt and the FD circuit 140 produces a "new" value P.sub.dy/dt which, as will be described below, are used to generate a unit normal vector associated with the "new" point p. After generating the "new" values P.sub.x, P.sub.y, P.sub.w, P.sub.dx/dt, and P.sub.dy/dt, the FD unit 40 transmits the "new" values to the offset generator 60. Upon completion of step S1100, control passes to step S1110.

In step S1110, the offset generator 60 generates a unit normal vector P.sub.n associated with the "new" point p, as follows: ##EQU4## The circuitry required by the offset generator 60 to generate the unit normal vector P.sub.n can comprise, for example, adders, multipliers, storage registers, and appropriate control logic. Upon completion of step S1110, control then passes to step S1120.

In step S1120, the offset generator 60 generates "new" right and left offset points corresponding to the "new" point p. Specifically, the offset generator 60 generates the "new" offset points such that each is associated with a horizontal coordinate and a vertical coordinate generated in accordance with the horizontal coordinate, vertical coordinate, width, and normal vector associated with the "new" point p.

For example, the processor 30 generates a "new" right offset point p.sub.ro =(P.sub.rox, P.sub.roy) and "new" left offset point P.sub.lo =(P.sub.lox, P.sub.loy), as follows: ##EQU5## Once again, the circuitry required by the offset generator 60 to generate the "new" offset points can comprise, for example, adders, multipliers, storage registers, and appropriate control logic. Upon completion of step S1120, control passes to step S1130.

In step S1130, the offset generator 60 converts the horizontal and vertical coordinates associated with each of the "new" offset points into horizontal and vertical screen coordinates, respectively. As mentioned above with regard to step S1050, the horizontal and vertical screen coordinates correspond to horizontal and vertical positions, respectively, of pixels on the display 70. As also mentioned above with regard to step S1050, the offset generator 60, preferably, selects the high order bits of the internal representations for performing the conversion process. Upon completion of step S1130, control passes to step S1140.

In step S1140, the offset generator 60 compares the horizontal and vertical screen coordinate associated with the "new" right offset point with the horizontal and vertical screen coordinates, respectively, associated with the "current" right offset point to determine a right offset horizontal distance and a right offset vertical distance, respectively.

Also in step S1140, the offset generator 60 compares the horizontal and vertical screen coordinate associated with the "new" left offset point with the horizontal and vertical screen coordinates, respectively, associated with the "current" left offset point to determine a left offset horizontal distance and a left offset vertical distance, respectively.

It should be understood that the left and right offset horizontal and vertical distances indicate how far apart on the display 70 graphical representations of the "new" and "current" right and left offset points would be displayed. Upon completion of step S1140, control passes to step S1150.

In step S1150, the offset generator 60 determines whether each of the right and left offset horizontal distances and each of the right and left offset vertical distances is within a predetermined range of values. The purpose of this step is to determine whether the differences between the screen coordinates associated with the "current" and "new" offset points correspond to the distances between adjacent pixels of the display 70. Preferably, the "current" and "new" offset points are one pixel distance apart and, therefore, the predetermined range of values, preferably, corresponds to one pixel distance of the display 70.

If in step S1150 the offset generator 60 determines that any of the right and left offset horizontal distances and the right and left offset vertical distances are not within the predetermined range of values, control passes to step S1160. Otherwise, control passes to step S1170.

In step S1160, the offset generator 60 instructs the adjustment unit 50 to update the forward differencing coefficients that are stored in its registers in accordance with a new step size, and to load the updated coefficients into the FD unit 40. Preferably, the offset generator 60 instructs the adjustment unit 50 to update the coefficients in accordance with a doubled step size when any of the right and left offset horizontal distances and right and left offset vertical distances is less than the predetermined range of values. Likewise, preferably, the offset generator 60 instructs the adjustment unit 50 to update the coefficients in accordance with a halved step size when any of the right and left offset horizontal distances and right and left offset vertical distances is greater than the predetermined range of values. Upon completion of step S1160 control returns to step S1100. Preferably, however, if the step size has been halved since the last step was taken, it is not doubled until another step is taken.

In step S1170, the offset generator 60 designates the "new" offset points as the "current" offset points. Upon completion of step S1170, control returns to step S1070.

As shown in FIG. 6, there is provided a data processing system 200 for generating and displaying a freeform stroke of constant or varying width in accordance with a second embodiment of the present invention. The data processing system 200 comprises an input device 210, a processor 220, a memory 230, and a display 240.

The input device 210 and display 240 of FIG. 6 comprise the same or equivalent components and perform the same or equivalent functions as the input device 20 and display 70, respectively, of FIG. 1.

The processor 220 comprises, for example, any standard CPU capable of performing the same or equivalent functions performed by the processor 30, FD unit 40, adjustment unit 50, and offset generator 60 of FIG. 1. As in the first embodiment, the processor 220 can comprise a Motorola 680x0, Intel/IBM R6000, or SPARC.

The memory 230 comprises, for example, any of a magnetic, optical, and semiconductor memory for storing a software program which is executed by the processor 220 to enable it to perform the same or equivalent functions performed by the processor 30, FD unit 40, adjustment unit 50, and offset generator 60 of FIG. 1. An example of such a software program can be found in Appendix A. Appendix A is incorporated in and constitutes a part of the specification. The program in Appendix A is written in the language "C" and is intended to be executed by a data processing system based upon the Motorola 680x0, Intel/IBM R6000, or SPARC processor. The memory 230 also serves as a workspace for the processor 220 in a manner known to those of ordinary skill in the art.

It should be understood that operation of the data processing, system 200 of FIG. 6 is the same or equivalent to the operation of the freeform stroke generation and display system 10 of FIG. 1 and, therefore, a detailed description of such will be omitted.

Additional advantages and modifications of the present invention will readily occur to those skilled in the art. Therefore, the invention in its broader aspects is not limited to the specific details, representative devices, and illustrated examples shown and described. Accordingly, departures may be made from such details without departing from the spirit or scope of the general inventive concept as defined by the appended claims and their equivalents. ##SPC1##