Method and apparatus for adaptive hierarchical visibility in a tiled three-dimensional graphics architecture

• US 6,525,726 B1
• Filed: 11/02/1999
• Issued: 02/25/2003
• Est. Priority Date: 11/02/1999
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Intel Corporation
• Inventors: Xie, Feng, Shantz, Michael J.
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Santiago, Enrique L.
• Application Number:
  US09/432,134
• Time in Patent Office: 1,211 Days
• Field of Search: 345/421, 345/422
• US Class Current: 345/421
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

A data processing system providing high performance three-dimensional graphics includes at least one system processor, chipset core logic, a graphics processor, and a Z-buffer. In one embodiment an adaptive hierarchical visibility (AHV) method performs occlusion-culling in a tiled 3D graphics hardware architecture. Polygon bins for each tile are bucket-sorted in order of increasing depth Z. Polygon bins are rendered starting with the bin closest to the viewer. After some number of bins are rendered, a single layer, hierarchical Z-buffer (HZ) may be constructed from the Z-buffer thus far accumulated for the rendered bins, if it would be cost effective to do so. Subsequent bins are rendered by first testing their polygons against the HZ buffer to see if they are hidden. Also described are an integrated circuit for implementing the AHV algorithm, and a computer-readable medium storing a data structure for implementing the AHV method and apparatus.

Claims

1. A method for use in a processor to be used in a data processing system comprising a frame buffer and a Z-buffer, the method operating to cull occluded polygons from a scene being assembled in the frame buffer and comprising:

rendering polygons in the scene in depth order, starting with a closest polygon, and storing them in the Z-buffer;

as polygons are rendered, evaluating whether a coverage parameter has been satisfied and if so, constructing a hierarchical Z-buffer from the Z-buffer; and

comparing subsequent polygons to the hierarchical Z-buffer to determine whether they are occluded and if so, culling them;

wherein the coverage parameter is proportional to an estimated cost of constructing and using the hierarchical Z-buffer less an estimated cost of rendering an expected number of occluded polygons.

2. The method of claim 1, wherein the coverage parameter represents the maximum value of the fraction of polygons rendered during a previous frame.

3. The method of claim 1, wherein the scene is partitioned into tiles, and wherein the coverage parameter represents an optimal fraction of the polygons that have been rendered (Fmax) for a tile and a frame based on an analysis of a previous frame.

4. The method of claim 3, wherein Fmax is the fraction of polygons that had been rendered (FOPR) during the previous frame for the tile when the following coverage expression reached its maximum:

Pixels_remaining*(Coverage−

HZ_Test_Cost),

where Pixels_remaining=the sum of all polygon areas still to process,

Coverage=the number of fresh Z-buffer writes, and

HZ_Test_Cost=Cppt*AverageTriangleArea,

where Cppt is the desired cost per pixel of hierarchical Z-buffer testing, represented as a fraction of the total cost of rendering a pixel with just a Z-buffer, and

AverageTriangleArea=the average triangle area.

5. The method of claim 1, wherein the hierarchical Z-buffer is not constructed unless the cost of constructing and using the hierarchical Z-buffer is less than the cost of rendering an expected number of occluded polygons.

6. The method of claim 1, wherein the operations are performed in a different order.

7. A method for use in a data processing system comprising a processor, a Z-buffer, a frame buffer, and a display screen, the method operating to cull occluded polygons from a scene being assembled in the frame buffer for display on the display screen and comprising:

sorting polygons in the scene by tile and by depth;

rendering the tiles sequentially and storing them as pixels in the frame buffer while performing the following operations for each tile;

rendering polygons in depth order, starting with a closest polygon, and storing them in the Z-buffer;

as polygons are rendered, evaluating whether a coverage parameter has been satisfied and, if so, constructing a hierarchical Z-buffer from the Z-buffer, but if not, rendering them;

comparing subsequent polygons to the hierarchical Z-buffer to determine whether they are occluded and if so, culling them, but if not, rendering them; and

using the contents of the frame buffer to display the scene on the display screen;

wherein the coverage parameter is proportional to an estimated cost of constructing and using the hierarchical Z-buffer less an estimated cost of rendering an expected number of occluded polygons.

8. The method of claim 7, wherein the hierarchical Z-buffer is a single layer.

9. The method of claim 8, wherein the coverage parameter represents an optimal fraction of the polygons that have been rendered (Fmax) for a tile and a frame based on an analysis of a previous frame.

10. The method of claim 9, wherein Fmax is the fraction of polygons that had been rendered (FOPR) during the previous frame for the tile when the following coverage expression reached its maximum:

Pixels_remaining*(Coverage−

HZ_Test_Cost),

where Pixels_remaining=the sum of all polygon areas still to process,

Coverage=the number of fresh Z-buffer writes, and

HZ_Test_Cost 32 Cppt*AverageTriangleArea,

where Cppt is the desired cost per pixel of hierarchical Z-buffer testing, represented as a fraction of the total cost of rendering a pixel with just a Z-buffer, and

AverageTriangleArea=the average triangle area.

11. The method of claim 7, wherein the operations are performed in a different order.

12. A processor to execute a computer program comprising the operations of:

rendering polygons in a scene in depth order, starting with a closest polygon, and storing them in a Z-buffer;

as polygons are rendered, evaluating whether a coverage parameter has been satisfied and if so, constructing a hierarchical Z-buffer from the Z-buffer; and

comparing subsequent polygons to the hierarchical Z-buffer to determine whether they are occluded and if so, culling them;

wherein the coverage parameter is proportional to an estimated cost of constructing and using the hierarchical Z-buffer less an estimated cost of rendering an expected number of occluded polygons.

