Method and apparatus for culling in a graphics processor with deferred shading

• US 6,664,959 B2
• Filed: 08/29/2002
• Issued: 12/16/2003
• Est. Priority Date: 08/20/1998
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Duluk, Jerome F. Jr., Fang, Emerson S., Redgrave, Jason R., Dodgen, Stephen L., Hessel, Richard E., Hsu, Hengwei, Trivedi, Sushma S.
• Primary Examiner(s): Bella, Matthew C.
• Assistant Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US10/231,436
• Publication Number:
  US 20020196251A1
• Time in Patent Office: 474 Days
• Field of Search: 345/421, 345/422, 345/612, 345/423, 345/589, 345/426
• US Class Current: 345/422
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 15/30 Clipping
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 15/50 Lighting effects
• CPC Class Codes: G06T 15/80 Shading
• CPC Class Codes: G06T 15/83 Phong shading
• CPC Class Codes: G06T 15/87 Gouraud shading

Abstract

Structure, apparatus, and method for performing conservative hidden surface removal in a graphics processor. Culling is divided into two steps, a magnitude comparison content addressable memory cull operation (MCCAM Cull), and a subpixel cull operation. The MCCAM Cull discards primitives that are hidden completely by previously processed geometry. The Subpixel Cull takes the remaining primitives (which are partly or entirely visible), and determines the visible fragments. In one embodiment the method of performing hidden surface removal includes: selecting a current primitive comprising a plurality of stamps; comparing stamps to stamps from previously evaluated primitives; selecting a first stamp as a currently potentially visible stamp (CPVS) based on a relationship of depth states of samples in the first stamp with depth states of samples of previously evaluated stamps; comparing the CPVS to a second stamp; discarding the second stamp when no part of the second stamp would affect a final graphics display image based on the stamps that have been evaluated; discarding the CPVS and making the second stamp the CPVS, when the second stamp hides the CPVS; dispatching the CPVS and making the second stamp the CPVS when both the second stamp and the CPVS are at least partially visible in the final graphics display image; and dispatching the second stamp and the CPVS when the visibility of the second stamp and the CPVS depends on parameters evaluated later in the computer graphics pipeline.

Claims

1. A method for culling in a graphics rendering pipeline configured to render three-dimensional (3-D) graphics information onto a two-dimensional (2-D) screen. said graphics information comprising a plurality of graphics primitives, said method comprising:

sorting said graphics primitives into tiles, wherein said 2-dimensional screen is represented by said tiles; and

wherein said culling is performed such that all graphics primitives sorted to a first tile are processed before graphics primitives sorted to a second tile;

identifying a first group of primitives wherein each primitive overlaps a pixel of said 2-D screen;

culling portions of said first group of primitives that do not affect a final color of said pixel, wherein said graphics primitives comprise vertices and a time order of said vertices is preserved within each tile during said culling thereby generating a potentially visible group of graphics information; and

dispatching said potentially visible group of graphics information to a pixel unit.

2. A method according to claim 1, wherein said method further comprises:

performing a stencil test or alpha test on graphics information within said potentially visible group, and not performing stencil or alpha tests on culled portions of said first group.

3. A method according to claim 1, wherein said culling is based on depth and transparency data.

4. A method according to claim 1, wherein said culling comprises:

for each primitive in said first group of primitives, determining if said primitive is completely hidden within said 2-D screen, and

(i) if said primitive is completely hidden within said 2-D screen, discarding data associated with said primitive; and

(ii) if said primitive is not completely hidden within said 2-D screen, generating a visible stamp list, each stamp containing a portion of said primitive that may be visible.

5. A method according to claim 4, wherein said determining is based at least in part on said primitive'"'"'s bounding box.

6. A method according to claim 5, wherein said determining comprises querying a Magnitude Comparison Content Addressable Memory (MCCAM) with said bounding box.

7. A meted according to claim 4, wherein said generating a visible stamp list comprises calculating a left-most position and a right-most position of said primitive within each subraster line that contains at least one sample point.

8. A method according to claim 4, wherein said generating a visible stamp list comprises computing a z-value of said primitive at each sample point covered and comparing said calculated z-value with a current z-value associated with said sample point.

9. A method according to claim 1, wherein said potentially visible group of graphics information comprises a number of portions of said first group of primitives, and wherein said number is greater than two.

10. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer mechanism, comprising:

a program module that directs the culling of graphics information comprising a plurality of graphics primitives, the program module including instructions for;

sorting said graphics primitives into tiles, wherein said 2-dimensional screen is represented by said tiles; and

wherein said culling is performed such that all graphics primitives sorted to a first tile are processed before graphics primitives sorted to a second tile;

identifying a first group of primitives wherein each primitive overlaps a pixel of a two-dimensional display screen region;

culling portions of said first group of primitives that do not affect a final color of said pixel, thereby generating a potentially visible group of graphics information wherein said graphics primitives comprise vertices and a time order of said vertices is preserved within each tile during said culling; and

dispatching said potentially visible group of graphics information to a pixel unit.

