Method and apparatus for rendering anti-aliased polygons

• US 5,123,085 A
• Filed: 03/19/1990
• Issued: 06/16/1992
• Est. Priority Date: 03/19/1990
• Status: Expired due to Fees

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Wallner, Dawn M., Loo, James V., Wells, Stuart C.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Bayerl, Raymond J.
• Application Number:
  US07/495,338
• Time in Patent Office: 820 Days
• Field of Search: 340/728, 340/729, 340/747, 364/522, 364/521
• US Class Current: 345/421
• CPC Class Codes: G06T 15/503 Blending, e.g. for anti-aliasing

Abstract

A scan conversion process is performed on a polygon using a single pass technique. The pixels which comprise the edges and vertices of the polygon are first determined from the vertices which define the polygon. The alpha channel comprises either a sub-pixel mask associated with each pixel which indicates the amount and sub-pixel regions of coverage or a single value indicative of the percentage of coverage of a pixel. Furthermore, a z value indicative of the depth of each pixel is maintained. The pixels between the edge pixels of the polygon are then turned on, thereby filling the polygon. The pixels which comprise the polygon are then composited with the background pixels on a per pixel basis. The depth value of each pixel of the polygon (the z value) is used to determine the compositing equations to be used to composite each pixel of the polygon to the background. The compositing equations update the color of the pixel, the z buffer value of the background pixel and the sub-pixel mask to reflect the addition of information from the compositing of the pixel of the polygon into the background pixel. Through this method high quality anti-aliased polygons may be rendered without performing the time consuming process of sorting the polygons in depth order prior to compositing.

Claims

1. In a computer system comprising a central processing unit (CPU), memory and a graphic display, a process for rendering anti-aliased polygons on the graphic display, said polygons represented by a color, a set of coordinates which indicate the vertices of the polygon and a depth value indicative of the depth of the polygon, said process comprising the steps of:

providing a frame buffer located in memory in which pixels representative of a graphic image are stored for output to the graphics display, each pixel in the frame buffer being identified by a color value, a z buffer value and a representation indicative of coverage, said z buffer value representative of the depth of the pixel and the coverage representation representative of the extent of coverage within a pixel, said pixels in the frame buffer being identified as the background pixels;

identifying the pixels which comprise the polygon, said step comprising the steps of;

computing the pixel locations of the edges which form the polygon according to the vertices of the polygon;

forming a coverage representation for each edge pixel by determining the area within the pixel the polygon covers;

computing the depth value of each edge pixel, said depth value being equal to the depth value of the polygon at the pixel;

computing the pixel locations of the pixels interior to the polygon, said pixel locations being between edge pixels;

forming a coverage representation for each interior pixel indicative of full coverage; and

computing the depth value of each interior pixel, said depth value being equal to the depth value of the polygon at the pixel;

compositing each edge and interior pixel of the polygon with a corresponding background pixel at the location in the frame buffer the pixel is to be composited to, thereby forming a composited pixel which is a new background pixel and is stored in the frame buffer, the step of compositing comprising the steps of;

if the depth value of the polygon pixel is less than the depth value of the corresponding background pixel;

setting the color of the composited pixel to be equal to a first proportionate blend of the color of the polygon pixel and the color of the background pixel, said proportionate blend dependent upon the extend of coverage of the polygon pixel;

setting the depth value of the composited pixel to be equal to the depth value of the polygon pixel; and

setting the coverage representation of the composited pixel to be equal to a first proportionate blend of the coverage representation of the polygon pixel and the coverage representation of the background pixel;

if the depth value of the polygon pixel is greater than the depth value of the corresponding background pixel;

setting the color of the composited pixel to be equal to a second proportionate blend of the color of the polygon pixel and the color of the background pixel, said proportionate blend dependent upon the extent of coverage of the background pixel;

setting the coverage representation of the composited pixel to be equal to a second proportionate blend of the coverage representation of the polygon pixel and the coverage representation of the background pixel; and

setting the depth value of the composited pixel to be equal to the depth value of the background pixel;

if the depth value of the polygon pixel is equal to the depth value of the corresponding background pixel and the combination of the coverage representations of the polygon pixel and the background pixel represents full coverage;

setting the color of the composited pixel to be equal to the color of the polygon pixel;

setting the coverage representation of the composited pixel to represent full coverage; and

setting the depth value of the composited pixel to be equal to the depth value of the background pixel and polygon pixel;

if the depth value of the polygon pixel is equal to the depth value of the corresponding background pixel and the combination of the coverage representations of the polygon pixel and the background pixel does not indicate full coverage;

setting the color of the composited pixel to be equal to the first proportionate blend of the color of the polygon pixel and the color of the background pixel, said proportionate blend dependent upon the extent of coverage; and

setting the depth value of the composited pixel to be equal to the depth value of the polygon pixel; and

setting the coverage representation of the composited pixel to be equal to the first proportionate blend of the coverage representation of the polygon pixel and the coverage representation of the background pixel;

storing in the frame buffer the composited pixel at the location of the corresponding background pixel thereby replacing the background pixel with the composited pixel to form a new background pixel;

retrieving the pixels stored in the frame buffer and actuating the pixels on the graphic display at a color indicated by the color value and intensity indicated by coverage representation, to generate the graphic image on the graphic display;

wherein each of the pixels individually retain a depth value, a color value and a coverage representation and are individually composited with corresponding background pixels, each background pixel individually retaining a depth value, a color value and a coverage representation, to render high quality, anti-aliased polygons.

2. The process as described in claim 1, wherein the step of computing the pixel locations of the edges which form the polygon comprises the step of computing the pixel locations using Bresenham'"'"'s line algorithm.

3. The process as described in claim 1, wherein the step of computing the pixel locations of the edges which form the polygon comprises the step of computing the pixel locations using Pitteway and Watkinson line algorithm and the step of forming the coverage representation for each pixel comprises setting the coverage representation equal to (mx+y)+(1-m), where m is the slope of the edge and x,y are respectively the x and y coordinates of a location a pixel is determined to be closest to.

4. The process as described in claim 1, wherein the coverage representation for each pixel in the frame buffer comprises a sub-pixel mask and the step for forming a coverage representation for each edge pixel comprises the step of forming a sub-pixel mask for each edge pixel by determining the sub-pixels the edge of the polygon crosses and setting those sub-pixels the edge of the polygon crosses and the sub-pixels inclusive to the polygon.

5. The method according to claim 4, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point to the edge into the pixel and the sub-pixel exit point of the edge from the pixel;

determining the entry sub-pixel and the exit sub-pixel the edge of the polygon crosses; and

retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and exit sub-pixel.

6. The method according to claim 4, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the slope of the edge;

determining the entry sub-pixel and the slope of the edge; and

retrieving from memory from a sub-pixel mask indexed according to entry sub-pixel and slope of the edge.

7. The method according to claim 4, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the perpendicular distance from the edge to the center of the pixel and the slope of the edge;

determining the perpendicular distance from the edge to the center of the pixel and the slope of the edge; and

retrieving from memory a sub-pixel mask indexed according to the perpendicular distance from the edge to the center of the pixel and the slope of the edge.

