Method and apparatus for performing conservative hidden surface removal in a graphics processor with deferred shading

• US 6,476,807 B1
• Filed: 08/20/1999
• Issued: 11/05/2002
• 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): Zimmerman, Mark
• Assistant Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US09/378,391
• Time in Patent Office: 1,173 Days
• Field of Search: 345/420, 345/421, 345/422, 345/506, 345/582, 345/589, 345/539
• US Class Current: 345/421
• 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 of performing hidden surface removal in a computer graphics pipeline comprising the steps of:

selecting a current primitive from a group of primitives, each primitive comprising a plurality of stamps;

comparing stamps in the current primitive to stamps from previously evaluated primitives in the group of 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.

2. The method of claim 1 wherein the step of comparing the CPVS to a second stamp furthing comprises the steps of:

comparing depth states of samples in the CPVS to depth states of samples in the second stamp; and

evaluating pipeline state values.

3. The method of claim 1 wherein the depth state comprises one z value per sample, and wherein the z value includes a state bit which is defined to be accurate when the z value represents an actual z value of a currently visible surface and is defined to be conservative when the z value represents a maximum z value.

4. The method of claim 1 further comprising the step of dispatching the second stamp and the CPVS when the second stamp potentially alters the final graphics display image independent of the depth state.

5. The method of claim 1 further comprising the steps of:

coloring the dispatched stamps; and

performing an exact z buffer test on the dispatched stamps, after said coloring step.

6. The method of claim 1 further comprising the steps of:

comparing alpha values of a plurality of samples to a reference alpha value; and

performing said step of dispatching the second stamp and the CPVS, independent of alpha values when said alpha values of said plurality of samples are all greater than said reference value.

7. The method of claim 1 further comprising the steps of:

determining whether any samples in said current primitive may affect final pixel color values in said final graphics display image; and

turning blending off for said current primitive when no samples in said current primitive affect final pixel color values in said final graphics display image.

8. The method of claim 1 wherein the step of comparing stamps in the current primitive to stamps from previously evaluated primitives further comprises the steps of:

determining a maximum z value for a plurality of stamp locations of the current primitive;

comparing the maximum z value for a plurality of stamp positions with a minimum z value of the current primitive and setting corresponding stamp selection bits; and

identifying as a process row a row of stamps wherein the maximum z value for a stamp position in the row is greater than the minimum z value of the current primitive.

9. The method of claim 1, wherein:

the step of comparing the CPVS to a second stamp further comprises the steps of comparing depth states of samples in the CPVS to depth states of samples in the second stamp and evaluating pipeline state values;

the depth state comprises one z value per sample, and wherein the z value includes a state bit which is defined to be accurate when the z value represents an actual z value of a currently visible surface and is defined to be conservative when the z value represents a z value greater than an actual z value of a currently visible surface;

further comprising the steps of;

dispatching the second stamp and the CPVS when the second stamp potentially alters the final graphics display image independent of the depth state;

coloring the dispatched stamps;

performing an exact z buffer test on the dispatched stamps, after said coloring step;

comparing alpha values of a plurality of samples to a reference alpha value;

performing said step of dispatching the second stamp and the CPVS, independent of alpha values when said alpha values of said plurality of samples are all greater than said reference value;

for a current primitive that has blending turned on, examining the vertex alpha values of the current primitive, if all the vertices of the current primitive are opaque, and turning the blending off for said current primitive;

comparing stamps in the current primitive to stamps from previously evaluated primitives further comprises the steps of;

determining a maximum z value for a plurality of stamp locations of the current primitive; and

comparing the maximum z value for a plurality of stamp positions with a minimum z value of the current primitive and setting corresponding stamp selection bits;

determining a maximum z value for a plurality of stamp locations of the current primitive further comprises determining a maximum z value for each stamp in a bounding box of the current primitive;

comparing the CPVS to the second stamp comprises the steps of;

