Abstract:
An apparatus and method for filling regions bounded by piecewise-conic curves and more particularly to such an apparatus and method which is directed to curves defined by a conic equation. This simplifies the process of generating filled contours in applications, such as printing, which are based on font outlines while at the same time reducing computer time and generating more accurate results for each curve generation.

Description:
TECHNICAL FIELD OF THE INVENTION 
     This invention relates to an apparatus and method for filling regions bounded by piecewise-conic curves, and more particularly to such an apparatus and method which is directed to conic curves defined by a conic equation of the form: 
     
         f(x,y)=Ax.sup.2 +Bxy+Cy.sup.2 +Dx+Ey+F=0 
    
     BACKGROUND OF THE INVENTION 
     Simplifying the process of generating filled contours is beneficial in applications such as printing which are based on font outlines. The traditional method is to use a parametric cubic spline algorithm to generate points along the curve. These points are saved, and used as the vertices of an approximating polygon that represents the bounded fill region to some specified degree of accuracy. The approximating polygon is then filled using a method such as the edge flag algorithm. 
     The polygon fill is performed in two steps: first, a list is made of the edges on each horizontal scan line of the raster; and second, for each scan line, a pair of edges defines a horizontal span of the filled region. Thus, in the traditional method, three steps are required, namely: 
     1. Generating vertices of approximating polygon by using a cubic spline (or DDA) algorithm; 
     2. Converting each straight edge of the generated polygon into a list of edges on a per-scan-line basis; and 
     3. Drawing each pair of edges on a scan line as a horizontal span belonging to the filled region using a parity or non-zero winding number fill algorithm. 
     In order to reduce computing time and to generate more accurate results, a system is required which reduces the number of steps required for each curve generation. 
     SUMMARY OF THE INVENTION 
     By using a conic curve tracker algorithm to directly generate the raster edges for each scan line intersected by a boundary curve, the number of steps required to generate the curve is reduced from three to two. The two required steps are: 
     1. Generating, by way of a conic curve tracker algorithm, the edge intersections at each scan line crossed by the curve; and 
     2. Drawing each pair of edges on a scan line as a horizontal span belonging to the filled region. 
     This approach requires less software code when executed on a processor and also requires fewer components and executes more rapidly when implemented in hardware. 
     The arithmetic is simplified because the system works in integer rather than floating-point mathematics. The inner loops require only simple operations such as addition, subtraction, and shifts and require no multiplies. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which: 
     FIG. 1 depicts pixels arranged in an x-y coordinate system; 
     FIG. 2 shows curve tracking arrows indicating a curve tracking path along the circumference of a circle; 
     FIGS. 3A-3H are two step vectors for each octant of FIG. 2; 
     FIG. 4 depicts the eight gradient values at the octant boundaries of an ellipse; 
     FIG. 5A and 5B show the difference between the existing midpoint rule and the fill rule of the instant invention; and 
     FIGS. 6 and 7 show alternative embodiments of the invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Before beginning a discussion of the algorithm of the present invention, it should be noted that Pitteway&#39;s algorithm, published in 1967, used what can be called the &#34;midpoint&#34; algorithm to select a thin but connected set of pixels to represent an infinitely thin conic arc. This is shown in FIG. 5a. Pitteway&#39;s algorithm is adapted as will be seen, to filling regions bounded by curves. The selection of pixels to represent the interior of the filled region is performed according to what can be called the &#34;fill&#34; rule; namely, that a pixel is considered to be a part of the interior if its center lies within the region bounded by the conic are. This is shown in FIG. 5b. 
     As shown in FIG. 1, the x-y raster coordinate system 10 consists of integer coordinate grid lines (0-3) and (0-4) between pixels. 
     Thus, the zero y coordinate grid line and the zero x coordinate grid line, respectively, extend away normal to one another in the x and y directions and define the pixels at their respective intecies intersections. Accordingly, pixel 0,0 is in the lower left corner, x position 0, y position 0, and pixel 2,3 is in the upper right corner, x position 2, y position 3. Of course, other definitions of the pixel locations can be used with suitable adjustments to the described algorithms. The rest of the pixels, not identified separately by numeral but represented by circles, lie between the remaining integer grid lines. Also, the twelve pixels represented in FIG. 1 serve to describe the definition system used for any number of pixels desired. 
     FIG. 2 depicts the described x-y raster coordinate system 10 overlaid with small arrows, such as arrow 201, representing the path taken by the curve tracker algorithm of the invention in filling a circle 202 of radius r. By convention, the algorithm tracks the curve of circle 202 in a counter clockwise direction, keeping the interior on the left. Each arrow, such as arrow 201, represents a &#34;step&#34; (or iteration) of the algorithm. Pixels lying close to the curve are indicated; small, filled circles, such as circles 44 and 46, are pixels lying inside the circle, and small, unfilled circles, such as circles 48 and 50, are pixels lying outside circle 202. 
     The curve is partitioned into drawing octants 1 through 8. In drawing octant 1, the curve&#39;s slope m is between 0 and +1; in octant 2, the slope is between +1 and +infinity; and so on around circle 202. Within each octant each successive step is restricted to one of two neighboring grid (integer x-y coordinates) points, the grid points being represented by the crossed lines. In octant 1, for example, the next step is either (1) to the diagonally adjacent neighbor up and to the right, or (2) to the horizontally-adjacent neighbor to the right. 
     FIGS. 3A through 3H depict the two possible step directions, represented by pairs of arrows, such as 54 and 56, extending from the current point, such as point 58, for each octant. 
     As in Pitteway&#39;s algorithm, a decision variable d is used within each octant to determine which of the two directions to step. Let (x i ,y i ) represent the algorithm&#39;s current position, where x i  and y i  are integer coordinates. Also let f(x,y)=0 represent the equation for the conic curve (or circle, in the example of FIG. 2). At a point (x,y) that lies inside the circle, f(x,y)&lt;0; in other words, we can determine whether a point is inside, outside, or on the curve merely by determining the sign of function f evaluated at the point. The decision variable d is calculated by evaluating f(x,y) at a point (x 1  ±1/2,y 1  ±1/2), which is at one of the four pixel centers closest to the current position: 
     1. In octants 1 and 2, d i  =f(x i  +1/2,y i  +1/2); 
     2. In octants 3 and 4, d i  =f(x i  -1/2,y i  +1/2); 
     3. In octants 5 and 6, d i  =f(x i  -1/2,y i  -1/2); and 
     4. In octants 7 and 8, d i  =f(x i  +1/2,y i  -1/2). 
     Simplified versions of the algorithm for octants 1 through 8 for circle 202 of FIG. 2 follow. 
     
         ______________________________________In octant 1:   d=f(x+1/2,y+1/2);   if(d &lt; 0)     ++x;   else{     mark.sub.-- edge.sub.-- at(x+1/2,y+1/2);     ++x;     ++y;   }In octant 2:   d=f(x+1/2,y+1/2);   if(d &lt; 0)}     mark.sub.-- edge.sub.-- at(x+3/2,y+1/2);     ++x;     ++y;   {else}     mark.sub.-- edge.sub.-- at(x+1/2,y+1/2);     ++y;In octant 3:   d=f(x-1/2,y+1/2);   if(d &lt; 0){     mark.sub.-- edge.sub.-- at(x+1/2,y+1/2);     ++y;   {else}     mark.sub.-- edge.sub.-- at(x-1/2,y+1/2);     --x;     ++y;   {In octant 4:   d=f(x-1/2,y+1/2);   if(d &lt; 0){     mark.sub.-- edge.sub.-- at (x+1/2,y+1/2);     --x;     ++y;   }else     --x;In octant 5:   d=f(x-1/2,y-1/2);   if(d &lt; 0)     --x;   esle{      mark.sub.-- edge.sub.-- at(x+1/2,y-1/2);     --x;     --y;   }In octant 6:   d=f(x-1/2,y-1/2);   if(d &lt; 0){     mark.sub.-- edge.sub.-- at(x-1/2,y-1/2);     --x;     --y;   }else{     mark.sub.-- edge.sub.-- at(x+1/2,y-1/2);     --y;   }In octant 7:   d=f(x+1/2,y-1/2);   if(d &lt; 0){     mark.sub.-- edge.sub.-- at(x+1/2,y-1/2);     --y;   }else{     mark.sub.-- edge.sub.-- at(x+3/2,y-1/2);     ++x;     --y;   }In octant 8:   d=f(x+1/2,y-1/2);   if(d &lt; 0){     mark.sub.-- edge.sub.-- at (x+1/2,y-1/2);     ++x;     --y;   }else     ++x;______________________________________ 
    
     Decision variable d is negative if evaluated at a pixel (small filled circle in FIG. 2) that lies inside the circle; d is positive if evaluated at pixel (small unfilled circle in FIG. 2) that lies outside the circle. 
     The &#34;mark --  edge --  at&#34; function designates the pixel centered at the designated x and y coordinates as the leftmost pixel in a horizontal span. The pixels shown in FIG. 2 as small filled circles are marked along the left side of the circle; the pixels shown in FIG. 2 as small unfilled circles are marked along the right side. 
     Octant Tests 
     The determination of the octant is based on the values of partial derivatives df/dx and df/dy evaluated at or near the current position (defined by integer coordinates x i , y i ). The tests in octants 1-8 are summarized below (refer to FIG. 4): 
     
                       TABLE 1______________________________________In octant 1 while df/dx &lt; -df/dyIn octant 2 while df/dy &lt; 0In octant 3 while df/dx &gt; df/dyIn octant 4 while df/dx &gt; 0In octant 5 while -df/dx &lt; df/dyIn octant 6 while df/dy &gt; 0In octant 7 while -df/dx &gt; -df/dyIn octant 8 while df/dx &lt; 0  where f(x,y)=Ax.sup.2 +Bxy+Cy.sup.2 +Dx+Ey+F______________________________________ 
    
     Incremental Calculations 
     A practical implementation of the algorithm, modified to simplify the calculations and improve execution speed, calculates decision variable d incrementally based on its value at the previous iteration, similar to Pitteway&#39;s algorithm. Also, the number of loops can be reduced from 8 to 4 by exploiting symmetry between the loops for octants n and n+4 (for n=1, 2, 3 and 4). 
     The difference values necessary to incrementally update decision variable d in each of the 8 octants are derived below. Variables U and V below are the values by which d is incremented during square (horizontal or vertical) and diagonal steps, respectively. Variables U and V are in turn updated by increments k 1 , k 2  and k 3 , which remain constant within the inner loop. 
     
         ______________________________________OCTANT 1: Update Decision Variable dd.sub.i =f(x.sub.i +1/2, y.sub.i +1/2)=A(x,+1/2).sup.2 +B(x.sub.i +1/2) (y.sub.i +1/2)+C(y.sub.i +1/2).sup.2+D(x.sub.i +1/2)+E(y.sub.i +1/2)+FSquare Move: x.sub.i +1=x.sub.i +1,y.sub.i+1 =y.sub.iU.sub.i+i =d.sub.i+1 -d.sub.i =f((x.sub.i +1/2)+1,y.sub.i +1/2)-f(x.sub.i+1/2,y.sub.i +1/2)=A[2(x.sub.i +1/2)+1]+B[(y.sub.i +1/2)]+D=2Ax.sub.i+1 +By.sub.i+1 +B/2+D=U.sub.i +2A=U.sub.i +K.sub.1 where K.sub.1 =2A in octant 1V.sub.i+1 =V.sub.i +2A+B=V.sub.i +K.sub.2 where K.sub.2 =2A+BDiagonal Move: x.sub.i+i =x.sub.i +1,y.sub.i+1 =y.sub.i +1U.sub.i+1 =U.sub.i +2A+B=U.sub.i +K.sub.2 K.sub.2 =2A+B in octant 1.V.sub.i+1 =d.sub.i+1 -d.sub.i =f((x.sub.i+1/2)+1,(y.sub.i +1/2)+1)-f(x.sub.i +1/2, y.sub.i +1/2)=A[2(x.sub.i +1/2)+1]+B[(x.sub.i +1/2)+(y.sub.i +1/2)+1]+C[2(y.sub.i +1/2)+1]+D+E=(2A+B)x.sub.i+1 +(B+2C)y.sub.i+1 +D+E=V.sub.i +2(A+B+C)=V.sub.i +K.sub.3 where K.sub.3 =2(A+B+C) in octant 1Initialization: x.sub.0 =0,y.sub.0 =0d.sub.0 =(A+B+C)/4+(D+E)/2+Fu.sub.0 =B/2+Dv.sub.0 =D+Ek.sub.1 =2Ak.sub.2 =2A+Bk.sub.3 =2(A+B+C)OCTANT 2: Update Decision Variable ddi=f(x.sub.i +1/2, y.sub.i +1/2)=A(x.sub.i +1/2).sup.2 +B(x.sub.i +1/2) (y.sub.i +1/2)+C(y.sub.i +1/2).sup.2 +D(x.sub.i +1/2)+E(y.sub.i +1/2)+FSquare Move: x.sub.i+1 =x.sub.i,y.sub.i+1 =y.sub.i +1U.sub.i+1 =d.sub.i+ 1 =f(x.sub.i +1/2, (y.sub.i +1/2)+1)-f(x.sub.i +1/2,y.sub.i +1/2)=B[(x.sub.i +1/2)]+C[2(y.sub.i +1/2)+1]+E=Bx.sub.i+1 +2Cy.sub.i+1 +B/2+E=U.sub.i +2C=U.sub.i +K.sub.1 where K.sub.1 =2C in octant 2V.sub.i+1 V.sub.i +B+2C=V.sub.i +K.sub.2 where K.sub.2 =B+2CDiagonal Move: x.sub.i+1 =x.sub.i +1,y.sub.i+1 =y.sub.i +1U.sub.i+1 =U.sub.i +B+2C=U.sub.i +K.sub.2 where K.sub.2 =B+2C in octantV.sub.i+1 =d.sub.i+1 -d.sub.i =f((x.sub.i +1/2)+1,(y.sub.i +1/2)+1)-f(x.sub.i +1/2, y.sub.i +1/2)=A[2(x.sub.i +1/2)+1]+B[(x.sub.i +1/2)+(y.sub.i +1/2)+1]+C[2(y.sub.i+1/2) +1]+D+E=(2A+B)x.sub.i+1 +(B+2C) y.sub.i+1 +D+E=V.sub.i + 2(A+B+C)=V.sub.i +K.sub.3 where K.sub.3 =2 (A+B+C) in octant2Initialization: x.sub.0 =0,y.sub.0 =0d.sub.0 =(A+B+C)/4+(D+E)/2+Fu.sub.0 =B/2+Ev.sub.0 =D+EK.sub.1 =2CK.sub.2 =B+2CK.sub.3 =2(A+B+C)OCTANT 3: Update Decision Variable dd.sub.i =f(xhd i-1/2, y.sub.i +1/2)=A(x.sub.i -1/2).sup.2 +B(x.sub.i -1/2) (y.sub.i +1/2)+C(y.sub.i +1/2).sup.2 +D(x.sub.i -1/2)+E(y.sub.i +1/2) +FSquare Move: x.sub.i+1 =x.sub.i,y.sub.i+1 =y.sub.i +1U.sub.i+1 =d.sub.i+1 -d.sub.i =f(x.sub.i -1/2,(y.sub.i +1/2)+1)-f(x.sub.i-1/2,y.sub.i +1/2)=B[(x.sub.i -1/2)]+C[2(y.sub.i +1/2)+1]+E=Bx.sub.i+1 +2Cy.sub.i+1 -B/2+E=U.sub.i +2C=U.sub.i +K.sub.1 where K.sub.1 =2C in octant 3V.sub.i+1 =V.sub.i -B+2C=V.sub.i K.sub.2 where K.sub.2 =-B+B+2CDiagonal Move: x.sub.i+1 =x.sub.i -1,y.sub.i+1 =y.sub.i +1U.sub.i+1 =U.sub.i -B+2C=U.sub.i +K.sub.2 where K.sub.2 =-B+2C in octant3V.sub.i+1 =d.sub.i+1 -d.sub.i =f((x.sub.i -1/2)-1,(y.sub.i +1/2)+1)-f(x.sub.i -1/2,y.sub.i +1/2)=A[-2(x.sub.i -1/2)+1]+B[(x.sub.i -1/2)-(y.sub.i +1/2)-1]+C[2 (y.sub.i+1/2)+1]-D+E=(-2A+B)x.sub.i+1 +(-B+2C)y.sub.i+1 -D+E=V.sub.i +2A-2B+2C=V.sub.i +K.sub.3 where K.sub.3 =2 (A-B+C) in octant 3Initialization: x.sub.0 =0, y.sub.0 0d.sub.0 =(A-B+C)/4+(-D+E)/2+F              K.sub.1 =2CU.sub.0 =-B/2+E    K.sub.2 =-B+2CV.sub.0 = -D+E     K.sub.3 =2 (A-B+C)OCTANT 4: Update Decision Variable dd.sub.i =f(x.sub.i -1/2,y.sub.i +1/2)=A(x.sub.i -1/2).sup.2 +B(x.sub.i -1/2) (y.sub.i +1/2)+C(y.sub.i +1/2).sup.2 +D(x.sub.i -1/2)+E(y.sub.i +1/2)+FSquare Move: x.sub.i+1 =x.sub.i -1,y.sub.i+1 =y.sub.iU.sub.i+1 =d.sub.i+1 -d.sub.i=f((x.sub.i -1/2)-1,y.sub.i +1/2)-f(x.sub.i-1/2,y.sub.i +1/2)=A[-2(x.sub.i -1/2)+1]+B](y.sub.i +1/2)]-D=-2Ax.sub.i +1-By.sub.i +,-B/2-D=-2Ac.sub.i+1 -By.sub.i+1 -B/2-D=U.sub.i +2A=U.sub.i +K.sub.1 where K.sub.1 =2A in octant 4V.sub.i+1 =V.sub.i +2A-B=V.sub.i +K.sub.2 where K.sub.2 =2A-BDiagonal Move: x.sub.i+1 =x.sub.i -1,y.sub.i+1 =y.sub.i +1U.sub.i+1 =U.sub.i +2A-B=U.sub.i +K.sub.2 where K.sub.2 =2A-B in octant4V.sub.i+1 =d.sub.i+1 -d.sub.i =f((x.sub.i -1/2)-1,(y.sub.i +1/2)+1)-f(x.sub.i -1/2,y.sub.i +1/2)=A[-2(x.sub.i -1/2)+1]+B[(x.sub.i -1/2)-(y.sub.i +1/2)-1]+C[2(y.sub.i +1/2)+1]-D+E=(-2A+B)x.sub.i+1 +(-B+2C)y.sub.i+1 -D+E=V.sub.i +2A-2B+2C=V.sub.i +K.sub.3 where K.sub.3 =2(A-B+C) in octant 4Initialization: x.sub.0 =0,y.sub.0 =0d.sub.0 =(A-B+C)/4+(-D+E)/2+F              K.sub.1 =2AU.sub.0 =-B/2-D    K.sub.2 =2A-BV.sub.0 =-D+E      K.sub.3 =2(A-B+C)OCTANT 5: Update Decision Variable dd.sub.i =f(x.sub.i -1/2,y.sub.i -1/2)=A(x.sub.i -1/2).sup.2 +B(x.sub.i -1/2) (y.sub.i -1/2)+C(y.sub.i -1/2).sup. 2 +D(x.sub.i -1/2)+E(y.sub.i -1/2)+FSquare Move: x.sub.i+1 =x.sub.i -1,y.sub.i+1 =y.sub.iU.sub.i+1 =d.sub.i+1 -d.sub.i =f((x.sub.i -1/2)-1,y.sub.i -1/2)-f(x.sub.i-1/2,y.sub.i -1/2)=A[-2(x.sub.i -1/2)+1]+B[-(y.sub.i -1/2)]-D=-2Ax.sub.i+1 -By.sub.i+1 +B/2-D=U.sub.i +2A=U.sub.i +K.sub.1 where K.sub.1 =2A in octant 5V.sub.i+1 =V.sub.i +2A+B=V.sub.i +K.sub.2 where K.sub.2 =2A+BDiagonal Move: x.sub.i+1 =x.sub.i -1,y.sub.i+1 =y.sub.i-1U.sub.i+1 =U.sub.i +2A+B=U.sub.i +K.sub.2 where K.sub.2 =2A+B in octant5V.sub.i+1 =d.sub.i+1 -d.sub.i =f((x.sub.i -1/2)-1,(y.sub.i -1/2)-1)-f(x.sub.i -1/2,y.sub.i -1/2)=A[-2(x.sub.i -1/2)+1]+B[- (x.sub.i -1/2)-(y.sub.i +1/2)+1]+C[-2(y.sub.i -1/2)+1]-D-E=(-2A-B)x.sub.i+1 +(-B-2C)y.sub.i+1 -D-E=V.sub.i +2(A+B+C)=V.sub.i +K.sub.3 where K.sub.3 =2(A+B+C) in octant 5Initialization: x.sub.0 =0,y.sub.0 =0d.sub.0 =(A+B+C)/4+(-D-E)/2+FU.sub.0 =B/2-DV.sub.0 =-D-EK.sub.1 =2AK.sub.2 =2A+BK.sub.3 =2(A+B+C)OCTANT 6: Update Decision Variable dd.sub.i =f(x.sub.i -1/2,y.sub.i -1/2)=A(x.sub.i -1/2).sup.2 +B(x.sub.i-1/2)(y.sub.i -1/2)+C(y.sub.i -1/2).sup.2+D(x.sub.i -1/2)+E(y.sub.i -1/2)Square Move: x.sub.i+1 =x.sub.i,y.sub.i+1 -1U.sub.i+1 =d.sub.i+1 -d.sub.i =f((x.sub.i -1/2,(y.sub.i -1/2)-1)-f(x.sub.i -1/2, y.sub.i -1/2)=B[-(x.sub.i -1/2)]+C[-2(y.sub. i -1/2)+1]-E=-Bx.sub.i+1 -2Cy.sub.i+1 +B/2-E=U.sub.i +2C=U.sub.i +K.sub.1 where K.sub.1 =2C in octant 6V.sub.i+1 =V.sub.i +B+2C=V.sub.i +K.sub.2 where K.sub.2=B+2CDiagonal Move: x.sub.i+1 =x.sub.i -1,y.sub.i+1 =y.sub.i -1U.sub.i+1 =U.sub.i +B+2C=U.sub.i +K.sub.2 where K.sub.2 =B+2C in octant6V.sub.i+1 =d.sub.i+1 -d.sub.i =f((x.sub.i -1/2) -1,(y.sub.i -1/2)-1)-f(x-1/2, y-1/2)=A[-2(x.sub.i -1/2)+1]+B[-(x.sub.i -1/2)-(y.sub.i -1/2)+1]+C[-2(y.sub.i -1/2)+1]-D-E=(-2A-B) x.sub.i+1 +(-B-2C)y.sub.i+1 -D-E=V.sub.i +2(A+B+C)=V.sub.i +K.sub.3 where K.sub.3 =2(A+B+C) in octant 6Initialization: x.sub.0 =0,y.sub.0 = 0d.sub.0 =(A+B+C)/4+(-D-E)/2+FU.sub.0 =B/2-EV.sub.0 =-D-EK.sub.1 =2CK.sub.2 =B+2CK.sub.3 =2(A+B+C)OCTANT 7: Update Decision Variable dd.sub.i =f(x.sub.i +1/2,y.sub.i -1/2)=A(x.sub.i +1/2).sup.2 +B(x.sub.i +1/2) (y.sub.i -1/2)+C(y.sub.i -1/2).sup.2 +D(x.sub.i +1/2)+E(y.sub.i -1/2)+FSquare Move: x.sub.i+1 =x.sub.i,y.sub.i+1 =y.sub.i -1U.sub.i+1 =d.sub.i+1 -d.sub.i =f(x.sub.i +1/2,(y.sub.i -1/2)-1)-f(x.sub.i+1/2, y.sub.i -1/2)=B[-(x.sub.i +1/2)]+C[-2(y.sub.i -1/2)+1]-E=-Bx.sub.i+1 -2Cy.sub.i+1 -B/2-E=U.sub.i +2C=U.sub.i +K.sub.1 where K.sub.1 =2C in octant 7V.sub.i+1 =V.sub.i -B+2C=V.sub.1 +K.sub.2 where K.sub.2=-B+2CDiagonal Move: x.sub.i+1 =x.sub.i +1,y.sub.i+1 =y.sub.i -1U.sub.i+1 =U.sub.i -B+2C=U.sub.i +K.sub.2 where K.sub.2 =-B+2C in octant7V.sub.i+1 =d.sub.i+1 -d.sub.i =f((x.sub.i +1/2)+1,(y.sub.i -1/2)-1)-f(x.sub.i +1/2, y.sub.i -1/2)=A[2(x.sub.i +1/2)+1]+B[-(x.sub.i +1/2)+(y.sub.i -1/2)-1]+C[-2(y.sub.i-1/2) +1]+D-E=(2A-B)x.sub.i+1 +(B-2C)y.sub.i+1 +D-E=V.sub.i+2(A-B+C)=V.sub.i +K.sub.3 where K.sub.3=2(A-B+C) in octant 7Initialization: x.sub.0 =0,y.sub.0 =0d.sub.0 =(A-B+C)/4+(D-E)/2+FU.sub.0 =-B/2-EV.sub.0 =D-EK.sub.1 =2CK.sub.2 =-B+2CK.sub.3 =2(A-B+C)OCTANT 8: Update Decision Variable dd.sub.i =f(x.sub.i +1/2,y.sub.i -1/2)=A(x.sub.i +1/2).sup.2 +B(x.sub.i +1/2) (y.sub.i -1/2)+C(y.sub.i -1/2).sup.2 +D(x.sub.i +1/2)+E(y.sub.i -1/2)+FSquare Move: x.sub.i+1 =x.sub.i,y.sub.i+1 =y.sub.iU.sub.i+1 =d.sub.i+1 -d.sub.i =f((x.sub.i +1/2) +1,y.sub.i -1/2)-1)-f(x.sub.i +1/2, y.sub.i -1/2)=A[2(x.sub.i +1/2)+1]+B[(y.sub.i -1/2)]+D=2Ax.sub.i+1 +By.sub.i+1 -B/2+D=U.sub.i +2A=U.sub.i +K1 where K.sub.1 =2A in octant 8V.sub.i+1 =V.sub.i +2A-B=V.sub.i +K.sub.2 where K.sub.2 =2A-BDiagonal move: x.sub.i+1 =x.sub.i +1,y.sub.i+1 =y.sub.i -1U.sub.i+1 =U.sub.i +2A-B=U.sub.i +K.sub.2 where K.sub.2 =2A-B in octant8V.sub.i+1 =d.sub.i+1 -d.sub.i =f((x.sub.i +1/2)+1,(y.sub.i -1/2)-1)-f(x.sub.i +1/2,y.sub. i -1/2)=A[2(x.sub.i +1/2)+1]+B[(-x.sub.i +1/2)+(y.sub.i -1/2)-1]+C[-2(y.sub.i -1/2)+1]+D-E=(2A-B)x.sub.i+1 +(B-2C)y.sub.i+1 +D-E=V.sub.i +2(A-B+C)=V.sub.i +K.sub.3 where K.sub.3 =2(A-B+C) in octant 8Initialization: x.sub.0 =0,y.sub.0 =0d.sub.0 =(A-B+C)/4 +(D-E)/2 +FU.sub.0 =-B/2+DV.sub.0 =D-EK.sub.1 =2AK.sub.2 =2A-BK.sub.3 =2(A-B+C)______________________________________ 
    
     Detect Octant Change 
     In FIG. 4, ellipse 60 represents the general form of a conic section. As in FIG. 2, the perimeter of ellipse 60 is partitioned into octants numbered 1-8 by boundary arrows, such as boundary arrow 62. Again like in FIG. 2, the curve-tracking algorithm moves in a counter-clockwise direction around the perimeter of ellipse 60. The transition from one octant to the next is detected by examining the components of the gradient vector. After entering an octant, the algorithm&#39;s current position remains in that octant as long as the appropriate condition remains true to the conditions depicted in Table 1. 
     The gradient vector is defined to be: 
     
         grad f=df/dx·i+df/dy·j 
    
     where f(x,y)=Ax 2  =Bxy+Cy 2  +Dx+Ey+F=O and i and j are unit vectors in the x and y directions. 
     Octant Test 
     While a condition remains true, the current position of the algorithm on the perimeter of the ellipse is within the designated octant. 
     
         f(x,y)=Ax.sup.2 +Bxy+Cy.sup.2 +Dx+Ey+F 
    
     
         df/dx=2Ax+By+D, df/dy=Bx+2Cy+E 
    
     Octant 1 
     df/dx&lt;-df/dy, df/dx+df/dy&lt;0 df/dx+df/dy=(2A+B) x i  +(B+2C) y i  +D+E=V i  The condition is V i  &lt;0. 
     Octant 2 
     df/dy&lt;0,df/dy=Bx+2Cy+E df/dy=U i  +(K 1  -K 2 )/2. The condition is U i  &lt;(K 2  -K 1  )/2. 
     Octant 3 
     df/dx&gt;df/dy,df/dx-df/dy&gt;0 df/dx-df/dy=(2A-B)x i  +(B-2C)y i  +D-E=-V i . The condition is V i  &lt;0. 
     Octant 4 
     df/dx&gt;0, df/dx=2Ax i  +By i  +D df/dx=-U i  +(K 2  -K 1 )/2. The condition is U i  &lt;(K 2  -K 1 )/2. 
     Octant 5 
     -df/dx&lt;dy/dx,df/dx+dy/dx&gt;0 df/dx+df/dy=(2A+B)x i  +(B+2C)y i  +D+E=-V i . The condition is V i  &lt;0. 
     Octant 6 
     df/dy&gt;0,df/dy=Bx i  +Cy i  +E=-U i  +(K 2  -K 1 )/2. The condition is U i  &lt;(K 2  -K 1 )/2. 
     Octant 7 
     -df/dx&gt;-df/dy,df/dx-df/dy&lt;0 df/dx-df/dy=(2A-B)x i  +(B-2C)y i  +D-E=V i . The condition is V i  &lt;0. 
     Octant 8 
     df/dx&lt;0,df/dx=2Ax i  +By i  +D df/dx=U i  +(K 1  -K 2 )/2. The condition is U i  &lt;(K 2  -K 1 )/2. 
     Update Loop Parameters During Octant Change 
     When crossing the boundary from one octant to the next, parameters d, u, v, k 1 , k 2  and k 3  must be modified to be valid in the new octant. The new values can be calculated in terms of the values in the previous octant. 
     
         ______________________________________Case 1: Change from ODD to EVEN octant.d&#39;    =      d            k.sub.1 &#39;                           =    k.sub.1 -2k.sub.2 +k.sub.3v&#39;    =      v            k.sub.2 &#39;                           =    k.sub.3 -k.sub.2u&#39;    =      v-u-k.sub.1 +k.sub.2                     k.sub.3 &#39;                           =    k.sub.3new          old          new        oldCase 2: Change from EVEN to ODD octant.d&#39;    =      d+u-v+k.sub.1 -k.sub.2                     k.sub.1 &#39;                           =    k.sub.1v&#39;    =      2u-v+k.sub.1 -k.sub.2                     k.sub.2 &#39;                           =    2k.sub.1 -k.sub.2u&#39;    =      u+k.sub.1 -k.sub.2                     k.sub.3 &#39;                           =    k.sub.3 +4k.sub.1 -4k.sub.2new          old          new        old______________________________________ 
    
     In either case above, the primed quantities represent the values in the new octant, while the unprimed quantities are the values in the old octant. 
     The detailed derivations of the parameter changes occurring at each of the 8 octant boundaries are given below: 
     
         ______________________________________Octant 1- Octant 2: d&#39;=d,v&#39;=vu&#39;=v-u-k.sub.1 +k.sub.2=[(2A+B)x+(B+2C)y+D+E]-[2Ax+By+B/2+D]+B=Bx+2Cy+B/2+E2-3: d&#39;-d=u-v+k.sub.1 -k.sub.2=[Bx+Cy+B/2+E]-[(2A+B)x+(B+2C)y+D+E]-B=-2Ax-By-B/2-D=f((x+1/2)-1,y+1/2)-f(x+1/2,y+1/2)=A[-2(x+1/2)+1]+B[-(y+1/2)]-D=-2Ax-By-B/2-Dv&#39;=2u-v+k.sub.1 -k.sub.2=[Bx+2Cy+B/2+E]+[-2Ax-By-B/2-D]=(-2A+B)x+(-B+2C)y-D+Eu&#39;=u+k.sub.1 -k.sub.2 =[Bx+2Cy+B/2+E]-B=Bx+2Cy-B/2+E3-4: d&#39;=d,v&#39;=vu&#39;=v-u-k.sub.1 +k.sub.2=[(-2A+B)x+(-B+2C)y-D+E]-]Bx+2Cy-B/2+E]-B=-2Ax-By-B/2- D4-5: d&#39;-d=f(x-1/2,(y+1/2)-1)-f(x-1/2,y+1/2)=B[-(x-1/2)]+C[-2(y+1/2)+1]-E=-Bx-2Cy+B/2-E=u-v+k.sub.1 -k.sub.2 =[-2Ax-By-B/2-D]-[(-2A+B)x+(-B+2C)y-D+E]+B=-Bx-2Cy+B/2-Ev&#39;=2u-v+k.sub.1 -k.sub.2 =[-2Ax-By-B/2-D]+[-Bx-Cy+B/2-E]=(-2A-B)x+(-B-2C)y-D-Eu&#39;=u+k.sub.1 -k.sub.2 =u+B5-6: d&#39;=d,v&#39;=vu&#39;=v-u-k.sub.1 +k.sub.2=[(-2A-B)x+(-B-2C)y-D-E]-[-2Ax-By+B/2-D]+B=-Bx-2Cy+B/2-E6-7: d&#39;-d=f((x-1/2)+1,y-1/2)-f(x-1/2,y-1/2)=A[2(x-1/2)+1]+B[(y-1/2)]+D=2Ax+By-B/2+D=u-v+k.sub.1 -k.sub.2=[-Bx.sub.i -2Cy.sub.i +B/2-E]-[(-2A-B)x+(-B-2C)y-D-E]-B=2Ax+By-B/2+Dv=2u-v+k.sub.1 -k.sub.2 =u+[u-v+k.sub.1 -k.sub.2 ]=[-Bx-2Cy+B/2-E]+[2Ax+By-B/2+D]=(-B+2A)x+(B-2C)y+D-Eu&#39;=u+k.sub.1 -k.sub.2 =U-B7-8: d&#39;=d,v&#39;=vu&#39;=v-u-k.sub.1 +k.sub.2=[(2A-B)x+(B-2C)y+D-E]-[-Bx-2Cy-B/2-E]-B=2Ax+By-B/2+D8-1:d&#39;-d=f(x+1/2,(y-1/2)+1)-f(x+1/2,y-1/2)=B[(x.sub.i +1/2)]+C[2(y.sub.i -1/2)+1]+E=Bx+2Cy+B/2+E=u-v+k.sub.1 -k.sub.2=[2Ax+By-B/2+D]-[(2A-B)x+(B-2C)y+D-E]+B=Bx+2Cy+B/2+Ev&#39;=2u-v+k.sub.1 -k.sub.2=[2Ax+By-B/2+D]+[Bx+2Cy+B/2+E]=(2A+ B)x+(B+2C)y+D+Eu&#39;=u+k.sub.1 -k.sub.2=u+B______________________________________ 
    
     Implementation 
     The implementation of the invention can be purely in software, in which case the invention will run on existing computer equipment. Hardware enhancements, on the other hand, can accelerate the speed at which the invention operates. 
     FIG. 6 is a system-level block diagram of a software implementation of the invention. For some applications, a software implementation may not be fast enough to construct character shapes on a screen (or other display surface) directly from the font-outline specifications. In applications requiring real-time text speeds, an intermediate step may be necessary. The invention can be used to construct a bitmapped representation of some or all of a font&#39;s character shapes in a &#34;font cache&#34; contained in a buffer in off-screen memory. Once converted to bitmapped form, the individual character shapes are copied (via PixBlt, or pixel-aligned block transfer) to the screen from cache 604 as they are needed. Copying the bitmapped character shapes from font cache 604 can be performed much more rapidly than constructing the character shapes from the font-outline specification. This method, however, requires that the software maintain the font cache, and also requires the allocation of memory for the font cache bitmap. 
     FIG. 7 is a system-level block diagram of an implementation of the invention that includes hardware acceleration of critical operations. An efficient hardware implementation operates at speeds sufficient to eliminate the need to cache font bitmaps. Under these conditions, the invention can be used to construct the character shapes on screen 704 directly from their font-outline descriptions. This eliminates the software and storage overhead necessary to maintain the font cache. As described previously, the invention requires two processing steps to construct a filled character shape from its font-outline description. Both steps can be assisted by acceleration hardware. 
     The first step is to draw the outline of the character to an edge-flag buffer, which is a one-bit-per-pixel bitmap. Acceleration hardware can be designed to calculate the positions of edge flags along a curved boundary at high speeds using a hardwired implementation of a modified Pitteway algorithm 701. The acceleration hardware may be incorporated into a graphics processor chip such as the TMS34010, for instance. The implementation of a modified Pitteway algorithm is similar to implementations of Bresenham&#39;s line-drawing algorithm in existing hardware, except that Pitteway&#39;s algorithm draws conics, and is therefore somewhat more complex than Bresenham&#39;s. While edge-flag buffer 702 could be contained in main memory, the construction of the character outline could be performed more rapidly in an edge-flag buffer on the same chip as the graphics processor containing the hardware acceleration for the Pitteway algorithm. The speed improvement resulting from having an on-chip edge-flag buffer could be crucial for meeting the speed requirements of real time text applications. 
     The second step of the process can also be sped up by acceleration hardware. In this step, the character outline contained in the edge-flag buffer is used to guide the construction of a filled character shape on screen 703. The character is filled using a parity-fill algorithm that constructs the filled character shape one scan line at a time. For each scan line, the algorithm begins at the left edge of the portion of the edge-flag buffer containing the edge bits for the scan line. The algorithm searches from left to right, recording in turn the x coordinate of each edge flag (represented as a 1 in the bitmap). Each pair of adjacent edge flags on the scan line represents the beginning and end of a filled span within the character, and results in the span being filled on the screen. (The span includes the starting pixel but excludes the ending pixel). The acceleration hardware can speed up the process of searching the edge-flag buffer for edge flags. 
     In fact, a hardwired &#34;guided fill&#34; mechanism 703 can automatically perform the conversion of edge flag to filled spans on the screen with minimal software intervention. Again, the potential speed-up for the guided-fill process will be greater if the storage for the edge-flag buffer is on the same chip as the processor performing the guided fill. This arrangement supports a pipeline mechanism whereby one span in the display memory external to the graphics processor chip is being filled at the same time the pair of edge bits for the next span is being located in the edge-flag buffer internal to the chip. 
     The preceding discussion has assumed that the edge flags are stored in a one-bit-per-pixel bitmap; i.e., that the outline of a character shape is drawn into this bitmap. An equivalent implementation stores the same information as a linked list rather than a bitmap. In this implementation, the edge flags are bucket-sorted by scan line, and a linked list is maintained per scan line. Each list contains the x coordinates of the edge flags in left-to-right order across the scan line. For very large filled shapes, the edge-flag array may be relatively sparse, in which case the linked-list representation for the buffer may require less storage than a bitmap. In a typical text application, however, most character shapes should be small enough that the bitmap representation for the edge-flag buffer is preferable. 
     It should be noted that one use of the invention is to present graphics or type fonts to a user. This can be done, for example, on any output display device, such as a CRT display terminal or a printer. 
     Although this description describes the invention with reference to the above specified embodiments, the claims and not this description limit the scope of the invention. Various modifications of the disclosed embodiment, as well as alternative embodiments of the invention, will become apparent to persons skilled in the art upon reference to the above description. Therefore, the appended claims will cover such modifications that fall within the true scope of the invention.