8. The method according to claim 4, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and a sub-pixel sample on the edge within the pixel, said sample being the polygon vertex when the edge terminates within the pixel;

determining the entry sub-pixel and the sample sub-pixel of the edge; and

retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and sample sub-pixel.

9. The process as described in claim 1, wherein the step for forming a coverage representation for each edge pixel comprises the step of forming a sub-pixel mask for each edge pixel by determining the sub-pixels the edge of the polygon crosses, setting those sub-pixels the edge of the polygon crosses and the sub-pixels inclusive to the polygon and generating a cover value equal to the number of sub-pixels set.

10. The method according to claim 5, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the sub-pixel exit point of the edge from the pixel;

determining the entry sub-pixel and the exit sub-pixel edge the polygon crosses; and

retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and exit sub-pixel.

11. The method according to claim 5, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the slope of the edge;

determining the entry sub-pixel and the slope of the edge; and

retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and slope of the edge.

12. The method according to claim 5, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the perpendicular distance from the edge to the center of the pixel and the slope of the edge;

determining the perpendicular distance from the edge to the center of the pixel and the slope of the edge; and

retrieving from memory a sub-pixel mask indexed according to the perpendicular distance from the edge to the center of the pixel and the slope of the edge.

13. The method according to claim 5, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and a sub-pixel sample on the edge within the pixel, said sample being the polygon vertex when the edge terminates within the pixel;

determining the entry sub-pixel and the sample sub-pixel of the edge; and

retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and sample sub-pixel.

14. The method as described in claim 1, wherein pixels are sequentially composited for each scan line and the step of identifying the pixels which comprise the polygon further comprises the steps of:

providing a scan line buffer to store a scan line of pixels;

temporarily storing each pixel of the polygon in the scan line buffer until all pixels of the polygon for the scan line are identified; and

once all pixels of the polygon for the scan line are identified, writing the pixels stored in the scan line buffer to the corresponding scan line of the frame buffer.

15. The method as described in claim 14, wherein if more than one edge pixel crosses a pixel and a first edge pixel identified is stored in the scan line buffer, said step of identifying the pixels which comprises the polygon further comprises compositing the first edge pixel identified with a second edge pixel identified, said compositing comprising the steps of:

retrieving the pixel coverage representation of the edge pixel identified from the scan line buffer;

blending the coverage representation of the edge pixel retrieved from the scan line buffer with the coverage representation of the second edge pixel; and

storing the blended coverage representation in the scan line buffer.

16. The method according to claim 15, wherein,

the step for forming a coverage representation for each edge pixel comprises the step of forming a sub-pixel mask for each edge pixel by determining the sub-pixels the edge of the polygon crosses, setting those sub-pixels the edge of the polygon crosses and the sub-pixels inclusive to the polygon and generating a coverage value equal to the number of sub-pixels set;

and

the coverage values are blended according to the equation α

1+α

2-1, where α

1 and α

2 represent the coverage values for the edge pixels.

17. The method according to claim 15, wherein a coverage representation comprises a sub-pixel mask and the coverage representations are blended according to the equation, M_A AND M_B, where M_A and M_B represent the sub-pixel masks for the edge pixels and "AND" represents the logic AND operation.

18. The method according to claim 1 wherein:

said coverage representation is a single coverage value representative of the area of coverage of the polygon within a pixel;

said first proportionate blend of the color of the polygon pixel and the color of background pixel being;

space="preserve" listing-type="equation">Cb;

=Ca+(1-α

a)*Cb;

where Cb represents the color of the background pixel, Ca represents the color of the polygon pixel and Ca;

=α

a*Ca, α

a represents the coverage value of the polygon pixel, and ;

= represents a replacement function;

said first proportionate blend of the coverage value of the polygon pixel and the coverage value of the background pixel being;

space="preserve" listing-type="equation">α

b;

=α

a+(1-α

a)*α

b;

where α

b represents the coverage value for the background pixel;

said second proportionate blend of the color of the polygon pixel and the color of background pixel being;

space="preserve" listing-type="equation">Cb;

=(1-α

b)*Ca+Cb;

said second proportionate blend of the coverage value of the polygon pixel and the coverage value of the background pixel being;

space="preserve" listing-type="equation">α

b;

=(1-α

b)*α

a+α

b.

19. The method according to claim 1 wherein:

said coverage representation is a sub-pixel mask representative of the area of coverage of the polygon within a pixel;

said first proportionate blend of the color of the polygon pixel and the color of background pixel being;

space="preserve" listing-type="equation">Cb;

=Ca+(1-α

a)*Cb;

where α

a;

=count (Ma)/MASK_-- SIZE, Cb represents the color of the background pixel, Ca represents the color of the polygon pixel and Ca;

=α

a* Ca, Ma represents the sub-pixel mask for the polygon pixel, count represents a function which counts the number bits set to a value indicative of coverage, MASK_-- SIZE represents the total number of sub-pixels of the sub-pixel masks, and;

=represents a replacement function;

said first proportionate blend of the coverage representation of the polygon pixel and the coverage representation of the background pixel being;

space="preserve" listing-type="equation">Mb;

=Ma|Mb;

where Mb represents the sub-pixel mask of the background pixel, and "|" represents the logical OR function; and

said second proportionate blend of the color of the polygon pixel and the color of background pixel being,

space="preserve" listing-type="equation">Cb;

=(1-α

b)*Ca+Cb,

where,

α

b;

=count (Mb)/MASK_-- SIZE,

Ma;

=Ma &

˜

Mb,

α

a;

=Count (Mb)/MASK_-- SIZE, and

Ca;

=α

a*Ca

where "&

" represents the logical AND function and "˜

" represents the logical negation function,

said second proportionate blend of the coverage representation of the polygon pixel and the coverage representation of the background pixel being,

space="preserve" listing-type="equation">Mb;

=Ma|Mb.

20. In a computer system comprising a central processing unit (CPU), memory and a graphic display, a process for rendering anti-aliased polygons on the graphic display, said polygons represented by a color, a set of coordinates which indicate the vertices of the polygon and a depth value indicative of the depth of the polygon, said process comprising the steps of:

providing a frame buffer located in memory in which each pixel in the frame buffer is identified by a color value, a z buffer value and sub-pixel mask, said z buffer value representative of the depth of the pixel and the sub-pixel mask representative of the sub-pixels of the pixel which are set and which indicates the amount of coverage of a pixel, said pixels in the frame buffer being identified as the background pixels;

identifying the pixels which comprise the polygon, said step comprising the steps of;

computing the pixel locations of the edges which form the polygon according to the vertices of the polygon;

forming a sub-pixel mask for each edge pixel by determining the sub-pixels the edge of the polygon crosses and setting those sub-pixels the edge of the polygon crosses and the sub-pixels inclusive to the polygon;

computing the depth value of each edge pixel, said depth value being equal to the depth value of the polygon at the pixel;

computing the pixel locations of the pixels interior to the polygon, said pixel locations being between edge pixels;

