GB2248754A - Electronic painting system - Google Patents

Abstract

A two dimensional computer generated image system generates images using a tablet and stylus. Drawn lines are reduced to a series of parabolic splines by curve fitting and an outline corresponding to a given curiform pen nib is created. The outline is produced for each of a number of spline segments, end caps are formed and the outline filled. Different nib shapes can be generated by varying the nib tension and nib width may be varied along a spline. <IMAGE>

Description

ELECTRONIC PAINTING SYSTEM The present invention relates to the presentation in electronic form of two dimensional images created by object painting.

Hitherto such presentations have been either "pixel painting" or "object based drawing".

Pixel painting systems emulate an artist's painting process by colouring screen pixels with the "paint colour in the path of the brush". The brush is usually controlled by the pen of a digitising tablet, and the brush stroke is formed by repeating the image of the brush at close intervals on the screen so that the individual brush images appear to merge into a line.

This technique has the advantage of spontaneity, simplicity of implementation, and a close emulation of the process of painting with physical media.

Object based drawing systems keep a database of outlines of two dimensional screen regions, which can then be filled by scan-line rendering. The outlines are often entered into the computer by drawing them on a digitising tablet. Once drawn, the outlines ('objects') can be altered in many ways, including moving, re-colouring, size changing, rotation, deletion, copying, bringing in front or putting behind other objects, and so forth.

Two major advantages over pixel systems are that a large library of objects can be created which can be used repeatedly in many images to save work, and that the objects can be readily animated. The major disadvantage is that the method that a user must employ to create images is quite different from the process of painting. It is therefore difficult to utilise the creative processes that most artists must learn from a young age.

The object of the present invention is to combine the advantages of object based drawing with the expressiveness and simulation of traditional media that can be achieved with pixel painting, in order to provide significant advantages in both presentation graphics and animation. It will be appreciated by those skilled in the art that these advantages are achieved as a consequence of high complexity and increased computer processing power requirements. This combined method may be termed "vector painting n, The invention is defined in the independent claims to which reference should be made.

In a preferred embodiment of the invention an image is created and updated interactively using a tablet and stylus.

Data from the stylus is converted to floating point form and parabolic spline curves are fitted. The exactness of the fit is variable. Optionally the approximate appearance of a pen line is generated around the polyspline and displayed interactively. The term pen line and brush stroke are synonymous and both will be used throughout the description.

The polyspline data is loaded into a database and a complete brush stroke may be generated at this point. This involves the creation of a brush outline which will be described later. The outline is filled using a non-cumulative or a cumulative algorithm with a single colour or using an airbrush algorithm and then composited with the main picture.

At this stage all objects in the main picture that are affected by the new brush stroke are identified and outlines generated and filled. Finally the brush strokes are converted to pixel format and stored or displayed.

The brush stroke outline generation forms left and right curves on the respective sides of a spline segment. Where the tangents of adjacent splines of the inner curve interset a mitre point is generated.

A vertex is dealt with by considering it as a spline of length zero and acute angles can be dealt with by a spline bi-section technique which removes the acute angle.

Embodiments of the invention will now be described, by way of example, and with reference to the accompanying drawings, in which: Figure 1 is a flow chart showing a general overview of a vector painting system embodying the invention; Figure 2 shows how a brush stroke is formed using a quadratic round brush algorithm; Figure 3 shows how a brush stroke is formed using a square brush algorithm; Figures 4 a) and b) show a comparison of errors in forming brush strokes using, respectively, quadratic round and square brushes and the final appearance of those brush strokes; Figure 5 shows, in greater detail, the first stage in forming a brush stroke from a curve; Figure 6 shows the second stage in the process of figure 5; Figure 7 shows final formation of the brush stroke;; Figures 8 a) to d) show the use of mitre points to deal with conditions where a parabola cannot be filled while maintaining second order curve continuity; Figures 9 a) to d) show the detection of mitre points at the intersection of polyspline segments; Figure 10 shows the calculation of semi-circular and parabolic end caps for a brush stroke; Figure 11 illustrates the problems of acute angles at curve vertices and smooth curve portions; Figure 12 illustrates a solution to the problem outlined in figure 11; Figures 13, a) and b) show, respectively, a development of the solution of figure 12 and the finished controlled spline; Figure 14 shows two loops, one larger and one smaller than the brush size; Figure 15 shows how brush strokes including loops are constructed; Figure 16 a) shows the outlines of the looped brush strokes of figure 15;; Figure 16 b) shows the strokes of figure 16 a) filled and highlighting overlap; Figure 17 shows how polysplines are numbered according to parabola direction for filling; Figure 18 shows how brush stroke opacity accumulates at cross-over points; Figure 19 shows the brush stroke of figure 18 rendered with cumulative opacity; Figure 20 shows the brush stroke of figure 18 rendered with one level opacity Figure 21 shows the brush stroke of figure 19 with a highlighted outline; Figure 22 is a flow chart of the brush stroke formation and filling method; Figure 23 shows colour change requirements for an airbrush; Figure 24 shows how an airbrush stroke is divided into chambers for filling; Figure 25 shows how colour is calculated at intersections of scan lines with chamber edges; Figure 26 shows scan conversion for an airbrush where colour overlaying is non-commutative;; Figures 27 a) to k) show the effects available using brush tensioning; Figures 28 a) to d) show the different appearances of a brush stroke at different tensions; Figures 29 a) to e) show different elliptical brush strokes; Figures 30 a) to d) show how brush strokes may be constructed using a variable brush size; Figures 31 a) to d) show the resultant brush strokes of figures 30 a) to d); Figure 32 illustrates how unit pixels are defined for an antialiasing system; Figure 33 shows how a polyspline area covering two pixels is dealt with when calculating antialiasing colour; Figure 34 is similar to figure 44 and covers the case where the intersections of the polyspline with the pixel scan lines are not in a common unit pixel; Figure 35 covers the case where the intersections span more than three pixels; Figure 36 shows the behaviour of light incident on a paint layer;; Figure 37 is similar to figure 36 where a white paper layer is placed under the paint layer; Figure 38 considers a layer of paint in a multilayer surface; and Figure 39 shows light incident on two parallel layers.

Figure 1 shows the steps in the generation of interactive vector paint images. The process can be dividied into three stages as follows: 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 vary smoothly 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 screen 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.

Considering now each stage in more detail.

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; step numbers correspond to the numbered stages in figure 1.

1) Determine pen position and pressure: this is done in a known manner 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 in stage 2, when all of the information about the brush stroke is known.

Stare 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 1 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 shape 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 successive 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.

Stave 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 of the 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 or 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 successive frames. Whenever a change is made that affects a portion of the visible image, then that 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) 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 successive 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.

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.

BRUSH OUTLINES Step 7 in stage 2 and step 14 in stage 3 involve the generation of a brush outline from the spline data. For the purposes of this explanation parabolic splines are assumed although other spline curves could be used.

