Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
1999-07-01
2004-09-14
Razavi, Michael (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S581000
Reexamination Certificate
active
06791569
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method for providing antialiasing to a computer displayed line. More specifically, the present invention pertains to a method applying barycentric coordinates for computing a normalized minor axis distance to an ideal line which can then be used as part of the antialiasing technique.
BACKGROUND OF THE INVENTION
Today, computer graphics is used in a wide variety of applications, such as in business, science, animation, simulation, computer-aided design, process control, electronic publication, etc. Basically, computer generated graphics are comprised of points, lines, and polygons, which collectively are referred to as “primitives.” These primitives are then rendered to display realistic two-dimensional and three-dimensional objects, images, and scenes. A complex three-dimensional scene may contain upwards of millions of such primitives.
The way by which primitives are rendered involves a scan conversion process. Basically, a computer screen is made up of millions of pixels (e.g., 980×1024 monitor). The scan conversion process determines which pixels of a computer screen belong to which of the primitives. The pixels are then assigned attributes, such as color, depth, and blending, corresponding to the appropriate primitive. By way of example,
FIG. 1
shows a small 5×11 array of pixels. Each individual pixel is represented, for purposes of illustration, as a square, and the pixel centers are represented as dots. A line can be represented by defining its endpoints. In
FIG. 1
, the vertices
110
and
111
define an ideal line
112
. This straight horizontal line can be rendered for display by assigning a black color to pixels
101
-
109
, while maintaining the other pixels in an unchanged white background color.
Unfortunately, complications arise if a line is slanted, such that it is not either perfectly horizontal or vertical.
FIG. 2
shows a slanted line
203
. The ideal line
203
is defined by its endpoints which have vertices at
201
and
202
. Ideal line
203
passes through pixels
204
-
216
; assigning a black color to these pixels will produce the desired slanted line. However, as can be seen, the resulting line has a “stair-stepped” or “jagged” appearance. Due to the aliases, the displayed line is not smooth and is visually unappealing. The effect of aliasing with respect to lines is particularly disturbing in scenes involving movement. Aliased lines appear to be scintillating.
In order to minimize the effects of line aliasing, designers have implemented a number of clever and useful antialiasing techniques. Antialiasing techniques typically blend the pixel as a function of coverage. Those pixel centers located further away from the ideal line are blended with the background color such that the line color has less effect than those pixels whose centers are closer to the ideal line. Essentially, the greater the pixel area covered by the line, the greater the line's attribute contributes to that particular pixel. Referring back to the example shown in
FIG. 2
, the center of pixel
206
is relatively far away from ideal line
203
. This means that the area of pixel
206
covered by ideal line
203
is relatively small. The final color value assigned to pixel
206
is a blended function of the line color and the background color. But because of the relatively small coverage value, the background color is assigned a higher weighting than that of the line color. Consequently, the final color for pixel
206
is closer to that of the background color than the line color. In contrast, the center of pixel
207
is extremely close to that of ideal line
203
. This indicates that the area of pixel
207
covered by line
203
is relatively quite large (e.g. 50%). Thus, the line color is assigned a higher weighting than that of the background color for pixel
207
. By way of example, given a white background and a black line, pixel
206
would have a very light gray color, whereas pixel
207
would have a much darker gray color. Rather than having a pixel be either black or white, the anti-aliasing technique assigns varying degrees of black, gray, and white. By blending an interpolated line color with the background color, a smoother, straighter, and more realistic display is produced.
Although these types of anti-aliasing techniques are quite effective, they are computationally expensive. For each pixel, the minor axis distance must be calculated, and the coverage must be determined before blending can occur. Calculating the minor axis distance for each sample point as the line is traversed typically entails computing an initial value for the first sample point, forward biasing this value as the line is traversed through linear interpolation, and performing difference calculations to determine the current sample point with respect to the ideal line. These calculations consume valuable time and processing resources. As such, some computers become overwhelmed and are simply incapable of handling high-quality antialiasing for complex, three-dimensional scenes, especially those involving real-time, interactive graphics. Furthermore, antialiasing techniques become even more problematic for lines which are thicker than one pixel wide. It can be difficult to adapt standard antialiasing techniques to these variable width lines.
Thus, there exists a need for a system and method which can readily and accurately calculate the minor axis distance from a sample point to an ideal line for purposes of facilitating antialiasing. It would be preferable if such a system and method were to generate normalized distances so that standard anti-aliasing techniques are readily adapted to handle variable width lines. The present invention provides a novel solution which meets the above needs and which is computationally inexpensive.
SUMMARY OF THE INVENTION
The present invention pertains to a method for applying the principles of barycentric coordinates to perform antialiasing for a computer generated line. A line is defined by its two endpoints. In the present invention, a third point is specified for the purpose of forming a triangle defined by the two endpoints and the third point. Thereby, subarea computations can be performed for any pixel sample point relative to this triangle in order to generate barycentric coordinates which uniquely define that particular sample point. The three barycentric coordinates corresponding to the triangle are then mapped to create two barycentric coordinates, one for each of the two endpoints. An interpolated pixel color can be calculated as a function of these two barycentric coordinates applied to the color of the pixels corresponding to the two endpoints. One of the barycentric coordinates gives the relative minor axis distance from the sample point to the line. This barycentric coordinate is used as an index into a table containing pre-computed coverage values. The appropriate coverage value is then used to modulate a blending value, alpha. The interpolated pixel color is then blended with the background color according to the alpha value.
REFERENCES:
patent: 5361386 (1994-11-01), Watkins et al.
patent: 5381519 (1995-01-01), Brown et al.
patent: 5602979 (1997-02-01), Loop
patent: 5715166 (1998-02-01), Besl et al.
patent: 5809219 (1998-09-01), Pearce et al.
patent: 5844567 (1998-12-01), Gossett et al.
patent: 6038031 (2000-03-01), Murphy
patent: 6104415 (2000-08-01), Gossett
patent: 6597363 (2003-07-01), Duluk et al.
Hussain Zahid S.
Millet Timothy
Havan Thu-Thao
Microsoft Corporation
Razavi Michael
LandOfFree
Antialiasing method using barycentric coordinates applied to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Antialiasing method using barycentric coordinates applied to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Antialiasing method using barycentric coordinates applied to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3232941