forming a sub-pixel mask for each interior pixel by setting all sub-pixels of each sub-pixel mask;

computing the depth value of each interior pixel, said depth value being equal to the depth value of the polygon at the pixel;

compositing each edge and interior pixel of the polygon with a corresponding background pixel at the location in the frame buffer the pixel is to be composited to, thereby forming a new background pixel, the step of compositing comprising the steps of;

if the depth value of the polygon pixel is less than the depth value for the corresponding background pixel,

setting the color of the composited pixel to be equal to,

space="preserve" listing-type="equation">Cb;

=Ca+(1-α

a)*Cb,

where Ca;

=α

a*Ca, α

a represents the color of the polygon pixel, α

a;

=count (Ma)/MASK_-- SIZE and represents the coverage representation of the polygon pixel, Cb represents the color of the background pixel, Ma represents the sub-pixel mask for the polygon pixel, count represents a function which counts the number sub-pixels set, MASK_-- SIZE represents the total number of sub-pixels in the sub-pixel mask and;

=represents a replacement function;

setting the sub-pixel mask of the composited pixel to be equal to,

space="preserve" listing-type="equation">Mb;

=Ma|Mb,

where Mb represents the sub-pixel mask of the background pixel, and "|" represents the logical OR function; and

setting the depth value of the composited pixel to be equal to the depth value of the polygon pixel;

if the depth value of the polygon pixel is greater than the depth value for the corresponding background pixel and the sub-pixel mask for the background pixel is not equal to a full mask;

setting the color of the composited pixel to be equal to,

space="preserve" listing-type="equation">Cb;

=(1-α

b)*Ca+Cb,

where,

α

b;

=count (Mb)/MASK_-- SIZE,

Ma;

=Ma &

˜

Mb,

α

a;

=count (Ma)/MASK_-- SIZE,

Ca;

=α

a*Ca,

α

b is the coverage value representative of the amount of coverage of the background pixel, "&

" represents the logical AND function and "˜

" represents the logical negation function,

setting the sub-pixel mask of the composited pixel to be equal to,

space="preserve" listing-type="equation">Mb;

=Ma|Mb,

setting the depth value to be equal to the depth value of the background pixel;

if the depth value of the polygon pixel is equal to the depth value for the corresponding background pixel;

setting the sub-pixel mask of the composited pixel to be equal to,

space="preserve" listing-type="equation">Mb;

=Ma|Mb,

setting the color of the composited pixel to be,

space="preserve" listing-type="equation">Cb;

=Ca(1-α

a)*Cb,

and setting the depth value of the composited pixel to be equal to the depth value of the polygon pixel.

21. The process as described in claim 20, wherein the step of computing the pixel locations of the edges which form the polygon comprises the step of computing the pixel locations using Bresenham'"'"'s line algorithm.

22. The method according to claim 20, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the sub-pixel exit point of the edge from the pixel;

determining the entry sub-pixel and the exit sub-pixel the edge of the polygon crosses; and

retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and exit sub-pixel.

23. The method according to claim 20, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the slope of the edge;

determining the entry sub-pixel and the slope the edge; and

retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and slope of the edge.

24. The method according to claim 20, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the slope of the edge and the perpendicular distance from the edge to the center of the pixel;

determining the slope of the edge and the perpendicular distance from the edge to the center of the pixel; and

retrieving from memory a sub-pixel mask indexed according to slope of the edge and the perpendicular distance from the edge to the center of the pixel.

25. The method according to claim 20, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and a sub-pixel sample on the edge within the pixel, said sample being the polygon vertex when the edge terminates within the pixel;

determining the entry sub-pixel and the sub-pixel sample on the edge; and

retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and sub-pixel sample on the edge.

26. The method as described in claim 20, wherein pixels are sequentially composited for each scan line and the step of identifying the pixels which comprise the polygon further comprises the steps of:

providing a scan line buffer to store a scan line of pixels;

temporarily storing each pixel of the polygon in the scan line buffer until all pixels of the polygon for the scan line are identified; and

once all pixels of the polygon for the scan line are identified, writing the pixels stored in the scan line buffer to the corresponding scan line of the frame buffer.

27. The method as described in claim 26, wherein if more than one edge pixel crosses a pixel and a first edge pixel identified is stored in the scan line buffer, said step of identifying the pixels which comprises the polygon further comprises compositing the first edge pixel identified with a second edge pixel identified, said compositing comprising the steps of:

retrieving the pixel coverage representation of the edge pixel identified from the scan line buffer;

blending the coverage representation of the edge pixel retrieved from the scan line buffer with the coverage representation of the second edge pixel; and

storing the blended coverage representation in the scan line buffer.

28. The method according to claim 27, wherein the sub-pixel masks are blended according to the equation, M_A AND M_B, where M_A and M_B represent the sub-pixel masks for the edge pixels and "AND" represents the logical AND operation.

29. In a computer system comprising a central processing unit (CPU), memory and a graphic display, said memory including a frame buffer which stores a graphic image comprising pixels to be output to the graphic display, a process for rendering anti-aliased polygons on the graphic display, said polygons represented by a color, a set of coordinates which indicate the vertices of the polygon and a depth value indicative of the depth of the polygon, said process comprising the steps of:

identifying each pixel in the frame buffer by a color value, a z buffer value and a representation indicative of coverage, said z buffer value representative of the depth of the pixel and the coverage representation representative of the extent of coverage within a pixel, said pixels in the frame buffer being identified as the background pixels;

identifying the pixels which comprise the polygon, said step comprising the steps of;

computing the pixel locations of the edges which form the polygon according to the vertices of the polygon;

forming a coverage representation for each edge pixel by determining the area within the pixel the polygon covers;

computing the depth value of each edge pixel, said depth value being equal to the depth value of the polygon for the pixel;

computing the pixel locations of the pixels interior to the polygon, said pixel locations being between edge pixels;

forming a coverage representation for each interior pixel indicative of full coverage;

computing the depth value of each interior pixel, said depth value being equal to the depth value of the polygon for the pixel;

compositing each edge and interior pixel of the polygon with a corresponding background pixel at the location in the frame buffer the pixel is to be composited to, thereby forming composited pixel which is a new background pixel and is stored in the frame buffer, the step of compositing comprising the steps of;

if the depth value of the polygon pixel is less than the depth value for the corresponding background pixel,

setting the color of the composited pixel to be,

space="preserve" listing-type="equation">Cb;

=Ca(1-α

a)*Cb,

where Cb represents the color of the background pixel, Ca represents the color of the polygon pixel, Ca;

=α

a*Ca,α

a represents the coverage representation of the polygon pixel and ";

=" represents a replacement function,

setting the coverage representation of the composited pixel to be equal to,

space="preserve" listing-type="equation">α

b;

=α

a+(1-α

a)*α

b,

where α

b represents the coverage representation of the background pixel and

setting the depth value of the composited pixel to be equal to the depth value of the polygon pixel;

if the depth value of the polygon pixel is greater than the depth value for the corresponding background pixel and the coverage representation for the background pixel does not indicate full coverage;

setting the color of the composited pixel to be equal to,