(i) determining a set of sample points in a the second stamp;

(ii) computing a z value for a plurality of sample points in the set of sample points; and

(iii) comparing the computed z values with stored z values and outputting sample control signals; and

comparing stamps in the current primitive to stamps from previously evaluated primitives further comprises the step of dispatching the CPVS when the CPVS can affect stencil values.

10. A hidden surface removal system for a deferred shader computer graphics pipeline comprising:

a Magnitude Comparison Content Addressable Memory (MCCAM) Cull unit for identifying a first group of potentially visible samples associated with a current primitive;

a Stamp Selection unit, coupled to the MCCAM cull unit, for identifying, based on the first group and a perimeter of the primitive, a second group of potentially visible samples associated with the primitive;

a Z Cull unit, coupled to the stamp selection unit and the MCCAM cull unit, for identifying visible stamp portions by evaluating a pipeline state, and comparing depth states of the second group with stored depth state values; and

a Stamp Portion Memory unit, coupled to the Z Cull unit, for storing visible stamp portions based on control signals received from the Z Cull unit, wherein the Stamp Portion Memory unit dispatches stamps having a visibility dependent on parameters evaluated later in the computer graphics pipeline.

11. The hidden surface removal system of claim 10 wherein the stored depth state values are stored separately from the visible stamp portions.

12. The hidden surface removal system of claim 10 wherein the Z Cull unit evaluates depth state and pipeline state values, and compares a currently potentially visible stamp (CPVS) to a first stamp;

and

wherein said Stamp Portion Memory, based on control signals from the Z Cull unit;

discards the first stamp when no part of the first stamp would affect a final graphics display image based on the stamps that have been evaluated;

discards the CPVS and makes the first stamp the CPVS, when the first stamp hides CPVS;

dispatches the CPVS and makes the first stamp the CPVS when both the first stamp and the CPVS are at least partially visible in the final graphics display image; and

dispatches the first stamp and the CPVS when the visibility of the first stamp and the CPVS depends on parameters evaluated later in the computer graphics pipeline.

13. A method of rendering a computer graphics image comprising the steps of:

receiving a plurality of primitives to be rendered;

selecting a sample location;

rendering a front most opaque sample at the selected sample location, and defining the z value of the front most opaque sample as Zfar;

comparing z values of a first plurality of samples at the selected sample location;

defining to be Znear a first sample, at the selected sample location, having a z value which is less than Zfar and which is nearest to Zfar of the first plurality of samples;

rendering the first sample;

setting Zfar;

the value of Znear;

comparing z values of a second plurality of samples at the selected sample location;

defining as Znear the z value of a second sample at the selected sample location, having a z value which is less than Zfar and which is nearest to Zfar of the second plurality of samples; and

rendering the second sample.

14. The method of claim 13 further comprising the steps of:

when a third plurality of samples at the selected sample location have a common z value which is less than Zfar, and the common z value is the z value nearest to Zfar of the first plurality of samples;

rendering a third sample, wherein the third sample is the first sample received of the third plurality of samples;

incrementing a first counter value to define a sample render number, wherein the sample render number identifies the sample to be rendered;

selecting a fourth sample from said third plurality of samples;

incrementing a second counter wherein said second counter defines an evaluation sample number;

comparing said sample render number and said evaluation sample number; and

rendering a sample when the corresponding evaluation sample number equals the sample render number.

15. A computing system for 3D graphics rendering, the system comprising:

a host processor; and

a computer graphics pipeline coupled to the host processor;

the computer graphics pipeline further including a hidden surface removal device comprising;

an input for receiving a current primitive from a group of primitives, each primitive composed of one or more stamps;

a stamp selection unit for identifying a touched stamp list, the stamps in the touched stamp list being associated with, the primitive;

a z cull unit, coupled to the stamp selection unit, for identifying visible stamp portions by evaluating a pipeline state and comparing depth states of the stamps in the touched stamp list with stored depth state values; and