Deriving the envelope of brush movement has been a vexing design problem for 2 dimensional vector graphics, yet is fundamental to a 2D vector system which tries to emulate a paint system. There have been a number of solutions proposed, but none have yet been satisfactory. Real brush strokes from physical brushes have complex outlines affected by the direction and compression of brush hairs, quantity and viscosity of paint, smoothness of the painting surface, and other physical phenomena.

Accurate simulation of these artifacts is extremely difficult, probably undesirable, and certainly commercially unviable. What is required is a compromise with high aesthetic qualities, yet is defined by simple algorithms and implemented with readily tractable calculation.

The solution presented here addresses the following problems: Generation of outlines using "round" brushes.

Smooth interpolation of vertices, splines, and end-caps of lines The problem of spline extension to infinity as a vertex or tangent angle approaches zero.

Simulation of airbrush effects.

Rendering of transparent brush strokes with either cumulative or non-cumulative opacity The method also allows a wide range of embellishments, including: Tensioned brushes, smoothly interpolable between square, parabolic, circular, and diamond shapes.

Brush stroke opacity varying with pen pressure Variable brush radius along a line, which can be controlled by pen pressure.

Calligraphic style brush strokes.

Elliptical and rectangular brushes.

Square Brushes The first solution to the problem of brush strokes is to use square brushes. This has the advantage that the resultant outline of a square, non rotating brush moving along a quadratic splined path is also a quadratic spline.

However, square brushes have several disadvantages.

Firstly, the line thickness varies depending on the angle of the stroke by a ratio of J2 to 1. Secondly, second order continuity is not maintained, even on gentle curves, resulting in "kinks" in the brush outline. Moreover, the outline has flat portions wherever the base line becomes tangent to a side of the square brush. Furthermore, square ends of brush strokes are unsightly.

The algorithm for generation of square brushes is complex, and there are many exceptions. However square brushes do have their own distinctive style and thus their own set of applications and uses.

True Round Brushes Round brushes have long been used by pixel paint systems as a reasonable compromise between aesthetics, controllability, and simplicity. Systems such as the Quantel Paintbox (RTM) "stamp" a round brush at many points along a line, giving the illusion of continuity. The situation is more complex in a vector paint system, where the requirement is to calculate and fill the curve described by the outline of the brush. The problem is that the outline of a circle moving on a parabolic path is a quartic curve. Calculating the roots of quartic curves for every scan line is not an efficient process.

It must be noted that there is no "true solution" to brush strokes: while it is possible to generate the true curve of a circular brush, a circular brush is in itself a rough approximation. Even an entirely accurate simulation of real-world brushes is not a good solution, as many of the artifacts of real brushes are undesirable. The optimum solution is the one with the best combination of aesthetics, artistic control, and implementation simplicity.

quadratic Round Brushes The following describes a method of generating a close likeness to true round brushes, which has the advantages of only using second order, quadratic curves, which require a simple algorithm whilst maintaining second order continuity is maintained: there are no corners or kinks. Furthermore, overlaying transparency (where the brush path crosses itself, the line gets darker) can be handled accurately.

The algorithm is accurate at all knot points along the spline, but diverges from the true solution between the knot points This divergence is unobtrusive and usually unnoticeable.

Figures 2 and 3 show typical short brush strokes constructed using the quadratic round brush algorithm and a first square brush algorithm respectively.

Figure 4 compares the problems associated with each approach. The square, unsightly ends of the figure 3 brush stroke should be noticed as should the flats, kinks and irregular line thickness associated with the square brush.

The error for the quadratic round brushes shown in figure 4 is a worst case error, limited by an acute angle control technique presented later in this description. The square brush technique is theoretically correct, but unsightly. It also suffers from serious problems with acute angles where second order continuity breaks down, shown at 2, interpolability, and transparency shading. Internal lines, shown at 4, make cumulative opacity shading difficult and a complex exception to the algorithm is required to place the extra square shown at 10.

The unsightly flat 6 and ends 8 can be seen in figure 46b. The square brush also suffers from the problem that as it is not a simple closed curve it cannot be used as a brush outline.

Referring now to figure 5 the generation of a brush stroke using the quadratic round brush algorithm will now be described.

The algorithm assumes that the brush rotates with the direction of the line. With a circular brush, this rotation has no effect on the brush shape, but it does have implications for transparency overlays, as well as the extension of the algorithm to elliptical brushes.

The algorithm operates in the following manner: At each knot point in the original algorithm shown at 12 in figure 5, two points are generated. These are the knot points of the polysplines describing the left side and the right side of the brush stroke (left and right are used here both for convenience, and because they have real meaning in the rendering phase as will be explained later). These points 14, 16 lie along the normal 18 to the tangent 20 of the original knot a distance equal to the radius of the brush stroke from the original knot.

Squares 22 and 24 in figure 5 are the control points of the original polyspline and are the points at which the tangents of adjacent knot points 26, 28 intersect with tangent 20 of knot point 12.

From newly created left and right knot points 14, 16, the tangents of the parabolas which comprise the left and right polysplines can be calculated. This is simple as these tangents are parallel to the tangent of the path polyspline, but pass through the new knot points. The knots and tangents are more than adequate to fully define the new parabolas. The generation of the parallel tangents is shown in figure 6, with reference 30 showing the tangent to left hand know point 14 and 32 the tangent to right hand knot point 34. The left and right polyspline control points 36, 38, 40, 42 are calculated in the same manner as the path control points.

Now that the knot points and the control points of the left and right polyspline parabolas are known, all of the information required to display them is known. The completed left and right hand polyspline parabolas 44, 46 are shown in figure 7.

As can be seen from a consideration of figure 6, there are circumstances where a parabola cannot be fitted while maintaining second order continuity of the curve. This occurs on the inside of curves which are "tighter" than the brush thickness, including vertices. In these circumstances, a "mitre point" is introduced. Figure 8 shows four curves, three of which, b) to d), require mitre points. Mitre points are generated where the parabola generated which passes through the knot points does not maintain second order continuity at both knots. In figure 8 a) a parabola can be fitted to the inner curve so that no mitre point is required. Figure 8 b) shows the case where surrounding polyspline segments intersect at a knot point. This condition may either be treated as a mitre point 48 or as a parabola of zero size.In figure 8 c) a mitre point 48 is created at the intersection of surrounding polyspline segments.

Figure 8 d) shows the limit case. This case is not treated any differently from figure 8 c) and a mitre point 48 is generated at the intersection of the inner polyspline segments.

Figure 9 also illustrates conditions under which mitre points are required. Again, mitre points are required in conditions b)1 c) and d). Condition a) is the usual condition in which the tangent of parabola B are the opposite sign to those of the shared knots 50, 52 with parabolas A and C. In figure 9 b), the tangents of parabola B are the same sign as those of the shared knot points with parabolas A and C. In figure 9 c) the tangents of parabola B are of opposite sign to those of A at the shared knot and the same as those of C at the respective knot.

The reverse situation to 9 c) is shown in 9 d).