space="preserve" listing-type="equation">Cb;

=(1-α

b)*Ca+Cb,

setting the coverage representation of the composited pixel to be equal to,

space="preserve" listing-type="equation">α

b;

=(1-α

b)*α

a+α

b,

setting the depth value to be equal to the depth value of the background pixel;

if the depth value of the polygon pixel is equal to the depth value for the corresponding background pixel;

setting the coverage representation of the composited pixel to be,

space="preserve" listing-type="equation">α

b;

=α

a+(1-α

a)*α

b

setting the color of the composited pixel to be,

space="preserve" listing-type="equation">Cb;

=Ca(1-α

a)*Cb,

and setting the depth value of the composited pixel to be equal to the depth value of the polygon pixel;

storing in the frame buffer the composited pixel at the location of the corresponding background pixel thereby replacing the background pixel with the composited pixel to form a new background pixel;

retrieving the pixels stored in the frame buffer and actuating the pixels on the graphic display at a color indicated by the color value and intensity indicated by coverage representation, to generate the graphic image on the graphic display.

30. The process as described in claim 29, wherein the step of computing the pixel locations of the edges which form the polygon comprises the step of computing the pixel locations using Bresenham'"'"'s line algorithm.

31. The process as described in claim 30, wherein the step of computing the pixel locations of the edges which form the polygon comprises the step of computing the pixel locations using Pitteway and Watkinson line algorithm and the step of forming the coverage representation for each pixel comprises setting the coverage representation to a value equal to (mx+y)+(1-m), where m is the slope of the edge and x,y are respectively the x and y coordinates of a location a pixel is determined to be closest to.

32. The process as described in claim 30, wherein the step for forming a coverage representation for each edge pixel comprises the step of forming a sub-pixel mask for each edge pixel by determining the sub-pixels the edge of the polygon crosses, setting those sub-pixels the edge of the polygon crosses and the sub-pixels inclusive to the polygon and generating a cover value equal to the number of sub-pixels set.

33. The method according to claim 32, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the sub-pixel exit point of the edge from the pixel;

determining the entry sub-pixel and the exit sub-pixel the edge of the polygon crosses; and

retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and exit sub-pixel.

34. The method according to claim 32, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the slope of the edge;

determining the entry sub-pixel and slope of the edge; and

retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and slope of the edge.

35. The method according to claim 32, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the slope of the edge and the perpendicular distance from the edge to the center of the pixel;

determining the slope of the edge and the distance from the edge to the center of the pixel; and

retrieving from memory a sub-pixel mask indexed according to the slope of the edge and distance from the edge to the center of the pixel.

36. The method according to claim 32, wherein the step for forming a sub-pixel mask for each edge pixel comprises:

storing in a table in memory a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the sub-pixel sample on the edge within the pixel;

determining the entry sub-pixel and the sub-pixel sample on the edge within the pixel; and

retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and sub-pixel sample on the edge within the pixel.

37. The method as described in claim 29, wherein pixels are sequentially composited for each scan line and the step of identifying the pixels which comprise the polygon further comprises the steps of:

providing a scan line buffer to store a scan line of pixels;

temporarily storing each pixel of the polygon in the scan line buffer until all pixels of the polygon for the scan line are identified; and

once all pixels of the polygon for the scan line are identified, writing the pixels stored in the scan line buffer to the corresponding scan line of the frame buffer.

38. The method as described in claim 37, wherein if more than one edge pixel crosses a pixel and a first edge pixel identified is stored in the scan line buffer, said step of identifying the pixels which comprises the polygon further comprises compositing the first edge pixel identified with a second edge pixel identified, said compositing comprising the steps of:

retrieving the pixel coverage representation of the edge pixel identified from the scan line buffer;

blending the coverage representation of the edge pixel retrieved from the scan line buffer with the coverage representation of the second edge pixel; and

storing the blended coverage representation in the scan line buffer.

39. The method according to claim 38, wherein the coverage representations are blended according to the equation α

1+α

2-1, where α

1 and α

2 represent the coverage representations for the edge pixels.

40. In a computer system comprising a central processing unit (CPU), memory and a graphic display, an apparatus for rendering anti-aliased polygons on the graphic display, said polygons represented by a color, a set of coordinates which indicate the vertices of the polygon and a depth value indicative of the depth of the polygon, said apparatus comprising:

a frame buffer located in memory in which pixels representative of a graphic image are stored for output to the graphic display, each pixel in the frame buffer being identified by a color value, a z buffer value and a coverage representation, said z buffer value representative of the depth of the pixel and the coverage representation representative of the extent of coverage within a pixel, said pixels in the frame buffer being identified as the background pixels;

means for identifying pixels which comprise the polygon, said means comprising;

means for computing the pixel locations of the edges which form the polygon according to the vertices of the polygon;

means for forming a coverage representation for each edge pixel by determining the are a within the pixel the polygon covers;

means for computing the depth value of each edge pixel, said depth value being equal to the depth value of the polygon at the pixel;

means for computing the pixel locations of the pixels interior to the polygon, said pixel locations being between edge pixels;

means for forming a coverage representation for each interior pixel indicative of full coverage;

means for computing the depth value of each interior pixel, said depth value being equal to the depth value of the polygon at the pixel;

means for compositing each edge and interior pixel of the polygon with a corresponding background pixel at the location in the frame buffer the pixel is to be composited to, thereby forming a composited pixel which is a new background pixel and is stored in the frame buffer, said means comprising;

means for setting the color for the composited pixel;

means for setting the coverage representation for the composited pixel;

means for setting the depth value for the composited pixel; and

output means for storing in the frame buffer the composited pixel at the location of the corresponding background pixel thereby replacing the background pixel with the composited pixel to form a new background pixel;

means for controlling the means for compositing comprising;

means for comparing the depth value of the polygon pixel with the depth value of the corresponding background pixel;

means for combining the coverage representations of the polygon pixel and the background pixel;

means for comparing the combined coverage representation to a coverage representation representative of complete coverage;

if the depth value of the polygon pixel is less than the depth value of the corresponding background pixel, said means for controlling controls;

said means for setting the color to be the color of the composited pixel to be equal to a first proportionate blend of the color of the polygon pixel and the color of the background pixel, said proportionate blend dependent upon the extent of coverage of the polygon pixel;

said means for setting the depth value to set the depth value of the composited pixel to be equal to the depth value of the polygon pixel; and

said means for setting the coverage representation to set the coverage representation of the composited pixel to be equal to a first proportionate blend of the coverage representation of the polygon pixel and the coverage representation of the background pixel;

if the depth value of the polygon pixel is greater than the depth value of the corresponding background pixel, said means for controlling controls;

said means for setting the color to set the color of the composited pixel to be equal to a second proportionate blend of the color of the polygon pixel and the color of the background pixel, said proportionate blend dependent upon the extent of coverage of the background pixel;

said means for setting the coverage representation to set the coverage representation of the composited pixel to be equal to a second proportionate blend of the coverage representation of the polygon pixel and the coverage representation of the background pixel; and

said means for setting the depth value to set the depth value of the polygon pixel to be equal to the depth value of the background pixel;

