Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
1999-07-29
2002-08-20
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S441000
Reexamination Certificate
active
06437793
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the scan conversion, or pixel rendering, of outline fonts and other graphic elements with anti-aliasing.
BACKGROUND OF THE INVENTION
Many of the images used to communicate information today are pixel images, that is, images comprised of an array of discrete pixels, or picture elements. Displays on computer screens are normally created using pixel images. In computer displays a pixel normally represents the smallest portion of the display's screen which can be used to show a complete color value. In a monochrome display, a pixel is normally the smallest area the display is capable of illuminating or not. In color displays, a pixel is often the smallest area of the screen which the display can cause to output a composite color. Usually the composite color is formed from sub-pixels, such as a set of red, green, and blue sub-pixels, which are combined to define one full color pixel.
Many printed images are also created as pixel images. In two tone printed images each pixel often represents the smallest mark the printer can make on a piece of paper. In grayscale printed images, a pixel often represents the smallest region on which the printer creates a complete dot pattern having any one of the different grayscale values used to produce grayscale images. In color printed images a full color pixel is created by combining separate grayscale sub-pixels in each of a set of basic colors such as cyan, magenta, yellow, and black.
Many bitmap images are merely displays of information stored in bitmap form having a color value (where color value can represent white or black, a greyscale, or a composite color value) associated with each pixel to be displayed. The computation involved in displaying such bitmap requires little more than moving its pixel values from the bitmap to the portion of computer memory used to represent the screen image. If the display on the screen is at a higher or a lower resolution than that of the given bitmap, all that is required is to re-scale the bitmap to the desired size and to adjust the color values of any partially covered pixels of the resulting image in proportion to the extent they are covered by the re-scaled bitmap.
On the other hand, many bitmap's displayed on computer screens or in printed output are produced from descriptions of shapes to be rendered which are described at a substantially higher resolution than the size of the pixels of bitmapped image to be displayed. In such cases, an algorithm is required to convert such high resolution descriptions into an appropriate pixel image of the shapes they describe. This is particularly common with, so-called, scalable fonts. Scalable fonts are character fonts, the shapes of which are precisely described at a high resolution in terms of lines and curves. Because of this, the shape of a given character in the font can be displayed over a wide ranges of different sizes merely by expanding or contracting the projection of the character's precise description into a given pixel image.
In this specification and the claims which follow, reference to shapes which are defined at a higher or finer resolution than the resolution of a pixel image refer to shapes with definitions which are capable of specifying the boundaries of such shapes at a resolution higher than that of the pixel image. The high resolution referred to is the resolution of the shape defined, not necessarily that of the points or numbers used in the formula or statement which defines such a shape. For example, one could define an outline font in which all the points used as endpoints or control points in the formula or statement used to describe a character's curves or line segments occur on corners of the pixel grid of a given pixel image. In such a case, the points used to describe the font shape would have the same resolution as the pixel image, but if the character shapes include any curved or diagonal lines, the resolution of the shape described by such lines would be much higher than that of the pixel image.
FIG. 1
illustrates the word “Bitstream”
100
, the name of the assignee of the present invention, with the shape of its letters
102
described in a high resolution outline, causing those outlines to appear smooth.
FIG. 2
illustrates how the shapes of the characters
102
in
FIG. 1
begin to look more jagged when they are displayed at a pixel resolution lower than the resolution of the outline description.
FIG. 3
is a close-up of the portion of the pixel image of
FIG. 2
shown in the dotted box
108
. In
FIG. 3
individual pixels
110
of the pixel image are shown. The pixels of the image shown in
FIG. 3
are arranged in perpendicular rows
112
and columns
114
, as is commonly the case in video displays.
In
FIG. 3
the letter capital “B” is shown to have three outlines
113
A,
113
B, and
113
C and the letter small “i” has two outlines
113
D and
113
E.
FIG. 4
shows the outlines
113
A-
113
E in dotted lines superimposed on top of a pixel image corresponding to the shapes defined by those outlines. This pixel image corresponds to the image of “Bi” shown within the dotted box
108
in FIG.
2
.
As can be seen from
FIG. 4
, the process of converting high resolution outlines, such as the outlines
113
A-
113
E, to a lower resolution pixel image often produces images with jagged edges such as the jagged edges
118
shown in FIG.
4
.
It is well-known in the prior art that one can make the edges of a pixel images appear to human viewers to be more smooth by using a process known as anti-aliasing. Anti-aliasing is the process of causing pixels which are partially covered by higher resolution shape being rendered to have intermediate covered values, as is shown by the grayscale pixels
120
shown in FIG.
5
.
FIG. 6
is identical to
FIG. 5
except that it shows the pixel image of
FIG. 5
without the grid of individual pixels
110
being shown.
Anti-aliasing commonly seeks to assign a coverage value, also knows as a color or grayscale value, to a partially covered pixel which is proportional to the percent of the pixel which is covered by one or more high resolution shapes. This is indicated in
FIG. 7
in which a pixel
110
is shown partially covered by shape
114
.
It is possible to take the geometric definition of a shape provided by an outline font description and used geometric methods to calculate the exact percentage of the pixel
110
, shown in
FIG. 7
, covered by that shape. Once this has been done a coverage value corresponding to that percentage can be assigned to the pixel for purposes of anti-aliasing. Unfortunately such computations require a fair amount of processing, which can make rendering a large number of characters with such exactly calculated anti-aliasing undesirably slow. As a result it has been common to calculate the coverage values of partially covered pixels by using approximation.
FIG. 8
illustrates one such approximation method. In this method the curves in the outline description of a shape
114
being rendered are approximated with a series of corresponding linear segments
122
. Such an approximation is considerably faster than trying to calculate the exact area of the shape
114
.
FIG. 9
shows another prior-art approximation method. This method includes determining for each of an array of points
124
located within the pixel
110
whether or not that point falls within the shape
114
or not. It then assigns a coverage value to the pixel which is a function of the proportion of such points within the pixel which fall within the shape
114
relative to which do not.
FIG. 10
illustrates an approximation method which is been previously used by the inventor of the present application. According to this method, each pixel has associated with it one to five horizontal sampling lines
126
and one to five vertical sampling lines
128
. A determination is made for each sampling line of what percent of that line is covered by the shape
114
. Then pixel
110
is assigned a coverage value which equals the average of the c
Bitstream Inc.
Brier Jeffery
Porter Edward W.
LandOfFree
System for rapidly performing scan conversion with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for rapidly performing scan conversion with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for rapidly performing scan conversion with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2905269