A mitre point is therefore calculated at the intersection of the two surrounding polyspline segments. As these segments will usually be parabolas, there can be two intersections. The correct intersection can be calculated by intersecting only the half-parabolas lying on the appropriate side of the control points.

When the curve is rendered, the mitre point is used to limit the length of the curve which is considered an edge. While the knot point is usually used for this purpose, the knot point is ignored for edge list calculation where there is a Mitre point. The knot point is, however, still used to define the parabola.

The end caps at the start and end of a line are ideally perfect semicircles. While the end-caps can be readily implemented as semicircles, as will be described in section on tensioned splines there is an advantage in approximating the end-caps with two parabolas. This allows the end-caps to be implemented using the same system as used for acute angles. This means that the brush shape is not exactly circular, but then there is no particular reason why it should be. End-caps are generated by applying the method for acute angles to be described, with an angle of zero degrees. Alternatively, they can be treated as a special case with the spline knots and control points calculated as shown below.The difference between semi-circular and parabolic end caps is shown in figure 10 in which the right hand end cap 54 is semi-circular and the left hand end cap shows the small difference between parabolic 56 and semi-circular 58.

Vertices do not need to be treated as a special case: a vertex can simply be considered as a path spline segment of zero length. The outline polysplines will not have zero length unless the angle of the line at that vertex is zero. However, it is useful to tag vertices as special cases in order to give the appearance of square brushes and other brush effects.

The outline polyspline knot points are generated by projecting along the normal to the tangent a distance equal to the radius. The only difference from the normal spline algorithm is that the base polyspline knot points used for the two knot points is the same point. As the effective spline length (zero) will always be smaller than the brush width, a mitre point will be generated on the inside angle of a vertex (see figure 8d).

This is generated in the normal manner, as described previously, again treating the vertex as two co-incident knot points.

Acute angles, both at vertices and at smooth portions of the curve, present a problem for systems based on quadratic splines. The problem is that as the tangents at the knots approach parallel, the control point at the intersections of those tangents approaches infinity. If an acute angle is drawn as part of the initial curve before curve fitting, the problem is avoided. This is because the curve fitting algorithm will detect the high degree of error, and break up the curve into two or more parabolas. However, in an animation or interpolating system, the problem can become severe The tangents of a curve may interpolate through parallel during the course of an interpolation between more usual angles. As the angle approaches 0 (or 180Q, depending on how you look at it), the parabola will tend towards infinity.During an animation, a perfectly normal bit of curve will suddenly start growing longer and longer until it shoots off the screen. While this is theoretically correct for parabolic splines, natural objects do not behave in this way when bent. The object of an animation or drawing system is to create realistic and/or controllable images, not to implement perfectly parabolic splines. Figure 11 shows how a decrease in angle results in a very large increase in error.

A simple solution to the problem of acute angles is to prevent them from occurring. This can be achieved by bi-secting the spline into two parabolas. If this is done when the angle is less than or equal to 2 x arctan (0.5) (i.e. 53.130102350 or 0.9272952 radians), then complete interpolability and continuity of animation can be maintained, as vertices of lines bent to 1800 (with parallel tangents) will appear identical to end-caps of lines, and can be generated using the same algorithm as can be seen from figure 12.

Figure 13 a) shows how the problem may be avoided and figure 13 b) compares an uncontrolled spline 80 with a controlled spline 82 to which the following method has been applied.

In order for the spline to interpolate smoothly through the angles of 0Z and 53.13 , and therefore create a total continuity between vertices, end-caps, and spline segments, the new knot point must be at the position that it would be if the angle of the tangents of the line were 53.13 (arctan (0.5)) whenever the angle is less than this. This point is calculated as follows with reference to figure 13.

The tangents 60, 62 to the polyspline are derived on each side of the curve in question. Then the angle (+) between the two tangents is derived. Then, derive two lines 64, 66 passing through the existing knot points 68, 70-of the polyspline at an angle of Arctan (0,5 ] -#/2 from the tangents, angled towards each other. The angle between these lines will be Arctan (0.5). Next the intersection 72 of these lines is derived and then the mid-points 74, 76 between this intersection and the two knot points are derived. Finally, the midpoint 78 of the two midpoints 74, 76 is derived. This mid-point 78 is the new knot point.

The line 79 passing through the two midpoints is the tangent of the new knot, and is parallel to the line passing through the two path knots.

The control points 81, 83 of the two new parabolas are found at the intersection of the new knot tangent and the tangents of the path knots.

Figure 13 b) shows what the two new splines would look like compared to the result if the spline was not divided and controlled. The difference in this example is not extreme as the original angle is not much less than 53.13 . This difference becomes more pronounced as the angle between the tangents approaches 00.

The system embodying the invetnion can also properly handle cross-overs and loops. Loops may be smaller or larger than the brush size and the following is an example of a loop larger than the brush size, a crossover, and a loop smaller than the brush size.

Figures 14 to 17 show the treatment of loops and crossovers. The construction of the brush strokes is shown in figure 15. A regular on-grid loop is shown for drawing convenience and accuracy in the MacDraw (RTM). Similar results are obtained for irregular loops and crossovers. Both smaller and larger loops are formed from a polyspline made up of three spline segments. However, there is a large degree of overlap in the smaller loop.

The outline of the brush strokes is shown in figure 15.

The larger loop is exactly as one would expect and second order continuity is maintained. The loop is able to interpolate smoothly through the situation where the loop diameter equals the brush diameter. In this case, the knot points of the central parabola are co-incident, and the parabola has zero length.

Figure 16 a) shows the appearance of the loops when constructed and Figure 16 b) shows what the two loops would look like when scan converted and filled with a translucent colour which increases in density as more layers are applied (most translucent materials behave in this way). This highlights the next problem: how to distinguish between areas which are to be filled once, twice, multiple times, or not at all.

This problem will be considered with reference to figure 17.

The standard scan-line polygon fill algorithm (using odd=fill, even=don't fill) is inadequate where brush strokes may overlap. This is because the algorithm cannot distinguish between holes and overlaps. There is, however, a simple algorithm which can distinguish between these states, and between any level of overlapping transparency.

This algorithm scans a line from left to right, incrementing an opacity index on left edges, and decrementing it on right edges. In order to do this, it must know which spline segments are to the left and to the right of the spline defining the path of the brush (here called the path polyspline).

Detection of left and right edge segments must occur after the curve has undergone all applied rotations or reflections, and after spline segments with vertical extrema have been divided.

A link must be maintained to the path spline segment so that a left or right comparison can be made. This link can be achieved by numbering the path spline segments as shown in figure 17 a), and storing those numbers with the outline polyspline as each outline segment is created. Here, vertices are treated as segments and numbered so that the brush stroke in figure 17 a) which comprises three polyspline segments is numbered 1 to 5 with the two vertices being numbered 1 and 5. Alternatively, database links may be used, with each spline segment appearing as a record linked to the path spline segment. However, this approach is likely to be inefficient.