if the depth value of the polygon pixel is equal to the depth value of the corresponding background pixel and the combination of the coverage values of the polygon pixel and the background pixel indicates complete coverage, said means for controlling controls;

said means for setting the color to set the color of the composited pixel to be equal to the color of the polygon pixel;

said means for setting the coverage representation to set the coverage representation of the composited pixel to indicate complete coverage; and

said means for setting the depth to set the depth value of the polygon pixel to be equal to the depth value of the background pixel and polygon pixel;

if the depth value of the polygon pixel is equal to the depth value of the corresponding background pixel and the combination of the coverage values of the polygon pixel and the background pixel does not indicate complete coverage, said means for controlling controls;

said means for setting the color to set the color of the composited pixel to be equal to the first proportionate blend of the color of the polygon pixel and the color of the background pixel, said proportionate blend dependent upon the extent of coverage of the polygon pixel;

said means for setting the depth to set the depth value of the composited pixel to be equal to the depth value of the polygon pixel; and

said means for setting the coverage representation to set coverage representation of the composited pixel to be equal to the first proportionate blend of the coverage representation of the polygon pixel and the coverage representation of the background pixel;

frame buffer control means for retrieving the pixels stored in the frame buffer and actuating the pixels on the graphic display at a color indicated by the color value and intensity indicated by coverage representation, to generate the graphic image on the graphic display;

whereby the pixels individually retain a depth value, a color value and a coverage representation and are individually composited with corresponding background pixels, each background pixel individually retaining a depth value, a color value and a coverage representation to render high quality, anti-aliased polygons.

41. The apparatus as described in claim 40, wherein the means for computing the pixel locations of the edges which form the polygon utilizes Bresenham'"'"'s line algorithm.

42. The apparatus as described in claim 40, wherein the means for computing the pixel locations of the edges which form the polygon determines the pixel locations using Pitteway and Watkinson line algorithm and the means for forming the coverage value for each pixel comprises means for setting the coverage representation to be (mx+y)+(1-m), where m is the slope of the edge and x,y are respectively the x and y coordinates of a location a pixel is determined to be closest to.

43. The apparatus as described in claim 40, wherein the coverage representation for each pixel in the frame buffer comprises a sub-pixel mask and the means for forming a coverage representation for each edge pixel comprises means for forming a sub-pixel mask for each edge pixel which determines the sub-pixels the edge of the polygon crosses and sets to a value indicative of coverage those sub-pixels the edge of the polygon crosses and the sub-pixels inclusive to the polygon.

44. The apparatus according to claim 43, wherein the means for forming a sub-pixel mask for each edge pixel comprises:

a lookup table located in memory which stores a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the sub-pixel exit point of the edge from the pixel;

means for determining the entry sub-pixel and the exit sub-pixel the edge of the polygon crosses; and

means for retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and exit sub-pixel.

45. The apparatus according to claim 43, wherein the means for forming a sub-pixel mask for each edge pixel comprises:

a lookup table located in memory which stores a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the slope of the edge;

means for determining the entry sub-pixel and the slope of the edge; and

means for retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and the slope of the edge.

46. The apparatus according to claim 43, wherein the means for forming a sub-pixel mask for each edge pixel comprises:

a lookup table located in memory which stores a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the slope of the edge and the perpendicular distance from the edge to the center of the pixel;

means for determining the slope of the edge and the perpendicular distance from the edge to the center of the pixel; and

means for retrieving from memory a sub-pixel mask indexed according to the slope of the edge and perpendicular distance from the edge to the center of the polygon pixel.

47. The apparatus according to claim 43, wherein the means for forming a sub-pixel mask for each edge pixel comprises:

a lookup table located in memory which stores a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and a sub-pixel sample on the edge within the pixel, said sample being the polygon vertex when the edge terminates within the pixel;

means for determining the entry sub-pixel and the sub-pixel sample on the edge within the pixel; and

means for retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and sub-pixel sample on the edge within the pixel.

48. The apparatus as described in claim 40, wherein the means for forming a coverage representation for each edge pixel comprises means for forming a sub-pixel mask for each edge pixel which determines the sub-pixels the edge of the polygon crosses, sets to a value indicative of coverage those sub-pixels the edge of the polygon crosses and the sub-pixels inclusive to the polygon and generates a coverage value equal to the number of sub-pixels set.

49. The apparatus according to claim 44, wherein the means for forming a sub-pixel mask for each edge pixel comprises:

a lookup table located in memory which stores a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the sub-pixel exit point of the edge from the pixel;

means for determining the entry sub-pixel and the exit sub-pixel the edge of the polygon crosses; and

means for retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and exit sub-pixel.

50. The apparatus according to claim 44, wherein the means for forming a sub-pixel mask for each edge pixel comprises:

a lookup table located in memory which stores a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the slope of the edge;

means for determining the entry sub-pixel and the slope of the edge; and

means for retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and slope of the edge.

51. The apparatus according to claim 44, wherein the means for forming a sub-pixel mask for each edge pixel comprises:

a lookup table located in memory which stores a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the slope of the edge and the perpendicular distance from the edge to the center of the pixel;

means for determining the slope of the edge and the perpendicular distance from the edge to the center of the pixel; and

means for retrieving from memory a sub-pixel mask indexed according to the slope of the edge and the perpendicular distance from the edge to the center of the pixel.

52. The apparatus according to claim 44, wherein the means for forming a sub-pixel mask for each edge pixel comprises:

a lookup table located in memory which stores a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and a sub-pixel sample on the edge within the pixel, said sample being the polygon vertex when the edge terminates within the pixel;

means for determining the entry sub-pixel and sub-pixel sample on the edge within the pixel; and

means for retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and sub-pixel sample on the edge within the pixel.

53. The apparatus as described in claim 40, wherein pixels are sequentially composited for each scan line, said apparatus further comprising:

a scan line buffer to store a scan line of pixels; and

means for temporarily storing each pixel of the polygon in the scan line buffer until all pixels of the polygon for the scan line are identified;

means for transferring the pixels in the scan line buffer to the frame buffer when all pixels of the polygon for the scan line are identified.

54. The apparatus as described in claim 53, wherein if more than one edge pixel crosses a pixel and a first edge pixel identified is stored in the scan line buffer, said means for identifying pixels which comprise the polygon further comprises means for compositing the first edge pixel identified with a second edge pixel identified, said means for compositing comprising:

means for retrieving the pixel coverage representation of the edge pixel identified from the scan line buffer;

means for blending the coverage representation of the edge pixel retrieved from the scan line buffer with the coverage representation of the second edge pixel;

means for storing the blended coverage representation in the scan line buffer; and

once all pixels of the polygon for the scan line are identified, means for writing the pixels stored in the scan line buffer to the corresponding scan line of the frame buffer.

55. The apparatus according the claim 54, wherein the coverage representations are blended according to the equation α

1+α

2-1, where α

1 and α

2 represent the coverage representations for the edge pixels.

