Memory efficient system and method for creating anti-aliased images

• US 6,421,060 B1
• Filed: 03/31/1999
• Issued: 07/16/2002
• Est. Priority Date: 03/31/1999
• Status: Expired due to Term

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Luken, William L.
• Primary Examiner(s): Chang, Kent
• Assistant Examiner(s): Patel, Nitin
• Application Number:
  US09/282,813
• Time in Patent Office: 1,203 Days
• Field of Search: 345/136, 345/137, 345/132, 345/429, 382/266, 382/267, 382/268, 382/269
• US Class Current: 345/611
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77

Abstract

In accordance with the present invention, a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for creating anti-aliased images and/or a method for creating anti-aliased images includes the steps of providing a subject to be rendered, defining an output resolution of a complete image to be generated by rendering the subject, dividing the complete image into a number of image portions, the number of image portions being determined by an anti-aliasing quality, each image portion having a number of pixels determined by the output resolution of the complete image and the number of image portions, processing the complete image by traversing the subject multiple times to create an intermediate image for each image portion, the intermediate image having a greater number of pixels than the image portion, determining each pixel within the image portion by averaging over blocks of pixels in the intermediate image and combining the image portions to generate the complete anti-aliased image with the output resolution. A system for creating the image is also included.

Claims

1. A method for creating anti-aliased images comprising the steps of:

providing a subject to be rendered;

defining an output resolution of a complete image to be generated by rendering the subject;

dividing the complete image to be generated into a number of image portions to be generated, the number of the image portions being determined by an anti-aliasing quality, each image portion having a number of pixels determined by the output resolution of the complete image and the number of the image portions;

processing the complete image by traversing the subject multiple times to create an intermediate image for each image portion to be generated, the intermediate image having a greater number of pixels than the image portion;

determining each pixel within the image portion by averaging over blocks of pixels in the intermediate image; and

combining the image portions to generate the complete anti-aliased image with the defined output resolution.

2. The method as recited in claim 1, wherein the step of processing includes the steps of:

performing geometric processing; and

immediately passing results of the geometric processing to rasterization processing.

3. The method as recited in claim 1, wherein the step of processing includes the step of adjusting clipping boundaries on each traversal to select blocks of pixels to be processed.

4. The method as recited in claim 1, wherein the step of processing the image by traversing includes the step of traversing the subject a number of times equal to a predetermined sub-sampling for pixels determined by the anti-aliasing quality.

5. The method as recited in claim 1, wherein the subject includes a digital model of one of objects and scenery to be rendered.

6. The method as recited in claim 1, wherein the step of combining the image portions comprises the step of generating an anti-aliased image with resolution of m rows and n columns based on rendering the subject to be rendered i×

j successive times in which each successive rendering is defined by a contiguous m×

n intermediate image within an image space having i×

m rows and j×

n columns.

7. The method as recited in claim 1, wherein the image portions include a substantially same size.

8. The program storage device as recited in claim 7, wherein the image portions include a substantially same size.

9. The method as recited in claim 1 wherein the intermediate image has a greater resolution than the image portion.

10. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for creating anti-aliased images, the method steps comprising:

providing a subject to be rendered;

defining an output resolution of a complete image to be generated by rendering the subject;

dividing the complete image to be generated into a number of image portions to be generated, the number of the image portions being determined by an anti-aliasing quality, each image portion having a number of pixels determined by the output resolution of the complete image and the number of the image portions;

processing the complete image by traversing the subject multiple times to create an intermediate image for each image portion, the intermediate image having a greater number of pixels than the image portion;

determining each pixel within the image portion by averaging over blocks of pixels in the intermediate image; and

combining the image portions to generate the complete anti-aliased image with the defined output resolution.

11. The program storage device as recited in claim 10, wherein the step of processing includes the steps of:

performing geometric processing; and

immediately passing results of the geometric processing to rasterization processing.

12. The program storage device as recited in claim 10, wherein the step of processing includes the step of adjusting clipping boundaries on each traversal to select blocks of pixels to be processed.

13. The program storage device as recited in claim 10, wherein the step of processing the image by traversing includes the step of traversing the subject a number of times equal to a predetermined sub-sampling for pixels determined by the anti-aliasing quality.

14. The program storage device as recited in claim 10, wherein the subject includes a digital model of one of objects and scenery to be rendered.

15. The program storage device as recited in claim 10, wherein the step of combining the image portions comprises the step of generating an anti-aliased image with resolution of m rows and n columns based on rendering the subject i×

j successive times in which each successive rendering is defined by a contiguous m×

n intermediate image within an image space having i×

m rows and j×

n columns.

16. The program storage device as recited in claim 10, wherein the intermediate image has a greater resolution than the image portion.

17. A system for creating anti-aliased images comprising:

a memory storage device for storing a boundary representation of an image;

a rendering unit coupled to the memory storage device for determining addresses and color values of all pixels associated the image;

a first image buffer coupled to the rendering unit to receive results from a multiplicity of rendering passes for blocks of i×

j pixels, the first image buffer including a memory with a capacity of at least m×

n×

p bytes, where m is a number of rows in the image, n is the number of columns in the image, and p is the number of bytes needed to represent each pixel;

an image reduction unit coupled to the first image buffer for determining at least one pixel based on an average value for each i×

j block of pixels in the first image buffer; and

a second image buffer coupled to the image reduction unit for receiving each determined pixel, the second image buffer providing an anti-aliased image after completing the multiplicity of rendering passes.

19. The system as recited in claim 17, further comprising a frame buffer for producing a visible representation of the anti-aliased image.

20. The system as recited in claim 19, wherein the frame buffer includes a memory associated with video digital-to-analog converters, which produce the visible representation of the image on a display.

21. The system as recited in claim 19, wherein the frame buffer has a memory capacity substantially equal to the memory capacity of the second image buffer.

22. The system as recited in claim 17, wherein the first image buffer is employed as a frame buffer for producing a visible representation of the anti-aliased image.

23. The system as recited in claim 17, wherein the second image buffer has a memory capacity substantially equal to the memory capacity of the first image buffer.

18. The system as recited in claim l7, wherein the memory capacity of the second image buffer is only sufficient to produce the anti-aliased image with a resolution less than the resolution of the transformed image portion in the first image buffer.