a pixel unit, to receive the visible stamp portions and perform fragment operations the received visible stamp portions.

16. The computing system of claim 15, wherein:

the stamp selection unit for identifying a touched stamp list further comprises;

(a) means for selecting a first stamp from the previously evaluated primitives 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 at least some of the stamps in the previously evaluated primitives; and

(b) means for selecting a second stamp, the second stamp being from the current primitive; and

the z cull unit for comparing depth states of the stamps in the touched stamp list with stored depth state values further comprises;

(i) means for comparing the CPVS to the second stamp;

(ii) means for discarding the second stamp when no part of the second stamp would affect the final graphics display image based on the stamps that have been evaluated;

(iii) means for discarding the CPVS and making the second stamp the CPVS, when the second stamp hides the CPVS;

(iv) means for 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

(v) means for 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.

17. The computing system of claim 15, wherein the hidden surface removal device further comprises:

a magnitude comparison content addressable memory cull unit, coupled to the stamp selection unit, for processing the current primitive, using a perimeter of the current primitive, and either (i) eliminating entire current primitive, or, (ii) if the primitive can not be completely eliminated, generating a first group of stamps indicated by the value of stamp selection bits used to affect the touched stamp list.

18. The computing system of claim 16, wherein the hidden surface removal device further comprises:

a magnitude comparison content addressable memory update unit for determining a maximum z value for a plurality of stamp locations of the current primitive; and

the magnitude comparison content addressable memory cull unit compares the maximum z value for a plurality of stamp positions with a minimum z value of the current primitive and sets corresponding stamp selection bits used to affect the touched stamp list.

19. A method of performing hidden surface removal to form a final graphics display of pixels, each pixel comprising one or more samples, each sample comprising a finite state machine, each finite state machine maintaining, (1) z coordinate information;

(2) primitive information, the primitive information consisting of either (a) information needed to generate a primitive'"'"'s color at that sample or pixel, or (b) a pointer to the information needed to generate a primitive'"'"'s color at that sample or pixel; and

(3) one or more sample state bits.

20. The method of claim 19, wherein the one or more sample state bits designate the z value or z values to be either (i) accurate or (ii) conservative;

and the state bit is defined to be accurate when the z value represents an actual z value of a surface, and is defined to be conservative when the z value represents a z value greater than an actual z value of a surface.

21. A method of performing hidden surface removal in a computer graphics pipeline that forms a final graphics image from a plurality of graphics primitives, the method comprising the steps of:

(1) performing conservative hidden surface removal, the conservative hidden surface removal further comprising;

(a) storing a plurality of first sample depth values;

(b) computing depth values for the selected input primitive at sample locations within selected stamp regions;

(c) comparing stored first sample depth values to computed depth values;

(d) updating stored first sample depth values based on the comparison of the stored first sample depth values to the computed depth values; and

(e) dispatching visible stamp portions, visible stamp portions being one or more sample locations of input primitives that were not eliminated by the comparisons of the stored first sample depth values to the computed depth values; and

(2) performing z buffer operations, said z buffer operations further comprising;

(f) storing a plurality of second sample depth values;

(g) comparing the stored second depth values to depth values corresponding to sample locations in visible stamp portions; and

(h) updating the second sample depth values based on the comparisons of the stored second depth values to the depth values corresponding to sample locations in visible stamp portions.

22. A device for performing hidden surface removal in a computer graphics pipeline to form a final graphics image from a plurality of graphics primitives, comprising:

(1) a z cull unit including;

(1a) means for storing a plurality of first sample depth values;

(1b) means for computing depth values for the selected input primitive at sample locations within selected stamp regions;

(1c) means for comparing stored first sample depth values to computed depth values;

(1d) means for updating stored first sample depth values based on the comparison of the stored first sample depth values to the computed depth values; and

(1e) means for dispatching visible stamp portions, visible stamp portions being one or more sample locations of input primitives that were not eliminated by the comparisons of the stored first sample depth values to the computed depth values; and