56. The apparatus according to claim 54, wherein a coverage representation comprises a sub-pixel mask and the coverage representations are blended according to the equation, M_A AND M_B, where M_A and M_B represent the sub-pixel masks for the edge pixels and "AND" represents the logical AND operation.

57. The apparatus according to claim 40 wherein:

said coverage representation is a single value representative of the area of coverage of the polygon within a pixel;

said first proportionate blend of the color of the polygon pixel and the color of background pixel being,

space="preserve" listing-type="equation">Cb;

=Ca+(1-α

a)*Cb,

where Cb represents the color of the background pixel, Ca represents the color of the polygon pixel and Ca;

=α

a*Ca, α

a represents the coverage value of the polygon pixel, and ;

= represents a replacement function;

said first proportionate blend of the coverage value of the polygon pixel and the coverage value of the background pixel being,

space="preserve" listing-type="equation">α

b;

=α

a+(1-α

a)*α

b,

where α

b represents the coverage value for the background pixel;

said second proportionate blend of the color of the polygon pixel and the color of background pixel being,

space="preserve" listing-type="equation">Cb;

=(1-α

b)*Ca+Cb;

said second proportionate blend of the coverage value of the polygon pixel and the coverage value of the background pixel being,

space="preserve" listing-type="equation">α

b;

=(1-α

b)*α

a+α

b.

58. The apparatus according to claim 40 wherein:

said coverage representation is a sub-pixel mask representative of the area of coverage of the polygon within a pixel;

said first proportionate blend of the color of the polygon pixel and the color of background pixel being,

space="preserve" listing-type="equation">Cb;

=Ca+(1-α

a)*Cb,

where α

a;

=count (Ma)/MASK_-- SIZE, Cb represents the color of the background pixel, Ca represents the color of the polygon pixel, Ma represents the sub-pixel mask for the polygon pixel, count represents a function which counts the number sub-pixels set, MASK_-- SIZE represents the total number of sub-pixels in the sub-pixel mask, and ";

=" represents a replacement function;

said first proportionate blend of the coverage representation of the polygon pixel and the coverage representation of the background pixel being,

space="preserve" listing-type="equation">Mb;

=Ma|Mb,

where Mb represents the sub-pixel mask of the background pixel, and "|" represents the logical OR function; and

said second proportionate blend of the color of the polygon pixel and the color of background pixel being,

space="preserve" listing-type="equation">Cb;

=(1-α

b)*Ca+Cb,

where,

α

b;

=count (Mb)/MASK_-- SIZE,

Ma;

=Ma&

˜

Mb,

α

a;

=count (Ma)/MASK_-- SIZE,

Ca;

=α

a*Ca,

"&

" represents the logical AND function and "˜

" represents the logical negation function,

said second proportionate blend of the coverage representation of the polygon pixel and the coverage representation of the background pixel being,

space="preserve" listing-type="equation">Mb;

=Ma|Mb.

59. In a computer system comprising a central processing unit (CPU), memory and a graphic display, an apparatus for rendering anti-aliased polygons on the graphic display, said polygons represented by a color, a set of coordinates which indicate the vertices of the polygon and a depth value indicative of the depth of the polygon, said apparatus comprising:

a frame buffer located in memory in which each pixel in the frame buffer is identified by a color value, a z buffer value and sub-pixel mask, said z buffer value representative of the depth of the pixel and the sub-pixel mask representative of the sub-pixels of the pixel which are set and which indicates the amount of coverage of a pixel, said pixels in the frame buffer being identified as the background pixels;

means for identifying the pixels which comprise the polygon, said means comprising;

means for computing the pixel locations of the edges which form the polygon according to the vertices of the polygon;

means for forming a sub-pixel mask for each edge pixel by determining the sub-pixels the edge of the polygon crosses and setting those sub-pixels the edge of the polygon crosses and the sub-pixels inclusive to the polygon;

means for computing the depth value of each edge pixel, said depth value being equal to the depth value of the polygon at the pixel;

means for computing the pixel locations of the pixels interior to the polygon, said pixel locations being between edge pixels;

means for forming a sub-pixel mask for each interior pixel by setting all sub-pixels of each sub-mask;

means for computing the depth value of each interior pixel, said depth value being equal to the depth value of the polygon;

means for compositing each edge and interior pixel of the polygon with a corresponding background pixel at the location in the frame buffer the pixel is to be composited to, thereby forming a composited pixel which is a new background pixel, said means comprising;

means for setting the color for the composited pixel;

means for setting the sub-pixel mask for the composited pixel;

means for setting the depth value for the composited pixel;

means for controlling the means for compositing comprising;

means for comparing the depth value of the polygon pixel to the depth value of the corresponding background pixel,

means for combining the sub-pixel masks of the polygon pixel and the background pixel;

means for comparing the combined sub-pixel mask to a sub-pixel mask representative of complete coverage;

if the depth value of the polygon pixel is less than the depth value for the corresponding background pixel, means for controlling,

said means for setting the color to set the color of the composited pixel to be equal to,

space="preserve" listing-type="equation">Cb;

=Ca+(1-α

a)*Cb,

where α

a represents the coverage representation of the polygon pixel and α

a;

=count (Ma)/MASK_-- SIZE, Cb represents the color of the background pixel, Ca represents the color of the polygon pixel, Ma represents the sub-pixel mask for the polygon pixel, count represents a function which counts the number bits set to a value indicative of coverage, MASK_-- SIZE represents the total number of sub-pixels in the sub-pixel mask, and ";

=" represents a replacement function,

said means for setting the sub-pixel mask to set the sub-pixel mask of the composited pixel to be equal to,

space="preserve" listing-type="equation">Mb;

=Ma|Mb,

Where Mb represents the sub-pixel mask of the background pixel and "|" represents the logical OR function; and

said means for setting the depth value to set the depth value of the composited pixel to be equal to the depth value of the polygon pixel;

if the depth value of the polygon pixel is greater than the depth value for the corresponding background pixel and the sub-pixel mask for the background pixel does not indicate complete coverage, means for controlling,

said means for setting the color to set the color of the composited pixel to be equal to,

space="preserve" listing-type="equation">Cb;

=(1-α

b)*Ca+Cb,

where,

α

b;

=count (Mb)/MASK_-- SIZE,

Ma;

=Ma&

˜

Mb,

α

a;

=count (Ma)/MASK_-- SIZE,

Ca;

=α

a*Ca,

"&

" represents the logical AND function and "˜

" represents the logical negation function,

said means for setting the sub-pixel mask to set the sub-pixel mask of the composited pixel to be equal to,

space="preserve" listing-type="equation">Mb;

=Ma|Mb,

said means for setting the depth value to be equal to the depth value of the background pixel;

if the depth value of the polygon pixel is equal to the depth value for the corresponding background pixel, means for controlling,

said means for setting the sub-pixel mask to set the sub-pixel mask of the composited pixel to be equal to,

space="preserve" listing-type="equation">Mb;

=Ma|Mb,

said means for setting the color to set the color of the composited pixel to be,

space="preserve" listing-type="equation">Cb;

=Ca(1-α

a)*Cb,

