Method and system for merging pixel fragments in a graphics rendering system

• US 5,990,904 A
• Filed: 06/27/1996
• Issued: 11/23/1999
• Est. Priority Date: 08/04/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Griffin, Kent E.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/672,425
• Time in Patent Office: 1,244 Days
• Field of Search: 345/430-2, 345/426, 345/136, 345/149-50, 345/153, 345/435
• US Class Current: 345/631
• 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 merging pixel fragments to reduce memory usage in a graphics rendering system. In rendering a graphics scene, geometric primitives of objects in the scene are rasterized to create pixel data including pixel fragments representing partially covered pixels. Lists of pixel fragments having color, depth, and coverage data are stored in a fragment buffer. When a new fragment is generated, an attempt is made to merge the fragment with the last fragment stored for a corresponding pixel location. Fragments are merged if they are within predefined depth and color tolerances.

Claims

1. In a graphics rendering system for rendering geometric primitives to generate an image, a method for merging pixel fragments comprising:

rasterizing geometric primitives to generate pixel fragments having depth, color, and coverage data;

storing lists of selected pixel fragments in a fragment buffer, each list corresponding to a pixel location in the image;

for a first generated pixel fragment at a first pixel location, determining whether a selected pixel fragment in a corresponding list is within a predefined color tolerance, and determining whether the selected pixel fragment is within a predefined depth tolerance;

merging the generated pixel fragment with a first selected pixel fragment within the predefined color tolerance, and the predefined depth tolerance; and

storing the merged pixel fragment in the corresponding list structure.

2. The method of claim 1 wherein the selected fragment in the corresponding list is the most recently added fragment to the corresponding list, and wherein the determining step comprises only determining whether the most recently added fragment is within a predefined color tolerance.

3. The method of claim 1 comprising the steps of:

rasterizing the geometric primitives to generate fully covered pixels having depth and color data, including rasterizing sets of the geometric primitives sorted among 2D subregions of the image being rendered;

generating pixel fragments for only one subregion of the image at a time; and

storing selected fully covered pixels in a pixel buffer, with memory locations corresponding only to pixel locations in a single subregion.

4. The method of claim 1 comprising the steps of:

rasterizing the geometric primitives to generate pixel data including fully covered pixels having depth and color data;

performing a depth compare operation on the generated fully covered pixels to identify selected fully covered pixels; and

storing selected fully covered pixels in a pixel buffer that has memory locations corresponding to only a single subregion of the image and that is reused for subregions in the image.

5. The method of claim 1 further including:

rasterizing the geometric primitives to generate pixel data including fully covered pixels having depth and color data, including rasterizing sets of the geometric primitives sorted among 2D subregions of the image being rendered;

performing a depth compare operation on the generated fully covered pixels to identify selected fully covered pixels;

storing selected fully covered pixels in a pixel buffer; and

performing depth compare operations between the generated pixel fragments and corresponding selected fully covered pixels in the pixel buffer to identify the selected pixel fragments to store in the fragment buffer;

wherein pixel fragments are generated for only one subregion of the image at a time, and the fragment buffer is re-used for temporarily storing pixel fragments for subregions in the image.

6. The method of claim 1 wherein the coverage data includes a coverage mask, and the merging step comprises:

combining the coverage mask of the generated pixel fragment with the first selected pixel fragment within the predefined color tolerance, and the predefined depth tolerance; and

storing the combined coverage mask in the merged pixel fragment.

7. The method of claim 6 further including:

rasterizing sets of the geometric primitives sorted among 2D subregions of the image being rendered for only one subregion at a time;

determining whether the merged pixel fragment has become a fully covered pixel as a result of the merging step; and

if so,

storing color and depth of the merged pixel fragment at a corresponding location in the pixel buffer, wherein the pixel buffer includes memory locations only for an array of pixel locations corresponding substantially to dimensions of each of the subregions.

8. The method of claim 1 further including:

resolving the lists of selected pixel fragments in the pixel buffer;

repeating the rasterizing and resolving steps to generate a display image; and

generating the display image and subsequent images at rate greater than 10 Hz.

9. The method of claim 8 wherein the rasterizing step includes rasterizing sets of the geometric primitives sorted among 2D subregions of the image being rendered one subregion at a time, and the resolving step is performed for one subregion at a time such that lists of selected pixel fragments are maintained for only one subregion at a time.

10. The method of claim 1 wherein the predefined depth and color tolerances are user adjustable to regulate fragment memory consumption.

11. The method of claim 1 wherein the rasterizing step includes rasterizirig sets of the geometric primitives sorted among 2D subregions of the image being rendered;

and further including;

generating pixel fragments for only one subregion of the image at a time; and

resolving the pixel fragments generated for one subregion of the image at a time such that pixel fragments are maintained for only one subregion at a time.

12. The method of claim 11 wherein a single rasterization buffer with memory locations corresponding only to pixel locations of a single subregion is used to perform hidden surface removal and pixel resolve operations for each subregion in the image.

