Image compression to reduce pixel and texture memory requirements in a real-time image generator

• US 5,999,189 A
• Filed: 06/27/1996
• Issued: 12/07/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: Kajiya, James T., Powell, William Chambers III, Gabriel, Steven A.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/672,102
• Time in Patent Office: 1,258 Days
• Field of Search: 345/419-20, 345/430-31, 345/433-37, 345/501-507
• US Class Current: 382/232
• 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 supporting image compression in a real-time graphics rendering pipeline includes sorting object geometry for a scene among image regions called chunks. The object geometry for each chunk is rendered separately, and in a serial fashion. After the object geometry is completely rendered for a given chunk, the pixel data for that chunk is compressed and stored. Each chunk of an image can be generated and stored in this manner. To assemble a display image, compressed image chunks are retrieved, decompressed, and temporarily cached. Decompressed image data in the cache is combined into a display image. The process of generating a display image with compression can be performed at real-time rates.

Claims

1. A method for generating display images at a computational rate greater than 10 Hz in an image generation system in which 3D graphical objects in a view volume are rendered to generate each of the display images, the method comprising:

sorting object geometry of the 3D graphical objects among two or more image regions of a 2D view space, where each image region comprises a 2D array of view space coordinates, the object geometry comprises a collection of polygons representing surfaces of the 3D graphical objects and the polygons are spatially sorted such that each image region has a set of polygons that at least partially project into the image region when transformed to the 2D space;

separately rendering the sets of polygons to associated image regions to generate pixel data for the image regions;

independently compressing the pixel data for the image regions;

storing the compressed pixel data for the image regions such that each of the compressed image regions is randomly accessible;

generating a display image including selectively fetching and decompressing the compressed image regions and combining the selectively fetched and decompressed image regions into the display image;

wherein the sorting, rendering, compressing, storing, and generating steps are performed within a computational period of 1/10 of a second; and

repeating the sorting, rendering, compressing, storing, and generating steps to produce subsequent display images at the computational rate.

2. The method of claim 1 wherein the rendering step includes generating sub-pixel anti-aliasing data and including the step:

resolving the sub-pixel anti-aliasing data for each of the image regions before the compressing step.

3. The method of claim 1 in which the compressing step includes performing a discrete cosine transform on pixel blocks, and quantizing spatial frequency components in each of the blocks.

4. The method of claim 3 wherein the compressing step further includes arithmetically encoding quantized frequency components in each of the pixel blocks.

5. The method of claim 3 wherein the compressing step further includes Huffman encoding the quantized frequency components in each of the pixel blocks.

6. The method of claim 1 wherein the compressing step includes using a lossless form of compression including Huffman and run length encoding.

7. The method of claim 1 wherein the image regions are overlapping gsprites at non-fixed screen locations, and wherein the sorting step includes sorting object geometry among the gsprites;

and wherein the method further includes allocating gsprites the for the graphical objects.

8. The method of claim 1 including the steps of:

allocating gsprites for the graphical objects; and

dividing each of the gsprites into the two or more image regions;

wherein the sorting step includes sorting object geometry of a first graphical object among the two or more image regions of a first gsprite allocated to the first graphical object; and

repeating the sorting of object geometry of subsequent graphical objects among the two or more image regions of subsequent gsprites.

9. The method of claim 8 wherein the generating step includes compositing the gsprites to produce the display image.

10. The method of claim 1 wherein the rendering step includes separately and serially rendering sorted object geometry to the two or more image regions.

11. The method of claim 10 wherein the rendering step includes:

rasterizing sorted object geometry for each of the two or more image regions, one image region at a time;

resolving pixel data generated during the rasterizing step; and

wherein the compressing step includes compressing the resolved pixel data.

12. The method of claim 11 wherein the rasterizing step includes rasterizing geometric primitives to generate pixel fragment data;

and

wherein the resolving step includes resolving the pixel fragment data.

13. The method of claim 1 wherein the compressing step includes compressing the pixel data in image sub-regions of the two or more image regions.

14. The method of claim 13 wherein the image sub-regions are 8×