said means for setting the depth value to set the depth value of the composited pixel to be equal to the depth value of the polygon pixel;

frame buffer control means for retrieving the pixels stored in the frame buffer and actuating the pixels on the graphic display at a color indicated by the color value and intensity indicated by coverage representation, to generate the graphic image on the graphic display.

60. The apparatus as described in claim 59, wherein the means for computing the pixel locations of the edges which form the polygon utilizes Bresenham'"'"'s line algorithm.

61. The apparatus as described in claim 59, wherein the means for computing the pixel locations of the edges which form the polygon determines the pixel locations using Pitteway and Watkinson line algorithm and the means for forming the coverage representation for each pixel comprises means for setting the coverage representation to a value equal to (mx+y)+(1-m), where m is the slope of the edge and x,y are respectively the x and y coordinates of a location a pixel is determined to be closest to.

62. The apparatus according to claim 59, wherein the means for forming a sub-pixel mask for each edge pixel comprises:

a lookup table located in memory which stores a plurality of sub-pixel masks which represent the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the sub-pixel exit point of the edge from the pixel;

means for determining the entry sub-pixel and the exit sub-pixel the edge of the polygon crosses; and

means for retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and exit sub-pixel.

63. The apparatus as described in claim 59, wherein pixels are sequentially composited for each scan line, said apparatus further comprising:

a scan line buffer to store a scan line of pixels; and

means for temporarily storing each pixel of the polygon in the scan line buffer until all pixels of the polygon for the scan line are identified;

means for transferring the pixels in the scan line buffer to the frame buffer when all pixels of the polygon for the scan line are identified.

64. The apparatus as described in claim 63, wherein if more than one edge pixel crosses a pixel and a first edge pixel identified is stored in the scan line buffer, said means for identifying pixels which comprise the polygon further comprises means for compositing the first edge pixel identified with a second edge pixel identified, said means for compositing comprising:

means for retrieving the sub-pixel mask of the edge pixel identified from the scan line buffer;

means for blending the sub-pixel mask of the edge pixel retrieved from the scan line buffer with the sub-pixel mask of the second edge pixel;

means for storing the blended sub-pixel mask in the scan line buffer; and

means for writing the pixels stored in the scan line buffer to the corresponding scan line of the frame buffer once all pixels of the polygon for the scan line are identified.

65. The apparatus according to claim 64, wherein the sub-pixel masks are blended according to the equation, M_A AND M_B, where M_A and M_B represent the sub-pixel masks for the edge pixels and "AND" represents the logical AND operation.

66. In a computer system comprising a central processing unit (CPU), memory and a graphic display, an apparatus for rendering anti-aliased polygons on the graphic display, said polygons represented by a color, a set of coordinates which indicate the vertices of the polygon and a depth value indicative of the depth of the polygon, said apparatus comprising:

a frame buffer located in memory in which pixels representative of a graphic image are stored for output to the graphic display, each pixel in the frame buffer being identified by a color value, a z buffer value and a coverage representation, said z buffer value representative of the depth of the pixel and the coverage representation representative of the extent of coverage within a pixel, said pixels in the frame buffer being identified as the background pixels;

means for identifying pixels which comprise the polygon, said means comprising;

means for computing the pixel locations of the edges which form the polygon according to the vertices of the polygon;

means for forming a coverage representation for each edge pixel by determining the area within the pixel the polygon covers;

means for computing the depth value of each edge pixel, said depth value being equal to the depth value of the polygon at the pixel;

means for computing the pixel locations of the pixels interior to the polygon, said pixel locations being between edge pixels;

means for forming a coverage representation for each interior pixel indicative of complete coverage;

means for computing the depth value of each interior pixel, said depth value being equal to the depth value of the polygon at the pixel;

means for compositing each edge and interior pixel of the polygon with a corresponding background pixel at the location in the frame buffer the pixel is to be composited to, thereby forming a composited pixel which is a new background pixel and is stored in the frame buffer, said means comprising;

means for setting the color for the composited pixel;

means for setting the coverage representation for the composited pixel; and

means for setting the depth value for the composited pixel;

means for controlling the means for compositing comprising;

means for comparing the depth value of the polygon pixel with the depth value of the corresponding background pixel,

means for combining the coverage representations of the polygon pixel and the background pixel,

means for comparing the combined coverage representation to a coverage representation representative of complete coverage,

if the depth value of the polygon pixel is less than the depth value for the corresponding background pixel, said means for controlling controls,

said means for setting the color to set the color of the composited pixel to be equal to,

space="preserve" listing-type="equation">Cb;

=Ca(1-α

a)*Cb,

where Cb represents the color of the background pixel, Ca represents the color of the polygon pixel, Ca;

=α

a*Ca, α

a represents the coverage representation of the polygon pixel and ";

=" represents a replacement function,

said means for setting the coverage representation to set the coverage representation of the composited pixel to be equal to,

space="preserve" listing-type="equation">α

b;

=α

a+(1-α

a)*α

b,

where α

b represents the coverage representation of the background pixel, and

said means for setting the depth value to set the depth value of the composited pixel to be equal to the depth value of the polygon pixel;

if the depth value of the polygon pixel is greater than the depth value for the corresponding background pixel and the coverage representation for the background pixel is not equal to a full coverage, said means for controlling controls,

said means for setting the color to set the color of the composited pixel to be equal to,

space="preserve" listing-type="equation">Cb;

=(1-α

b)*Ca+Cb,

said means for setting the coverage representation to set the coverage representation of the composited pixel to be equal to,

space="preserve" listing-type="equation">α

b;

=(1-α

b)*α

a+α

b,

and said means for setting the depth value to set the depth value to be equal to the depth value of the background pixel;

if the depth value of the polygon pixel is equal to the depth value for the corresponding background pixel, said means for controlling controls,

said means for setting the coverage representation to set the coverage representation of the composited pixel to be

space="preserve" listing-type="equation">α

b;

=α

a+(1-α

a)*α

b

said means for setting the color to set the color of the composited pixel to be,

space="preserve" listing-type="equation">Cb;

=Ca+(1-α

a)*Cb,

and said means for setting the depth value to set the depth value of the composited pixel to be equal to the depth value of the polygon pixel;

output means for storing in the frame buffer the composited pixel at the location of the corresponding background pixel thereby replacing the background pixel with the composited pixel to form a new background pixel;

frame buffer control means for retrieving the pixels stored in the frame buffer and actuating the pixels on the graphic display at a color indicated by the color value and intensity indicated by coverage representation, to generate the graphic image on the graphic display.

67. The apparatus as described in claim 66, wherein the means for computing the pixel locations of the edges which form the polygon utilizes Bresenham'"'"'s line algorithm.

68. The apparatus as described in claim 67, wherein pixels are sequentially composited for each scan line, said apparatus further comprising:

a scan line buffer to store a scan line of pixels; and

means for temporarily storing each pixel of the polygon in the scan line buffer until all pixels of the polygon for the scan line are identified;

means for transferring the pixels in the scan line buffer to the frame buffer when all pixels of the polygon for the scan line are identified.

