System for rapidly performing scan conversion with anti-aliasing upon outline fonts and other graphic elements

• US 6,437,793 B1
• Filed: 07/29/1999
• Issued: 08/20/2002
• Est. Priority Date: 07/29/1999
• Status: Expired due to Term

• Current Assignee: MyFonts, Inc.
• Original Assignee: Bitstream Incorporated
• Inventors: Kaasila, Sampo J.
• Primary Examiner(s): BRIER, JEFFERY A
• Application Number:
  US09/363,513
• Time in Patent Office: 1,118 Days
• Field of Search: 345/433, 345/443, 345/136, 345/619, 345/611, 345/421, 345/606, 345/441, 345/442, 345/613, 345/614, 382/269
• US Class Current: 345/611
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 15/503 Blending, e.g. for anti-aliasing

Abstract

A system rapidly rasterizes high resolution shapes, such as outline fonts, for use in a lower resolution pixel image. For individual pixels a line coverage value is determined for each of at least two sampling lines running in different directions, such as at right angles, within the pixel. The pixel'"'"'s line coverage value for each line is a function of the degree to which the line is covered by any shapes within the pixel. Then a coverage value is determined for the pixel, itself, as a non-linear function of it'"'"'s one or more line coverage values running in each of the different directions. Commonly the non-linear function causes the pixel'"'"'s coverage value to vary more rapidly with variations in the line coverage value of that one of its sampling line which is closest to being half covered within the pixel. Such rasterization can be performed even more rapidly by using two passes, a first which calculates a pixel coverage value for all pixels as a function of the coverage within each pixel of one or more lines of the first set of parallel lines which run in a first direction, and a second pass which varies the pixel coverage value set in the first pass only if there is an intersection between the outline of a shape being rendered and a one or more lines of the second set of parallel lines which run in a second direction.

Claims

1. A computerized method for setting pixel coverage values in a 2-diminsional pixel image for use in human-readable displays in which the pixel image represents a higher-resolution 2-dimensional representation of one or more shapes defined at a finer resolution than the resolution of the pixel image and in which the pixel image is formed of a plurality of pixels, each representing a corresponding sampling area of the higher-resolution representation and each having a pixel coverage value indicating the extent to which the corresponding sampling area is covered by one of said shapes, said method comprising the following for each of a plurality of said pixels:

determining a line coverage value for each of at least two sampling lines running in different non-parallel directions within the pixel'"'"'s corresponding sampling area as a function of the degree to which the sampling line is covered by any of said shapes within the sampling area; and

determining the pixel coverage value for the pixel as a non-linear function of the line coverage values determined for the two sampling lines.

2. A computerized method as in claim 1 wherein, over a majority of possible different combinations of line coverage values for the two sampling lines produced by the method, the rate of change of the pixel coverage value varies more rapidly with variations in the line coverage value of that one of the two sampling lines whose line coverage value is nearest a value associated with one half of the sampling line being covered by said shapes.

3. A computerized method as in claim 2 wherein, over a majority of possible different combinations of line coverage values for the two sampling lines produced by the method, the rate of change of the pixel coverage value varies only in response to the line coverage value of that one of the two sampling lines whose line coverage value is nearest a value associated with one half of the sampling line being covered by said shapes.

4. A computerized method as in claim 2 wherein, over a majority of possible different combinations of line coverage values for the two sampling lines produced by the method, the rate of change of the pixel coverage value varies in response to variations in the line coverage values of both of said two sampling lines.

5. A computerized method as in claim 1 wherein the non-linear function determines the pixel coverage value by looking up a value at a location in a look-up table which is addressed as a function of the line coverage values of at least the two sampling lines.

6. A computerized method as in claim 5 wherein the value at a location in the look-up table addressed by a given combination of line coverage values of the two sampling lines is derived from a plurality of pixel coverage value calculated made by a more computational intensive method in prior situations in which a pixel had a corresponding combination of line coverage values.

7. A computerized method as in claim 5 wherein said shapes are the shapes of characters in one or more sets of fonts, and where the method includes using different look-up tables to determine the pixel coverage value when rendering characters from different sets of fonts.

