Method for rendering a spline for scan conversion of a glyph comprising a plurality of discrete segments

Abstract

An improved scan converter to support the efficient and accurate display of character outlines by pixel-oriented display devices. To conserve the finite resource of memory, the improved scan converter supports an efficient use of available memory workspace by accurately determining an upper bound for the amount of memory required to support scan conversion calculations. To achieve improvements in speed and character image quality, the improved scan converter renders the spline segments of a character outline by using a second order equation to calculate an implicit function based on the control points of each segment. The improved scan converter further addresses in a systematic manner the rendering of an endpoint located on a scan line to determine whether the pixel associated with the endpoint should be activated. This decision is based upon the direction of approach to and exit from this endpoint for the pair of segments connected to the endpoint. The improved scan converter also reduces the number of calculations requiring sub-pixel precision to support the selection of a pixel located nearest the contour, thereby providing an improved solution for dropout condition.

We claim: 
     
       1. A method for rendering a spline for scan conversion of a glyph comprising a plurality of discrete spline segments, said glyph superimposed on a pixel grid comprising a plurality of horizontal scan lines and vertical scan lines, said pixel grid divided into quadrants, comprising the steps of: (A) dividing said spline into said spline segments;   (B) selecting one of said spline segments;   (C) if drop-out control for resolving a drop-out condition is elected, then selecting based upon the location of said selected spline within said pixel grid one of a pair of horizontal transition tables for storing horizontal transitions and one of a pair of vertical transition tables for storing vertical transitions, each horizontal transition defining the location of an intersection of one of said horizontal scan lines with said selected segment, each horizontal transition table for storing horizontal transitions having one of a pair of opposite transition senses, each vertical transition defining the location of an intersection of one of said vertical scan lines with said selected segment, each vertical transition table for storing vertical transitions having one of a pair of opposite transition senses; (i) if said selected spline segment is located in one of said quadrants other than said first quadrant, then reflecting said selected spline segment into said first quadrant of said pixel grid;   (ii) generating a non-parametric equation describing said selected spline segment;   (iii) solving said non-parametric equation using a set of pixel coordinates (x, y) to produce a sum Q;   (iv) testing whether the value of said sum Q is greater than zero; (1) if said sum Q is less than or equal to zero, the pixel coordinates associated with said value of said sum Q define one of said horizontal transitions, then placing said pixel coordinates for said horizontal transition within said selected horizontal transition table, and adding a whole integer pixel unit to the y pixel coordinate value to generate a new set of said pixel coordinates, and solving said non-parametric equation using said new set of said pixel coordinates to produce another value of said sum Q;   (2) otherwise, the pixel coordinates associated with said value of said sum Q define one of said vertical transitions, then placing said pixel coordinates for said vertical transition within said selected vertical transition table, and adding a whole integer pixel unit to the x pixel coordinate value to generate a new set of said pixel coordinates, and solving said non-parametric equation using said new set of said pixel coordinates to produce another value of said sum Q;     (v) repeating steps (C)(iii)-(C)(iv) until said selected spline segment has been completely rendered;     (D) if drop-out control is not elected, then selecting one of said pair of horizontal transition tables based upon the location of said selected spline within said pixel grid; (i) if said selected spline segment is located in one of said quadrants other than said first quadrant, then reflecting said selected spline segment into said first quadrant of said pixel grid;   (ii) generating a non-parametric equation describing said selected spline segment;   (iii) solving said non-parametric equation using a set of pixel coordinates (x, y) to produce a sum Q;   (iv) testing whether the value of said sum Q is greater than zero; (1) if said sum Q is greater than zero, then adding a whole integer pixel unit to the x pixel coordinate value to generate a new set of said pixel coordinates, and solving said non-parametric equation using said new set of said pixel coordinates to produce another new value of said sum Q;   (2) otherwise, the pixel coordinates associated with said new value of said sum Q define one of said horizontal transitions, then placing said pixel coordinates for said horizontal transition within said selected horizontal transition table, and adding a whole integer pixel unit to the y pixel coordinate value to generate a new set of said pixel coordinates, and solving said non-parametric equation using said new set of said pixel coordinates to produce another new value of said sum Q;     (v) repeating step (D)(iii)-(D)(iv) until said selected spline segment has been completely rendered; and     (E) repeating steps (B)-(D) for each of the remaining ones of said selected spline segments.   
     
     
       2. The method of claim 1, wherein said step of selecting said transition table in the event that said drop-out control is not elected comprises selecting one of said horizontal transition tables having a "ON" transition sense if said selected spline is located in said first quadrant or a second quadrant of said pixel grid, otherwise selecting said other horizontal transition table having an "OFF" transition sense. 
     
     
       3. The method of claim 2, wherein said step of selecting said transition table in the event that said drop-out control is elected comprises selecting one of said horizontal transition tables having a "ON" transition sense and one of said vertical transition tables having an "OFF" transition sense if said selected spline is located in said first quadrant of said pixel grid. 
     
     
       4. The method of claim 3, wherein said step of selecting said transition table in the event that said drop-out control is elected comprises selecting one of said horizontal transition tables having a "ON" transition sense and one of said vertical transition tables having an "ON" transition sense if said selected spline is located in said second quadrant of said pixel grid. 
     
     
       5. The method of claim 4, wherein said step of selecting said transition table in the event that said drop-out control is elected comprises selecting one of said horizontal transition tables having a "OFF" transition sense and one of said vertical transition tables having an "ON" transition sense if said selected spline is located in said third quadrant of said pixel grid. 
     
     
       6. The method of claim 5, wherein said step of selecting said transition table in the event that said drop-out control is elected comprises selecting one of said horizontal transition tables having a "OFF" transition sense and one of said vertical transition tables having an "OFF" transition sense if said selected spline is located in said fourth quadrant of said pixel grid. 
     
     
       7. The improved method recited in claim 1, wherein said non-parametric equation is a second order, non-parametric equation for describing the representation of a parabola, said non-parametric equation is of the form   Q=Rx.sup.2 +Sxy+Ty.sup.2 +Ux+Vy,     wherein "R", "S", "T", "U", and "V" represent coefficients and "x" and "y" represent the values of pixel coordinates for pixels of said pixel grid.   
     
     
       8. The improved method recited in claim 7, wherein said coefficients are defined by control points of said selected spline segment, said control points for said selected spline segment comprising a pair of endpoints and a point defined by the intersection of tangents extending from said endpoints. 
     
     
       9. A computer-readable medium having computer executable instructions for rendering a spline for scan conversion of a glyph comprising a plurality of discrete spline segments, said glyph superimposed on a pixel grid comprising a plurality of horizontal scan lines and vertical scan lines, said pixel grid divided into quadrants, the instructions performing steps comprising: (A) dividing said spline into said spline segments;   (B) selecting one of said spline segments;   (C) if drop-out control for resolving a drop-out condition is elected, then selecting based upon the location of said selected spline within said pixel grid one of a pair of horizontal transition tables for storing horizontal transitions and one of a pair of vertical transition tables for storing vertical transitions, each horizontal transition defining the location of an intersection of one of said horizontal scan lines with said selected segment, each horizontal transition table for storing horizontal transitions having one of a pair of opposite transition senses, each vertical transition defining the location of an intersection of one of said vertical scan lines with said selected segment, each vertical transition table for storing vertical transitions having one of a pair of opposite transition senses; (i) if said selected spline segment is located in one of said quadrants other than said first quadrant, then reflecting said selected spline segment into said first quadrant of said pixel grid;   (ii) generating a non-parametric equation describing said selected spline segment;   (iii) solving said non-parametric equation using a set of pixel coordinates (x, y) to produce a sum Q;   (iv) testing whether the value of said sum Q is greater than zero; (1) if said sum Q is less than or equal to zero, the pixel coordinates associated with said value of said sum Q define one of said horizontal transitions, then placing said pixel coordinates for said horizontal transition within said selected horizontal transition table, and adding a whole integer pixel unit to the y pixel coordinate value to generate a new set of said pixel coordinates, and solving said non-parametric equation using said new set of said pixel coordinates to produce another value of said sum Q;   (2) otherwise, the pixel coordinates associated with said value of said sum Q define one of said vertical transitions, then placing said pixel coordinates for said vertical transition within said selected vertical transition table, and adding a whole integer pixel unit to the x pixel coordinate value to generate a new set of said pixel coordinates, and solving said non-parametric equation using said new set of said pixel coordinates to produce another value of said sum Q;     (v) repeating steps (C)(iii)-(C)(iv) until said selected spline segment has been completely rendered;     (D) if drop-out control is not elected, then selecting one of said pair of horizontal transition tables based upon the location of said selected spline within said pixel grid; (i) if said selected spline segment is located in one of said quadrants other than said first quadrant, then reflecting said selected spline segment into said first quadrant of said pixel grid;   (ii) generating a non-parametric equation describing said selected spline segment;   (iii) solving said non-parametric equation using a set of pixel coordinates (x, y) to produce a sum Q;   (iv) testing whether the value of said sum Q is greater than zero; (1) if said sum Q is greater than zero, then adding a whole integer pixel unit to the x pixel coordinate value to generate a new set of said pixel coordinates, and solving said non-parametric equation using said new set of said pixel coordinates to produce another new value of said sum Q;   (2) otherwise, the pixel coordinates associated with said new value of said sum Q define one of said horizontal transitions, then placing said pixel coordinates for said horizontal transition within said selected horizontal transition table, and adding a whole integer pixel unit to the y pixel coordinate value to generate a new set of said pixel coordinates, and solving said non-parametric equation using said new set of said pixel coordinates to produce another new value of said sum Q;     (v) repeating step (D)(iii)-(D)(iv) until said selected spline segment has been completely rendered; and     (E) repeating steps (B)-(D) for each of the remaining ones of said selected spline segments.   
     
     
       10. The computer-readable medium of claim 9, wherein said step of selecting said transition table in the event that said drop-out control is not elected comprises selecting one of said horizontal transition tables having a "ON" transition sense if said selected spline is located in said first quadrant or a second quadrant of said pixel grid, otherwise selecting said other horizontal transition table having an "OFF" transition sense. 
     
     
       11. The computer-readable medium of claim 10, wherein said step of selecting said transition table in the event that said drop-out control is elected comprises selecting one of said horizontal transition tables having a "ON" transition sense and one of said vertical transition tables having an "OFF" transition sense if said selected spline is located in said first quadrant of said pixel grid. 
     
     
       12. The computer-readable medium of claim 11, wherein said step of selecting said transition table in the event that said drop-out control is elected comprises selecting one of said horizontal transition tables having a "ON" transition sense and one of said vertical transition tables having an "ON" transition sense if said selected spline is located in said second quadrant of said pixel grid. 
     
     
       13. The computer-readable medium of claim 12, wherein said step of selecting said transition table in the event that said drop-out control is elected comprises selecting one of said horizontal transition tables having a "OFF" transition sense and one of said vertical transition tables having an "ON" transition sense if said selected spline is located in said third quadrant of said pixel grid. 
     
     
       14. The computer-readable medium of claim 13, wherein said step of selecting said transition table in the event that said drop-out control is elected comprises selecting one of said horizontal transition tables having a "OFF" transition sense and one of said vertical transition tables having an "OFF" transition sense if said selected spline is located in said fourth quadrant of said pixel grid. 
     
     
       15. The computer-readable medium of claim 9, wherein said non-parametric equation is a second order, non-parametric equation for describing the representation of a paraboloa, said non-parametric equation is of the form   Q=Rx.sup.2 +Sxy+Ty.sup.2 +Ux+Vy,     wherein "R", "S", "T", "U", and "V" represent coefficients and "x" and "y" represent the values of pixel coordinates for pixels of said pixel grid.   
     
     
       16. The computer-readable medium of claim 10, wherein said coefficients are defined by control points of said selected spline segment, said control points for said selected spline segment comprising a pair of endpoints and a point defined by the intersection of tangents extending from said endpoints.