US 6,476,807 B1 · Method and apparatus for performing conservative hidden surface removal in a graphics processor with deferred 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.

Claims31

Dependent claims

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.

6 more elements

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.

2 more elements

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.

6 more elements

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.

12 more elements

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.

13 more elements

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.

42 more elements

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.

15 more elements

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.

59 more elements

Dependencies are inferred from the claim text.

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

Life of this patent

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

Life of this patent

Abstract

Claims31