Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
1999-02-10
2002-03-19
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S600000, C345S605000, C345S549000
Reexamination Certificate
active
06359626
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to systems for computer graphics. More specifically, the present invention includes a method and apparatus for producing accurate pixel colors using a limited number of reduced accuracy samples.
BACKGROUND OF THE INVENTION
Computer systems (and related devices) typically create three-dimensional images using a sequence of stages known as a graphics pipeline. During early pipeline stages, images are modeled using a mosaic-like approach where each image is composed of a collection of individual points, lines and polygons. These points, lines and polygons are known as primitives and a single image may require thousands, or even millions, of primitives. Each primitive is defined in terms of its shape and location as well as other attributes, such as color and texture.
The primitives used in early pipeline stages are transformed, during a rasterization stage, into collections of pixels. The rasterization stage is often performed by a specialized graphics processor (in low-end systems, rasterization may be performed directly by the host processor) and the pixels are stored in a device known as a frame buffer. The frame buffer is a memory device that includes individual memory locations for each pixel.
During the rasterization stage, the graphics processor renders each primitive into the frame buffer. The graphics processor accomplishes this task by determining which pixels (i.e., which frame buffer memory locations) are included within the bounds of each primitive. The frame buffer memory locations for included pixels are then initialized to reflect the attributes of the primitive, including color and texture.
In some cases, individual pixels will include portions of more than one primitive. This may occur, for example, at the edge of overlapping or adjacent primitives. When pixels are shared between primitives, a form of pixel aliasing occurs. Pixel aliasing is generally undesirable because it is not always possible to render aliased pixels to accurately reflect each of the primitives in which they are included. As an example, consider the case of a pixel that is shared between primitives of different colors. In such a case, if the pixel is rendered to reflect the color of one primitive, it will be incorrectly colored for the remaining primitives in which it is included.
Multisample antialiasing is a technique that is designed to improve the appearance of aliased pixels. The underlying idea of multisample antialiasing is to generate color values for a series of sample locations within each pixel (rather than at a single location per-pixel). This process is generally referred to as dithering. The color values for the sample locations are generated as part of the rendering process. Each time a primitive is rendered, the color values for the samples included within that primitive are generated. When all of the primitives that include a given pixel have been rendered, a color for that pixel can be generated. The pixel color is generated by averaging, or otherwise combining the values of the color samples for that pixel.
The process of combining or averaging color sample values can be subdivided into two cases: reconstruction and construction. The first case, reconstruction, occurs when all of the color sample values have been generated for the same color value. This may happen, for example, when a pixel is included entirely within a single primitive. It can also happen when a pixel is shared between different primitives that have identical coloring at the pixel's location. In these cases, the color sample values are optimally combined in a way that is an exact reconstruction of the original color value.
The second case, construction, occurs when the color sample values have been generated for two or more color values. This typically happens when a pixel is shared between primitives having distinct color values. In these cases, the color sample values are combined in a way that is an intermediate color value. The intermediate color value creates a visually pleasing transition between primitives.
Multisample antialiasing is an effective technique for improving the appearance of aliased pixels. At the same time, the use of multiple color samples increases the amount of memory that is used by each pixel. Memory bandwidth must also be increased to allow each of the multiple color sample values to the stored and retrieved.
Providing greater storage capacity and bandwidth makes graphics processors more expensive and makes multisample antialiasing less desirable. One way in which this disadvantage may be partially overcome is by using smaller color samples. This is the approach used within ONYX2 INFINITEREALITY computer systems produced by SILICON GRAPHICS, INC. INFINITEREALITY computer systems pair each pixel location with a series of color samples. The number of color samples used for each pixel (referred to as n in this document) is runtime configurable. Typical values for n include four, eight and sixteen color samples for each pixel. The precision of each color sample (referred to as b in this document) is based on n and the precision of each rasterized pixel (referred to as B in this document). The relation between n, b and B is defined by the equation:
b=B−log
2
(n)
As an example, if five bits of color are stored for each rasterized pixel (i.e., B=5) and four color samples are used for each pixel (n=4), then each color sample would have a precision of three bits (b=3). The rasterizing process generates the n color sample values for each pixel using a set of equations of the form:
S[k]=MIN(2
b
−1,(c+k)
)
where c is the color value being sampled and k ranges from 0 to n−1 and where division is performed as integer division with no remainder. For the preceding example of n=4 and b=3, the following equations are used:
S[0]=MIN(7,(c)/4)
S[1]=MIN(7,(c+1)/4)
S[2]=MIN(7,(c+2)/4)
S[3]=MIN(7,(c+3)/4)
The color sample values S[k] are then combined to form a pixel color value r using the equation:
r=S[0]+S[1]+S[2]+. . . S[n−1]
The INFINITEREALITY multisample antialiasing method is an effective method for reducing the number of bits that must be stored for each color sample. Unfortunately, the INFINITEREALITY multisample antialiasing method does not accurately reconstruct all color values. This occurs because each color sample has limited precision. As the color value being sampled is increased, the value that must be stored in each color sample also increases. There is a point where increasing the color value being sampled would cause the values of the color samples to overflow their limited precision. This overflow is prevented because each color sample value is limited, or clamped, to a predefined maximum value of 2
n
−1. The color sample values generated for the numerically greatest n−1 color values may include one or more of these clamped values. Thus, in the example case of n=4 and b=3, the numerically greatest color is 31. The color sample values generated for the values 31, 30, and 29 each include one or more clamped values and, as a result, are not correctly reconstructed.
This result is summarized in the following table:
color
reconstructed
value
S[0]
S[1]
S[2]
S[3]
color value
0
0
0
0
0
0
1
0
0
0
1
1
2
0
0
1
1
2
3
0
1
1
1
3
4
1
1
1
1
4
5
1
1
1
2
5
6
1
1
2
2
6
7
1
2
2
2
7
8
2
2
2
2
8
9
2
2
2
3
9
10
2
2
3
3
10
11
2
3
3
3
11
12
3
3
3
3
12
13
3
3
3
4
13
14
3
3
4
4
14
15
3
4
4
4
15
16
4
4
4
4
16
17
4
4
4
5
17
18
4
4
5
5
18
19
4
5
5
5
19
20
5
5
5
5
20
21
5
5
5
6
21
22
5
5
6
6
22
23
5
6
6
6
23
24
6
6
6
6
24
25
6
6
6
7
25
26
6
6
7
7
26
27
6
7
7
7
27
28
7
7
7
7
28
29
7
7
7
7
28
30
7
7
7
7
28
31
7
7
7
7
28
The inability to reconstruct n−1 possible color values is, of course, not a crippling limitation. Still, there is no
Brier Jeffery
Sajous Wesner
Silicon Graphics Incorporated
Squire Sanders & Dempsey
LandOfFree
Multisample dither method with exact reconstruction does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multisample dither method with exact reconstruction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multisample dither method with exact reconstruction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2833489