13. The processor of claim 12, wherein the scene is partitioned into tiles and the scene is assembled as a frame in a frame buffer coupled to the processor, and wherein the coverage parameter represents an optimal fraction of the polygons that have been rendered (Fmax) for a tile and a frame based on an analysis of a previous frame.

14. The processor of claim 13, wherein Fmax is the fraction of polygons that had been rendered (FOPR) during the previous frame for this tile when the following coverage expression reached its maximum:

Pixels_remaining*(Coverage−

HZ_Test_Cost),

where Pixels_remaining=the sum of all polygon areas still to process,

Coverage=the number of fresh Z-buffer writes, and

HZ_Test_Cost=Cppt*AverageTriangleArea,

where Cppt is the desired cost per pixel of hierarchical Z-buffer testing, represented as a fraction of the total cost of rendering a pixel with just a Z-buffer, and AverageTriangleArea=the average triangle area.

15. The processor of claim 12, wherein the hierarchical Z-buffer is not constructed unless the cost of constructing and using the hierarchical Z-buffer is less than the cost of rendering an expected number of occluded polygons.

18. The system of claim 12, wherein the coverage parameter represents the maximum value of the fraction of polygons rendered (FOPR) during a previous frame.

19. The system of claim 12, wherein the coverage parameter represents an optimal fraction of the polygons that have been rendered (Fmax) for a tile and a frame based on an analysis of a previous frame.

20. The system of claim 19, wherein Fmax is the fraction of polygons that had been rendered (FOPR) during the previous frame for the tile when the following coverage expression reached its maximum:

Pixels_remaining*(Coverage−

HZ_Test_Cost),

where Pixels_remaining=the sum of all polygon areas still to process,

Coverage=the number of fresh Z-buffer writes, and

HZ_Test_Cost=Cppt*AverageTriangleArea,

where Cppt is the desired cost per pixel of hierarchical Z-buffer testing, represented as a fraction of the total cost of rendering a pixel with just a Z-buffer, and

AverageTriangleArea=the average triangle area.

21. The system of claim 20, wherein the operations are performed in a different order.

16. An integrated circuit for use in a system rendering a scene on a display screen, the scene comprising a plurality of polygons of varying depth, the integrated circuit comprising at least one processor to execute a computer program culling occluded polygons from the scene and comprising the operations of:

rendering polygons in the scene in depth order, starting with a closest polygon, and storing them in a Z-buffer;

as polygons are rendered, evaluating whether a coverage parameter has been satisfied and if so, constructing a hierarchical Z-buffer from the Z-buffer; and

comparing subsequent polygons to the hierarchical Z-buffer to determine whether they are hidden and if so, culling them;

wherein the coverage parameter is proportional to an estimated cost of constructing and using the hierarchical Z-buffer less an estimated cost of rendering an expected number of occluded polygons.

17. A data processing system to execute a computer program comprising the operations of:

sorting polygons in a scene by tile and by depth;

rendering the tiles sequentially and storing them as pixels in a frame buffer while performing the following operations for each tile;

rendering polygons in depth order, starting with a closest polygon, and storing them in a Z-buffer;

as polygons are rendered, evaluating whether a coverage parameter has been satisfied and, if so, constructing a hierarchical Z-buffer from the Z-buffer, but if not, rendering them;

comparing subsequent polygons to the hierarchical Z-buffer to determine whether they are occluded and if so, culling them, but if not, rendering them; and

using the contents of the frame buffer to display the scene on a display screen;

wherein the coverage parameter is proportional to an estimated cost of constructing and using the hierarchical Z-buffer less an estimated cost of rendering an expected number of occluded polygons.

22. A computer-readable medium containing computer instructions to instruct a processor to perform a method of culling polygons from a scene being rendered for display, the instructions comprising:

rendering polygons in the scene in depth order, starting with a closest polygon;

storing the rendered polygons;

as polygons are rendered, evaluating whether a coverage parameter has been satisfied and if so, constructing a hierarchical Z-buffer from the stored polygons; and

comparing subsequent polygons to the hierarchical Z-buffer to determine whether they are occluded and if so, culling them;

wherein the coverage parameter is proportional to an estimated cost of constructing and using the hierarchical Z-buffer less an estimated cost of rendering an expected number of occluded polygons.

23. A computer-readable medium having computer-executable instructions culling occluded polygons from a scene comprising:

rendering polygons in the scene in depth order, starting with a closest polygon;

storing the rendered polygons in a Z-buffer;

as polygons are rendered, evaluating whether a coverage parameter has been satisfied and if so, constructing a hierarchical Z-buffer from the Z-buffer; and

comparing subsequent polygons to the hierarchical Z-buffer to determine whether they are occluded and if so, culling them;

wherein the coverage parameter is proportional to an estimated cost of constructing and using the hierarchical Z-buffer less an estimated cost of rendering an expected number of occluded polygons.

24. A computer-readable medium having stored thereon a data structure comprising:

a first block of data regarding a plurality of polygons from a tiled scene which have been sorted by tile and by depth;

a second block of data regarding polygons which have been rendered in depth order starting with a polygon closest to a viewer of the scene;

a third block of data comprising coverage data and a coverage parameter pertaining to the rendered polygons, wherein the coverage parameter is proportional to an estimated cost of constructing and using a hierarchical Z-buffer to determine whether polygons are occluded less an estimated cost of rendering an expected number of occluded polygons; and

a fourth block of data representing the hierarchical Z-buffer, the fourth block of data being constructed only if the coverage parameter reaches a threshold value.