A segment is left if: Edge knot 1 (x) + Edge knot 2 (x) (Path knot 1 (x) + Path knot 2 (xf) CO.

A segment is right if: Edge knot 1 (x) + Edge knot 2 (x) - (Path knot 1 (x) + Path knot 2 (x)) > O.

The equation can only equal zero if the spline segment is a horizontal straight line or the brush radius =zero. In neither of these cases is the line rendered anyway. (the treatment of horizontal straight lines is determined by the anti-aliasing algorithm). Tagging of the spline segments as left or right is probably best performed in the same pre-processing step that splits parabolas with vertical extrema, but must be done after this split is performed, or erroneous tagging may occur.

Vertexes are simply treated as spline segments of length zero, so the vertex is substituted for both knots of the path spline. Note that the parabolas which make up the end-caps of a vertex may also require splitting due to vertical extreme, but that this need not be treated as a special case as those parabola are no different from others. Figure 17 b) shows the brush stroke of figure 17 a) after tagging with left parabolas highlighted with respect to right parabolas. At the vertical extremum 90 the parabolas are broken.

After tagging, the brush stroke may be filled. This is achieved by the following method which is given with reference to figure 18: 1. Determine the x value of the intersection of all relevant parabolas with the scan line in question. (there can be only one intersection per parabola, as segments with two possible intersections have already been divided); 2. Sort these in order of increasing x (assuming positive x is to the right); 3. Set opacity index to zero; Go through list of intersections, incrementing the opacity index on every left edge, and decrementing it on every right edge; 4. The opacity index is then a direct indicator of the number of time the brush overlays itself for the region between the two intersections. This can then be used directly to calculate the cumulative transparency of that region.Zero = no layers (brush stroke not present), 1 = one layer, 2 = two layers, etc. The opacity index is shown superimposed on the scan line and brush stroke in figure 18.

This simplified algorithm is presented here for clarity.

It has the fundamental flaw that it does not distinguish between the order of overlays. While this is adequate for transparent colours, or any situation where the colour in all portions of the line is the same, it breaks down for airbrushing, blended lines, or multiple different colour brush strokes. This is because the "z axis" stacking order of overlays is undetermined and the colour overlaying operation is non-commutative.

An algorithm combining cumulative opacity, opaque lines, and airbrushing is presented later in the "airbrush" section.

Figure 19 shows how the brush stroke of figure 18 would appear when rendered with cumulative opacity. However, there are circumstances, such as filling in a region which is supposed to be flat shaded, where a single level of transparency can be desirable. This is easily achieved by interpreting all opacity index values greater than 1 as being equal to one. As the opacity index is an accurate index to the numbers of times the brush overlays an area, it can also be used for other purposes, such as defining holes, where the opacity index can determine how far the hole "eats through" underlying polygons or cell layers.

The brush stroke of figure 18 rendered with single level translucency is shown in figure 20.

The outline of a parabolic polyspline using this method is also a parabolic polyspline. As no new constructs are introduced, the outline can be used as the path of a brush using the same algorithms. This can give accents to the edge of lines, or be used for special effects. This is not true of the square brush algorithm, as there are internal "construction" lines which would also be followed by an outline. The square brush algorithms will be considered later. The brush stroke of figure 19 with outline is shown in figure 21.

The flow chart of figure 22 summarises the brush stroke generation and filling as described.

AIRBRUSHES In a system which attempts to simulate and surpass pixel paint systems using vectors, one of the most important aspects is an airbrush simulation. This is because airbrushes have translucent edges, allowing an artist to build up colour, and subtly modify areas without introducing the hard colour edges prevalent in most computer graphics.

The problem with doing this is the difficulty of calculating the appropriate colour changes along a scan line that an airbrush would exhibit.

The following description describes a simple and tractable algorithm which closely approximates a "perfect" airbrush solution. The algorithm has the following characteristics: 1. The colour error term is constrained; 2. Colour continuity is maintained; 3 It operates on all of the spline constructs mentioned previously without special cases; 4. It handles overlaying line segments; No mathematics more complex than a linear interpolation is involved.

This discussion defines the colour of the path spline as colour A, and the colour of the outline as colour B. In a typical airbrush, colour B is fully transparent, but there is no need for this to be a constraint. A typical airbrush stroke showing colour changes is shown in figure 23.

The following description describes the airbrush algorithm with reference to figures 23 to 26. For convenience only, the novel portions of the algorithm are described in detail, these are essentially the fill and colour calculation methods.

Alqorithm Context The context of the algorithm is important, as several steps must precede it. A rough overview of the stages of rendering a brush stroke is as follows: 1) Spline input stage: Input the raw curve data from the pen; Provide user feedback by rendering temporary brush; stroke segments using the following stages; 2) Curve fit stage; Fit parabolic splines to the raw data, to obtain the "path polyspline"; Number the polyspline segments between knot points in order from the start of the line to the end.A vertex is treated as a polyspline segment (two co-incident knot points) and therefore has its own number; 3) Animation stage Perform any animation transformations on the objects; 4) Prepare to render stage; Transform viewpoint into object co-ordinate space; Determine bounds of region to be rendered; Cull any objects lying outside these bounds; Distribute remaining objects to accelerator processors; Assign scan lines to processors; 5) Outline generation stage: generate the outline polyspline (accelerated); Project knot points of outline polyspline at normals from path polyspline knots points; Divide any spline with the angle of tangents at less then 53.13"; Generate mitre points on the inside of vertices Divide parabolas at vertices to generate tensioned brushes (if included); Number the outline polysplines generated, incorporating the number of the path polyspline segment; 6) Screen co-ordinate conversion stage (accelerated): Transform all polysplines to screen coordinates (performing rotations, translations, and scaling operations as defined by the camera, picture, cell object hierarchy, and brush stroke transformation matrices); Break all parabolas with vertical extrema into two matching parabolas with a knot point at the extremum.

Renumber these parabolas: Create "chamber" numbering (chambers are defined in the next section) Prepare bounding boxes of brush strokes; 7) Scan line cull stage (accelerated): Cull any objects whose bounding box does not intersect the scan line; Cull any chambers within remaining objects which do not intersect the scan line; Cull any edges of chambers which do not intersect the scan line; 8) Intersection stage (accelerated): Intersect all remaiing lines with the scan line; 9) Sort stage (accelerated): Sort all intersections in order of increasing x; 10) Intersection colour calculate stage (accelerated): Calculate the colour at all x intersections for each overlay layer.

The method for doing this follows.

11) Pixel colour calculation stage (accelerated}: Where possible, generate an incremental run to interpolate pixel colour in hardware. Overlapping airbrush lines cannot be run-length encoded at high quality, as the resultant colour from the overlap is non-linear. This will be the case in any situation where the transparency between any two linearly varying layers also varies, as it does with the standard airbrush situation of transparent edges and semi-opaque centre.