69. The apparatus as described in claim 68, wherein if more than one edge pixel crosses a pixel and a first edge pixel identified is stored in the scan line buffer, said means for identifying pixels which comprise the polygon further comprises means for compositing the first edge pixel identified with a second edge pixel identified, said means for compositing comprising:

means for retrieving the pixel coverage representation of the edge pixel identified from the scan line buffer;

means for blending the coverage representation of the edge pixel retrieved from the scan line buffer with the coverage representation of the second edge pixel;

means for storing the blended coverage representation in the scan line buffer; and

means for writing the pixels stored in the scan line buffer to the corresponding scan line of the frame buffer once all pixels of the polygon for the scan line are identified.

70. The apparatus according to claim 69, wherein the coverage representations are blended according to the equation α

1+α

2-1, where α

1 and α

2 represent the coverage representations for the edge pixels.

71. The apparatus as described in claim 66, wherein the means for computing the pixel locations of the edges which form the polygon determines the pixel locations using Pitteway and Watkinson line algorithm and the means for forming the coverage representation for each pixel comprises means for setting the coverage representation to be a value equal to (mx+y)+(1-m), where m is the slope of the edge and x,y are respectively the x and y coordinates of a location a pixel is determined to be closest to.

72. The apparatus as described in claim 66, wherein the means for forming a coverage representation for each edge pixel comprises means for forming a sub-pixel mask for each edge pixel which determines the sub-pixels the edge of the polygon crosses, sets to a value indicative of coverage those sub-pixels the edge of the polygon crosses and the sub-pixels inclusive to the polygon and generates a cover value equal to the number of sub-pixels set.

73. The apparatus according to claim 72, wherein the means for forming a sub-pixel mask for each edge pixel comprises:

a lookup table located in memory which stores a plurality of sub-pixel masks which represents the sub-pixel masks for different combinations of sub-pixels indexed according to the sub-pixel entry point of the edge into the pixel and the sub-pixel exit point of the edge from the pixel;

means for determining the entry sub-pixel and the exit sub-pixel the edge of the polygon crosses; and

means for retrieving from memory a sub-pixel mask indexed according to entry sub-pixel and exit sub-pixel.

74. A scanned conversion process for rendering on a graphics display device a visual display of a polygon comprising the steps of:

determining the pixels and the pixel attributes which comprise the polygon, said attributes comprising the color of a pixel and the extent of coverage within a pixel;

defining a depth for each pixel;

compositing each pixel of the polygon with the background pixel to generate a composite pixel comprising the steps of;

comparing the depth of the polygon pixel to the depth of the background pixel;

if the background pixel is in front of the polygon pixel;

forming the color attribute of the composited pixel to be the color of the background pixel combined with the color of the polygon pixel proportionately reduced by the extent of coverage of the background pixel;

determining the extent of coverage for the composite pixel to be the combination of the extent of coverage of the background pixel and the extent of coverage of the polygon pixel proportionately reduced by the extent of coverage of the background pixel; and

identifying the depth of the composite pixel is to be that of the background pixel;

if the background pixel is behind the polygon pixel;

forming the color attribute of composite pixel to be the color of the polygon pixel combined with the color of the background pixel proportionately reduced by the extent of coverage of the polygon pixel;

determining the extent of coverage of the composite pixel to be the combination of the extent of coverage of the polygon pixel and the extent of coverage of the background pixel proportionately reduced by the extent of coverage of the polygon pixel; and

identifying the depth of the composite pixel to be the depth of the polygon pixel;

if the depth of the polygon pixel equals the depth of the background pixel and the extent of coverage of the background pixel completely covers the pixel;

forming the color attribute of the composite pixel to be the color of the polygon pixel;

determining the coverage of the composite pixel to complete coverage; and

identifying the depth of the composite pixel to be the depth of the polygon pixel; and

if the depth of the polygon pixel equals the depth of the background pixel and the background pixel partially covers the pixel;

forming the color of the composite pixel to be the color of the polygon pixel combined with the color of the background pixel proportionately reduced by the extent of coverage of the polygon pixel;

determining the extent of coverage of the composite pixel to be the combination of the extent of coverage of the polygon pixel and the extent of coverage of the background pixel proportionately reduced by the extent of coverage of the polygon pixel; and

identifying the depth of the composite pixel to be the depth of the polygon pixel;

storing the composite pixels in a frame buffer memory;

reading the pixel data from the frame buffer; and

generating a pixel on the graphic display device at a color defined by the color attribute and intensity defined by the extent of coverage of the composite pixel determined to provide a visual depiction of the anti-aliased polygon image on the graphic display device.

75. In a computer graphics system comprising a CPU, input/output devices and memory, an apparatus for rendering anti-aliased polygons comprising:

pixel generating means for generating pixels composing the polygon according to a definition of a polygon to be rendered, said pixels comprising;

color, depth and coverage attributes said color defining the color of a pixel to be generated, said depth identifying the visual depth of the image, said coverage attribute representing the extent of coverage within a pixel;

pixel compositing means for compositing each of the pixels of the polygon with pixels of a background image comprising;

comparison means for comparing the depth of the polygon pixel to the depth of the background pixel;

means responsive to the comparison means for selecting the means for compositing according to specific compositing techniques such that;

if the polygon pixel is in front of the background pixel, the color of the composited pixel is determined according to the color of the polygon pixel combined with the color of the background pixel proportionately decreased by the extent of coverage of the polygon pixel, the extent of coverage of the composited pixel is determined according to the extent of coverage of the polygon pixel combined with the extent of coverage of the background pixel decreased proportionately by the extent of coverage of the polygon pixel, and the depth is identified to be the depth of the polygon pixel;

if the polygon pixel is behind the background pixel, the color of the composite pixel is determined to be the color of the background pixel combined with the color of the polygon pixel proportionately decreased by the extent of coverage of the background pixel, the coverage of the composite pixel is determined to be the extent of coverage of the background pixel combined with the extent of coverage of the polygon pixel proportionately decreased by the extent of coverage of the background pixel, and the depth of the pixel is identified to be the depth of the background pixel;

if the depth of the polygon pixel equals the depth of the background pixel and the background pixel completely covers the pixel, the color of the composite pixel is set to be the color of the polygon pixel, the extent of coverage of the composite pixel is set to indicate complete coverage, and the depth value of the composite pixel is set to be the depth of the polygon pixel;

if the depth of the polygon pixel is the same as the depth of the background pixel and the background pixel partially covers the pixel, the color of the composite pixel is determined to be the color of the polygon pixel combined with the color of the background pixel proportionately decreased by the extent of coverage of the polygon pixel, the extent of coverage of the composite pixel is determined to be the extent of coverage of the polygon pixel combined with the extent of coverage of the background pixel proportionately decreased by the extent of coverage of the polygon pixel, and the depth of the composite pixel set to the depth of the polygon pixel;

a frame buffer in the memory means for storing the composite pixels in the frame buffer; and

a graphic display control means for retrieving the pixels stored in the frame buffer and actuating the pixels on the graphic display at a color indicated by the color attribute and intensity indicated by the extent of coverage, to generate the graphic image on the graphic display.