GB2247386A - Simulating line drawn by pen nib in computer graphics system - Google Patents

Abstract

A pen line is produced from curve data 2 generated from movement of a stylus across a tablet. A particular polygonal pen nib shape 10 is selected and the curve 2 divided into curve segments, for example parabolic segments. Closed curve outlines Fig 2(b) are produced for each segment by generating left and right outer curves and closing these at either end using the trailing edges 4, 5 of the nib. Successive segments Fig 2(b) are joined and an end cap 10 corresponding to the nib shape is added where the final segment does not join the first segment to form a closed curve. <IMAGE>

Description

DRAWING TECHNIQUE FOR COMPUTER GRAPHICS SYSTEM FIELD OF THE INVENTION This invention relates to 2D computer graphics drawing and painting systems and in particular to the provision of polygonal pen-nib effects.

BACKGROUND TO THE INVENTION 2D pixel-based pointing systems often rely on repeated stamping of the brush shape to achieve the effect of a brush stroke. 2D object based drawing systems, which are capable of supporting re-editing and animation of a drawing or picture, often ignore the concept of brushes or pens altogether.

The present invention aims to provide a rectangular nibbed pen or rectangular brush effect for use in an object based 2D graphics system.

SUMMARY OF THE INVENTION The invention is defined by independent Claims 1, 15 and 20 to which reference should be made.

In essence a pen line is formed by sub-dividing a curve into a number of curve segments and forming an outline around each. Each outline is preferably a closed curve. Each closed outline is formed by generating a selected polygonal outline, for example a square, and translating the start point of the curve segment to outside corners of the nib shape. Successive points along the curve are translated by a similar amount. The generated outlines, which will be on the left and right of the curve segment are joined at each end by the trailing edges of the nib.

Successive curve segments are processed in this manner until the curve is complete. If the completed curve is an open curve an end cap is generated at the end remote from the start point.

At the end of each curve segment the orientation of the curve is examined to see if there has been a turning point. A turning point occurs for a rectangular nib when the chosen corners of the nib to which the start point is translated are no longer adjacent the leading corner. In the more general case these corners may not be directly adjacent the leading corner and a turning point occurs when one or more additional corners have become interposed between the leading corner and the corners from which the outlines are generated.

During formation of the outline the orientation of the nib is fixed. That is, the nib orientation does not follow the curve so that the thickness of the line produced will vary. For a square nib the minimum line thickness is equal to the length of the nib edges and the maximum width is equal to f2* (edge length). For a hexagonal nib this varies between a minimum of J3 (edge length) = 1.732* (edge length) and 2* (edge length) at the maximum.

It will be appreciated that the invention enables a wide range of italic and other calligraphic effects to be generated.

Furthermore polygonal pen line are useful generally for generating shape outlines.

BRIEF DESCRIPTION OF DRAWINGS Embodiments of the invention will now be described with reference to the accompanying drawings in which: Figure 1 is a flow chart showing the shapes in a 2D graphics animation systems; Figure 2 shows the construction of a pen line embodying the invention, the line including a turning point; Figure 3 is a similar illustration to Figure 2 but without a turning point; Figure 4 shows the final appearance of the lines of figures 2 and 3 after rendering; and Figure 5 shows, schematically, components of a hardware system for putting the invention into operation.

DESCRIPTION OF PREFERRED EMBODIMENTS In order to appreciate the complete system to which the invention is applied figure 1 shows the stages in a 2D video animation process. The process is described in more detail in our common dated copending application no which claims priority from Australian application PK0619 filed 13th June 1990 and the content of which is incorporated herein by reference.

There are three major stages in the generation of interactive vector paint images: Stage 1: While the user is actually drawing a line, visual feedback is required which indicates the area of the screen covered by the brush stroke. This may change when the brush stroke is completed, so should only be temporarily combined with the remainder of the picture.

Stage 2: In many circumstances, the final appearance of any part of a brush stroke cannot be determined until the stroke is completed.

An example of this is where the colour of the brush stroke is defined to smoothly vary between one colour at the left extreme to another at the right extreme: the colour at any point cannot be determined until the left-right length of the stroke is known.

When a brush stroke is completed all of the information relating to that brush stroke can be derived, so the final appearance of the stroke can be generated. The pixel image of the brush stroke can then be permanently composited with the remainder of the picture.

Stage 3: When the picture is animated or altered in any way other than the addition of new objects on top of the existing picture, the altered regions of the screeen will need to be regenerated. This is done in a third stage, where the composite effect of all of the brush strokes and other graphic objects is calculated.