(2) a pixel unit including;

(2a) means for storing a plurality of second sample depth values;

(2b) means for comparing the stored second depth values to depth values corresponding to sample locations in visible stamp portions; and

(2c) means for updating the second sample depth values based on the comparisons of the stored second depth values to the depth values corresponding to sample locations in visible stamp portions.

23. A computing system for 3D graphics rendering comprising:

a host processor coupled to a computer graphics pipeline, the computer graphics pipeline including a hidden surface removal device comprising;

(1) a z cull unit storing a plurality of first sample depth values, computing depth values for the selected input primitive at sample locations within selected stamp regions, comparing stored first sample depth values to computed depth values, updating stored first sample depth values based on the comparison of the stored first sample depth values to the computed depth values, and dispatching visible stamp portions, the visible stamp portions being one or more sample locations of input primitives that were not eliminated by the comparisons of the stored first sample depth values to the computed depth values; and

(2) a pixel unit storing a plurality of second sample depth values, comparing the stored second depth values to depth values corresponding to sample locations in visible stamp portions, and updating the second sample depth values based on the comparisons of the stored second depth values to the depth values corresponding to sample locations in visible stamp portions.

24. A method of performing hidden surface removal in a computer graphics pipeline, forming a final graphics image from a plurality of graphics primitives, comprising the steps of:

(1) performing a spatial cull operation, the spatial cull operation further comprising steps of;

(1a) storing a plurality of maximum z values, each maximum z value corresponding to a stamp, each stamp corresponding to a plurality of samples;

(1b) comparing the maximum z values to a minimum z value of a selected input primitive; and

(1c) selecting none, some, or all of corresponding stamp regions within a perimeter of the input primitive for further processing based on the result of the comparison of the maximum z values to he minimum z value;

(2) performing a conservative hidden surface removal operation, the conservative hidden surface removal operation further comprising steps of;

(2a) storing a plurality of first sample depth values;

(2b) computing depth values for the selected input primitive at sample locations within selected stamp regions;

(2c) comparing stored first sample depth values to computed depth values;

(2d) updating stored first sample depth values based on the comparison of the stored first sample depth values to the computed depth values; and

(2e) dispatching visible stamp portions, visible stamp portions being one or more sample locations of input primitives that were not eliminated by either the comparisons of the maximum z values to the minimum z value or the comparisons of the stored first sample depth values to the computed depth values; and

(3) performing a z buffer operation, the z buffer operation further comprising steps of;

(3a) storing a plurality of second sample depth values;

(3b) comparing the stored second depth values to depth values corresponding to sample locations in visible stamp portions; and

(3c) updating the second sample depth values based on the comparisons of the stored second depth values to the depth values corresponding to sample locations in visible stamp portions.

25. A device for performing hidden surface removal in a computer graphics pipeline and forming a final graphics image from a plurality of graphics primitives, the device comprising:

(1) an magnitude comparison content addressable cull unit;

(a) storing a plurality of maximum z values, each maximum z value corresponding to a stamp, each stamp corresponding to a plurality of samples;

(b) comparing the maximum z values to a minimum z value of a selected input primitive; and

(c) selecting none, some, or all of corresponding stamp regions within a perimeter of the input primitive for further processing based on the result of the comparison of the maximum z values to the minimum z value;

(2) a z cull unit;

(a) storing a plurality of first sample depth values;

(b) computing depth values for the selected input primitive at sample locations within selected stamp regions;

(c) comparing stored first sample depth values to computed depth values;

(d) updating stored first sample depth values based on the comparison of the stored first sample depth values to the computed depth values; and

(e) dispatching visible stamp portions, the visible stamp portions being one or more sample locations of input primitives that were not eliminated by either the comparisons of the maximum z values to the minimum z value or the comparisons of the stored first sample depth values to the computed depth values; and

