Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-07-10
2004-04-27
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S422000
Reexamination Certificate
active
06727899
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to graphical display systems and, in particular, to a system and method for occlusion culling graphical data based on frame-to-frame temporal coherence.
2. Related Art
A three-dimensional (3-D) graphical display system typically renders three-dimensional images to a two-dimensional display screen, which displays the three-dimensional images to a user. The display screen is divided into discrete picture elements (“pixels”), and each pixel is colored a particular color based on the data rendered by the graphical display system.
In this regard, an application program, sometimes referred to as a “graphics application,” normally includes graphical data defining a frame of a graphical image. This frame often includes multiple three-dimensional objects that are each defined by different sets of graphical data, referred to as primitives. To display the image frame, the graphical data (i.e., the primitives) defining the objects of the frame are transmitted to a graphics pipeline that renders the graphical data via well known techniques. More specifically, the graphics pipeline determines how each pixel of the display screen should be colored in order for the display screen to display the image frame defined by the graphical data. The color value of each pixel is stored in a frame buffer, and the display screen is designed to read the frame buffer, typically via a rasterization process, and to color each pixel its corresponding color value from the frame buffer. Once each pixel has been colored its corresponding color value from the frame buffer, the display screen should be displaying a two-dimensional representation of the three-dimensional objects defined by the graphical data transmitted to the graphics pipeline.
The graphical data of each object includes position values that define the object's position relative to the other objects of the frame. The graphics pipeline translates these position values into (X, Y, Z) coordinate values that represent the object's position on the display screen. The X and Y coordinate values are aligned with the rows and columns of the display screen, and the Z coordinate value represents the object's depth (i.e., the object's distance along the axis that is perpendicular to the display screen).
Since objects can be positioned at different depths, it is possible for a first object to wholly or partially occlude a second object. This occurs when the first object and the second object have at least one set of coordinates with the same respective X and Y values but different Z values. In such a case, the first object, when displayed on the display screen, should appear to be in front of the second object. Therefore, the pixel having the foregoing X and Y values should normally be colored the appropriate color of the first object (i.e., the front object) instead of the color of the second object (i.e., the back object), assuming that the front object is not occluded by another object. As used hereafter, any object of an image frame having at least one non-occluded primitive shall be referred to as “visible.”
Since only visible objects are displayed by the display screen, the rendering of non-visible or occluded objects often decreases the efficiency of the graphical display system. Thus, many conventional graphical systems perform occlusion culling to limit the rendering of occluded objects. There are many different types of occlusion culling techniques, but in general, occlusion culling involves the steps of determining whether a current object is occluded by a previously rendered object and then preventing further processing of the current object, if the current object is occluded.
Occlusion culling can be performed by the graphics application that transmits the objects to the graphics pipeline. In such an embodiment, the application, before transmitting the current object to a graphics pipeline, occlusion tests the current object against the graphical data defining objects previously transmitted to the graphics pipeline for the same image frame. Alternatively, occlusion culling can be performed by the graphics pipeline. In such an embodiment, the graphics pipeline occlusion tests the current object shortly after receiving it from the application and before substantial rendering of the current object has been performed by the pipeline.
Bounding box techniques may be utilized to increase the efficiency of the occlusion tests. In this regard, before the current object is rendered, an object, referred to as a “bounding box,” is defined that encompasses each primitive of the current object. The bounding box may be defined by only a few primitives while the current object may be defined by many thousands of primitives. The bounding box is then occlusion tested against the previously rendered objects. If the bounding box is determined to be occluded by the occlusion test, then the current object is assumed to be occluded and rendering of the current object is prevented. However, if the bounding box is determined to be visible by the occlusion test, then the current object is assumed to be visible and is, therefore, rendered. Bounding box techniques make occlusion testing much more efficient by decreasing the number of primitives manipulated during an occlusion test.
A shortcoming of many existing occlusion culling techniques is that an occluded object may be occlusion tested before the occluder (i.e., the object that blocks or occludes the occluded object) is rendered. In such a case, the occluded object is normally determined to be visible by the occlusion test. Thus, the occluded object is typically rendered to the frame buffer and then replaced by the occluder once the occluder is rendered. In general, the processing time spent processing or rendering the occluded object is wasted, thereby decreasing the efficiency of the graphics display system.
To help minimize the impact of the foregoing shortcoming, some occlusion culling techniques sort objects from front to back (i.e., sort the objects based on their Z value) before performing occlusion culling. The objects that are closer to the screen and, therefore, more likely to be occluders are rendered first so that any occluded object is likely to be occlusion tested after the front objects have been rendered. However, front-to-back sorting for each frame increases the overall processing time of the graphical display system. Other techniques exist for occlusion culling, but these other techniques typically suffer from similar limitations.
SUMMARY OF THE INVENTION
Thus, a heretofore unaddressed need exists in the industry for providing a more efficient occlusion culling system and method. Generally, the present invention provides a system and method for efficiently occlusion culling graphical data based on frame-to-frame temporal coherence.
In architecture, the system of the present invention utilizes a frame buffer and rendering logic. The rendering logic is configured to receive graphical objects that define an image frame. In response to receiving one of the objects, the rendering logic is configured to make a determination as to whether the one object is visible in a previous image frame that was previously rendered to the frame buffer. The rendering logic is further configured to render the one object to the frame buffer based on the determination.
The present invention can also be viewed as providing a graphical display method. The method can be broadly conceptualized by the following steps: receiving a graphical object of an image frame; determining, in response to the receiving step, whether the object is visible in a previously rendered image frame that is being displayed by a display device; rendering the object to a frame buffer based on the determining step; and displaying, via the display device, an image based on data stored in the frame buffer.
REFERENCES:
patent: 5751291 (1998-05-01), Olsen et al.
patent: 5757321 (1998-05-01), Billyard
patent: 6088035 (2000-07-01), Sudarsky et al.
Cunniff Ross
Gee Joseph Norman
Hoffman Don B.
Stroyan Howard D
Hewlett--Packard Development Company, L.P.
Vo Cliff N.
LandOfFree
System and method for occlusion culling graphical data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for occlusion culling graphical data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for occlusion culling graphical data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3221356