STAGE 1 Stage 1 is the interactive drawing stage, and is repeated rapidly during the drawing process to give the appearance that the brush stroke is being continually painted by the user. Stage 1 consists of the following major steps: 1) Determine pen position and pressure: this is done by a digitising tablet, which in most cases will output the information as an RS232C data stream.

2) Decode, buffer, and convert to floating point: this stage accepts the data stream from a digitising tablet and converts it to a standard format.

Considerable advantage is gained by using a floating point format, and all further calculations are performed in floating point until the pixel stage.

3) Curve fitting: this stage takes the X and Y point samples from the digitising tablet and fits spline curves to that data. The type of spline is not particularly important, but parabolic splines, a subset of conic splines commonly used for 2D graphics, are suitable, and are assumed for the remainder of this document.

4) Generate approximate appearance of brush line segment: this step calculates the shape and position of the brush stroke segment which has been added since the last pass through stage 1, fills the region with pixels, and writes the resulting pixels to the overlay frame store.

5) Temporarily composite with main picture: this step overlays the brush segments on the main picture, and displays the results on the monitor. The incomplete brush stroke is not permanently composited with the picture at this stage, as it will be replaced with a final rendition on stage 2, when all the information about the brush stroke is known.

STAGE 2 Stage 2 occurs whenever the brush stroke currently being drawn is completed. This is usually signified by the user lifting the pen from the digitising tablet. The temporary brush stroke image generated in Stage l is replaced by the final appearance in this stage.

6) Place entire curve into database: This step accumulates the entire path curve and creates a database object describing the brush stroke. The path is in the form of parabolic spline data.

7) Generate brush stroke outline: this step generates a closed spline curve which approximately traces the outline that would result were the brush shapes to be moved along the brush path. This outline is also in the form of parabolic spline data.

8) Determine edges and colours of brush strokes: This step calculates the intersections of the brush stroke outline with scan lines, and determines the colour at each intersection.

9) Convert to pixels and linear ramp run-lengths: this step sorts the edges into monotonic order along a scan line, converts the floating point scan-line intersections into screen pixel coordinates and generates the pixel colours between sucessive edges.

Where appropriate, -linear ramp colour runs are generated instead of individual pixel colours. The compression into linear ramps is done to reduce the computing overhead and data transmission times, and is not a fundamental part of the system.

10) Write pixels and expand runs into overlay frame store: in this step pixels are written into the overlay frame store, and linear ramps are expanded by hardware into the frame store. This produces a pixel image of the entire brush stroke, along with a digital linear key which indicates the level of transparency at each pixel of the brush stroke.

11) Composite with main picture: This step combines the image with the main picture using the digital linear key to determine the proportion of colour intensity from the brush stroke in comparison versus the picture. This is similar to step 5, except that the results of the combination process are written to the picture frame store.

STAGE 3 Quite a different image generation process is required after any changes have been made to all or a portion of the screen. Any operation which changes the picture, with the exception of compositing more objects or brush strokes on top ofthe image, can require that a portion of the entire image be re-generated. The sequence of major steps required for stage 3 is: 12) Alter or animate picture database: in this step the picture database is altered in some manner which would result in a visible change to all or part of the picture displayed on the screen. These changes may include mathematical transformations on brush strokes, other 2D objects or groups of objects, changing the layering order, altering the shape of objects or the path of brush strokes, changing the colour of transparency of objects, changing a fill texture or image, and so forth.

These changes may be animated using key-frame or other techniques, requiring the automatic generation of a sequence of images based on the original picture, but with alterations between sucessive frames. Whenever a change is made that affects a portion of the visible image, then the image must eventually be regenerated to show those changes.

This stage (3) outlines the process of regenerating the image.

13) Cull any objects not in altered region: In this step any brush strokes or other 2D objects (such as polygons or text) which do not overlap the region of the screen which must be updated are removed from further calculation. This step is not necessary for accurate rendition of the image, but can greatly reduce the computer time taken to generate the picture.

14) Generate outlines of all visible brush strokes: in this step outline polysplines for all brush strokes are generated based on the path data for those brush strokes.

15) Determine edges and colours of brush strokes: This step calculates the intersections of all of the brush stroke outlines (and those of other 2D objects) with scan lines, and determines the colour at each intersection.

16) Covert to pixels and linear ramp run-lengths: this step sorts the edges into monotonic order along a scan line, converts the floating point scan-line intersections into screen pixel coordinates and generates the pixel colours between sucessive edges.

Where appropriate, linear ramp colour runs are generated instead of individual pixel colours. The compression in linear ramps is done to reduce the computing overhead and data transmission times, and is not a fundemental part of the system.

17) Convert to pixels of final image: in this step pixels are written into the main picture frame store, and linear ramps are expanded by hardware into the frame store.

