Method and apparatus for video graphics antialiasing with memory overflow optimization

• US 6,429,876 B1
• Filed: 05/21/1999
• Issued: 08/06/2002
• Est. Priority Date: 08/28/1998
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: ATI International SRL (Advanced Micro Devices, Inc.)
• Inventors: Morein, Stephen L.
• Primary Examiner(s): Chauhan, Ulka J.
• Application Number:
  US09/316,438
• Time in Patent Office: 1,173 Days
• Field of Search: 345/611, 345/613, 345/614, 345/501-503, 345/520, 345/531, 345/536, 345/545, 345/555, 345/564, 345/572
• US Class Current: 345/611
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

A method and apparatus for antialiasing in a video graphics system is accomplished by determining if a pixel sample set, which results from oversampling, can be reduced to a compressed sample set, where the compressed sample set contains information describing a corresponding pixel. When the pixel sample set can be reduced to a compressed sample set, the compressed sample set is stored in a frame buffer at a location corresponding to the particular pixel that the sample set describes. When the pixel sample set cannot be reduced to a compressed sample set, a pointer is stored at the frame buffer location corresponding to the particular pixel. The pointer points to a selected address in a sample memory at which the complete sample set for the pixel is stored. When the sample memory reaches capacity, storage of the complete sample set in the sample memory is reduced to a subset of the complete set, allowing all pixels in each frame to be accommodated, but removing the loss-less characteristic of the compression technique.

Claims

1. A method for storing antialiasing pixel data, the method comprising:

sampling a pixel in a predetermined manner to produce a pixel sample set, wherein the predetermined manner is such that absence of selected samples in the pixel sample set does not invalidate the pixel sample set as a representation of the pixel;

determining if the pixel sample set can be reduced to a compressed sample set;

when the pixel sample can be reduced to the compressed sample set, storing the compressed sample set in a first memory at a first memory location; and

when the pixel sample set can not be reduced to the compressed sample set;

determining a selected address in a second memory by;

reading a counter; and

determining if the counter has exceeded a memory address limit;

when the counter has not exceeded the memory address limit, incrementing the counter by an increment step;

when the counter has exceeded the memory address limit;

determining a new address offset for the next available memory address based on a current address offset; and

loading the counter with the next available memory address such that the new address offset becomes the current address offset;

determining a storage portion of the pixel sample set based on the selected address, wherein the storage portion includes at least a portion of the pixel sample set, wherein samples included in the storage portion are determined based on the predetermined manner of sapling;

storing the storage portion of the pixel sample set in the second memory at the selected address; and

storing a pointer to the selected address in the first memory location.

2. The method of claim 1 wherein storing the compressed sample set in the first memory further comprises:

storing a mask;

storing a first color and a first Z; and

storing a second color and a second Z.

3. The method of claim 1, wherein storing the compressed sample set in the first memory further comprises:

storing a first color and a first Z;

storing a second color and a second Z;

storing a third color and a third Z;

storing a first mask, wherein the first mask corresponds to the first color and the first Z; and

storing a second mask, wherein the second mask corresponds to the second color and the second Z, and wherein a combination of the first mask and the second mask corresponds to the third color and the third Z.

4. The method of claim 1, wherein the step of determining the selected memory address further comprises:

incrementing the counter such that the counter indicates a next available memory address.

5. The method of claim 1, wherein determining a new address offset further comprises determining a new address offset such that addresses produced by the counter result in a storage portions determined for subsequent pixel sample sets for storage in the second memory are one-half as large as storage portions determined for pixel sample sets based on the current address offset.

6. The method of claim 5 further comprises:

when data corresponding a pixel represented by samples in the second memory is required;

determining a valid storage portion for a pixel sample set corresponding to the pixel based on the current address offset; and

reading the valid storage portion of the pixel sample set from the second memory based on a pointer stored in the first memory corresponding to the pixel.

7. An apparatus for display antialiasing comprising:

a sample memory, wherein the sample memory stores a plurality of pixel entries, wherein each pixel entry of the plurality of pixel entries includes a plurality of pixel samples;

a frame buffer operably coupled to the sample memory, wherein the frame buffer stores a pixel array, wherein each element of the pixel array describes a pixel of the display, wherein

when pixel data corresponding to a pixel of the pixel array can be reduced to a compressed sample set, the compressed sample set is stored in an element of the pixel array corresponding to the pixel, and

when pixel data corresponding to the pixel requires more pixel samples than the compressed sample set to describe the pixel, a pointer to a pixel entry of the sample memory is stored in the element of the pixel array, wherein at least a portion the pixel data corresponding to the pixel is stored in the pixel entry;

a counter that indicates an unused pixel entry of the sample memory, wherein when the counter exceeds a maximum count, the counter adjusts a current address offset value to a new address offset value, wherein the current address offset value corresponds to an address offset of subsequent pixel entries in the sample memory, wherein the new address offset value is determined based on the current address offset value; and

a compressed sample block operably coupled to the frame buffer, the sample memory, and the counter, wherein the compressed sample block determines whether pixel data sets can be summarized in compressed sample sets, wherein the compressed sample block controls storage of pixel data in the frame buffer and the sample memory, wherein when pixel data is to be stored in the sample memory, the compressed sample block utilizes the current address offset value of the counter to determine a number of samples of the pixel data that are stored in the sample memory.

