Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-07-19
2003-12-30
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S422000, C345S441000, C345S589000, C345S506000, C345S614000
Reexamination Certificate
active
06670955
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to graphics processing in a computer system, and more particularly to a method for blending graphic fragments.
BACKGROUND OF THE INVENTION
Transparency effects are a desirable and necessary part of rendering in graphic systems. The difficulty is that correctly handling transparency requires processing the polygons that contribute to the color of a pixel in a front to back or back to front order to determine the color. The transparency of an object is usually specified as an “alpha” value which indicates how much of the color is from this polygon and how much should be transmitted from a polygon behind this one.
When an object is rendered on the screen, an RGB color and a Z-buffer depth are associated with each pixel. Another component, called alpha, can also be stored. Alpha is a value describing the degree of opacity of an object for a given pixel. An alpha of 1.0 means the object is opaque and entirely covers the pixel's area of interest, 0.0 means the pixel is not obscured at all.
One well known approach to drawing objects with transparency is to sort the objects and draw them in a back to front order. This method can not correctly handle cases where polygons inter-penetrate. In each pixel in the screen that an polygon covers the current color in the pixel is multiplied by (1-the alpha of the polygon), the color of the polygon is multiplied by the polygon alpha, and the two results are summed and placed into the pixel as the new current color. In many applications the cost to sort the polygons is unacceptable, frequently due to the large number, but increasingly due to the inclusion of geometric transformation hardware into the graphics pipeline which makes the correct ordering unknown until the primitives are transformed. While it might be possible to move the sorting into the graphics hardware, this is generally impractical as a buffer large enough to hold the polygons would need to be provided.
In addition most 3D graphics systems provide a mechanism for determining which object elements are visible at each pixel. The most common is “z buffering” which involves storing a depth (Z) value at each pixel. Initially this value is set to the most distant value. When an polygon is drawn into the pixel, the depth value is calculated for the intersection of the polygon and the pixel. If the calculated depth value is behind the depth value stored in the pixel, the polygon is not visible in the pixel and its contribution is discarded. If instead the image element depth value is in front of the depth value of the pixel then the image elements color and z can replace the color and z in the pixel. If the objects are opaque the image elements can be rendered in any order. If they are not then the transparent image elements must be rendered last and sorted back to front. An transparent fragment would be correctly occluded if the depth value in the fragment is in front of the depth value of the transparent image element. If the transparent image element were in front it would be alpha blended with the existing color value at the pixel. A third polygon then drawn to that pixel that has depth in-between the previously drawn opaque polygon and the more recent transparent polygon could not be drawn correctly. It will fail the z test, the z having been updated when the first transparent polygon was drawn and the correct color can not be determined without knowing the two colors before they were blended into the pixels color.
One simple method for approximating transparency is called screen-door transparency. The idea is to render the transparent polygon with a checkerboard fill pattern. That is, every other pixel of the polygon is rendered, thereby leaving the object behind it partially visible. Usually the pixels on the screen are close enough together that the checkerboard pattern itself is not visible. The problem with this technique is two fold. First, a transparent object can be only 50% transparent with a simple checkerboard. Larger patterns than a checkerboard are used, but in practice such patterns are usually visible. Second, only one transparent object can be convincingly rendered on one area of the screen. For example, if a transparent red object and transparent green object are rendered atop a blue object, only two of the three colors can appear on the checkerboard pattern. A more complex pattern might allow for the occasional correct rendering of transparency, but since there is no knowledge of what patterns were previously used it is possible that a pattern would be chosen that would exactly cover a previously used pattern for the pixel resulting in an incorrect color. However, one advantage of this technique is its simplicity. Transparent objects can be rendered at any time, in any order, and no special hardware (beyond fill pattern support) is needed.
This approach has been further improved in prior art systems that support anti-aliasing through supersampling. In this case several colors represent each pixel, each color sample representing a slightly different position within the pixel. The primary purpose of this approach is to handle cases where only part of a polygon intersects a pixel. In such a case only some of the samples in a pixel are covered by the polygon. The final color of the pixel is only determined when all primitives have been rendered, at which point the samples are filtered into one single representative color. The screen door approach can be applied on a per sample instead of a per pixel basis. This will completely hide the pattern in the case where the pattern is smaller than the number of samples in each pixel. The other drawback of the screen door approach—incorrect color in the case of overlapping transparency remains.
What is necessary for more general and flexible transparency effects is the ability to keep track of more than one color/z value per pixel.
A prior art algorithm that is used to increase the sampling rate per pixel is Carpenter's A-buffer and is commonly used in software for generating high-quality renderings, but at non-interactive speeds. The A-Buffer approach also includes a improved approach for anti-aliasing but that can be ignored when looking at how it implements transparency that is independent of the order than polygons are rendered.
The core of the A buffer approach is maintaining a list in each pixel of all of the “fragments” that contribute to it. A fragment is the portion of a polygon that intersects the pixel. The process of drawing an polygon includes generating the fragments for each pixel that the polygon intersect. Generating a fragment usually includes calculation the color, depth (Z) and alpha value of the polygon at the pixel.
Each fragment is added to the list at its pixel if it might contribute to the final color. One option is to assume that all fragments will contribute. The list may be maintained in a depth sorted order. When all of the polygons have been drawn, each pixel is processed. The fragments in the list of the pixel are sorted if they were not maintained sorted. The fragments are then processed in order, which allows the correct color to be determined.
The prior art system used a linked list structure for the per pixel fragment list. The complexity of implementing a linked list or alternative structures have generally restricted the A buffer scheme to non-interactive software implementations of rendering systems.
Thus there is a need for a method of alpha blending fragments that operates efficiently without using linked lists or similar structures.
REFERENCES:
patent: 5872902 (1999-02-01), Kuchkuda et al.
patent: 5923333 (1999-07-01), Stroyan
patent: 5977977 (1999-11-01), Kajiya et al.
patent: 6268875 (2001-07-01), Duluk et al.
ATI International SRL
Nguyen Kimbinh T.
Zimmerman Mark
LandOfFree
Method and system for sort independent alpha blending of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for sort independent alpha blending of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for sort independent alpha blending of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3132244