Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
1998-11-04
2002-04-23
Cuchlinski, Jr., William A. (Department: 3661)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C382S269000
Reexamination Certificate
active
06377273
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a computing method for 3D graphics. More specifically, the present invention relates to a pixel based fast area-coverage computing method for anti-aliasing in 3D graphics applications.
BACKGROUND OF THE INVENTION
In the prior art of high-end 3D computer graphics, the pixels of an image are sub-divided into sub-pixels, and an area-coverage computing technique is employed to resolve the aliasing effect common to graphics imaging. That is, an anti-aliasing method is used which assigns pixel colors based on the fraction of the pixel area that is covered by the image being rendered. Various prior art examples of anti-aliasing methods are described in U.S. Pat. No. 4,908,780, by Priem, et al. (1990); and U.S. Pat. No. 5,299,308, by Suzuki, et al. (1994).
For real time anti-aliasing operation in the prior art, the segment based area-coverage computing method is generally used. That is, a set of consecutive pixels on a scan line constitute a segment, which is evaluated as an entity, utilizing existing graphics pipelines within a system, so that no additional hardware is required. However, because the pixel data is accumulated in segments, there are inherent time delays involved, which adversely affect the overall system pixel yield rate.
To illustrate the need for an anti-aliasing technique,
FIG. 1
shows a screen geometric of pixels and an aliased triangle image. The dash-lined lattice constitutes the geometric coordinate system for pixels. The geometric center of each pixel is located at the point where the vertical and horizontal dash lines intersect. The solid-lined lattice is appended to indicate the pixels' shape. Scan lines are horizontal lines which cross the geometric center of the pixels. The scan lines are shown as horizontal dash lines.
In graphics without anti-aliasing, as in
FIG. 1
, not all of the pixels on the edges are drawn. That is, a pixel is drawn only when it is interior to the edges of the triangle. More specifically, for a pixel on the left edge, it is drawn only if the point where the left edge and scan line intersect is located to the left of the pixel's geometric center. Similarly, for a pixel on the right edge, a pixel is drawn only if the point where the right edge and scan line intersect is located to the right of the pixel's geometric center. A pixel on an edge is considered to be covered when it is interior to the edge. For example, pixels A and B in
FIG. 1
illustrate the left and right edge cases, respectively, and are considered to be covered. Therefore, for a pixel to be drawn on an aliased triangle, it must be either interior to the triangle, or it must meet one of the edge conditions, as described above. This is the primary rule for determining whether or not a pixel should be drawn on an aliased image.
As a result, the pixel edges are drawn in a staircase fashion, as shown in FIG.
1
. The staircase shape is known in the art as “jagged”, and the phenomenon that causes the “jaggies” is called aliasing.
There are two approaches used in the graphics art to suppress the aliasing effect. First, all the pixels that intersect the edge lines, whether covered or not, are taken into account. Second, a pixel is drawn by blending its color (foreground color) with the background color. The amount of blending (ratio of foreground color to background color) is proportional to the pixel's area that is covered by the edge line.
FIG. 2
illustrates the same triangle as in
FIG. 1
, with the addition of all the “uncovered” pixels that intersect the edge lines. As shown in
FIG. 2
, the jaggies are reduced. However, a method is required for computing the area-coverage of an edge over a pixel.
Calculating a pixel's area-coverage may be accomplished by dividing each physical pixel into logical sub-pixels.
FIG. 3
depicts an enlargement of the second row of the triangle and pixels shown in FIG.
2
. In general, a pixel is divided linearly in both the x-direction and y-direction by a number n, which is a power of two. Accordingly a total of n
2
sub-pixels are generated. In
FIG. 3
, n=4, so that n
2
=16 sub-pixels for each pixel.
After dividing each pixel into sub-pixels, each sub-pixel is tested to determine whether or not it is interior to the edges. The same edge intersection rule is applied as in the aliased case, described above, except that the test is now run on sub-pixels, rather than on pixels. Testing of the sub-pixels can be implemented without the need for additional hardware, since the same hardware module used for testing pixels can be implemented to test sub-pixels. This is the most commonly used approach in the prior art.
The outcome of each sub-pixel's test is accumulated in a memory buffer. When all of the sub-pixels of a pixel have been tested, the accumulated test result is retrieved from memory. This accumulated test result represents the area-coverage of the pixel.
In the prior art implementation, the tests must be performed in scan-line order. Consequently, the test operation has to complete all n sub-pixel scan-lines of a segment before the coverage of a pixel is determined. Since the aperture of this type of test operation is the entire segment, this method is categorized as a segment based area-coverage computing algorithm.
In the
FIG. 3
example, there are approximately 3xn
2
sub-pixels along the path to be tested. Since the computation of area-coverage for each pixel must wait for n sub-pixel scan-lines to be completely tested, delays are introduced into the test operation. As such, the segment based area-coverage method has the disadvantage of slowing down the rate of pixel yield.
Accordingly, it is an object of the present invention to overcome this disadvantage of the prior art by using a pixel based method and apparatus for sub-pixel area-coverage, which does not incur the inherent testing delays of the segment based method.
SUMMARY OF THE INVENTION
In accordance with an illustrative embodiment of the present invention, a pixel based method for computing the area-coverage of an image bounded by edges is as follows:
a) selecting a segment of the image to be evaluated for area-coverage, the segment being made up of a set of consecutive pixels on a scan-line section which intersects at least one of the boundary edges,
b) dividing each of the pixels into an n by n sub-pixel array, with n rows and n columns, where n is a number equal to a power of 2, and where the sub-pixel array has n sub-pixel scan-lines, with each sub-pixel scan-line crossing the geometric center of each row of sub-pixels,
c) selecting one of the sub-pixel arrays to constitute a current pixel for area-coverage evaluation,
d) determining the x-axis coordinates of the intersection points of the sub-pixel scan-lines of the current pixel with at least one of the boundary edges of the image,
e) comparing these x-axis coordinates with the x-axis coordinate of the current pixel,
f) determining from this comparison an area-coverage value for each of the sub-pixel rows within the current pixel,
g) accumulating the area-coverage values for all of the sub-pixel rows within the current pixel, and
h) normalizing the accumulated area-coverage values to determine an area-coverage value for the current pixel.
The inventive method described above is implemented in an inventive hardware module which is appended to a conventional graphics rendering engine. The resulting increase in overall system pixel yield rate as compared to the prior art segment based method is more than adequate compensation for the additional cost of the inventive hardware module.
An illustrative embodiment of the present invention is more fully described below in conjunction with the following drawings.
REFERENCES:
patent: 5544294 (1996-08-01), Cho et al.
patent: 6057855 (2000-05-01), Barkans
patent: 6271850 (2001-08-01), Kida et al.
Fu Kuo-Chang
Lee Ruen-Rone
Wang Shin-Ping Robert
Cuchlinski Jr. William A.
Industrial Technology Research Institute
Nguyen Thu
Proskauer Rose LLP
LandOfFree
Fast area-coverage computing method for anti-aliasing in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast area-coverage computing method for anti-aliasing in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast area-coverage computing method for anti-aliasing in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2868954