8. A computerized method as in claim 1 wherein the non-linear function determines the pixel coverage value as a function of the line coverage values of at the two sampling lines which involves a weighted sum of the two line coverage values in which the contribution of each of the two line coverage values is a function of how close each such line coverage value is to an intermediate line coverage value.

9. A computerized method as in claim 1 wherein said two sampling lines are at right angles relative to each other.

10. A computerized method as in claim 9 wherein:

said pixel image is comprised of pixels arranged in rows and columns; and

said coverage values are determined for only two sampling lines in each pixel, one sampling line extending in substantially in the middle of each pixel row and one sampling line extending substantailly in the middle of each pixel column.

11. A computerized method as in claim 1 wherein:

said shapes are described by outlines which define said shapes at a higher resolution than the pixel resolution of said pixel image; and

said determining of line coverage values determines such line coverage as a function of the distance between intersections between the outlines of said shapes and the sampling lines.

12. A computerized method for creating a 2-diminsional pixel image for use in human-readable displays in which the pixel image represents a higher-resolution 2-dimensional representation of one or more shapes defined at a finer resolution than the resolution of the pixel image and in which the pixel image is formed of a plurality of pixels, each representing a corresponding sampling area of the higher-resolution representation and each having a pixel coverage value indicating the extent to which the corresponding sampling area is covered by one of said shapes, said method comprising:

calculating the intersections between said shapes and a first set of parallel sampling line running in a first direction in said higher-resolution representation;

calculating the intersections between said shapes and a second set of parallel sampling line running in a second direction, different than, and non-parallel to, said first direction, in said higher-resolution representation;

performing a first pixel setting pass including calculating a pixel coverage value for each pixel by;

determining the line coverage values of the one or more sampling lines of the first set in said pixel'"'"'s sampling area as a function of the degree to which such sampling lines are covered by any of said shapes within the sampling area; and

then determining the pixel coverage value for the pixel as a function of such line coverage values; and

after performing the first pass, performing a second pixel setting pass which only changes pixel coverage values set in the first pass for pixels presenting a sampling area in which one or more of said intersections between said shapes and the second set of sampling lines have been calculated, said second pass changing the pixel coverage value of a pixel in which such an intersection has been calculated by;

determining the line coverage values of the one or more sampling lines of the second set in said pixel'"'"'s sampling area as a function of the degree to which such sampling lines are covered by any of said shapes within the sampling area; and

then determining the pixel coverage value for the pixel as a function of the line coverage values calculated for the pixel in the first pass and the line coverage values calculated for the pixel in the second pass.

13. A computerized method as in claim 12 wherein:

the pixel image is comprised of a series of pixel rows stored in a memory at sequential addresses, and each pixel row includes a series of said pixel coverage values stored in the memory at more closely spaced sequential addresses; and

the first pass is performed for sampling lines which extend in the direction of such pixel rows.

14. A computerized method as in claim 12 wherein said pixel image is comprised of a two dimensional array of pixels, and said first and second directions correspond to the two dimensions of said array.

15. A computerized method as in claim 12 wherein said second pass causes the pixel coverage value for a pixel to be determined as a non-linear function of the line coverage values of sampling lines running in said first and second directions, in which the rate at which the pixel coverage value changes as a function of the rate of change in a given line coverage value varies as a function of the line coverage value itself.

16. A computerized method for creating a 2-diminsional pixel image for use in human-readable displays in which the pixel image represents a higher-resolution 2-dimensional representation of a character-font shape defined by outlines at a finer resolution than the resolution of the pixel image and in which the pixel image is formed of a plurality of pixels arranged in rows and columns, each pixel representing a corresponding sampling area of the higher-resolution representation and each having a pixel coverage value indicating the extent to which the corresponding sampling area is covered by one of said shapes, said method comprising:

calculating the intersections in said higher-resolution 2-dimensional representation between said shape outlines and a set of parallel row sampling lines which run along said pixel rows and between said shape outlines and a set of parallel column sampling line which run along said pixel columns, said calculation including;

advancing around each outline of the character-font shape, finding each such intersection which occurs during such advance; and

placing each such intersection with a given sampling line in an ordered intersection list associated with the sampling line, in an ordered position indicating its distance, relative to any other such intersections which occur with the sampling line, to a start end of the sampling line;

