Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-04-16
2002-11-05
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S626000
Reexamination Certificate
active
06476806
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention relates to computer graphics display systems and, more particularly, to a method and apparatus for performing occlusion culling operations in a computer graphics display system while exploiting frame-to-frame temporal coherence.
BACKGROUND OF THE INVENTION
In three-dimensional images (3-D) computer graphics display systems, it is necessary to prevent pixels from being displayed on the display monitor if the pixels of a primitive will cause pixels that are closer to the viewer of the scene to be blocked, or occluded. In 3-D images, each pixel has a depth associated with it, normally referred to as the Z coordinate, which relates to the distance of the pixel from the screen of the display monitor. Several known techniques have been developed and implemented to ensure that pixels that are closer to the screen of the display monitor are not occluded by pixels that are further away from the screen of the display monitor.
Hidden Surface Removal (HSR) corresponds to a class of occlusion culling techniques that are used for this purpose. One well known HRS technique transforms all graphics primitives (e.g., triangles) from object coordinate space into a viewing, or screen, coordinate space. The resulting screen coordinate primitives are then “rasterized”. The process of rasterization involves scanning a “footprint” (i.e., color and depth) of each primitive into a frame buffer on a line-by-line, pixel-by-pixel basis. The primitives to be rasterized exist in 3-D space where the X and Y coordinates are aligned with the rows and columns of the screen and the Z coordinate is a depth axis that is perpendicular to the screen.
The frame buffer is comprised in the graphics hardware and is comprised of an image buffer and a depth buffer. The pixel colors are stored in the image buffer and the Z coordinates associated with the pixels are stored in the depth buffer. The depth buffer is used to sort the primitives on a pixel-by-pixel basis to determine, for each pixel, which primitive is closest the screen and, therefore, visible. Only the pixels that are visible are displayed in the final image.
One of the shortcomings of this technique is that all primitives that fall within the X and Y bounds of the screen are rasterized on a pixel-by-pixel basis, even though many of the pixels will not be contained in the final image displayed on the display monitor. Rasterizing each pixel requires a significant amount of processing time and resources. Various occlusion culling techniques have been developed to reduce the number of primitives which must be transformed and rasterized.
Another known HRS technique that is utilized for performing occlusion culling is front-to-back sorting of primitives. The success of an occlusion culling technique is a function of the number of valid occlusion results produced via the technique verses not being able to determine with certainty that a primitive being tested is occluded even though the primitive will be occluded in the final scene. If, during the occlusion check, an attempt is made to occlusion test an object whose occluder(s) have not yet been rendered, the object will appear visible in the occlusion test, even if it will be occluded in the final scene. Front-to-back sorting of primitives increases the likelihood that a potentially occluding object will be rendered before rendering an object that may be occluded by the potentially occluding object.
One of the shortcomings of this front-to-back sorting technique is that the objects must be sorted for each frame since the order of the frames may change as a function of the viewing angle or as a function of the relative position of the objects. This sorting results in substantial processing overhead in the image rendering process.
Other occlusion culling techniques involve identifying entire groups of primitives, sometimes referred to as bounding boxes or volumes, that will not appear in the final image, and excluding those groups from the rendering process. Since these primitives are “occluded” in the final image, they may be omitted from the rendering process with no impact on the resulting final image.
Variations on the typical bounding box occlusion culling technique have also been proposed. For example, techniques have been proposed which utilize a recursive hierarchy of objects in order to reduce the number of occlusion checks that must be performed. An example of an object hierarchy is a wheel, which comprises a rim, which comprises a hub, etc. If the wheel will be occluded, the rim and hub will also be occluded. If the wheel is not fully occluded, but the rim will be occluded, the hub will also be occluded.
In accordance with this technique, a bounding box is created which encloses all of the primitives in the object. The graphics hardware then performs Z depth comparison tests by comparing the Z values of the bounding box primitives against the Z values stored in the depth buffer. Software being executed by the host processor of the computer graphics display system uses the results of the Z depth comparison tests to determine whether any pixel in the frame buffer would be modified if the bounding box were rendered. If a determination is made that no pixels would be modified if the bounding box is rendered, then the object can be considered occluded and, therefore, it need not be rendered.
All of these occlusion culling techniques require the graphics pipeline to be turned around from a rendering mode to an occlusion testing mode, and vice versa, relatively often. This turn around time is expensive and is accrued on a per-object basis. Each turn around of the graphics pipeline is costly in terms of the number of states required for the turn around and, consequently, decreases processing throughput.
Accordingly, a need exists for an occlusion culling technique which reduces the overall number of pixels that must be rasterized by reducing the number of false positive visibility results, which eliminates the need for front-to-back sorting, and which minimizes the frequency with which the graphics pipeline must be switched between the rendering mode and the testing mode.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for performing occlusion testing in a computer graphics display system. The apparatus comprises logic configured to determine whether or not an object of a current image frame was occluded in a previous image frame. If a determination is made that the object was not occluded in the previous image frame, then the logic causes the object of the current image frame to be rendered to a frame buffer of the computer graphics display system.
The current and previous image frames are each comprised of a plurality of objects, and the logic determines whether or not each of the objects of the current image frame were occluded in the previous image frame. The logic causes any objects of the current image frame that it determines were not occluded in the previous image frame to be rendered to the frame buffer. Once all of the objects of the current image frame that were not occluded in the previous image frame have been rendered to the frame buffer, the logic determines whether or not any of the rendered objects of the current image frame are occluded. If the logic determines that a particular rendered object of the current image frame is not occluded, the logic determines whether or not the particular object was occluded in the previous image frame. If so, then the logic determines that a prediction error has occurred. In accordance with a first embodiment of the present invention, when the logic determines that a prediction error has occurred, it causes the particular object to be rendered to the frame buffer to correct the error.
The logic determines whether or not any objects in the current image frame are occluded by performing an occlusion test on each of the objects in the current image frame. The occlusion tests can be performed in serial fashion, one object at a time, or they may be performed on all of the objects of
Cunniff Ross
Gee Norman
Stroyan Howard D.
Hewlett--Packard Company
Vo Cliff N.
LandOfFree
Method and apparatus for performing occlusion testing while... 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 apparatus for performing occlusion testing while..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing occlusion testing while... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2994004