Method for rendering a spline for scan conversion of a glyph

Claim 2

In a method of rendering a spline for scan conversion of a glyph comprising a plurality of discrete spline segments, said method of the type including steps of determining, for each selected one of said plurality of spline segments, each intersection of one of a plurality of scan lines of a pixel grid and said selected spline segment, each intersection defining a transition having a transition sense and, for each transition, placing a transition entry in a transition table representing said transition sense for said corresponding transition, said transition entry including the location of said transition in pixel coordinates, an improvement for said determining step comprising the steps of: (a) generating a non-parametric equation describing said selected one of said spline segments, wherein said non-parametric equation is a second order, non-parametric equation for describing the representation of a parabola, wherein 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, wherein said coefficients are defined by control points of said selected spline segment, and wherein said control points for said selected spline segment comprise a pair of endpoints and a point defined by the intersection of tangents extending from said endpoints (b) using forward differencing to determine for said selected spline segment the location in pixel coordinates of each transition: and (c) determining the corresponding transition sense for each transition.

Claim 5

The method of claim 2, wherein said step of selecting said transition table comprises selecting one of said transition tables having an "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 transition table having an "OFF" transition sense.

Claim 6

The improved method recited in claim 2, wherein said non-parametric equation is a second order, non-parametric equation for describing the representation of a parabola.

Claim 7

The improved method recited in claim 4, wherein 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.

Claim 8

The improved method recited in claim 5, wherein said coefficients are defined by control points of said selected spline segment.

Claim 9

The improved method recited in claim 6, wherein said control points for said selected spline segment comprise a pair of endpoints and a point defined by the intersection of tangents extending from said endpoints.

Claim 10

In a computer-readable medium having computer-executable instructions for performing steps to render a spline for scan conversion of a glyph comprising a plurality of discrete spline segments, comprising determining, for each selected one of the plurality of spline segments, each intersection of one of a plurality of scan lines of a pixel grid and the selected spline segment, each intersection defining a transition having a transition sense and, for each transition, placing a transition entry in a transition table representing the the transition sense for the corresponding transition, the transition entry including the location of the transition in pixel coordinates, an improvement of the instructions for performing the determining step, comprising: (a) normalizing a selected one of the spline segments to insure that the selected spline segment is monotonically ascending and located in a first quadrant of the pixel grid; (b) generating a non-parametric equation describing the selected spline segment, wherein the non-parametric equation is a second order, non-parametric equation for describing the representation of a parabola, wherein the 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 the pixel grid, and wherein the coefficients are defined by control points of the selected spline segment, the control points comprising a pair of endpoints and a point defined by the intersection of tangents extending from the endpoints; (c) using forward differencing to determine for the selected spline segment the location in pixel coordinates of each transition; and (d) determining the corresponding transition sense for each transition.

Claim 11

In a computer-readable medium having computer-executable instructions for performing steps to render a spline for scan conversion of a glyph comprising a plurality of discrete spline segments, comprising determining, for each selected one of the plurality of spline segments, each intersection of one of a plurality of scan lines of a pixel grid and the selected spline segment, each intersection defining a transition having a transition sense and, for each transition, placing a transition entry in a transition table representing the the transition sense for the corresponding transition, the transition entry including the location of the transition in pixel coordinates, an improvement of the instructions for performing the determining step, comprising: (a) normalizing a selected one of the spline segments to insure that the selected spline segment is monotonically ascending and located in a first quadrant of the pixel grid; (b) generating a non-parametric equation describing the selected spline segment, wherein the non-parametric equation is a second order, non-parametric equation for describing the representation of a parabola, wherein the 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 the pixel grid, and wherein the coefficients are defined by control points of the selected spline segment, the control points comprising a pair of endpoints and a point defined by the intersection of tangents extending from the endpoints; (c) using forward differencing to determine for the selected spline segment the location in pixel coordinates of each transition; and (d) determining the corresponding transition sense for each transition.

Claim 12