Where incremental runs are not accurate enough (perhaps determined by a "quality" parameter), calculate the colour at each pixel by interpolating the colour in each overlay layer, and applying the colour overlay algorithm. Do this from the top overlay layer to the bottom, stopping when 100% opacity is reached; Convert to render engine commands; Send the pixel and run-length data to the root transputers; 12) Draw stage: Dump the result in the frame store; Fill Algorithm The fill algorithm is essentially a bi-linear interpolation, similar to Gouraud shading. The algorithm is performed at scan-convert time, and requires no special preparation before scan conversion, except that the path spline is included in the scan conversion list and the brush stroke must have two colours associated with it.As with the standard scan conversion method, the algorithm must be preceded by the splitting of parabolas at vertical extrema.

The lines included in the scan conversion list are: 1. Outline polyspline segments; 2. Path polyspline segments (centre line); 3. Normals (lines connecting knots or vertices of the path polyspline with corresponding knots on the edge polyspline). These normals do not need to be explicitly included, as the points defining the lines will be included in the list as spline knots and vertices; 4. Normals to the outline spline knots on the "inside" of a vertex are not included: the mitre line is used instead; 5. Mitre lines (lines joining a vertex to mitre point on the inside of a vertex outline); Chambers (Figure 24) The brush stroke is divided into "chambers", each of which lie between the path polyspline and the outline. Each chamber has points, with a vertex being treated as two knot points. Each chamber is a closed curve with 4 sides, up to two of which may be parabolas.In the case of vertices, one of those sides has zero length. If a scan line intersects a chamber, there will be two, and only two, intersection points, as spline segments with two horizontal intersections have previously been divided at vertical extrema. In order to know the overlaying order of chambers for colour calculations, it is necessary to number the chambers in the same order as they were generated from the path polyspline. More than one chamber is generated from each path polyspline segment, but the order in which the chambers from a segment are numbered is not important, as they cannot overlay.

In figure 24 the original spline numbering is shown in a) and the chamber numbering in b). Starting at the left hand end of the brush stroke chambers 1 and 2 are formed by the vertex (which is treated as two knots of length zero and the knot points of spline segment two. Chambers 3 and 4 are formed between the knot points at the ends of spline segments 2, with the mitre point between segments 2 and 3 treated as a knot point. The chambers are allocated similarly around the brush stroke.

The chamber data structure consists of three parts: 1) The path polyspline (with splines broken at vertical extrema); 2) The outline polyspline; 3) The chamber list (a table of four pointers for each chamber as shown in chambers 12 and 13 in figure 24).

The chamber list is simply a sequential list of all of the chambers in the brush stroke, with four pointers associated with each chamber. These pointers point to the knot points in the path polyspline or the outline polyspline that define the chamber. Vertices in the path polyspine are entered into the chamber's table twice, as they are treated as two co-incident knot points. Mitre points are entered once only.

The order of the pointers in the chamber's table is not important as long as they circle the chamber (in either direction) and do not cross over.

Colour Calculation The colour is calculated at each scan-line intersection with chamber edges, consisting of either outline or centre parabolas, mitre lines, or normals. This is shown in figure 25.

For outline parabolas, the colour is B. For centre spline segments, the colour is A. For intersections with the normals and mitre lines, the colour is the linear interpolation between A and B, depending upon the distance that the intersection is from the centre knot or vertex as a proportion of the radius. Colour of a single chamber along the scan line between the two intersection points is linearly interpolated. In figure 25 the colour at scan line intersection 100 has contributions from A and B. The A contribution is the distance dl from the knot divided by the radius r and the B contribution is the distance from the B colour knot point 102 which is (r-dl) divided by the radius r.

Thus the colour at intersection 100 is (dlA + (r-dl)B)/r.

Similarly the colour at intersections 104 is (d3A + (r-d3)B)/r.

This process can be generalised by generating an interpolation value (ss) which is a single floating point value between 0 and 1.0. This value is calculated on the basis that the outline of a brush stroke is always 00, and the center line is always 1.0. The colour is later calculated by using the interpolation value as a proportion between colour A and colours B.

This approach is more general, as the interpolation value can then be used in the same manner as a texture value, and can therefore be used in conjunction with colour lines to obtain non-linear airbrush blending, or to blend between a colour and a texture, or between two textures. This technique is illustrated in figure 26.

Overlavinq In a colour model which includes opacity as well as translucency, the order of layers is critical. The colour model currently in use is (R,G,B,T), where T is a translucency value.

If we use the symbol @ to represent the action of combining colours that overlay, and C(l) @ C(2), means that C(2) overlays C(l), then C(l) @ @ C(2) = C(2) @ C(1), that is the colour combining operation is non commutative. For truly transparent colours, such as clear inks and cellophane, the order of colour overlay does not matter. However, the RGBT colour model cannot represent these materials. Correct rendering order can be ensured because each chamber is numbered. If two chambers overlay, then the lower numbered chamber is C(1), and the higher numbered chamber is C(2).

Error This method does produce some error from the "perfect" result. However, this error is constrained, continuous, and will rarely be noticeable.

It is easy to see that there is no error at the intersection of chamber edges with the scan line. A discrepancy can only occur within a chamber.

There is also no error when the polyspline segment is straight, or when the scan line is normal to the polyspline segment.

Maximum error occurs in the central region of a chamber bounded by polysplines of high curvature.

Rotation The error term is invariant under scaling, but not invariant under rotation. This is evident by the following logic: if you rotate the brush stroke around the point in error to an angle where the scan line is normal to the polyspline segment, the error will reduce to zero. As this fluctuating error of an airbrush stroke will maintain both spatial and temporal continuity as the brush stroke is rotated, it is quite unlikely to be noticed, and will not be objectionable.

Enhancements to the round brush algorithm Tensioned Brushes Square brushes, circular brushes, diamond brushes and rounded square brushes can readily be achieved by tensioning the spline segments at vertices. This involves replacing one parabola with two parabolas. A vertex with an angle greater than 53.13 would be represented by two parabolas, and one with an angle of less than 53.13 (including end caps) would be represented by four parabolas. This uses the standard tensioned quadratic spline algorithm already in use. The most useful range for tension is between -1.0 and +1.0, though values through to -2.0 are useful for scalloped" brushes.

The tension of a brush is directly interpol able, and could even be specified independently for each vertex.

Only the tension of splines segments generated from a vertex are affected by brush tension: other spline segments are unaltered by this method.

Figure 27 shows how the 900 and 1800 vertices would appear when rendered with brush tensions of -2, -1, -0.3, 0 and 1 respectively 27 d) with a tension of O is a conventional parabolic spline.

Figure 31 shows how the same curve would appear when rendered with brush tensions of -1, -0.3, 0 and 1 respectively.

This curve has a mixture of vertices at acute, 90 , and obtuse angles. It also shows the appearance of end-caps for horizontal and diagonal lines. The appearance of curves is not affected, as only vertices are tensioned.

Note that the exterior curve of angles greater than 53.13 shows a single vertex at the intersection of the tangents, irrespective of the angle of the brush stroke. As well as being an aesthetic solution, this means that the appearance of the brush stroke does not change with rotation.

