Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1997-07-16
2001-04-24
Cuchlinski, Jr., William A. (Department: 3661)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S501000
Reexamination Certificate
active
06222552
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to computer systems, and more particularly to the display of images via computer systems.
BACKGROUND OF THE INVENTION
Three-dimensional (3D) objects are commonly represented in computer graphics applications as an approximation of their surface via a sufficiently large number of polygons, such as triangles. Graphical output devices for displaying computer graphics are typically raster devices having a display area or screen comprised of a set of discrete picture elements referred to as pixels as illustrated in FIG.
1
. Each pixel on the screen is associated with one entry in a display buffer (also referred to as a “frame buffer”) which stores a value for the color of each pixel. The frame buffer is then loaded with image information and that information is displayed by the pixels of the display.
The approximation of a cylindrical surface using multiple triangles may be used to illustrate the use of polygons to approximate an object. The steps for approximating the surface of a cylindric object via multiple triangles (also referred to as “primitives”) are illustrated in FIG.
2
. For display purposes, each triangle is typically decomposed into a set of screen pixels, a process called “rasterization”. Rasterization is usually implemented via a specific rasterizer chip.
Referring now to
FIG. 3
, a conventional layout of graphics system hardware is schematically illustrated. As seen in
FIG. 3
, an application program
1
may display a 3D graphic object (image) on a conventional two-dimensional (2D) display
2
. Typically, the 3D data is stored in a database
3
. A processing unit (CPU)
4
may control the 3D data input to the database
3
and a geometric graphics unit
5
which is responsible for geometric object transformations like scaling, moving or rotating the objects. The CPU
4
may also control a rasterizer
7
for decomposing each primitive into pixels. A pixel driver
8
, which is also connected to the CPU
4
, controls the display
2
for 2D presentation of 3D graphics.
In converting from a 3D representation of an image to a 2D representation, the visible parts of an object can be determined by computing for each pixel a measure of the distance to the observer, called Depth Value or “Z-Value”, and by comparing that Z-Value to the Z-Value of the pixel previously generated for a particular screen address. Routines for handling visible surface determination within 3D graphics display systems are known. The most common of these routines relate to pre-sorting of objects/polygons according to depth before rasterization, or relate to depth buffering.
A depth sort routine, developed by Newell and Sancha (Newel, M. E., R. G. Newell, and T. L Sancha, “A solution to the Hidden Surface Problem”, in Proceedings of the ACM National Conference 1972, 433-450), paints polygons into a frame buffer in order of decreasing distance from the viewpoint. Three conceptual steps are performed: 1) sorting all polygons according to the smallest (farthest) Z coordinate of each; 2) resolving any ambiguities resulting when Z coordinates of polygons overlap, and splitting polygons if necessary; and 3) scan-converting each polygon in ascending order of smallest Z coordinate, (i.e. from back to front).
For CPU performance reasons, pre-sorting of polygons is used typically for smaller scenes having a relatively small number of objects. Other routines may be used for applications dealing with more complex 3D) scenes. As used herein, the term “scene” is synonymous with the terms “graphics” and “images”.
The depth-buffer routine, developed by E. Catmull, and disclosed in an article entitled “A Subdivision Algorithm for Computer Display of Curved Surfaces” (published in Ph.D. Thesis, Computer Science Department, University of Utah, December 1974), is commonly implemented in 3D display system. This routine requires a frame buffer in which color values are stored, and a Z-Buffer, with the same number of entries, in which a Z-Value (depth value) is stored for each pixel of a scene, as illustrated in FIG.
5
A. The Z-Buffer is initialized to zero, representing the Z-Value at the back clipping plane. The frame buffer is initialized to the background color. The largest value that can be stored in the Z-Buffer represents the Z-Value (or depth) of the front clipping plane. The advantage of this routine is that polygons which belong to any object can be rendered in arbitrary order independent of their depth. However, depth buffer routines may require large amounts of memory, which is less of a significant disadvantage as semiconductor memory increases in density which decreases cost.
In a depth-buffer routine, during the scan conversion process, if the polygon point being scan-converted at (X, Y) is no farther from the viewer than is the point whose color and depth are currently in the frame buffer and the Z-Buffer, respectively, then the color and depth of the new points replace the old values, as illustrated in FIG.
5
B. Prior art implementations of depth buffer routines typically have a dedicated Z-Buffer integrated in dynamic random access memory (DRAM). The rasterizer typically requires at least one access to the Z-Buffer and one comparison of the old and new depth values. Around 50% of the pixels typically require write access to the external Z-Buffer. The operations and accesses typically are done at pixel frequency. Limiting factors for a Z-Buffer routine include: the access time to the dedicated DRAM Z-Buffer; overall bandwidth requirements during Z-Buffer access; and cost of on-board space for the dedicated Z-Buffer memory.
In U.S. Pat. No. 4,475,104 a method of generating a two-dimensional image representing a three-dimensional image or scene in the form of an array of pixels utilizes “depth buffer” or “Z-Buffer” hidden surface removal (HSR) is provided. The hidden surface removal occurs at the time of scan conversion and attempts to ensure that the image of an object in the scene, which has already been converted, is not overwritten by input pixel data which arrives later, but in fact, corresponds to an object behind the one already stored. In the depth-buffer routine, the stored foreground color is overwritten if the input depth is less than the stored foreground depth. The input depth is then stored as a new foreground depth.
The depth-buffer routine is described more generally in “Principles of Interactive Computer Graphics”, page 369, by W. M. Newman and R. F. Sproull. As described by Newman and Sproull, the routine does not require knowledge of any object other than that being scan-converted at the time.
Referring now to
FIG. 4
, a conventional three-dimensional graphic display apparatus is schematically illustrated. A line generator generates X-, Y-, and Z-coordinate data in a three-dimensional coordinate system. The output of the line generator is fed into a depth-buffer memory
10
which stores coordinate data representing the depth of each pixel in order to execute a hidden-surface process of a graphic image on the basis of the X-, Y-, and Z-data supplied from the line generator. X- and Y-coordinate data from the line generator and the Z-coordinate data from the depth-buffer memory
10
are input into a frame buffer memory
11
. The frame buffer memory
11
stores display information used to display an image on the basis of the data feed from the line generator and the depth-buffer memory
10
. The output of the frame buffer memory
11
is delivered to a cathode ray tube (CRT)
12
which displays the three-dimensional scene.
Since the depth-buffer routine needs a depth-buffer memory with a large capacity of storage, a DRAM is usually used because of its relatively low cost. Unfortunately, DRAMs typically have a slow access speed. In a hidden-surface process, a depth-buffer memory operates to read out depth information (Z-coordinate data), to compare this information, and to update this depth information. Consequently, the depth-buffer memory is required to execute a READ-WRITE cycle, which often results in slow operating speeds as compa
Haas Jurgen
Narayanaswami Chandra
Schneider Bengt-Olaf
Cuchlinski Jr. William A.
Duffield Edward H.
International Business Machines - Corporation
Myers Bigel Sibley & Sajovec P.A.
Nguyen Thu
LandOfFree
Systems and methods for caching depth information 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 Systems and methods for caching depth information of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for caching depth information of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2539723