Method and system for memory decomposition in a graphics rendering system

• US 5,852,443 A
• Filed: 06/27/1996
• Issued: 12/22/1998
• Est. Priority Date: 08/04/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kenworthy, Mark L.
• Primary Examiner(s): Buckhel, Jr., Rudolph J.
• Application Number:
  US08/671,506
• Time in Patent Office: 908 Days
• Field of Search: 345/426, 345/431-432, 345/433, 345/113, 345/136, 345/152, 345/191, 345/507, 345/509
• US Class Current: 345/441
• 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 13/80 2D [Two Dimensional] animation, e.g. using sprites
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 15/60 Shadow generation

Abstract

A method for memory decomposition in a graphics rendering system with a pixel fragment memory includes tracking memory usage of the fragment memory to determine when a threshold is attained, and in response, separately rasterizing geometric primitives to smaller image regions. The system includes a pixel memory that can be hierarchically decomposed into smaller regions corresponding to a portion of the image currently being rendered. This hierarchical sub-division can be performed while rendering a scene and can be performed recursively to ensure that the capacity of the fragment buffer is not exceeded.

Claims

1. In a graphics rendering system, a method of rendering geometric primitives, the method comprising:

rasterizing a first set of the geometric primitives for a first image region of size S₁ to generate pixel fragments;

storing the pixel fragments as fragment entries in a fragment buffer,

determining whether a number of fragment entries in the fragment buffer exceed a predetermined value;

in response to determining that the number of fragment entries exceed the predetermined value, dividing the first image region into two or more image regions of a size S₂ ;

rendering serially the two or more image regions of size S₂ including rasterizing a first sub-set of the first set of geometric primitives for a first image region of size S₂ to generate first corresponding pixel fragments, resolving the first corresponding pixel fragments, and repeating the rasterizing and resolving steps for subsequent image regions of size S₂.

2. The method of claim 1 wherein the dividing step includes:

evaluating the size S₁ of the first image region, and based on the size of the first image region, determining the size of S₂ ; and

dividing the first image region of size S₁ into image regions of size S₂.

3. The method of claim 1 wherein the dividing step includes hierarchically dividing the image region of size S₁ into four image regions, each of the four image regions being one-fourth the size of the size of the first image region S₁.

4. The method of claim 1 further including sorting the geometric primitives among image regions of size S₁.

5. The method of claim 1 further including clearing the fragment buffer in response to determining that the fragment entries exceed the predetermined value.

6. The method of claim 1 further including:

clearing the fragment buffer in response to determining that the fragment entries exceed the predetermined value; and

and wherein the step of rasterizing the first sub-set of the first set of geometric primitives for the first image region of size S₂ includes reading the first set of geometric primitives and rejecting any primitives that do not project onto the first image region of Size S₂.

7. The method of claim 1 including:

clearing the fragment buffer in response to determining that the number of fragment entries exceed the predetermined value;

sorting the first set of geometric primitives among the two or more image regions of size S₂ to produce two or more corresponding sub-sets of the first set of geometric primitives, and

wherein the step of rasterizing the first sub-set of the first set of geometric primitives for the first image region of size S₂ includes rasterizing one of the corresponding sub-sets of the first set of geometric primitives.

8. The method of claim 1 including:

incrementing a fragment buffer counter to keep track of the number of fragment buffer entries in the fragment buffer; and

wherein the determining step includes evaluating a value of the fragment buffer counter.

9. The method of claim 1 further including:

storing the first corresponding set of pixel fragments in the fragment buffer,

determining whether a number of fragment entries in the fragment buffer exceed a predetermined value as the first corresponding set of pixel fragments are added to the fragment buffer; and

in response to determining that the number of fragment entries in the fragment buffer exceed the predetermined value while rasterizing the first sub-set of the first set of geometric primitives, dividing the image regions of size S₂ into two or more image regions of size S₃.

10. The method of claim 1 wherein the pixel fragments include color, coverage, and depth data.

11. The method of claim 1 wherein the pixel fragments include color, coverage, opacity, and depth data.

12. A method for rendering geometric primitives comprising:

rasterizing geometric primitives in a set of geometric primitives for a first image region of size S₁ and as a result of rasterizing the geometric primitives, generating pixel fragments corresponding to the geometric primitives;

storing the pixel fragments in a fragment memory;

monitoring memory consumed in storing the pixel fragments;

in response to detecting that a first memory threshold has been attained;

sub-dividing the first image region into two or more image regions of size S₂

rasterizing a first sub-set of the set of geometric primitives to a first image region of size S₂ and as a result of rasterizing the first sub-set, generating pixel fragments corresponding to the first sub-set;

storing the pixel fragments corresponding to the first sub-set,

rasterizing a second sub-set of the set of geometric primitives to a second image region of size S₂ and as a result of rasterizing the second sub-set, generating pixel fragments corresponding to the second sub-set; and

storing the pixel fragments corresponding to the second sub-set.

13. The method of claim 12 including:

monitoring memory consumed in storing the pixel fragments corresponding to the first sub-set, in response to detecting that a second memory threshold has been attained;

sub-dividing the first image region of size S₂ into two or more image regions of size S₃ ;

rasterizing a third sub-set of the set of geometric primitives to a first image region of size S₃ and as a result of rasterizing the third sub-set, generating pixel fragments corresponding to the third sub-set; and

storing the pixel fragments corresponding to the third sub-set.

14. Apparatus for rendering geometric primitives to compute a display image, the apparatus comprising:

a fragment memory;

a rasterizer operable to read the geometric primitives, and operable to generate pixel data for image regions of size S₁, and for image sub-regions of size S₂ ;

a pixel engine in communication with the rasterizer, the pixel engine operable to receive the pixel data and operable to control transfer of selected pixel data to the fragment memory, the pixel engine in communication with fragment memory to store the selected pixel data in the fragment memory; and

buffer control circuitry in communication with the fragment memory, the buffer control circuitry operable to determine whether memory usage of the fragment memory has attained a predetermined value, and in communication with the rasterizer to cause the rasterizer to rasterize a sub-set of the geometric primitives for one of the sub-regions when the memory usage of the fragment memory has attained the predetermined value.

15. The apparatus of claim 14 further including a pixel memory having a size S₁ and including sub-regions of size S₂ ;

wherein the pixel engine is operable to control transfer of the selected pixel data to the fragment and pixel memories, wherein the pixel engine is communication with the fragment and pixel memories to store the selected pixel data in the pixel or fragment memories;

and wherein the buffer control circuitry is in communication with the rasterizer to cause the rasterizer to rasterize a sub-set of the geometric primitives for an image region of size S₂ to a corresponding sub-region of the pixel memory when the memory usage of the fragment memory has attained the predetermined value.

16. The apparatus of claim 14 wherein the rasterizer is operable to generate pixel data for image regions of size S₁, and for image sub-regions of size S₂, which are sub-regions of the image regions of size S₁, and for image sub-regions of size S₃, which are sub-regions of the image regions of size S₂.

17. The apparatus of claim 16 wherein the pixel memory has a size S₁ and has sub-regions of sizes S₂ and S₃ ;

and wherein the rasterizer is operable to generate the pixel data for the image regions of size S₁, S₂, or S₃ to corresponding regions of the pixel memory.

18. The apparatus of claim 17 wherein the rasterizer is operable to sub-divide the pixel memory hierarchically when the memory usage of the fragment memory has attained the predetermined value.