(3) a pixel unit;

(a) storing a plurality of second sample depth values;

(b) comparing the stored second depth values to depth values corresponding to sample locations in visible stamp portions; and

(c) updating the second sample depth values based on the comparisons of the stored second depth values to the depth values corresponding to sample locations in visible stamp portions.

26. A computing system for 3D graphics rendering comprising:

a host processor coupled to a computer graphics pipeline, the computer graphics pipeline including a hidden surface removal devise comprised of;

(1) an MCCAM cull unit for;

(1a) storing a plurality of maximum z values, each maximum z value corresponding to a stamp, each stamp corresponding to a plurality of samples;

(1b) comparing the maximum z values to a minimum z value of a selected input primitive; and

(1c) selecting none, some, or all of corresponding stamp regions within a perimeter of the input primitive for further processing based on the result of the comparison of the maximum z values to the minimum z value;

(2) a z cull unit for;

(2a) storing a plurality of first sample depth values;

(2b) computing depth values for the selected input primitive at sample locations within selected stamp regions;

(2c) comparing stored first sample depth values to computed depth values;

(2d) updating stored first sample depth values based on the comparison of the stored first sample depth values to the computed depth values; and

(2e) dispatching visible stamp portions, visible stamp portions being one or more sample locations of input primitives that were not eliminated by either the comparisons of the maximum z values to the minimum z value or the comparisons of the stored first sample depth values to the computed depth values; and

(3) a pixel unit for;

(3a) storing a plurality of second sample depth values;

(3b) comparing the stored second depth values to depth values corresponding to sample locations in visible stamp portions; and

(3c) updating the second sample depth values based on the comparisons of the stored second depth values to the depth values corresponding to sample locations in visible stamp portions.

27. 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 rendering of a digital representation of a final graphics image from a plurality of graphics primitives, to function in a specified manner, storing the final graphics image into a frame buffer memory, the program module including instructions for;

(1) conservative hidden surface removal, the conservative hidden surface removal including the steps of;

(1a) storing a plurality of first sample depth values;

(1b) computing depth values for the selected input primitive at sample locations within selected stamp regions;

(1c) comparing stored first sample depth values to computed depth values;

(1d) updating stored first sample depth values based on the comparison of the stored first sample depth values to the computed depth values; and

(1e) identifying visible stamp portions, visible stamp portions being one or more sample locations of input primitives that were not eliminated by the comparisons of the stored first sample depth values to the computed depth values; and

(2) z buffer processing, the z buffer processing including the steps of;

(2a) storing a plurality of second sample depth values;

(2b) comparing the stored second depth values to depth values corresponding to sample locations in visible stamp portions; and

(2c) updating the second sample depth values based on the comparisons of the stored second depth values to the depth values corresponding to sample locations in visible stamp portions.

28. 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 rendering of a digital representation of a final graphics image from a plurality of graphics primitives, to function in a specified manner, storing the final graphics image into a frame buffer memory, the program module including instructions for;

(1) a spatial cull operation comprising steps of;

(1a) storing a plurality of maximum z values, each maximum z value corresponding to a stamp, each stamp corresponding to a plurality of samples;

(1b) comparing the maximum z values to a minimum z value of a selected input primitive; and

(1c) selecting none, some, or all of corresponding stamp regions within a perimeter of the input primitive for further processing based on the result of the comparison of the maximum z values to the minimum z value;

(2) a conservative hidden surface removal operation comprising steps of;

(2a) storing a plurality of first sample depth values;

(2b) computing depth values for the selected input primitive at sample locations within selected stamp regions;

(2c) comparing stored first sample depth values to computed depth values;

(2d) updating stored first sample depth values based on the comparison of the stored first sample depth values to the computed depth values; and

(2e) identifying visible stamp portions, visible stamp portions being one or more sample locations of input primitives that were not eliminated by either the comparisons of the maximum z values to the minimum z value or the comparisons of the stored first sample depth values to the compute,d depth values; and

