Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
1999-03-31
2002-07-16
Chang, Kent (Department: 2673)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S619000
Reexamination Certificate
active
06421060
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to video images, and more particularly to anti-aliased images provided by a memory efficient system and method.
2. Description of the Related Art
A common operation in the field of computer graphics is the creation of an image based on a representation of the boundaries of numerous 2 dimensional (2d) or 3 dimensional (3d) objects. An image is typically defined by a rectangular array of picture elements (pixels), either in a file, a data structure in the memory of a computer, or a set of rows and columns on a display device or printer. Numerical values associated with each pixel define the color assigned to the corresponding row and column of the image. The numerical values associated with each pixel in an image are determined by establishing which pixels are required to represent each member of a set of 2d or 3d drawing primitives such as vectors, triangles, or polygons. The process of determining the addresses (rows and columns) and numerical values (such as colors) of the pixels associated with a drawing primitive is called rasterizing the primitive.
The set of drawing primitives used to create an image is called a scene or a model. The process of generating an image for a particular scene or model is called rendering the scene or model. The process of rendering a scene or model is accomplished by rasterizing each of the drawing primitives in the scene or model.
Referring to
FIG. 1
, an apparatus
10
for creating such an image is shown. This includes a memory
12
for storing a boundary representation of a model or scene, a rendering unit
14
, an image buffer
16
, and a frame buffer
18
. The rendering unit
14
includes one or more processors capable of determining the addresses and color values of all pixels associated with each component of the scene or model. The image buffer
16
is a memory with a capacity of at least m×n×p bytes, where m is a number of rows in the generated image, n is the number of columns, and p is the number of bytes required to represent each pixel. The frame buffer
18
may be a special memory associated with video digital-to-analog converters (DACs) which produce a visible representation of the image on a cathode ray tube (CRT). In some cases, the frame buffer
18
may be a data file or other data structure. In some cases, the image buffer
16
and frame buffer
18
may be the same physical memory.
Referring to
FIG. 2A
, when a primitive such as a triangle
20
is rasterized, there are typically a number of pixels
22
on the interior of the triangle which are completely covered by the triangle. Other pixels
24
located on the boundary of the primitive, however, may be only partly covered by the primitive.
In the simplest case, the process of rasterizing a drawing primitive associates pixels with the primitive on an all or nothing basis. For example, if the center of a particular pixel lies within the area of a particular drawing primitive, then the color of that pixel is determined exclusively by that primitive, and other drawing primitives, which may also partially cover the same pixel, are ignored. The result of associating pixels with drawing primitives on an all or nothing basis results in jagged lines along the boundary of a primitive, as shown in FIG.
2
B. These jagged boundaries in an image are an undesirable artifact known as aliasing. Techniques for avoiding these artifacts are known as anti-aliasing techniques.
The problem of aliasing may be diminished by super-sampling in which the color of a pixel is determined by a number of points within the area of the pixel instead of representing the pixel by its center. This could be accomplished by using conventional rendering and rasterization techniques to generate a super-image as shown in
FIGS. 3A and 3B
. Instead of generating an image with m rows and n columns, an image i×m rows and j×n columns is generated, where i and j are the super-sampling factors. After the super-image has been completed, each i×j block of pixels in the super-image is averaged to determine one pixel in the final m×n anti-aliased image. The color of each pixel in the resulting image reflects the portions of the pixel covered by each drawing primitive, as shown in FIG.
3
C.
Referring to
FIG. 4
, an apparatus
40
required to create an anti-aliased image with the super-image method is shown. In addition to the components of the conventional apparatus shown in
FIG. 1
, this apparatus has a super-image buffer
42
and an image reduction unit
44
. The image reduction unit
44
determines one pixel in the image buffer
16
based on the average value for each i×j block of pixels in the super-image buffer
42
.
The principal problem with the super-image technique is the massive amount of memory required to hold the super-image. A conventional image with a resolution of 600 rows, 800 columns, and 3 bytes per pixel requires nearly 1.5 Mbytes. Super sampling this with factors of i=j=4 would require 16 times as much memory, or roughly 24 Mbytes. If i=j=16, then 256×1.5 Mbytes of memory would be required. In order to implement this in hardware, it would be necessary to provide sufficient real.memory to support the worst case. This would either impose a low upper limit to the super sampling factors, or require providing massive amounts of memory which would be rarely used.
Referring to
FIG. 5
, an alternative apparatus
50
for generating an anti-aliased image is the use of an accumulation buffer
52
. In this case, a conventional m×n image buffer with e.g., 8-bits for each color value is supplemented with a second mxn buffer having 16-bits for each color buffer.
The accumulation buffer
52
is initially cleared to all zeroes. Then the entire scene is rendered into the first buffer i×j times, shifting the entire image by multiples of (1/i) rows and (1/j) columns each time. In effect, each rendering pass determines the pixel values determined by every ith row and every jth column of the super-image.
After each rendering pass, the contents of the image buffer
16
are added (block
56
) to the contents the accumulation buffer
52
. After completing all i×j passes, each color value in the accumulation buffer
52
is divided (block
58
) by i×j, truncated to an 8-bit integer, and copied back to the image buffer
16
. This allows an image to be sampled with up to 256 samples per pixel using only a fixed modest amount of memory beyond that required by the original image buffer
16
. One drawback of this is that the entire image must be rendered many times resulting in a severe performance penalty.
The “accumulation buffer” method may be summarized as follows:
step b1. Create a digital model of the object(s) or scenery to be rendered.
step b2. Decide on the resolution of the image to be generated by the rendering process (for example, this may be 640×480, 1280×1024, etc.).
step b3. Traverse the digital model many times. Clipping boundaries are shifted by a fraction of a pixel on each traversal, and each traversal produces a complete image at the full resolution. For example, the model may be traversed 16 times corresponding to shifting the horizontal and vertical clipping boundaries by (−⅜, −⅛, +⅛, and +⅜) pixel.
step b4. On each traversal, each element of the model is processed. That is, the geometry processing is performed and then the results of the geometry processing are immediately passed on to the rasterization processing. This is fully compatible with standard hardware accelerators for 3d graphics.
step b5. The image created in step b4 is added into a special buffer called an “accumulation buffer”. An accumulation buffer is similar to an ordinary image buffer, except that the accumulation buffer has 16 bits for each component (r, g, b, and possibly alpha) of each pixel. Each of these components is also called a “sample”. The accumulation buffer is not compatible with stand
Chang Kent
F.Chau&Associates,LLP
International Business Machines - Corporation
Patel Nitin
LandOfFree
Memory efficient system and method for creating anti-aliased... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory efficient system and method for creating anti-aliased..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory efficient system and method for creating anti-aliased... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2853106