Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-04-30
2001-06-12
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S421000, C345S427000, C345S440000, C345S440000
Reexamination Certificate
active
06246415
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is directed to a method and apparatus for reducing the load on hardware in a display system. More particularly, the present invention is directed to a method and apparatus for culling polygons from display data prior to rasterization of the display data.
Computer graphics processing devices have become more and more powerful with the result being that more and more complex graphics capabilities are being provided to enable the display of more and more complex visual data.
These complex graphical devices generate displays on a frame by frame basis. Each frame includes display data information for the picture elements or pixels of the display. In known systems graphics display data is provided as a plurality of polygons (often triangles) of display information dispersed across the pixels of the display. For instance, a picture of a house which might be shown on a display, such as shown in
FIG. 1
, would be constituted by thousands of tiny polygons having certain textural characteristics. The polygons are positioned on the display in accordance with the pixels to which they correspond. For example,
FIG. 6
of the present application shows a block diagram of a high level representation of a number of elements utilized in displaying an image constituted by a plurality of these tiny polygons. In particular, a geometry engine
601
provides the polygon information along with space coordinate information for each of the polygons. A rasterizer
602
takes the polygon information and the space coordinate information and processes it so as to drive the display to appropriately place the polygon to cover picture elements on the display in the correct locations. Those skilled in the art should appreciate the fact that a rasterizer can be constituted by a number of rasterizer subsystems each responsible for rasterizing different portions of the display. The use of the term rasterizer throughout this specification is to intended to cover the single or multiple rasterizer component systems.
As graphics processing devices have become faster and faster, the amount of information which can be displayed over the course of a frame has grown dramatically. More and more polygons of visual data can be processed and rasterized. For example, regarding the picture of the house shown in FIG. I the display system could provide not only a display of the exterior of the house, but could also write the polygon information for the interior portions of the house or even for the area behind the house during the processing of a frame of information. The closer parts of the view of the image occlude, however, the back portions of the image, that is the exterior walls closer in view occlude the interior portions of the illustrated house. Displaying an image in this manner wastes hardware resources as the graphics machine expends computational power on display fragments that will not be seen. It would be beneficial if graphics devices could detect certain occlusion parameters with respect to a frame of information and utilize those occlusion parameters to reduce the waste of hardware resources. It would be especially beneficial if a small number of parameters could be used to avoid accessing the visibility information, such as depth values, that may be stored in conjunction with each picture element.
SUMMARY OF THE INVENTION
The present invention provides an improvement to graphics processing systems by defining and taking advantage of occlusion parameters. In an embodiment of the present invention a display is constituted by a plurality of display regions. Each region has associated therewith a maximum depth value. When visual data regarding a scene to be displayed, for instance a primitive which can be a polygonal portion of the display data, is received and is associated with a given area of the display, its depth value is detected and compared against the maximum depth value of the display region. If it is determined that the newly received polygon is deeper than the maximum depth value of the region, that is, behind previous rasterized primitives for each and every portion of the region of the display in interest, then that particular polygon is culled out of the stream of polygons. Thus, at a minimum, depending on where the culling operation is performed this operation of the present invention reduces a waste of the resources of the rasterizing portion of the device. In essence, information that will not contribute to the display is simply ignored or discarded. If the culling is done earlier in the processing operation other hardware resources could be conserved as well.
The present invention also provides a method and apparatus for determining values for controlling the culling process. In particular, the present invention provides a method and apparatus by which the display is divided into a plurality of display regions such as tiles which can be made up of a block of pixels. In fact, each pixel could be represented by multiple samples. As primitives or polygons representative of display information are received into the system, the polygon's display location is determined. In so doing the system identifies those tiles or regions upon which the polygon may have some effect. A maximum depth value for the polygon in the region is detected. This depth value is obtained by examining the depth values of any newly visible fragments in the region and noting the maximum. This depth value is compared to a maximum culling value for the tile as indicated by polygons that have previously written on or covered other portions of the tile. If this regional maximum depth value of the received primitive or polygon exceeds the maximum depth value then attributed to the tile, then the most recently received primitive's depth value is substituted for the maximum depth value. This operation is continued for a given tile until all of the pixels (or multi-samples) of that region have been covered by polygons in the process of displaying a particular frame of information. The maximum depth value of a given tile at the time that all of the pixels (or multi-samples) of the tile have been written on or covered is considered the culling or occlusion parameter in connection with subsequent primitives that are related to this tile. The occlusion parameter is then active and serves as a comparison value for any subsequently received primitives for that tile in the remainder of that frame of information. If the depth value of a subsequently received polygon is greater than the maximum depth value associated with the tile in the active occlusion parameter then that primitive or polygon is culled out and is not rasterized as in the first described aspect of the present invention.
In accordance with another aspect of the present invention, while an active occlusion parameter buffer operates in conjunction with a culling algorithm to cull or discard invisible fragments of the display represented by polygons that are “too deep into the display”, those primitives which are not discarded, but which are sent on to be rasterized, may be used to update the occlusion parameter. This updated value, which would be even closer, that is, have a smaller maximum depth, for a given tile could further reduce the number of polygons which are processed.
In a disclosed embodiment of the present invention the culling operation is performed in connection with a pre-rasterizer. The pre-rasterizer can be located at the input portion of the rasterizer, at the output portion of a geometry engine, or it can be a stand-alone piece of equipment coupled somewhere between the geometry engine and the rasterizer. The pre-rasterizer thereby operates to cull (i.e., reject from) a stream of polygons only those which have no chance of making a contribution to a given graphical image.
It is further possible in accordance with the present invention to pre-sort the polygons in an effort to further enhance the benefits of the culling operation. The polygons could be pre-sorted based on their respective depth values suc
Grossman Mark Stefan
Morgan David Lloyd
Voorhies Douglas Allen
Nguyen Kimbinh T.
Silicon Graphics Inc.
Stearne, Kessler, Goldstein & Fox, p.l.l.c.
Zimmerman Mark
LandOfFree
Method and apparatus for culling polygons 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 culling polygons, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for culling polygons will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2498837