(3) a z buffer operation comprising steps of;

(3a) storing a plurality of second sample depth values;

(3b) comparing the stored second depth values to depth values corresponding to sample locations in visible stamp portions; and

(3c) updating the second sample depth values based on the comparisons of the stored second depth values to the depth values corresponding to sample locations in visible stamp portions.

29. A method of performing hidden surface removal in a computer graphics pipeline, forming a final graphics image from a plurality of graphics primitives, comprising the steps of:

(1) selecting a current primitive from a group of primitives, each primitive comprising a plurality of stamps;

(2) performing a spatial cull operation, the spatial cull operation further comprising steps of;

(2a) storing a plurality of maximum z values, each maximum z value corresponding to a stamp, each stamp corresponding to a plurality of samples;

(2b) comparing the maximum z values to a minimum z value of a selected input primitive; and

(2c) selecting none, some, or all of corresponding stamp regions within a perimeter of the input primitive for further processing based on the result of the comparison of the maximum z values to the minimum z value;

(3) performing a conservative hidden surface removal operation, the conservative hidden surface removal operation further comprising steps of;

(3a) storing a plurality of first sample depth values, each first sample depth value comprising a finite state machine, each finite state machine maintaining;

(3a1) z coordinate information including a z value;

(3a2) primitive information, the primitive information consisting of either

(3a2a) information needed to generate a primitive'"'"'s color at that sample or pixel, or

(3a2b) a pointer to the information needed to generate a primitive'"'"'s color at that sample or pixel; and

(3a3) one or more sample state bits, at least one state bit per sample as depth state bit, defining the depth state bit as accurate when the z value represents an actual z value of a surface, and defining the depth state bit as conservative when the z value represents a z value greater than or equal to an actual z value of a surface;

(3b) computing depth values for the selected input primitive at sample locations within selected stamp regions, and comparing stamps in the current primitive to stamps from previously evaluated primitives in the group,of primitives, the comparing being done in one of two selectable modes;

(3b1) a first selectable mode, time order mode, comprising the steps of;

(3b1a) selecting a first stamp from the previously evaluated primitives as a currently potentially visible stamp (CPVS) based on a relationship of depth states of samples in the first stamp with depth state'"'"'s of samples of at least some of the stamps in the previously evaluated primitives;

(3b1b) selecting a second stamp, the second stamp being from the current primitive;

(3b1c) comparing the CPVS to the second stamp, the steps comprising;

(3b1c1) comparing stored first sample depth values to computed depth values; and

(3b1c2) updating stored first sample depth values based on the comparison of the stored first sample depth values to the computed depth values; and

(3b1d) discarding the second stamp when no part of the second stamp would affect the final graphics display image based on the stamps that have previously been evaluated;

(3b1e) discarding the CPVS and making the second stamp the CPVS, when the second stamp hides the CPVS;

(3b1f) 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

(3b1g) 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.

(3b2) a second selectable mode, sorted transparency mode, comprising the steps of;

(3b2a) selecting a sample location in the stamp in the current primitive;

(3b2b) rendering a front most opaque sample at the selected sample location, and defining the z value of the front most opaque sample as Zfar;

(3b2c) comparing z values of a first plurality of samples at the selected sample location;

(3b2d) defining to be Znear a first sample, at the selected sample location, having a z value which is less than Zfar and which is nearest to Zfar of the first plurality of samples;

(3b2e) rendering the first sample;

(3b2f) setting Zfar to the value of Znear;

(3b2g) comparing z values of a second plurality of samples at the selected sample location;

(3b2h) defining as Znear the z value of a second sample at the selected sample location, having a z value which is less than Zfar and which is nearest to Zfar of the second plurality of samples; and

(3b2i) rendering the second sample; and

(4) performing a z buffer operation, the z buffer operation further comprising steps of;

(4a) storing a plurality of second sample depth values;