Elliptical Brushes A variety of elliptical brush shapes are shown in figure 29. Elliptical brushes can be simulated by the simple expedient of changing the shape of the end cap, and the angle that acute splines are divided at (normally 53.13 for round brushes) the only things affeted by these elliptical brushes are angles less than the breaking angle: obtuse vertices and normal splines are not affected. The brush outline is that traced by an ellipse with the short axis co-incident with the spline tangent. This algorithm does not produce the effect of a non-rotating brush, as is effective for calligraphy. Calligrahic style effects are treated in a separate section. These elliptical brushes may also be tensioned using the same tension algorithm as previously presented, resulting in rectangular and other shaped brushes.

VARIABLE BRUSH SIZE The area of contact between a real world brush and a painting surface varies with brush pressure. Were the size of a round brush to be controlled by the pressure from a pressure sensitive pen, this effect can be simulated in a vector painting system. The algorithm presented here lends itself to this purpose quite well. The examples below can utilise the algorithm in an entirely unmodified manner; all that is required is that the radius of the brush be stored at each knot point instead of being a constant. Figures 30 and 31 show respectively, how variable size brush curves may be constructed by varying brush size at each knot point, and the end result of such variations.

ANTIALIASING Unit Pixels For calculation speed and simplicity, this antiliasing system considers a pixel as having the size 1.0 in both the X and Y directions. Therefore, the area of a complete pixel is also 1.0. This is illustrated in figure 32.

Intersections between the object and the image are calculated using horizontal intersection lines, spaced one unit in Y apart. Pixels lie between scan lines, so if the centre of a pixel is to be considered to lie at integral positions in (m,n), then the pixel is bounded by scan lines at n-0.5 and n+0.5.

USE OF AREA IN COLOUR CALCULATION Area Calculation of the area covered by a polyspline is significant, as it is used in the antialiased calculation of the pixel colour as follows: Pixel colour=area*Polyspline colour+ (1-area) *background colour This algorithm calculates the area of a pixel which is covered by a polygon or polyspline. The polyspline boundary is shown in figure 33 with a thick line for clarity, and is not intended to imply a polyspline with a border line. Intersection of the polyspline with the line Y=n-0.5 is labelled A, and intersection with the line Y=n+0.5 is labelled B.

In this simple case Frac(A) is the fractional part of A Frac(B) is the fractional part of B. The area can be calculated by: Area=(Frac(A)+Frac(B) )/2 Where A and B do not fall within the same pixel, the calculation is more complex: figure 34 considers this problem.

In this case, J=1/(2*(A-B)) Then: Area (1) = J * (l-Frac(B))2 Area (2) = l-J*Frac(A)2 Intersections SPanninq More than Two Pixels Fortunately, the area calculation for intersections spanning more than two pixels is very simple, involving just one addition for each extra pixel: figure 35 shows a case in which the area spans six pixels. The area is calculated as follows: Here: K = 2J Then: Area (l)=J*(l-Frac(B))2 Area (2)=K*(0.5-Frac(B))+K Area (3)=Area(2)+K Area (4)=Area(3)+K Area (5)=Area(4)+K Area (6)=l-J*Frac(A)2 PAINTING WITH HOLES One of the primary advantages of a pixel system is the ease of "erasing". The system simply paints black (or the background colour if it isn't black). As all data exists only on one plane, holes can not be added to an object revealing the objects underneath.Complex pixel system can reveal from one paint frame to another, thus creating dramatic effects, but this is a one level hardware function. By creating a brush colour which in itself is fully transparent and which also effects the transparency of the next object underneath it, the net effect is painting with "holes".

If a brush stroke is transparent - the colour of the brush stroke under it is obviously used. This class of special brushes over-rides the transparency definition of the lower brush stroke. The amount or degree of this over-riding can be user varied. Either semi-transparency, full transparency or multiple layers of brush's transparency can be easily varied.

From a user's point of view, three arbitrary Hole types are possible.

1. One brush layer, directly below the special brush stroke.

2. A hole through all brush strokes in that "Cel" layer.

3. A hole, through all brush strokes and "Cel layers" to the backdrop.

This method describes an elegant and effective way of implementing "erasers" which are both hard and soft edged, as the translucency can be variable across the brush stroke. Drawing "holes" in a vector based painting system is more significant than it sounds: it is capable of all of the effects achieved the Quantel two plane "reveal" painting effects, as well as being resolution independent, fully animatable, editable, transformable and object based in the same manner as all other "vector" objects. There can also be an essentially unlimited number of planes, with an unlimited number of holes and eraser strokes.

Thus the system works in an entirely different manner to Quantel's two plane reveal painting effects which is based on a two framestore "mix". The solution presented above, can, by contrast be implemented in software.

IMPROVED COLOUR MODEL Physical media such as paints behave in complex ways, and it is not practical, not necessarily desirable, to simulate the optical properties of paints, inks, dyes and other media too closely. What is required is a simple model which captures the major optical qualities of a range of media. The RGBT colour model currently used has the problem that transparent inks and fils are poorly modelled: there is no possibility of a totally-non-reflective paint which also has colour.

A fairly accurate colour model considers the incident light, the scattered or reflected light, the absorbed light, and the transmitted light. In the vast majority of paints Scattered + Absorbed + Transmitted = Incident light, or so close that it doesn't matter. This is illustrated is figure 36.

If we define: L(r.g.b)=incident light S(r,g,b)=ratio of scattered to incident light A(r,g,b)=ratio of absorbed to incident light T(r,g,b)=ratio of transmitted to incident light Then S(r,g,b) + A(r,g,b) + T(r,g,b) = (1,1,1) The absorbed portion is never seen, so does not need to be calculated. It can also not be explicitly defined, as it can be derived from the transmitted and scattered ratios. The transmitted portion of the light will not be seen from the front, unless the paint layer is on top of a reflective surface, such as white paper.Considering perfectly reflective white paper, the colour seen at the top surface of the paint will be: Colour=L(r,g,b) (S(r,g,b)+T(r, g,b)2+S(r,g,b)T(r,g,b)2+ S(r,g,b)2T(r,g,b)2...) The contribution of the latter terms will be small, and can be safely ignored, leaving: Colour=L(r,g,b)(S(r,g,b)+T(r,g,b)2). This is illustrated in figure 37.

If we define separately the light incident from the top surface of the layer of paint from the (usually reflected, unless the painting is backlit) light incident on the bottom surface, then each paint layer can be treated in isolation as shown in figure 38 where B(r,g,b)=backlight intensity.

When paint is layered, the transmitted light of the top paint layer becomes the incident light of the layer below. The sum of the scattered light and the transmitted backlight of the lower layer becomes the backlight of the top layer. Thus any number of layers may be calculated. Colour layers should be evaluated from the top down, unless the painting is backlit. It is not necessary to evaluate layers below the layer where the transmitted L(r,g,b) falls below 4.4%, as this light will not make it to the surface in sufficient quantity to cause a 1/2 LSB difference in an 8 bit colour intensity. This condition is illustrated in figure 39.

The method described above is not more computationally expensive per layer than the "opacity" method currently used.

The equation per layer for this method is: Colour (r,g,b)=L(r,g,b)S(r,g,b)+B(r,g,b)T(r,g,b) when this equation is expanded it reads: Colour (r,g,b) = (L(r)S(r)+B(r)T(r) , L(g)S(g)+B(g)T(g) ,L(b)S(b)+B(b)T(b)) While the translucency method has the following equation per layer: defining 0 to be proportion of opacity from 0.0 to 1.0 Colour (r,g,b)=OS(r,g,b)+(l-0)B(r,g,b) when this equation is expanded it reads: Colour (r,g,b) - (OS(r)+l(l-O)B(r),OS(g)+(l-O)B(g),OS(b)+ (l-O)B(b)) Both methods involve 6 multiplications and three additions per layer, so there is no performance penalty in using the method suggested here.

The method described above has the following advantages: 1) Colour transparent films and inks can be rendered accurately. This is not possible with the transparency model.