A computer-readable medium having computer-executable instructions for performing steps to render a spline for scan conversion of a glyph comprising a plurality of discrete spline segments, the glyph superimposed on a pixel grid comprising a plurality of scan lines and divided into quadrants, comprising: (a) dividing the spline into the spline segments; (b) selecting one of the spline segments; (c) selecting one of a pair of transition tables based upon the location of the selected spline within the pixel grid, each transition defining the location of an intersection of one of the scan lines with the selected segment, each transition table for storing transitions having one of a pair of opposite transition senses, wherein one of the transition tables having an "ON" transition sense is selected if the selected spline is located in the first quadrant or a second quadrant of the pixel grid, otherwise selecting the other transition table having an "OFF" transition sense; (d) if the selected spline segment is located in one of the quadrants other than the first quadrant, then reflecting the selected spline segment into the first quadrant of the pixel grid; (e) generating a non-parametric equation describing the selected spline segment; (f) solving the non-parametric equation using a set of pixel coordinates (x, y) to produce a sum Q; (g) testing whether the value of the sum Q is greater than zero; (1) if the 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 the pixel coordinates, and solving the non-parametric equation using the new set of the pixel coordinates to produce another value of the sum Q; (2) otherwise, the pixel coordinates associated with the value of the sum Q define one of the transitions, then (i) placing the pixel coordinates for the transition within the selected transition table, and (ii) adding a whole integer pixel unit to the y pixel coordinate value to generate a new set of the pixel coordinates, and solving the non-parametric equation using the new set of the pixel coordinates to produce another value of the sum Q; (h) repeating step (f)-(g) until the selected spline segment has been completely rendered; and (i) repeating steps (b)-(h) for each of the remaining ones of the selected spline segments.

Claim 13

A computer-readable medium having computer-executable instructions for performing steps to render a spline for scan conversion of a glyph comprising a plurality of discrete spline segments, the glyph superimposed on a pixel grid comprising a plurality of scan lines and divided into quadrants, comprising: (a) dividing the spline into the spline segments; (b) selecting one of the spline segments; (c) selecting one of a pair of transition tables based upon the location of the selected spline within the pixel grid, each transition defining the location of an intersection of one of the scan lines with the selected segment, each transition table for storing transitions having one of a pair of opposite transition senses, wherein one of the transition tables having an "ON" transition sense is selected if the selected spline is located in the first quadrant or a second quadrant of the pixel grid, otherwise selecting the other transition table having an "OFF" transition sense; (d) if the selected spline segment is located in one of the quadrants other than the first quadrant, then reflecting the selected spline segment into the first quadrant of the pixel grid; (e) generating a non-parametric equation describing the selected spline segment; (f) solving the non-parametric equation using a set of pixel coordinates (x, y) to produce a sum Q; (g) testing whether the value of the sum Q is greater than zero; (1) if the 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 the pixel coordinates, and solving the non-parametric equation using the new set of the pixel coordinates to produce another value of the sum Q; (2) otherwise, the pixel coordinates associated with the value of the sum Q define one of the transitions, then (i) placing the pixel coordinates for the transition within the selected transition table, and (ii) adding a whole integer pixel unit to the y pixel coordinate value to generate a new set of the pixel coordinates, and solving the non-parametric equation using the new set of the pixel coordinates to produce another value of the sum Q; (h) repeating step (f)-(g) until the selected spline segment has been completely rendered; and (i) repeating steps (b)-(h) for each of the remaining ones of the selected spline segments.

Claim 14

The computer-readable medium recited in claim 9, wherein the non-parametric equation is a second order, non-parametric equation for describing the representation of a parabola, wherein the non-parametric equation is of the form Q=Rx 2 +Sxy+Ty 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 the pixel grid.

Claim 15

The computer-readable medium recited in claim 5, wherein the coefficients are defined by control points of the selected spline segment, the control points comprising a pair of endpoints and a point defined by the intersection of tangents extending from the endpoints.