(4b) comparing the stored second depth values to depth values corresponding to sample locations in visible stamp portions; and

(4c) updating the second sample depth values based on the comparisons of the stored second depth values to the depth values corresponding to sample locations in visible stamp portions.

30. A computing system for 3D graphics rendering comprising:

a host processor coupled to a computer graphics pipeline, the computer graphics pipeline including a hidden surface removal devise comprised of;

an input for receiving a current primitive from a group of primitives, each primitive composed of one or more stamps;

(1) an MCCAM cull unit for;

(1a) storing a plurality of maximum z values, each maximum z value corresponding to a stamp, each stamp corresponding to a plurality of samples;

(1b) comparing the maximum z values to a minimum z value of a selected input primitive; and

(1c) selecting none, some, or all of corresponding stamp regions within a perimeter of the input primitive for further processing based on the result of the comparison of the maximum z values to the minimum z value;

a stamp selection unit for identifying a touched stamp list, the stamps in the touched stamp list being associated with the current primitive;

(2) a z cull/unit, coupled to the stamp selection unit, for identifying visible stamp portions by evaluating a pipeline, state and comparing depth states of the stamps in the touched stamp list with stored depth state values the z cull unit further comprising;

(2a) a circuit for storing a plurality of first sample depth values;

(2b) a circuit for computing depth values for the selected input primitive at sample locations within selected stamp regions;

(2c) a circuit for comparing stored first sample depth values to computed depth values;

(2d) a circuit for updating stored first sample depth values based on the comparison of the stored first sample depth values to the computed depth values; and

(2e) a circuit for dispatching visible stamp portions, visible stamp portions being one or more sample locations of input primitives that were not eliminated by either the comparisons of the maximum z values to the minimum z value or the comparisons of the stored first sample depth values to the computed depth values; and

(3) a pixel unit, to receive the visible stamp portions and perform fragment operations the received visible stamp portions, the pixel unit further comprising;

(3a) a circuit for storing a plurality of second sample depth values;

(3b) a circuit for comparing the stored second depth values to depth values corresponding to sample locations in visible stamp portions; and

(3c) a circuit for updating the second sample depth values based on the comparisons of the stored second depth values to the depth values corresponding to sample locations in visible stamp portions.

31. A computing system for 3D graphics rendering comprising:

a host processor coupled to a computer graphics pipeline, the computer graphics pipeline including a hidden surface removal devise comprised of;

an input for receiving a current primitive from a group of primitives, each primitive composed of one or more stamps;

(1) an MCCAM cull unit for;

(1a) storing a plurality of maximum z values, each maximum z value corresponding to a stamp, each stamp corresponding to a plurality of samples;

(1b) comparing the maximum z values to a minimum z value of a selected input primitive; and

(1c) selecting none, some, or all of corresponding stamp regions within a perimeter of the input primitive for further processing based on the result of the comparison of the maximum z values to the minimum z value;

a stamp selection unit for identifying a touched stamp list, the stamps in the touched stamp list being associated with;

the current primitive;

(2) a z cull unit, coupled to the stamp selection unit, for identifying visible stamp portions by evaluating a pipeline state and comparing depth states of the stamps in the touched stamp list with stored depth state values, the z cull unit further comprising;

(2a) a circuit for storing a plurality of first sample depth values;

(2b) a circuit for computing depth values for the selected input primitive at sample locations within selected stamp, regions;

(2c) a circuit for comparing stored first sample depth values to computed depth values;

(2d) a circuit for updating stored first sample depth values based on the comparison of the stored first sample depth values to the computed depth values; and

(2e) a circuit for dispatching visible stamp portions, visible stamp portions being one or more sample locations of input primitives that were not eliminated by either the comparisons of the maximum z values to the minimum z value or the comparisons of the stored first sample depth values to the computed depth values;

(3) a pixel unit, to receive the visible stamp portions and perform fragment operations the received visible stamp portions, the pixel unit further comprising;