11. A computer program product according to claim 10, wherein said program module further Including instructions for:

performing a stencil test or alpha test on graphics information within said potentially visible group, and not performing stencil or alpha tests on culled portions of said first group.

12. A computer program product according to claim 10, wherein said culling is based on depth and transparency data.

13. A computer program product according to claim 10, wherein said culling comprises:

for each primitive in said first group of primitives, determining if said primitive is completely hidden within said 2-D screen, and

(i) if said primitive is completely hidden within said 2-D screen, discarding data associated with said primitive; and

(ii) if said primitive is not completely hidden within said 2-D screen, generating a visible stomp list, each stamp containing a portion of said primitive that may be visible.

14. A computer program product according to claim 13, wherein said determining is based at least in part on said primitive'"'"'s bounding box.

15. A computer program product according to claim 14, wherein said determining comprises querying a Magnitude Comparison Content Addressable Memory (MCCAM) with said bounding box.

16. A computer program product according to claim 13, wherein said generating a visible stamp list comprises calculating a left-most position and a right-most position of said primitive within each subraster line that contains at least one sample point.

17. A computer program product according to claim 13, wherein said generating a visible stamp list comprises computing a z-value of said primitive at each sample point covered and comparing said calculated z-value with a current z-value associated with said sample point.

18. A computer program product according to claim 10, wherein said potentially visible group of graphics information comprises a number of portions of said first group of primitives, and wherein said number is greater than two.

19. A method for culling graphics primitives prior to rendering said graphics primitives in a two-dimensional region, said method comprising:

sorting said graphics primitives into tiles, wherein said 2-dimensional screen is represented by said tiles; and

wherein said culling is performed such that all graphics primitives sorted to a first tile are processed before graphics primitives sorted to a second tile;

identifying a first group of graphics primitives, each of said first group of graphics primitive overlapping a pixel of a two-dimensional display region;

culling portions of said first group of graphics primitives that do not affect a final value of said pixel wherein said graphics primitives comprise vertices and a time order of said vertices is preserved within each tile during said culling;

generating a potentially visible group of graphics primitives that excludes said culled graphics primitive portions; and

communicating at most selected ones of said potentially visible group of graphics primitives but none of said culled portions of said graphics primitives to a pixel rendering unit.

20. A method for culling in a graphics rendering pipeline configured to render three-dimensional (3-D) graphics information onto a two-dimensional (2-D) screen, said graphics information comprising a plurality of graphics primitives, said method comprising:

sorting said graphics primitives into tiles, wherein said 2-dimensional screen is represented by said tiles; and

wherein said culling is performed such that all graphics primitives sorted to a first tile are processed before graphics primitives sorted to a second tile;

identifying a first group of primitives wherein each primitive overlaps a pixel of said 2-D screen;

culling portions of said first group of primitives that do not affect a final color of said pixel, wherein said culling is performed such that guaranteed opaque geometry within said first tile is processed before other geometry in said first tile thereby generating a potentially visible group of graphics information; and

dispatching said potentially visible group of graphics information to a pixel unit.

21. A method for culling graphics primitives prior to rendering said graphics primitives in a two-dimensional region, said method comprising:

sorting said graphics primitives into tiles, wherein said 2-dimensional screen is represented by said tiles; and

wherein said culling is performed such that graphics primitives sorted to a first tile are processed before graphics primitives sorted to a second tile;

identifying a first group of graphics primitives, each of said first group of graphics primitive overlapping a pixel of a two-dimensional display region;

culling portions of said first group of graphics primitives that do not affect a final value of said pixel wherein said culling is performed such that guaranteed opaque geometry within said first tile is processed before other geometry in said first tile;

generating a potentially visible group of graphics primitives that excludes said culled graphics primitive portions; and

communicating at most selected ones of said potentially visible group of graphics primitives but none of said culled portions of said graphics primitives to a pixel rendering unit.

22. A method according to claim 21, wherein said final value is selected from the set of final values consisting of a depth value, a color value, a z-value, and combinations thereof.

23. A method according to claim 21, wherein said pixel rendering unit is in electronic communication with a frame buffer memory.

24. A method according to claim 21, wherein said communicating at most selected ones of said potentially visible group of graphics primitives but none of said culled portions of said graphics primitives to a two-dimensional pixel rendering unit comprises communicating only said potentially visible group of graphics primitives but none of said culled portions of said graphics primitives to said frame buffer memory.

25. A method according to claim 21, wherein said culling it based at least in part on graphic primitive depth and transparency data.

26. A method according to claim 21, wherein said culling comprises:

for each graphic primitive in said first group of graphic primitives, determining if said graphic primitive is completely hidden within a two-dimensional display screen region, and (i) if said primitive is hidden within said two-dimensional display region, discarding data associated with said primitive; and

(ii) if said primitive is not hidden within said two-dimensional display region, identifying portions of said graphics primitive that may be visible.

27. A method according to claim 21, wherein said potentially visible group of graphics information comprises a number of portions of said first group of primitives, and wherein said number is greater than two.