The present invention is concerned with step seven of stage 2 and in particular with the generation of a brush stroke or pen line using a polygonal brush or pen nib for example a rectangular nib. Figure 2 shows a constructed pen line in which the following reference points can be identified: The pen nib shape is here shown as a square 1 which traces a path 2 in a manner to be described. The square has a leading corner 3 and trailing edges 4 and 5. Construction of the pen line involves the formation of left and right curve segments 6 and 7 either side of the path 2. A turning points 8 will be created when the pen line has turned through 90 degrees as will be explained.

The pen line or brush stroke of a polygonal or rectangular brush is the region swept out by the polygon or rectangle as it follows a curve described by a set of first order discontinuous and discontinuous parabolic curve segments. The curve segments are derived mathematically during step four of the process illustrated in figure 1 from data aquired from a stylus and tablet in stages 1 and 2. The choice of first order parabolic curves is made for convenience only and should not be construed as limiting.

The polygon or rectangle does not rotate as it follows the curve. This means that the pen line width will vary along the line of the curve. This can be understood by considering a square nib as shown in figure 2. At the start point the line width is equal to the side lengths x. However, when the line path has moved through 45 degrees the line width will be the diagonal length f2 x.

It should be noted that the pen line is generated by applying a defined pen nib to a stored curve. The pen line may be derived from the curve data and the pen nib shape.

At the starting point of every curve segment 0 in figure 2, the curve direction is defined by its tangent at that point.

The direction defines which quadrant the curve segment lies, the starting point being the origins. Curve segments continue to contribute to the pen line until a turning point is reached. A turning point occurs when the quadrant of the next segment is different from the quadrant of the current segment. A turning point is shown at 8 in figure 2. There is no turning point in the example of figure 3. It is assumed that non-monotonic curve segments have already been segmented at their turning points.

When a turning point is reached, the line outline is completed as shown in figure 2b and this portion is treated as a single object for rendering. When the last curve portion has been completed, one of two possibilities may occur. If the line is closed, that is the end of the last segment joins the beginning of the first, the pen line is complete when the rendering of the final portion has finished. However, if the curve is open, as in the examples of figures 2 and 3, an end cap 10 is generated as a separate object. The end cap is the shape of the pen nib.

To construct the pen line outline it is first necessary to identify the leading corner of the pen nib. This can only be done when it has been decided in what quadrant the curve segment lies. In the case at the origin in figure 2 the curve segment lies in the first quadrant and corner 3 is identified as the leading corner. The two corners adjacent the leading corner are used to contruct the pen line outline. These are the left and right corners 10 and 12.

Each pen outline, like the pen curve itself, comprises a number of segments. However, the outline is necessarily closed, even for an open curve.

With the leading corner identified, the trailing edges 4 and 3 are appended to the curve and form the end of the outline.

The left curve segment is then developed by translating the first point on the current curve to the left corner 10 and translating the remaining points by the same amount. The left curve segment 6 is then appended to the curve outline.

A similar process is performed to develop the right hand curve. Thus, the first point is translated to the right corner 12 and successive points are translated by the same amount. When constructed the right hand curve is pushed onto the processor stack for future use.

The next left hand curve segment is then developed in a similar manner and a corresponding right hand curve is constructed and pushed onto the stack.

When a turning point is reached the trailing edges 4, 5 are appended to the curve, as shown in figure 2(b) this time taken counter-clockwise. The curve is then closed by popping the right hand curve segments off the stack and appending them to the curve outline. The completed curve path is shown as segment 14 in figure 2(b).

Once the turning point has been reached, the process is repeated for the next set of curve segments until another turning point or the line end is reached. At the line end, a square end cap is generated to finish the line.

The process described is illustrated in the flow chart of figure 4.

The figure 4 flow chart and description relate to rectangular nibs, and in particular to square nibs. However, the method may easily be modified to include any polygonal nib shape.

For example, with an equilateral triangular nib the right and left hand curve segments would be constructed from the two trailing corners. Similarly, rather than appending the two trailing edges at the start and end of the curve, the base edge only would be appended and a turning point would occur every 600.

Likewise with a pentagonal nib, the three trailing edges would replace the two used for the rectangular case and turning points will occur every 108 .

With hexagonal and larger sided nibs, the algorithm has to be modified so that the outer most corners of the nib are used to construct the right and left hand curve segments. The corners adjacent the leading corner will no longer be on the longest diagonal of the nib shape.

Rendering of the curve produced by any polygonal nib shape may be performed by any standard technique. One possible technique is that described in our common dated copending application no claiming priority from Australian application PK0619 dated 13th June 1990. The rendering process assumes that any internal boundaries and areas of overlap between different nib outlines belong to the same curve are eliminated.