(3a) a circuit for storing a plurality of second sample depth values;

(3b) a circuit for comparing the stored second depth values to depth values corresponding to sample locations in visible stamp portions; and

(3c) a circuit for updating the second sample depth values based on the comparisons of the stored second depth values to the depth values corresponding to sample locations in visible stamp portions;

the magnitude comparison content addressable memory cull unit processing the current primitive by performing a spatial cull operation comprising;

 

(1a) storing a plurality of maximum z values, each maximum z value corresponding to a stamp, each stamp corresponding to a plurality of samples;

 

(1b) comparing the maximum z values to a minimum z value of a selected input primitive; and

 

(1c) selecting none, some, or all of corresponding stamp regions within a perimeter of the input primitive for further processing based on the result of the comparison of the maximum z values to the minimum z value;

the z cull unit processing the selected corresponding stamp regions by performing a conservative hidden surface removal operation comprising;

 

(2a) storing a plurality of first sample depth values, each first sample depth value comprising a finite state machine, each finite state machine maintaining;

(2a1) z coordinate information including a z value;

(2a2) primitive information, the primitive information consisting of either

 

(2a2a) information needed to generate a primitive'"'"'s color at that sample or pixel, or

 

(2a2b) a pointer to the information needed to generate a primitive'"'"'s color at that sample or pixel; and

(2a3) one or more sample state bits, at least one state bit per sample as depth state bit, defining the, depth state bit as accurate when the z value represents an actual z value of a surface, and defining the depth state bit as conservative when the z value represents a z value greater than or equal to an actual z value of a surface;

 

(2b) computing depth values for the selected input primitive at sample locations within selected stamp regions, and comparing stamps in the current primitive to stamps from previously evaluated primitives in the group of primitives, the comparing being done in one of two selectable modes;

(2b1) a first selectable mode, time order mode, comprising the steps of;

 

(2b1a) selecting a first stamp from the previously evaluated primitives 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 at least some of the stamps in the previously evaluated primitives;

 

(2b1b) selecting a second stamp, the second stamp being from the current primitive;

 

(2b1c) comparing the CPVS to the second stamp, the steps comprising;

(2b1c1) comparing stored first sample depth values to computed depth values; and

(2b1c2) updating stored first sample depth values based on the comparison of the stored first sample depth values to the computed depth values; and

 

(2b1d) discarding the second stamp when no part of the second stamp would affect the final graphics display image based on the stamps that have previously been evaluated;

 

(2b1e) discarding the CPVS and making the second stamp the CPVS, when the second stamp hides the CPVS;

 

(2b1f) 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

 

(2b1g) 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.

(2b2) a second selectable mode, sorted transparency mode, comprising the steps of;

 

(2b2a) selecting a sample location in the stamp in the current primitive;

 

(2b2b) rendering a front most opaque sample at the selected sample location, and defining the z value of the front most opaque sample as Zfar;

 

(2b2c) comparing z values of a first plurality of samples at the selected sample location;

 

(2b2d) defining to be Znear a first sample, at the selected sample location, having a z value which is less than Zfar and which is nearest to Zfar of the first plurality of samples;

 

(2b2e) rendering the first sample;

 

(2b2f setting Zfar to the value of Znear;

 

(2b2g) comparing z values of a second plurality of samples at the selected sample location;

 

(2b2h) defining as Znear the z value of a second sample at the selected sample location, having a z value which is less than Zfar and which is nearest to Zfar of the second plurality of samples; and

 

(2b2i) rendering the second sample; and

the pixel unit processing the visible stamp portions by performing a z buffer operation comprising;

 

(3a) storing a plurality of second sample depth values;

 

(3b) comparing the stored second depth values to depth values corresponding to sample locations in visible stamp portions; and

 

(3c) updating the second sample depth values based on the comparisons of the stored second depth values to the depth values corresponding to sample locations in visible stamp portions.