8. The apparatus of claim 7, wherein the compressed sample set further comprises a mask, a first color, a first Z, a second color, and a second Z.

9. The apparatus of claim 7, wherein the compressed sample set further comprises:

a first color;

a first Z;

a second color;

a second Z;

a third color;

a third Z;

a first mask corresponding to the first color and the first Z; and

a second mask corresponding to the second color and the second Z, wherein a combination of the first mask and the second mask corresponds to the third color and the third Z.

10. A method for antialiasing comprising:

receiving a pixel fragment corresponding to a stored pixel in a pixel array, wherein the pixel fragment is characterized by pixel fragment data, and wherein the stored pixel is characterized by stored pixel data;

merging the pixel fragment with the stored pixel to produce a resultant pixel, wherein the resultant pixel is characterized by resultant pixel data;

storing the resultant pixel data, wherein storing includes;

when the resultant pixel data can be described with a compressed sample set, storing the compressed sample set in the pixel array;

when the resultant pixel data cannot be described with a compressed sample set;

reading a counter value to determine a memory address, wherein the memory address has a base memory address offset;

storing a sample set representing the resultant pixel data at the memory address, wherein samples in the sample set are determined based on the base memory address offset;

when the counter value is within memory boundaries, incrementing the counter value to correspond to a next memory address;

when the counter value exceeds memory boundaries, setting the counter value to a value that corresponds to a new memory address having a new base memory address offset;

storing a pointer in the pixel array, wherein the pointer points to the sample set.

11. The method of claim 10, wherein storing the sample set further comprises:

storing a selected number of samples, wherein each sample of the selected number of samples includes a color value and a Z value, wherein the selected number is determined based on the base memory address offset.

12. The method of claim 11, wherein storing the compressed sample set in the pixel array further comprises:

storing a first descriptor, wherein the first descriptor includes a first color value and a first Z value;

storing a second descriptor, wherein the second descriptor includes a second color value and a second Z;

storing a mask, wherein the mask indicates pixel coverage area of the first descriptor and the second descriptor.

13. The method of claim 12, wherein storing the mask further comprises storing the mask such that when the mask is represented in binary format, a first binary value indicates sample coverage of the first descriptor and a second binary value indicates sample coverage of the second descriptor.

14. The method of claim 13, wherein when the pointer is stored in the pixel array, presence of the pointer is indicated by a predetermined value in a portion of the pixel array corresponding to the mask of the stored pixel.

15. An antialiasing video graphics system, comprising:

a frame buffer that stores a two-descriptor array, wherein each pixel of the video graphics system has a corresponding element in the two-descriptor array;

a sample memory that stores a multi-sample array, wherein each element of the multi-sample array stores a predetermined number of samples;

a next element counter, wherein the next element counter stores a next free element location of the multi-sample array, wherein the predetermined number of samples stored for each element of the multi-sample array is determined based on the next free element location;

a controller operably coupled to the frame buffer, the sample memory, and the next element counter, wherein the controller includes instructions, wherein when the instructions are executed by the controller, the controller performs the steps of;

receiving a pixel fragment that corresponds to a pixel of the video graphics system;

merging the pixel fragment with pixel data corresponding to the pixel to produce a resultant pixel, wherein the resultant pixel is characterized by resultant pixel data; and

storing the resultant pixel data, wherein storing includes;

when the resultant pixel data can be described with a two-descriptor data set, storing the two-descriptor data set in the frame buffer in the element of the two-descriptor array corresponding to the pixel; and

when the resultant pixel data requires a multi-sample data set;

retrieving the sample memory element address from the next element counter, wherein retrieving includes incrementing the next element counter;

determining the predetermined number of samples to include in the multi-sample data set based on the sample memory element address;

storing the multi-sample data set at the sample memory element address in the sample memory; and

storing a pointer in the frame buffer in the element of the two-descriptor array corresponding to the pixel, wherein the pointer points to the multi-sample data set.

16. The antialiasing video graphics system of claim 15, wherein a two-descriptor data set includes a mask, a first color, a first Z, a second color, and a second Z.

17. The antialiasing video graphics system of claim 15 further comprises a buffer operably coupled to the controller and the sample memory, wherein the controller uses the buffer to offload sample memory operations.

18. The antialiasing video graphics system of claim 15 further comprises a stack operably coupled to the controller, wherein the stack stores released locations corresponding to released multi-sample entries, wherein when the resultant pixel data requires a multi-sample data set and the stack includes a released entry, the released entry is popped from the stack and used as the sample memory element address rather than retrieving the sample memory address from the next element counter, wherein the next free element location in the next element counter is used to determine the number of samples in the multi-sample data set stored at the sample memory address in the sample memory.

19. The antialiasing video graphics system of claim 18, wherein when the next element counter is incremented to produce a subsequent free element location, it is determined whether the free element location exceeds boundaries of the sample memory, wherein when boundaries of the sample memory are exceeded, the free element location is set to a value within the boundaries of the sample memory, wherein the value has an offset that differs from an offset of previous free element locations generated by the next element counter for a current frame.