In other words colouring during rendering is non-additive for areas belonging to the same curve.

A rotated brush may be handled by transforming the curve to which the brush is being applied to a space where the brush is orthogonal and transforming the outline curves back after they have been generated.

Figure 5 shows, in block form, the major components of a 2D drawing system for putting the invention into practice. The curve around which the polygonal nib line is created is input by the user using a graphics tablet 20 and a stylus (not shown).

The actual nib shape is selected from a menu using keyboard 22.

Displays 24 and 26 provide the user with a visual monitor of the available options and of the pen line formation. The mathematical computations required to calculate the curve outlines are performed by transputers 30 and the 16 MByte DRAM 32 may be used as the stack to which the right hand curve segments are pushed and from which they are popped during curve formation.

Claims (20)

1. l. A method of drawing a pen line in a computer graphics system, comprising: defining a path for the pen; defining a polygonal nib shape; sub-dividing the pen path into a number of curve segments; calculating for each curve segment, the outline of a region swept out by the nib as it follows the path, wherein the nib orientation remains fixed as it follows the path.
2. 2. A method according to Claim 1, wherein the outline calculated for each curve segment is a closed curve.
3. 3. A method according to Claim 1 or 2, comprising for each curve segment after the first, identifying whether the pen path has moved through a turning point.
4. 4. A method according to Claim 1, 2 or 3, wherein the outline for the first curve segment is produced by calculating the tangent of the curve at the start point. Identifying the leading corner of the pen nib at that point and identifying the outermost corners of the nib on the left and right sides of the leading corner.
5. 5. A method according to Claim 4, comprising appending to the curve the trailing edges of the nib between the left and right outermost corner and opposite the leading corner.
6. 6. A method according to Claim 4 or 5, comprising constructing left and right curve segments.
7. 7. A method according to Claim 6, wherein the left curve segment is calculated by translating the start point of the curve segment to the left outermost corner of the nib and translating successive points on the curve segment by the same amount.
8. 8. A method according to Claim 6 or 7, wherein the right curve segment is calculated by translating the start poing to the right outermost edge and successive points on the curve segment are calculated by a similar amount.
9. 9. A method according to Claims 6, 7 or 8, wherein one of the left and right curve segments is appended to the outline and the other is stored in memory.
10. 10. A method according to Claim 9, wherein the trailing edges of the nib are appended to the free end of the appended one of the left and right curve segments.
11. 11. A method according to Claim 10, wherein the outline display segment is closed by appending that curve segment stored in memory between the trailing edges appended at opposite ends of the curve segment.
12. 12. A method according to any previous claim, wherein upon completion of the final outline segment the pen line is completed by addition of the pen outline if the pen path is not a closed path.
13. 13. A method according to any of Claims 4 to 12, appendent Claim 3 and 4, wherein upon detection of a turning point the next successive curve segment is produced by recalculating the tangent of the start point of the curve segment to be produced.
14. 14. A method according to any preceding claim, wherein a rotating nib effect is produced by transforming the pen path to a space where the nib is orthogonal and transforming the outline back after generation.
15. 15. A method of generating a pen line in a computer graphics system comprising the steps of: 1) loading a set of data defining a curve from which the line to be generated; 2) defining a polygonal pen nib; 3) dividing the curve into a plurality of curve segments; 4) for the first curve segment, identifying the tangent to the curve at the start-point and so defining the leading corner of the pen nib; 5) defining the left and outermost nib corners adjacent the leading corner and appending to the outline the trailing edges of the nib between the trailing edges of the nib between the outermost corners and opposite the leading corner; 6) calculating left and right curve outlines by translating the start point to the left and right corners respectively and by translating successive points along the curve segment by substantially the same amount;; 7) generating the trailing edges of the nib at the end of the left and right curve outlines and completing the curve segments outline by appending the left, right and trailing edges to the curve in a clockwise or counter-clockwise direction; and 8) repeating steps 5) to 7) for successive curve segments.
16. 16. A method according to Claim 15, wherein if a turning point is detected after step 7) step 8 further comprises repeating steps 4) for the next curve segment.
17. 17. A method according to Claim 15 or 16 further comprising 9) generating the nib polygon as an end cap after the final curve segment if the complete curve is an open curve.
18. 18. A method according to any preceding claim, wherein the pen nib is rectangular.
19. 19. A method according to Claim 18, wherein the pen nib is square.
20. 20. Apparatus for generating pen lines in a computer graphics system comprising: means for defining a polygonal nib shape; means for subdividing the curve into a plurality of curve segments; and means for generating the outline of a region swept out by the pen nib as it follows the curve, the nib orientation being fixed as it moves along the curve.