Method and apparatus for culling polygons

• US 6,246,415 B1
• Filed: 04/30/1998
• Issued: 06/12/2001
• Est. Priority Date: 04/30/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Voorhies, Douglas Allen, Morgan, David Lloyd, Grossman, Mark Stefan
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US09/069,971
• Time in Patent Office: 1,139 Days
• Field of Search: 345/433, 345/434, 345/435, 345/421, 345/422, 345/427
• US Class Current: 345/422
• CPC Class Codes: G06T 15/405 using Z-buffer

Abstract

A method and apparatus provide for preserving hardware resources in connection with a display of complex scenes. Polygons which make up portions of the display can be culled prior to use of the hardware resources. An occlusion parameter for use in the culling operation can be determined in accordance with a monitoring of a plurality of tiles which constitute a display. In particular, a maximum depth value associated with a given tile can be utilized to indicate whether a subsequently received polygon or primitive would otherwise be occluded and should therefore be discarded or ignored rather than rasterized.

Claims

1. A method for processing data that includes a plurality of primitives, the method comprising the steps of:

a) determining an occlusion parameter for a region of the display, said step of determining including the substeps of,

1) receiving depth data for a portion of a primitive to be mapped to said region,

2) detecting whether said portion is to be mapped to a part of said region that has been as yet uncovered,

3) if said detecting substep indicates said portion is to be mapped to an uncovered part of said region, updating an indication of the extent to which the region has been covered, and determining whether said depth data for said portion exceeds a depth data associated with said region, and if so the depth data associated with said region is updated with said depth data for said portion of said primitive, and

4) detecting whether all of said region has been covered, and if it has been covered treating said depth data for said region as a maximum depth data for said region and if the entire region has not been covered repeating steps a)

     1), a)

     2), and a)

     3);

b) receiving a subsequent primitive;

c) determining that at least part of said subsequent primitive is to be mapped to said region;

d) determining whether to display said at least part of said subsequent primitive based on said maximum depth data for said region.

2. In a system for culling primitives from being rasterized, a method for determining an occlusion parameter for use in the culling operation, the method including the steps of:

a) initializing a buffer associated with a rasterizing region that includes a plurality of display units;

b) initializing a count associated with said rasterizing region;

c) receiving a primitive;

d) determining those display units of said rasterizing region associated with said primitive;

e) detecting whether all of said display units associated with said primitive have been mapped to by an earlier received primitive and if not,

updating said count to account for the number of display units mapped to by said primitive which had previously been unmapped, and

updating said buffer if a depth value from said primitive exceeds a depth value for said rasterizing region previously stored in said buffer;

f) repeating steps c), d) and e) until said count reaches a predetermined threshold wherein said buffer entry at the time said counter reaches said predetermined threshold constitutes the occlusion parameter.

3. The method of claim 2 comprising the further steps of:

when said count reaches said predetermined threshold,

g) receiving another primitive;

h) determining those display units of said region associated with said another primitive; and

i) discarding a portion of said another primitive associated with said region if a depth value associated with said portion of said another primitive of said depth value exceeds said occlusion parameter.

4. The method of claim 3 comprising the further steps of:

k) initializing a second buffer associated with said rasterizing region;

l) re-initializing said count;

m) detecting whether all of said display units associated with said another primitive have been mapped to by a primitive received earlier in an update process and, if not,

updating said count to account for the number of display units mapped to by said another primitive which had previously been unmapped, and

updating said second buffer if a depth value for said another primitive exceeds a depth value for said rasterizing region previously stored in said second buffer; and

n) repeating steps g), h) and m) until said count reaches a predetermined threshold wherein said second buffer entry at the time said count again reaches said predetermined threshold constitutes an updated occlusion parameter if said second buffer entry does not exceed the occlusion parameter.

5. The method of claim 3 wherein said display unit comprises a pixel.

6. The method of claim 3 wherein said display unit comprises a multi-sample of a pixel.

7. The method of claim 2 wherein said display unit comprises a pixel.

8. The method of claim 2 wherein said display unit comprises a multi-sample of a pixel.

9. The method of claim 4 wherein said count includes an indicator that identifies which of said first and said second buffer is to be used for determining whether to discard a primitive.

10. The method of claim 9 wherein said indicator comprises a bit that toggles whenever the count reaches the predetermined threshold.

11. A system for processing display data comprising:

a display data subdivider,

an occlusion parameter memory;

a depth comparator coupled to said display data subdivider and said occlusion parameter memory; and

an occlusion parameter updater coupled to said occlusion parameter memory.

12. The system of claim 11 further comprising:

a rasterizer coupled to said depth comparator, wherein said rasterizer writes to a display on a region by region basis.

13. A system for processing display data comprising:

a display data subdivider;

an occlusion parameter memory;

a depth comparator coupled to said display data subdivider and said occlusion parameter memory;

a rasterizer coupled to said depth comparator, wherein said rasterizer writes to a display on a region by region basis; and

wherein said occlusion parameter memory includes a plurality of addressable spaces, wherein each region of a display has an addressable space in said memory associated therewith.

14. The system of claim 13 further comprising an occlusion parameter updater coupled to said occlusion parameter memory.

15. A system for displaying data on a display, comprising:

a plurality of rastrizesrs, each rasterizer corresponding to a plurality of regions of the display; and

a plurality of display data depth analyzers, each analyzer including,

a display data subdivider,

an occlusion parameter memory,

a depth comparator coupled to said display data subdivider, said occlusion

parameter memory and one of said plurality of rasterizers, and

an occlusion parmeter updater coupled to said occlusion parameter memory.