Apparatus and method for filling regions bounded by conic curves

A method of forming type fonts for a plurality of characters in an X-Y raster coordinate system, said method comprising the steps of:

• forming a closed region bounded by piecewise conic curves defined by corresponding conic equations of the form f(x,y) 0 for each character of the type font;
• for each character of the type font
• tracking a boundary of the closed region in a counter-clockwise direction by following the piecewise conic curves including
• determining an octant of the corresponding piecewise conic curve from df(x.sub.c,y.sub.c)/dx and df(x.sub.c,y.sub.c)/dy at a current pixel (x.sub.c,y.sub.c),
• determining a next pixel as one of a pair of adjacent pixels of a set of eight adjacent pixels corresponding to the determined octant and the value of f(x,y) at an incrementally displaced location corresponding to the determined octant,
• setting said next pixel as the current pixel and repeating said substeps of determining an octant of the corresponding piecewise conic curve, determining the next pixel, determining if said next pixel is within another piecewise conic curve and setting said next pixel as the current pixel until the tracking of boundary is complete,
• determining edge pixels within said X-Y raster coordinate system at an edge of the closed region from said corresponding conic equation of each piecewise conic curve, said step of determining edge pixels includes forming an edge-flag linked list of respective lines and columns of edge pixels;
• and said step of forming a filled pixel map includes
• sorting said edge-flag linked list by scan line from top to bottom,
• further sorting said scan line sorted edge-flag linked list within each scan line from left to right, and
• forming a filled pixel map in the X-Y raster coordinate system from said further sorted edge-flag linked list with any pixels between a pair of edge pixels on a scan line having a first state and other pixels having a second state, said pixels in said first state defining the pixels within the closed region;
• on a scan line by scan line, left to right basis determining any pixels between a pair of edge pixels,
• forming a filled pixel map of said pixels determined to be between a pair of edge pixels.

A processor system for generating font characters in an X-Y raster coordinate system from a closed region bounded by a set of piecewise conic curves defined by corresponding conic equations of the form f(x,y)=0 for each character of the type font, said processor system comprising:

• accepting circuitry for accepting a set of piecewise conic curves defined by corresponding conic equations of the form f(x,y)=0 for a character to be generated;
• tracking circuitry connected to said accepting circuitry for tracking a boundary of the closed region of said character to be generated in a counter-clockwise direction by following the piecewise conic curves, said tracking circuitry including
• circuitry for determining an octant fDf the corresponding piecewise conic curve from df(x.sub.c,y.sub.c)/dx and df(x.sub.c,y.sub.c)/dy at a current pixel (x.sub.c,y.sub.c),
• circuitry for determining a next pixel as one of a pair of adjacent pixels of a set of eight adjacent pixels corresponding to the determined octant and the value of f(x,y) at an incrementally displaced location corresponding to the determined octant,
• circuitry for setting said next pixel as the current pixel and repeating said substeps of determining an octant of the corresponding piecewise conic curve, determining the next pixel, determining if said next pixel is within another piecewise conic curve and setting said next pixel as the current pixel until the tracking of boundary is complete;
• edge development circuitry connected to said tracking circuitry for determining edge pixels within said X-Y raster coordinate system at an edge of the closed region from said corresponding conic equation of each piecewise conic curve;
• a edge buffer circuit connected to said edge development circuitry for storing said determined edge pixels, said edge buffer circuit consisting of an edge linked list memory storing an edge-flag linked list of respective lines and columns of edge pixels;
• a pixel map memory for storing a map of pixels in the X-Y raster coordinate system;
• and
• filling circuitry connected to said buffer circuit and said pixel map memory for filling pixels within said pixel map memory between a pair of edge pixels on a same scan line.