Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-11-29
2002-06-25
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06411295
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to storing and retrieving the depth information of a three-dimensional object in computer graphics systems, and particularly to an apparatus and method of Z-buffer compression.
BACKGROUND ART
Computer graphics systems are frequently used to model a scene having three-dimensional objects and then to display them on a two-dimensional display device such as a cathode ray tube. One such system in common use is a polygon-based, object-order graphics system in which three-dimensional objects in a scene are each represented by a multitude of polygons (or primitives) that approximate the shapes thereof. Depending upon the orientation selected for viewing the scene in two dimensions, many of the primitives representing objects in the scene will be hidden behind other primitives and thus not displayed. Primitives not completely hidden are termed visible and will be displayed, either in full or in part depending upon whether a portion of a given primitive is hidden, in the rendered image on the display device. As the depth complexity (i.e. the number of levels of primitives hidden behind one another) of a scene to be rendered increases, the percentage of all primitives representing the scene that will ultimately be visible by an observer on the display device decreases significantly. Thus, in many cases, most of the primitives for a scene will be hidden.
Conventional computer graphics systems typically have a frame buffer and a Z-buffer. The frame buffer is a memory (e.g. DRAM or SRAM) which holds the digital representation of the color and intensity for each pixel in the image. The frame buffer is also referred to as a video bitmap. The Z-buffer (also referred to as a depth buffer) is a large array of memory with an entry for each pixel in the frame buffer.
One method for determining which primitives will be visible or hidden involves the use of a Z-buffer. The Z axis in a graphics system reflects the distance from a specific observer's viewpoint. Thus, a larger Z value represents a greater distance from the viewpoint. A comparison of Z values of points on the generated objects determines which object is closest to the viewpoint and therefore should appear on the two-dimensional display. As a part of processing the graphical data for a scene, pixels are generated for each of the primitives in the scene. In Z-buffer systems, as each pixel is generated, its Z coordinate (new Z-value or Znew) is compared with the Z coordinate previously stored in the Z-buffer (old Z-value or Zold). Before processing the first primitive for a scene, the Z-buffer is initialized by storing the value corresponding to a maximum distance (Zmax) in the Z-buffer entry for every pixel so that initially Zold corresponds to Zmax. In general, if Znew is less than Zold (indicating that this pixel is closer to the viewpoint than the previous viewpoint), then the pixel is written to the display device and the Z-buffer memory is updated to contain Znew. If Znew is greater than or equal to Zold, then the pixel is not written and the Z-buffer remains unchanged. All of the pixels for a primitive that is completely hidden will ultimately be overwritten in the Z-buffer during this process so that the primitive is not displayed. U.S. Pat. No. 4,951,232 entitled “Method of Updating Pipelined, Single Port Z-Buffer by Segments on a Scan Line,” provides good background material on Z-buffering.
In computer graphics, “rendering” is the process of translating a set of data into a picture that can be displayed. In the rendering process, a picture database typically holding polygon data is read, and calculations are performed by the rendering hardware, pixel by pixel, to decide the color of each pixel.
When a polygon is rendered, a color sample is obtained for each pixel that the polygon covers. If over-sampling is carried out, each pixel will have multiple corresponding color samples that are averaged to give the final color of the pixel. Each color sample has an associated Z-value and a location. The Z-buffer stores the smallest Z-value so far encountered for each location. If a color sample has a Z-value smaller than the value for that location as recorded in the Z-buffer, that sample is written into the frame buffer and the Z-buffer is updated. Otherwise, the color sample is discarded.
However, one of the disadvantages of Z-buffering is that it is expensive in terms of the amount of memory required. The size of the Z-buffer is in direct proportion to the size of the required output, i.e., a larger Z-buffer is required for a larger picture or an over-sampled picture. For example, each Z-value is typically a 4-byte value, which means that for a low-resolution 640×480 image, 1228800 bytes (≈1 MB) of memory is needed for the Z-buffer. In addition, if 16× over-sampling is employed, the size of the Z-buffer increases to approximately 16 MB which is prohibitively large. Thus, the size of the Z-buffer disadvantageously increases the cost and size of the computer graphics systems.
With the importance of providing cheaper and smaller computer graphics systems, particularly for portable computers, improvements in Z-buffer design have been long sought but have eluded those skilled in the art.
DISCLOSURE OF THE INVENTION
The present invention provides a system and method for Z-buffer compression and decompression. The memory requirements for Z-buffer are reduced with a slight loss of image quality. When coupled with over-sampling, the Z-buffer compression algorithm of the present invention significantly reduces the memory requirements for over-sampled images with negligible loss of image quality.
The present invention further provides a system and method for Z-buffer compression and decompression where, once a block of h Z-values has been accumulated in the memory, the block is compressed by an encoder. First, the minimum (MIN) and maximum (MAX) values are recorded. Next, the range between MIN and MAX is divided into a number of intervals (L). Instead of storing each of the 32-bit samples, an index k
i
is used to represent each sample. The index k
i
is calculated for i equals 1 to h, using the following equation: k
i
=(Z
i
−MIN)*L/(MAX−MIN). This equation will yield a number between 0 and the number of intervals. Next the compressed Z-values are transferred to a Z-buffer. This saves memory space for the Z-buffer because only 2 full values (MAX and MIN) have to be stored, and the remaining h indices can be stored using smaller numbers of bits because there are only a finite, small number of intervals. To decompress a value, the MAX and MIN from the block which contains that value are first obtained. The actual Z-value may then be decoded by a decoder using the equation: Z
i
=k
i
*(MAX−MIN)/L. This significantly reduces memory requirements.
The above and additional advantages of the present invention will become apparent to those skilled in the art from a reading of the following detailed description when taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 5729669 (1998-03-01), Appleton
patent: 5771046 (1998-06-01), Izawa et al.
patent: 5819017 (1998-10-01), Akeley et al.
Hung Daniel D.
Kwa Hian Tiat
Wang Samuel C.
Carr & Ferrell LLP
Reindor Alexander
S3 Graphics Co., Ltd.
Vo Cliff N.
LandOfFree
Apparatus and method for Z-buffer compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for Z-buffer compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for Z-buffer compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2969679