performing a first pixel setting pass including;

for each pixel row;

for each pixel in the row starting with the pixel nearest the start end of its corresponding row sampling line;

if there is no intersection in row sampling line'"'"'s associated intersection list which occurs in the pixel'"'"'s sampling area, set the pixel to a pixel coverage value corresponding to the sampling line'"'"'s current line coverage state;

else;

change the sampling line'"'"'s current line coverage state to reflect each successive intersection in the intersection list in the pixel'"'"'s sampling area;

calculate a row line coverage value as a function of the portion of the row sampling line within the pixel'"'"'s sampling area which is covered by the character-font shape; and

set the pixel to a pixel coverage value determined as a function of the row line coverage value calculated for the pixel; and

performing a second pixel setting pass after performing the first pass, said second pass including;

for each pixel column with any intersections in its associated intersection list;

for each pixel in the column starting with the pixel nearest the start end of its corresponding column sampling line, for which there is an intersection in corresponding intersection list in the pixel'"'"'s sampling area;

change the column sampling line'"'"'s current line coverage state to reflect each successive intersection in the intersection list in the pixel'"'"'s sampling area;

calculate a column line coverage value as a function of the portion of the column sampling line within the pixel'"'"'s sampling area which is covered by the character-font shape; and

set the pixel'"'"'s pixel coverage value as a function of row line coverage value calculated for the pixel in the first pass and the column line coverage value calculated for the pixel in the second pass.

17. A computerized method as in claim 16 wherein the function used to set pixel coverage values in the second pass as a function of a pixel'"'"'s row and column line coverage values, is a non-linear function in which, over a majority of possible different combinations of row and column line coverage values, the rate of change of the pixel coverage value varies more rapidly with variations in the line coverage value of that one of the pixel'"'"'s row or column sampling line whose line coverage value is nearest a value associated with one half of the sampling line within the pixel being covered said shapes.

18. A computer readable memory including computer programming for setting pixel coverage values in a 2-diminsional pixel image for use in human-readable displays in which the pixel image represents a higher-resolution 2-dimensional representation of one or more shapes defined at a finer resolution than the resolution of the pixel image and in which the pixel image is formed of a plurality of pixels, each representing a corresponding sampling area of the higher-resolution representation and each having a pixel coverage value indicating the extent to which the corresponding sampling area is covered by one of said shapes, said programming including instructions for:

determining a line coverage value for each of at least two sampling lines running in different non-parallel directions within the pixel'"'"'s corresponding sampling area as a function of the degree to which the sampling line is covered by any of said shapes within the sampling area; and

determining the pixel coverage value for the pixel as a non-linear function of the line coverage values determined for the two sampling lines.

19. A computer readable memory as in claim 18 wherein, over a majority of possible different combinations of line coverage values for the two sampling lines produced by the method, the rate of change of the pixel coverage value varies more rapidly with variations in the line coverage value of that one of the two sampling lines whose line coverage value is nearest a value associated with one half of the sampling line being covered by said shapes.

20. A computer system for setting pixel coverage values in a 2-diminsional pixel image for use in human-readable displays in which the pixel image represents a higher-resolution 2-dimensional representation of one or more shapes defined at a finer resolution than the resolution of the pixel image and in which the pixel image is formed of a plurality of pixels, each representing a corresponding sampling area of the higher-resolution representation and each having a pixel coverage value indicating the extent to which the corresponding sampling area is covered by one of said shapes, said programming including instructions for:

computational logic for determining a line coverage value for each of at least two sampling lines running in different non-parallel directions within the pixel'"'"'s corresponding sampling area as a function of the degree to which the sampling line is covered by any of said shapes within the sampling area; and

computational logic for determining the pixel coverage value for the pixel as a non-linear function of the line coverage values determined for the two sampling lines.

21. A computer system as in claim 20 wherein, over a majority of possible different combinations of line coverage values for the two sampling lines produced by the method, the rate of change of the pixel coverage value varies more rapidly with variations in the line coverage value of that one of the two sampling lines whose line coverage value is nearest a value associated with one half of the sampling line being covered by said shapes.