8 pixel blocks.

15. The method of claim 13 wherein the compressing step includes compressing each of the image sub-regions, one sub-region at a time.

16. The method of claim 13 wherein the compressing step includes using double-buffering to compress each sub-region, the compressing step including:

filling a first staging buffer with resolved pixel data; and

while filling the first staging buffer, compressing resolved pixel data in a second staging buffer.

17. The method of claim 1 wherein the storing step includes storing the compressed pixel data in common format with compressed texture data in a shared memory for storing both the compressed pixel data and the compressed texture data.

18. The method of claim 1 wherein the rendering step includes:

retrieving compressed texture data from memory;

decompressing the compressed texture data; and

rasterizing the sorted object geometry for at least one of the two or more image regions, including using the decompressed texture data for a texture mapping operation.

19. A real-time graphics rendering system for generating a new display image at a computational rate equal to or greater than 10 Hz, the system comprising:

a rasterizer operable to receive object geometry sorted among image regions of a 2D view space, where each image region comprises a 2D array of view space coordinates, the object geometry comprises a collection of polygons representing surfaces of the 3D graphical objects and the polygons are spatially sorted such that each image region has a set of polygons that at least partially project into the region when transformed to the 2D space, and the rasterizer is operable to convert independently the set of polygons for each image region to pixel data for the image regions;

a rasterization buffer in communication with the rasterizer, the rasterization buffer operable to store the pixel data;

a compression engine in communication with the rasterization buffer, the compression engine operable to compress the pixel data;

a first memory in communication with the compression engine, the first memory operable to store the compressed pixel data such that each of the compressed image regions is independently accessible;

a first decompression engine in communication with the first memory, the first decompression engine operable to decompress the compressed pixel data; and

a display controller in communication with the first decompression engine, the display controller operable to selectively fetch and instruct the decompression engine to decompress fetched image regions and operable to combine the decompressed pixel data into at least a portion of a display image such that the display image is generated in less than 1/10 of a second.

20. The system of claim 19 wherein the compression engine is operable to perform DCT compression on the pixel data.

21. The system of claim 19 further including a second memory, a second decompression engine in communication with the second memory and a texture cache, and a texture filter engine in communication with the texture cache;

wherein the second memory is operable to store compressed texture data;

wherein the second decompression engine is operable to decompress the compressed texture data and transfer decompressed texture data to the texture cache;

wherein the texture filter engine is in communication with the texture cache, and is operable to filter the decompressed texture data to compute filtered pixel data.

22. The system of claim 19 further including an anti-aliasing engine in communication with the rasterization buffer, the anti-aliasing engine operable to resolve the pixel data;

and

wherein the compression engine is in communication with the anti-aliasing engine, and is operable to compress the resolved pixel data.

23. The system of claim 19 wherein the rasterizer is operable to completely generate the pixel data for one image region at a time;

and wherein the compression engine compresses the pixel data for each image region in a serial fashion, one image region at a time.

24. A method for supporting image compression in a real-time graphics rendering pipeline, the method including:

a) allocating 3D object geometry to two or more gsprites;

b) sub-dividing each of the two or more gsprites into two or more image regions of a 2D view space, where each image region comprises a 2D array of view space coordinates;

c) sorting object geometry associated with the gsprites among the two or more image regions of associated gsprites such that each region has an associated set of polygons representing 3D object geometry that projects into the region;

d) separately rendering the object geometry corresponding to a first image region to generate pixel data for the first image region;

e) storing the pixel data for the first image regions in a rasterization buffer;

f) resolving the pixel data for the first image region;

g) compressing the pixel data for the first image region;

h) storing the compressed pixel data for the first image region;

i) repeating steps d-i for the rest of the image regions for the two or more gsprites such that the compressed image regions are independently accessible;

j) decompressing the pixel data for the image regions;

k) generating a display image from the decompressed pixel data, including compositing pixel data from independently accessed and decompressed image regions of overlapping gsprites;

l) repeating steps a-k to generate subsequent display images at a computational rate at least as fast as one-tenth of a second.