2) The overall lighting of an image can be readily changed by altering L(r,g,b), changing the global colour or brightness of an image 3) Images can be backlit in any colour by varying B(r,g,b) of the lowest layer, readily giving effects similar to stained glass, lit windows, glows, lights, and so forth.

Figure 40 is a block diagram illustrating the hardware required to put the methods described into effect. It is to be understood that most of the steps of the processes are performed as software functions. For example curve fitting and calculation of outline curves are performed as a series of mathematical functions.

The hardware consists of a processor board 100 which can be accessed by a space ball 102, keyboard 104 or graphics tablet 106. Data is generated from the tablet by using a stylus (not shown). Tablets and stylii are well known in the art. The processor board can read and write data from or to tape and disc memories 110 through SCSI (Small Computer Systems Interface) 112.

This is a parallel data transfer cable bus. The interface 115 with the tablet, keyboard and spaceball is serial.

The processor board is illustrated in more detail in figure 4. The processing power of the board comprises six T800-20 Transputers 114 made by the Inmos Corp. each of which has lMbyte Private RAM. The transputers have their serial links connected to a link array plug. This plug can connect the links for any on-board Transputer to either a backplane link or another on-board transputer.

Each transputer has its 32 bit address/data bus and control signals connected via buffers to the processor board's Internal Processor bus IPB. The IPB can be accessed by only one Transputer, the Block Move engine (DMA) or the Futurebus master at any one time. Access is controlled by a prioritised arbitrament scheme. From the IPB various modules may be accessed, for example the 256 KByte EPROM 130, the 128 KByte SRAM 132 the 16 MByte shared DRAM 134, the 4XRS232 serial interface 114 and the parallel interface 112.

Unit 140 is a processor accelerator which is basically a depopulated processor board. The accelerator comprises a further six T800-20 transputers with a similar link array plug.

The linear framestore board 150 comprises 3 MBytes of fast page mode DRAM 152 which is enough for more than two frames of video data. The board enables high speed rendering as it has access to a graphics rendering machine. This interprets commands that have been placed in a graphics segment memory and writes strips of pixels into the framestore at any time that video is not being written or read. This makes possible generation of shaded graphics in real time.

Mixing of video is performed by video mixer board 160.

The board provides timing for all the modules. Video Monitor board 170 converts 4:2:2 format video to RGB found suitable for display on a moniter. This allows interactive preview.

The moves framestore 180 provides an output signal where the picture is a spatially distorted version of the input picture. Spatial movement and size change are accounted for. In practice this is done by manipulating the 2-D image one dimension at a time using vertical and horizontal re-map units 182 and 184.

Claims (55)

CLAINS

1. A method for creating in electronic form two-dimensional computer generated images by object drawing using pen lines, comprising: a) creating a temporary image of a line drawn by the user, and displaying the temporary image temporarily combined with the remainder, if any of the image; b) generating a final pen line on completion of the line, including storing date describing the line, and combining the completed line with the remainder, if any, of the image to replace the temporary combination; c) repeating steps a) and b) as desired until the operator has created a substantially completed drawing.

2. A method according to claim 1, wherein the creation of a temporary image comprises drawing a line and converting the line into a stream of digital data and wherein the temporary display of the line is substantially simultaneous with the drawing of the line.

3. A method according to claim 2, wherein the line is drawn using a tablet and stylus.

4. A method according to claim 2 or 3, wherein the digital data stream is converted into floating point format for processing.

5. A method according to any of claims 2, 3 or 4, wherein the stream of digital data representing the line is processed by fitting spline curves to the data, whereby the line is reduced to a series of spline curves closely matching the line drawn.

6. A method according to claim 5 wherein the accuracy with which the spline curves match the line represented by the data stream is variable.

7. A method according to claim 5 or 6 wherein the spline curves are parabolic curves.

8. A method according to any of claims 5 to 7, wherein creation of the temporary image further comprises calculating the shape and position of a pen line around the spline curves, filing the pen line and storing the pen line in an overlay store.

9. A method according to claim 8, comprising overlaying the contents of the overlay store on the remainder, if any, of the image to provide the temporarily combined image.

10. A method according to any of claims 1 to 9, wherein generation of the final pen line comprises the step of placing the line into a database to create a database object.

11. A method according to claim 10 appendent to any of claims 4 to 9, wherein the line stored in the database is in the form of spline data and the generation of the final pen line comprises generating a closed spline curve corresponding to the outline of a pen nib moving along the splines representing the pen line.

12. A method according to claim 11, wherein the generation of the final pen line comprises identifying the intersection of the closed spline curve with scan lines of a raster scan, and determining the colour of the pen line at each intersection.

13. A method according to claim 12 appendent to claim 2, wherein the generation of the final pen line comprises sorting edges of the outline along a scan line into monotonic order, converting floating point scan line intersections into display pixel co-ordinates, and generating pixel colours between successive edges.

14. A method according to claim 13, wherein the generation of the final pen line further comprises writing derived curve data into the overlay store to produce a pixel image of the entire pen line, compositing the pixel image with the remainder if any of the image and storing the pen line in the store containing the remainder of the picture.

15. A method according to any preceding claim, comprising regenerating the regions of the remainder of the image altered by combination of the created pen line.

16. A method according to claim 15 wherein the regeneration of the altered regions of the remainder of the image comprises generating a sequence of successive frames of the image, applying the generated final pen line between frames and identifying images whose appearance is altered by the application of the final pen line.

17. A method according to Claim 15 or 16, wherein the regeneration of the altered regions comprises identifying and remove those areas of the image unaffected by the combination of the created pen line.

18. A method according to Claim 15, 16 or 17, comprising generating outlines of a visible pen line from stored data describing the pen line, filling the generated outline and writing the filled pen line data into the picture store.

