Method and apparatus for early culling of occluded objects

• US 6,924,801 B1
• Filed: 02/09/1999
• Issued: 08/02/2005
• Est. Priority Date: 02/09/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dorbie, Angus
• Primary Examiner(s): Wong, Don
• Assistant Examiner(s): MANCUSO, HUEDUNG XUAN CAO
• Application Number:
  US09/247,816
• Time in Patent Office: 2,366 Days
• Field of Search: 345/422, 345/424, 345/435, 345/425, 345/428, 345/629
• US Class Current: 345/422
• CPC Class Codes: G06T 15/405 using Z-buffer

Abstract

A method and apparatus for early occlusion culling are provided. For the method of the present invention, a host processor establishes a coarse Z-buffer. The coarse Z-buffer is divided into a series of tiles. Each tile has an associated depth value. The depth values are updated using information fed back from the Z-buffer. The host processor uses the depth values to selectively discard occluded objects before they are rendered.

Claims

1. A system, used as a host for a graphics pipeline, comprising:

a host processor executing a graphics application program, wherein the graphics application program is capable to implement;

a generation stage for creation, acquisition, and modification of information to be displayed, and organizing the information into application data structures; and

a traversal stage for traversal of the application data structures, and passing on appropriate graphics data; and

a graphics processor, communicatively couples to the host processor, capable to implement;

a transformation stage for transformation of graphics data from object space coordinates into eye-space coordinates, performing requested lighting operation, clipping the transformed data in clip-space, and projecting resulting coordinates into window-space;

a rasterization stage for rendering window-space primitives into a frame buffer, and performing shading calculations, texture lookups and calculations, and per-pixel operations;

a feedback loop permitting the rasterization stage to return information to the traversal stage; and

a display stage for scanning resulting pixels in frame buffer for display to a display device.

2. A method for early culling of occluded objects, comprising:

a) ordering all objects, the objects being included in an image being rendered, according to their distance from eye point, comprising;

i) logically dividing area of the image into a coarse Z-buffer, the coarse Z-buffer including a series of tiles, the tiles being arranges in an rectangular grid, wherein the grid may have different resolutions, and wherein each tile has an associated depth value, the depth value being a Z-buffer value farthest from the eye that is included within that tile;

ii) constructing a surrogate volume for each object of the image, wherein each surrogate volume is a three-dimensional object that is just large enough to contain the object being ordered and wherein each surrogate volume may span only one tile of tan appropriate resolution;

iii) determining a depth value of the surrogate volume that is nearest the eye of the viewer;

iv) determining the depth value of the one tile that includes the surrogate volume;

v) comparing the depth value of the surrogate volume versus the depth value of the tile including the surrogate volume;

b) culling the object whose surrogate volume has a depth value farther from the eye than the depth value of the tile, including the surrogate volume, after a single comparison; and

c) rendering the objects whose surrogate volume has a depth value closer to the eye than the depth value of the tile, including the surrogate volume, or equidistant to the eye with the depth value of the tile including the surrogate volume.

3. The method of claim 2, wherein the surrogate volume may span several tiles and further comprising:

comparing the depth value of the surrogate volume with each of the spanning tiles; and

culling the objects whose surrogate volume has a depth value farther from the eye than the depth value of the tiles including the surrogate volume; and

rendering the objects whose surrogate volume has a depth value closer to the eye than the depth value of at least one of the tiles including the surrogate volume or is equidistant to the eye with at least one of the tiles including the surrogate volume.

4. The method of claim 2, further comprising:

subdividing the objects that are not occluded into smaller objects; and

determining if the smaller objects are occluded.

5. A method for early culling of occluded objects, comprising:

a) ordering all objects, the objects being included in an image being rendered, according to their distance from eye point, comprising;

i) logically dividing area of the image into a coarse Z-buffer, the coarse Z-buffer including a series of tiles, the tiles being arranges in an rectangular grid, wherein the grid may have different resolutions, and wherein each tile has an associated depth value, the depth value being a Z-buffer value farthest from the eye that is included within that tile;

ii) constructing a surrogate volume for each object of the image, wherein each surrogate volume is a three-dimensional object that is just large enough to contain the object being ordered and wherein each surrogate volume may span only one tile of an appropriate resolution;

iii) determining a depth value of the surrogate volume that is nearest the eye of the viewer;

iv) determining the depth value of the one tile that includes the surrogate volume;

v) comparing the depth value of the surrogate volume versus the depth value of the tile including the surrogate volume;