13. A system for rendering geometric primitive data to generate an image for a view space, the system comprising:

a rasterization buffer;

a rasterizer operable to receive geometric primitives and operable to rasterize the geometric primitives to produce pixel fragments including color, depth, and coverage data;

a pixel engine in communication with the rasterizer to receive the pixel fragments, operable to perform a depth compare operation to determine whether to store the pixel fragments in the rasterization buffer, the pixel engine in communication with the rasterization buffer to read stored pixel fragments, operable to compare a pixel fragment generated by the rasterizer with at least a first pixel fragment stored in the rasterization buffer to determine whether the generated pixel fragment is within a color tolerance, and operable to merge the generated pixel fragment with one of the pixel fragments stored in the rasterization buffer.

14. The system of claim 13 wherein the rasterization buffer includes a pixel buffer operable to store color and depth data for fully covered pixel locations in the view space, and a fragment buffer operable to store color, depth, and coverage data for partially covered pixel locations in the view space.

15. The system of claim 14 wherein the fragment buffer is operable for storing lists of the pixel fragments, the lists corresponding to one of the pixel locations in the view space.

16. The system of claim 13 wherein the pixel engine includes a comparator circuit to perform the depth compare operation.

17. The system of claim 13 wherein the pixel engine includes a comparator circuit to compare a pixel fragment generated by the rasterizer with at least a first pixel fragment stored in the rasterization buffer to determine whether the generated pixel fragment is within a color tolerance.

18. The system of claim 13 wherein the pixel engine includes a first comparator circuit to compare the pixel fragment generated by the rasterizer with at least the first pixel fragment stored in the rasterization buffer to determine whether the generated pixel fragment is within a color tolerance, and a second comparator circuit to compare the pixel fragment generated by the rasterizer with at least the first pixel fragment stored in the rasterization buffer to determine whether the generated pixel fragment is within a depth tolerance.

19. The system of claim 13 wherein the pixel engine is operable to maintain the most recent fragment stored in the rasterization buffer for each pixel location in the image, and wherein the pixel engine is operable to merge only the most fragment stored in the rasterization buffer for a pixel location corresponding to a pixel location of the generated fragment.

20. The system of claim 13 wherein the rasterizer is operable to rasterize sets of the geometric primitives sorted among 2D subregions of the image being rendered one subregion at a time and the rasterzation buffer only maintains pixel fragments for only one subregion at a time.

21. The system of claim 20 wherein the rasterizer and an antialiasing engine for resolving pixel fragments for a subregion are operable to generate a new image from an updated group of geometric primitives at a rate of greater than 10 Hz.

22. A system for rendering geometric primitive data to generate an image for a view space, the system comprising:

a rasterization buffer including a pixel buffer operable to store pixel records having color and depth data only for pixel locations in a subregion of the image, and a fragment buffer operable to store lists of fragment records corresponding to the pixel locations, the fragment records including color, coverage and depth data for partially cove red pixel locations;

a rasterizer operable to receive geometric primitives and operable to rasterize the geometric primitives to produce pixel data including color, depth, and coverage data, operable to rasterize sets of the geometric primitives sorted among 2D subregions of the image being rendered one subregion at a time;

a pixel engine in communication with the rasterzer to receive the pixel data, operable to perform a depth compare operation to determine whether to store the pixel data as pixel records or fragment records in the rasterization buffer, the pixel engine in communication with the rasterization buffer to read stored fragment records, operable to compare color data for a partially covered pixel location generated by the rasterizer with at least a first fragment record stored in the fragment buffer to determine whether the color data is within a color tolerance, and operable to merge the color data with one of the fragment records stored in the fragment buffer.

23. In an image processing system for rendering geometric primitives to generate an image, a method for merging pixel fragments comprising:

rasterizing sets of geometric primitives sorted amond 2D subregions of the image to generate pixel data including color, depth, and coverage data, the pixel data corresponding to pixel locations in the subregion of the image being rasterized;

storing pixel records for fully covered pixels in memory elements of a pixel buffer, where the number of memory elements in the pixel buffer correspond approximately to M×

N where M and N are dimensions of the subregions;

storing fragment records in a fragment buffer for partially covered pixels or pixels having translucency in linked lists corresponding to the memory elements of the pixel buffer, wherein fragment records are stored for only the subregion being rasterized;

for incoming pixel data generated in the rasterizing step, performing depth compare operations between the incoming pixel data and corresponding pixel records stored in the pixel buffer to determine whether to replace pixel records stored in the pixel buffer, and to determine whether to add fragment records to corresponding fragment lists;

before adding a new fragment record to a corresponding list, determining whether a fragment record added to the corresponding list is within a predefined color tolerance and a predefined depth tolerance relative to the color and depth of the new fragment;

merging the new fragment with the fragment record most recently added to the corresponding list when the new fragment is within the predefined color tolerance, and the predefined depth tolerance; and

storing the merged fragment record in the corresponding list structure.