19. A method according to Claim 18, wherein the generated outline is filled by calculating intersections of the outline with scan lines of a raster scan, converting the intersections into display coordinates and generating colour of display pixels between edges of the pen line, and wherein writing of the filled pen line comprises writing pixel data into a main image frame store.

20. A method for creating in electronic from two-dimensional computer generated images by object drawing using pen lines, comprising the steps of a) acquiring data representing a pen line drawn by a user and fitting stored curves to the data, b) storing the pen line as a sequence of the said curves, and combining the stored representation of the curve with the remainder of an image; c) identifying those areas of the remainder of the image affected by the combination, and d) regenerating the affected areas by generating the outlines of pen line formed by a nib as it follows the line, and filling the derived outline.

21. A method according to Claim 20, wherein the data is acquired from a tablet and stylus and is converted into a stream of digital data.

22. A method according to Claim 21, wherein the digital data stream is converted into floating point format for processing.

23. A method according to Claim 20, 21 or 22, wherein after curve fitting a temporary image of the pen line is created and interactively displayed.

24. A method according to Claim 23, wherein the temporary image is an approximation of the appearance of a pen line formed around the drawn line temporarily composited with the remainder of the image.

25. A method according to any of Claims 20 to 24, wherein after storing the curve data and before combining with the remainder of the image the outline of the pen line is generated and interactively displayed.

26. A method according to Claim 24, wherein after generation of the pen line outline the colour of the pen line is calculated, the outline is filled and displayed interactively.

27. A method of generating a pen line in a two dimensional object based computer graphics system, comprising deriving data representing a line to be formed into a pen line, generating the outline of a nib as it follows the line and filling the derived outline.

28. A method according to Claim 27, wherein the nib rotates with the line as it follows the line.

29. A method according to Claim 27 or 28, wherein the data representing the line is a stream of coordinate data and the method comprises fitting a series of spline curves to the coordinate data, the outline generated being that of the nib as it follows the spline curves.

30. A method according to any of Claims 27 to 29, wherein the data is derived using a stylus and tablet.

31. A method according to Claim 29 or 30, wherein the outline is generated for a given spline of the series of spline curves by identifying knot points for the spline drawing a tangent to the spline at each of the knot points, generating left and right edge knot points on a normal to each of the tangents of the knot points at a distance equal to half the major axis of the nib on the left and right hand sides respectively of the knot points, generating tangents parallel to the tangents to the spline at each of the left and right knot points, identifying control points of the spline at the intersection of said tangents, deriving left and right control points at the respective intersections of the left and right tangents, and deriving outline curves from the left and right knot and control points.

32. A method according to Claim 31, comprising comparing the sense of the tangents at the knot points at the ends of the spline with the tangents of adjacent splines sharing those knot points and generating a mitre point if the sense of either spline tangent is the same as the sense of the tangent of the respective adjacent spline at that common knot point.

33. A method according to Claim 32, wherein a mitre point is generated on the inner of the left and right outline curves at the intersections of the adjacent splines.

34. A method according to Claim 33, wherein the set of spline curves includes a vertex, comprising treating the vertex as a spline curve of zero length having co-incident knot points, and generating a mitre point on the inner outline curve.

35. A method according to any of claims 31 to 34, wherein a spline curve subtends an acute angle, comprising bisecting the spline curve into two spline curves.

36. A method according to Claim 35, comprising further bisecting any bisected spline curve subtending an angle less than or equal to 2.arctan (0.5).

37. A method according to Claim 35 or 36, wherein bisecting a spline curve subtending an acute angle comprises a) deriving tangents to the adjacent spline curves at common knot points; b) projecting a line from each common knot point at an angle arctan ss #/2 to a respective adjacent tangent, where + is the angle between the adjacent tangents and ~ is chosen according to the desired nib shape and wherein the projected lines are convergent; c) deriving the intersection of the projected lines; d) deriving the mid-points between the intersection and respective knot points of the projected lines; e) deriving the mid-point of a line passing through the said mid-points on the projected lines; and f) deriving two new spline curves having control points at the intersections of the said adjacent tangents and the line passing through the said mid-points on the projected lines, wherein the said mid-point derived in step e) is the common knot point of the two new spline curves and the said line is the tangent to that mid-point.

38. A method according to any of Claims 29 to 37, wherein the spline curves are quadratic curves.

39. A method according to Claim 38, wherein the spline curves are parabolic.

40. A method according to any of Claims 1 to 39, wherein the nib is curviform.

41. A method according to any of Claims 40, wherein the nib is circular.

42. A method according to any of Claims 27 to 41, wherein the outline of the generated pen line is filled using a scan-line fill algorithm and the method comprises tagging each generated outline segment as being to the left or right of the respective spline curve, for each scan line arranging intersections of the outline with the curve in order of position along the scan line, assigning a variable opacity to each part of the scan line by incrementing an opacity index where an intersection is with a left curve segment and decrementing the opacity under where the opacity is with a right curve, and rendering the outline pen line with an opacity and the opacity index at any given point along the scan line.

43. A method according to Claim 42, wherein a pen line is rendered with a single level of opacity by interpreting values of the opacity index greater than one as equal to one.

44. A method according to Claim 42 or 43, wherein the edges of a rendered pen line are highlighted by highlighting the outline curves.

45. A method according to any of Claims 33 to 41, wherein a pen line outline is filled using a scan-line fill algorithm and comprises subdividing the outline into a plurality of closed chambers, each chamber being bounded by a segment of the outline curve and a segment of the spline curve and each having four knot or mitre points defining its corners, assigning a number to each chamber in order of the splines from which they generate, calculating at the intersection of the edges of each chamber with scan lines, intersections of spline curves being assigned a first colour value, intersections of outline curves a second colour value and remaining chamber edges being assigned a linear interpolation between the first and second colour values and rendering the pen line with the calculated colour at each intersection.

46. A method according to Claim 45, wherein chambers including a vertex have four knot points, the two knot points at the vertex being co-incident.

47. A method according to Claims 45 or 46, wherein calculation of the colour at each intersection comprises calculating the colour at any given intersection as a proportion between a first colour equivalent to the first colour value and a second colour equivalent to the second colour values.

48. A method according to Claim 46 to 47, wherein calculation of colour in overlaying layers is performed in order of increasing chamber number from the start of the pen line.

49. A method according to any of Claims 31 to 48, wherein the visual appearance of the pen line is varied by tensioning adjacent spline curves at vertices.

50. A method according to Claim 49, wherein adjacent curves are tensioned to a tension of -2 to produce a scallop.

51. A method according to Claim 49, wherein adjacent curves are tensioned to a tension of -1 to produce a diamond.

52. A method according to Claim 49, wherein adjacent curves are tensioned to a tension of -0.3 to produce a circle.

53. A method according to Claim 49, wherein the adjacent curves are tensioned to a tension of +1 to produce a square.

54. A method according to any claim appendent Claim 37, wherein the B = 0.5 and the pen line is a round pen.

55. A method according to any of Claims 27 to 54 wherein the nib size is variable along the pen line.