b) culling the object whose surrogate volume has a depth value farther from the eye than the depth value of the tile, including the surrogate volume, after a single comparison; and

c) rendering the objects whose surrogate volume has a depth value closer to the eye than the depth value of the tile, including the surrogate volume, or equidistant to the eye with the depth value of the tile including the surrogate volume;

wherein each coarse Z-buffer is replicated one or more times at different resolutions, each separate coarse Z-buffer spans the image using a different resolution, the number of tiles in the coarse Z-buffers of various resolutions remains constant, for lower resolution coarse Z-buffers, each tile covers a larger area of the image, for lower resolution coarse Z-buffers, the tiles overlap one another,

center points of successive resolutions of tiles of the coarse Z-buffers are offset from the center points of preceding resolution of tiles,

lower resolution of the coarse Z-buffers split the image between tiles with overlap, a higher resolution coarse Z-buffer splits the image between tiles with no overlap, and a host processor is allowed to select a resolution that corresponds to a size of any given object.

7. The method of claim 5, wherein the surrogate volume may span several tiles and further comprising:

comparing the depth value of the surrogate volume with each of the spanning tiles; and

culling the objects whose surrogate volume has a depth value farther from the eye than the depth value of the tiles including the surrogate volume; and

rendering the objects whose surrogate volume has a depth value closer to the eye than the depth value of at least one of the tiles including the surrogate volume or is equidistant to the eye with at least one of the tiles including the surrogate volume.

8. The method of claim 5, further comprising:

subdividing the objects that are not occluded into smaller objects; and

determining if the smaller objects are occluded.

6. A system comprising:

a memory for storing depth values, wherein the depth values are derived by;

a) ordering all objects, the objects being included in an image being rendered, according to their distance from eye point, comprising;

i) logically dividing area of the image into a coarse Z-buffer, the coarse Z-buffer including a series of tiles, the tiles being arranged in a rectangular grid, wherein the grid may have different resolutions, and wherein each tile has an associated depth value, the depth value being a Z-buffer value farthest from the eye that is included within that tile;

ii) constructing a surrogate volume for each object of the image, wherein each surrogate volume is a three-dimensional object that is just large enough to contain the object being ordered and wherein each surrogate volume may span only one tile of an appropriate resolution;

iii) determining a depth value of the surrogate volume that is nearest to eye of a viewer;

iv) determining a depth value of the one tile that includes the surrogate volume;

a host processor for;

determining which objects are occluded by comparing the depth value of the surrogate volume versus the depth value of the tile including the surrogate volume,

generating the surrogate volumes for the objects being processed, and transforming the surrogate volumes from object space to eye space; and

a graphics processor for rendering objects that are not occluded.

9. A system comprising:

a memory for storing depth values, wherein the depth values are derived by;

a) ordering all objects, the objects being included in an image being rendered, according to their distance from eye point, comprising;

i) logically dividing area of the image into a first coarse Z-buffer and a second coarse Z-buffer, the first coarse Z-buffer and a second coarse Z-buffer each including a series of tiles, the tiles being arranged in a rectangular grid, wherein the grid of the first coarse Z-buffer and the second Z-buffer have different resolutions, wherein each tile has an associated depth value, the depth value being a Z-buffer value farthest from the eye that is included within that tile, and wherein center points of tiles of the first coarse Z-buffer and center points of tiles of the second Z-buffer resolution are offset from each other;

ii) constructing a surrogate volume for each object of the image, wherein each surrogate volume is a three-dimensional object that is just large enough to contain the object being ordered and wherein each surrogate volume may span only one tile of an appropriate resolution;

iii) determining a depth value of the surrogate volume that is nearest to eye of a viewer;

iv) determining a depth value of the one tile that includes the surrogate volume;

a host processor for;

determining which objects are occluded by comparing the depth value of the surrogate volume versus the depth value of the tile including the surrogate volume,

generating the surrogate volumes for the objects being processed, and transforming the surrogate volumes from object space to eye space; and

a graphics processor for rendering objects that are not occluded.

10. The system of claim 9, wherein a second coarse Z-buffer resolution is greater than a first coarse Z-buffer resolution, whereby tiles in the first coarse Z-buffer cover a larger area of an image than tiles of the second coarse Z-buffer.

11. The system of claim 9, wherein a host processor selects a resolution for each coarse Z-buffer that corresponds to a size of any given object.

12. A method for culling occluded objects from an image being rendered into a frame buffer, the method comprising:

constructing at least two coarse Z-buffers, each Z-buffer covering the same image wherein a first coarse Z-buffer has a higher resolution than a second coarse Z-buffer, each coarse Z-buffer subdivided into a series of tiles, each tile having an associated depth value;

and center points of tiles of the first coarse Z-buffer having an offset from the center points of tiles of the second coarse Z-buffer;

updating the depth values of each of the coarse Z-buffers using Z information from the frame buffer; and

using the depth values to selectively discard the occluded objects from the image being rendered by constructing a surrogate volume for an object and retrieving a greatest depth value from the depth values set of tiles that are spanned by the surrogate volume, and comparing the nearest Z-value of the surrogate volume to the retrieved depth value;

wherein a host processor selects different resolutions for coarse Z-buffers that corresponds to a size of a given image.

13. A computer-readable medium having computer-executable instructions for performing a method for culling occluded objects from an image being rendered into a frame buffer, the method comprising:

constructing at least two coarse Z-buffers, each Z-buffer covering the same image wherein a first coarse Z-buffer has a higher resolution than a second coarse Z-buffer, each coarse Z-buffer subdivided into a series of tiles, each tile having an associated depth value;

applying means for determining differing Z-buffer resolutions and offsetting center points of tiles of the first coarse Z-buffer from the center point of tiles of the second coarse Z-buffer;

updating the depth values of each of the coarse Z-buffers using Z information from the frame buffer; and

using the depth values to selectively discard the occluded objects from the image being rendered by constructing a surrogate volume for an object and retrieving a greatest depth value from the depth values set of tiles that are spanned by the surrogate volume, and comparing the nearest Z-value of the surrogate volume to the retrieved depth value;

wherein a host processor selects different resolutions for coarse Z-buffers that corresponds to a size of a given image.

14. A computer-readable medium having computer-executable instructions for performing a method for culling occluded objects from an image being rendered into a frame buffer, the method comprising:

a) ordering all objects, the objects being included in an image being rendered, according to their distance from eye point, comprising;

i) logically dividing area of the image into a coarse Z-buffer, the coarse Z-buffer including a series of tiles, the tiles being arranged in a rectangular grid, wherein the grid may have different resolutions, and wherein each tile has an associated depth value, the depth value being a Z-buffer value farthest from the eye that is included within that tile;

ii) constructing a surrogate volume for each object of the image, wherein each surrogate volume is a three-dimensional object that is just large enough to contain the object being ordered and wherein each surrogate volume may span only one tile of an appropriate resolution;

iii) determining a depth value of the surrogate volume that is nearest the eye of the viewer;

iv) determining the depth value of the one tile that includes the surrogate volume;

v) comparing the depth value of the surrogate volume versus the depth value of the tile including the surrogate volume;

b) culling the object whose surrogate volume has a depth value farther from the eye than the depth value of the tile, including the surrogate volume, after a single comparison; and

c) rendering the objects whose surrogate volume has a depth value closer to the eye than the depth value of the tile, including the surrogate volume, or equidistant to the eye with the depth value of the tile including the surrogate volume;

wherein each coarse Z-buffer is replicated one or more times at different resolutions, each separate coarse Z-buffer spans the image using a different resolution, the number of tiles in the coarse Z-buffers of various resolutions remains constant, for lower resolution coarse Z-buffers, each tile covers a larger area of the image, for lower resolution coarse Z-buffers, the tiles overlap one another,

center points of successive resolutions of tiles of the coarse Z-buffers are offset from the center points of preceding resolution of tiles,

lower resolution of the coarse Z-buffers split the image between tiles with overlap, a higher resolution coarse Z-buffer splits the image between tiles with no overlap, and a host processor is allowed to select a resolution that corresponds to a size of any given object.

15. The computer-readable medium of claim 14, wherein the step of constructing a surrogate volume comprises constructing a surrogate volume that spans several tiles and further comprises:

comparing the depth value of the surrogate volume with each of the spanning tiles; and

culling the objects whose surrogate volume has a depth value farther from the eye than the depth value of the tiles including the surrogate volume; and

rendering the objects whose surrogate volume has a depth value closer to the eye than the depth value of at least one of the tiles including the surrogate volume or is equidistant to the eye with at least one of the tiles including the surrogate volume.

16. The computer-readable medium of claim 14, further comprising:

subdividing the objects that are not occluded into smaller objects; and

determining if the smaller objects are occluded.