Antialiasing of silhouette edges

• US 5,742,277 A
• Filed: 10/06/1995
• Issued: 04/21/1998
• Est. Priority Date: 10/06/1995
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Gossett, Carroll Phillip, Van Hook, Timothy J.
• Primary Examiner(s): SARAS, STEVEN J
• Application Number:
  US08/539,956
• Time in Patent Office: 928 Days
• Field of Search: 345/136, 345/137, 345/138, 345/145, 345/199, 345/114, 395/131, 395/135, 395/129, 395/122
• US Class Current: 345/611
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 2200/12 involving antialiasing
• CPC Class Codes: G06T 3/403 Edge-driven scaling; Edge-based scaling

Abstract

A system and method for antialiasing silhouette edges are described herein. A video interface accesses the frame buffer to retrieve a foreground color of an edge pixel that falls on the silhouette edge. The video interface estimates a background color of the edge pixel based on foreground colors of neighboring pixels that are proximate to the edge pixel. Then, the video interface interpolates between the foreground color and the estimated background color to determine an output color of the edge pixel. Also described herein are a system and method of internal edge antialiasing.

Claims

1. A method of antialiasing a silhouette edge, the silhouette edge representing an edge of a polygon which is coincident with an edge of a surface on which the polygon is located, the method comprising the steps of:

(1) retrieving a color value for a silhouette edge pixel which falls on the silhouette edge from a frame buffer, the retrieved color value representing a color of one or more foreground polygons which fall within the silhouette edge pixel;

(2) estimating a background color of the silhouette edge pixel based on colors of neighboring pixels that are proximate to the silhouette edge pixel, the estimated background color representing a color of a portion of the silhouette edge pixel which is not occupied by the one or more foreground polygons; and

(3) determining an output color of the silhouette edge pixel by interpolating between the retrieved color and the estimated background color.

2. The method of claim 1, wherein step (1) comprises:

(a) prior to retrieving the color for the silhouette edge pixel from the frame buffer, storing in the frame buffer only information associated with the one or more foreground polygons and not storing color information associated with any background polygons.

3. The method of claim 1, wherein step (2) comprises the steps of:

(a) identifying neighboring pixels of the silhouette edge pixel;

(b) rejecting any of the neighboring pixels which are silhouette edge pixels;

(c) determining a penultimate maximum value and a penultimate minimum value for each color component of the neighboring pixels which were not rejected in step (b); and

(d) estimating the background color of the silhouette edge pixel based on the retrieved color, the penultimate maximum value of each non-rejected neighboring pixel and the penultimate minimum value of each non-rejected neighboring pixel.

4. The method of claim 3, wherein step (c) comprises the steps of:

(i) generating a list of color values for each color component of the neighboring pixels which were not rejected in step (b);

(ii) rejecting a maximum color value and a minimum color value contained in each of the lists; and

(iii) for each of the lists, setting the penultimate maximum value equal to a remaining maximum value in each of the lists and setting the penultimate minimum value equal to a remaining minimum value in each of the lists.

5. The method of claim 4, wherein step (d) comprises the steps of:

(i) generating a color value sum for each color component of the non-rejected neighboring pixels by adding the penultimate maximum value for each of the color components of the non-rejected neighboring pixels to the penultimate minimum value for each of the color components of the non-rejected neighboring pixels; and

(ii) estimating the background color of the silhouette edge pixel by subtracting a color value of each color component of the retrieved silhouette edge pixel color from a corresponding color value sum of the non-rejected neighboring pixels.

6. The method of claim 1, wherein step (3) comprises the steps of:

(a) retrieving a coverage value stored in the frame buffer representing an area of the silhouette edge pixel occupied by the one or more foreground polygons; and

(b) determining the output color of the edge pixel as follows;

retrieved silhouette edge pixel coverage value*retrieved silhouette edge pixel color)+(1-retrieved silhouette edge pixel coverage value)*estimated background color.

7. The method of claim 4, wherein step (d) comprises the steps of:

(i) determining a maximum color value by selecting the larger of the retrieved silhouette edge pixel color and the penultimate maximum value;

(ii) determining a minimum color value by selected the smaller of the retrieved silhouette edge pixel color and the penultimate minimum value;

(iii) determining an average color by averaging the maximum color value with the minimum color value for each color component;

(iv) determining a difference value by subtracting the average color from the retrieved silhouette edge pixel color;

(v) estimating the background color of the silhouette edge pixel by multiplying the difference value by two and subtracting the result from the retrieved silhouette edge pixel color.

8. A method of antialiasing an internal edge and a silhouette edge, the internal edge representing coincident edges of same-surface polygons which edges are not coincident with an edge of the same-surface, the silhouette edge representing an edge of a polygon which is coincident with an edge of a surface on which the polygon is located, the method comprising the steps of:

(1) determining if a portion of a new polygon which falls within a pixel is in a same surface with a portion of an existing polygon which falls within the pixel and for which information is stored in a frame buffer entry associated with the pixel; and

(2) if the portion of the new polygon and the portion of the existing polygon are in the same surface, then antialiasing the pixel as an internal edge pixel;

wherein step (2) comprises the steps of;

(a) retrieving a coverage value from the frame buffer entry, the retrieved coverage value representing an area of the internal edge pixel which is occupied by the portion of the existing polygon which falls within the internal edge pixel;

(b) generating a new coverage value by summing the retrieved coverage value with a coverage value of the new polygon representing an area of the internal edge pixel which is occupied by the portion of the new polygon which falls within the internal edge pixel;

(c) storing the new coverage value in the frame buffer entry;

(d) generating a new color value by averaging a color value of the portion of the new polygon and a color value of the portion of the existing polygon proportional to their respective coverage values; and

(d) storing the new color value in the frame buffer entry.

9. The method of claim 8, wherein step (1) comprises the steps of:

(a) determining a Z-range of the portion of the existing polygon by reference to a Z value and a delta Z value associated with the portion of the existing polygon;

(b) determining a Z-range of the portion of the new polygon by reference to a Z value and a delta Z value associated with the portion of the new polygon; and

(c) determining that the portion of the new polygon and the portion of the existing polygon are in the same surface if the Z-range of the portion of the new polygon overlaps with the Z-range of the portion of the existing polygon.

10. The method of claim 8, further comprising the steps of:

(3) if it is determined in step (1) that the portion of the new polygon and the portion of the existing polygon are not in the same surface, then determining whether the portion of the new polygon is in a surface which is in front of a surface containing the portion of the existing polygon;

(4) if the portion of the new polygon is in a surface which is in front of a surface containing the portion of the existing polygon, then storing a coverage value and a color value for the portion of the new polygon in the frame buffer entry; and

(5) if the portion of the new polygon is not in a surface which is in front of a surface containing the portion of the existing polygon, then rejecting information associated with the portion of the new polygon for the internal edge pixel.

11. The method of claim 8, further comprising the steps of:

(3) retrieving a color value stored for a silhouette edge pixel from the frame buffer, the retrieved color representing a color of one or more foreground polygons which fall within the silhouette edge pixel;

(4) estimating a background color of the silhouette edge pixel based on colors of neighboring pixels which are proximate to the silhouette edge pixel, the estimated background color representing a color of a portion of the silhouette edge pixel which is not occupied by the one or more foreground polygons; and

(5) interpolating between the retrieved color and the estimated background color to determine an output color of the silhouette edge pixel.

12. A system for antialiasing a silhouette edge, the silhouette edge including an edge of a polygon which is coincident with an edge of a surface on which the polygon is located, comprising:

a frame buffer for storing pixel color information; and

a video interface for antialiasing silhouette edge pixel data stored in said frame buffer, comprising;

frame buffer accessing means for accessing said frame buffer to retrieve a color of a silhouette edge pixel;

background color estimating means for estimating a background color of the silhouette edge pixel based on colors of neighboring pixels that are proximate to the silhouette edge pixel; and

means for generating an output color for the silhouette edge pixel based on the retrieved color and the estimated background color, comprising means for interpolating between the retrieved color and the estimated background color.

13. The system of claim 12, wherein said frame buffer only stores foreground polygon information and does not store background polygon information.

14. The system of claim 12, wherein said background color estimating means comprises:

means for identifying neighboring pixels of the silhouette edge pixel;

means for rejecting any of the neighboring pixels which are silhouette edge pixels;

penultimate identifying means for identifying a penultimate maximum value and a penultimate minimum value for each foreground color component of the neighboring pixels that were not rejected by said means for rejecting neighboring pixels; and

estimating means for estimating the background color of the silhouette edge pixel based on the retrieved color of the silhouette edge pixel, the penultimate maximum value and the penultimate minimum value.

15. The system of claim 14, wherein said penultimate identifying means comprises:

means for generating a list of color values for each retrieved color component of the neighboring pixels which were not rejected by said means for rejecting neighboring pixels;

means for rejecting a maximum color value and a minimum color value contained in each of the lists;

means for setting a penultimate maximum value equal to a remaining maximum value in each of the lists; and

means for setting a penultimate minimum value equal to a remaining minimum value in each of the lists.

16. The system of claim 15, wherein said estimating means comprises:

means for adding the penultimate maximum value to the penultimate minimum value for each foreground color component of the neighboring pixels which were not rejected by said means for rejecting neighboring pixels to obtain a color value sum for each color component of the neighboring pixels; and

means for subtracting a color value for each retrieved color component of the silhouette edge pixel from the corresponding color value sum for each color component of the neighboring pixels to obtain a difference value for each color component for use in estimating a color value for a corresponding background color component of the silhouette edge pixel.

17. The system of claim 12, further comprising:

means for accessing the frame buffer to retrieve a coverage value of the silhouette edge pixel;

wherein said means for generating an output color for the edge pixel further comprises means for performing the following calculations;

retrieved silhouette edge pixel coverage value*retrieved silhouette edge pixel color)+(1-retrieved silhouette edge pixel coverage value)*estimated background color.

18. A system for antialiasing an internal edge and a silhouette edge, the internal edge representing coincident edges of same-surface polygons which edges are not coincident with an edge of the same-surface, the silhouette edge representing an edge of a polygon which is coincident with an edge of a surface on which the polygon is located, comprising:

a blend unit for antialiasing an internal edge, comprising;

same surface determining means for determining if a new polygon being rendered and an existing polygon stored in said frame buffer are in a same surface; and

internal edge antialiasing means for antialiasing an internal edge pixel comprising;

means for generating a new coverage value for the internal edge pixel comprising means for summing a coverage value of the new polygon for the internal edge pixel and a coverage value of the existing polygon for the internal edge pixel as stored in a frame buffer entry of the frame buffer;

means for storing the new internal edge pixel coverage value in the frame buffer entry;

means for generating a new internal edge pixel color value by averaging a color value of a portion of the new polygon which falls within the internal edge pixel and a color value of a portion of the existing polygon which falls within the internal edge pixel proportional to respective coverage values of the new polygon and the existing polygon; and

means for storing the new internal edge pixel color value in said frame buffer entry; and

a frame buffer for receiving pixel information from said blend unit.

19. The system of claim 18, wherein said same surface determining means comprises:

means for determining a Z-range of the portion of new polygon which falls within the internal edge pixel by reference to a Z value and a delta Z value associated with the portion of the new polygon;

means for determining a Z-range of the portion of the existing polygon which falls within the internal edge pixel by reference to a Z value and a delta Z value associated with the portion of the existing polygon; and

means for determining that the portion of the new polygon and the portion of the existing polygon are in the same surface if the Z-range of the portion of the new polygon overlaps with the Z-range of the portion of the existing polygon.

20. The system of claim 18, wherein said blend unit further comprises:

means for determining whether the portion of the new polygon is in a surface which is in front of a surface containing the portion of the existing polygon if it is determined that the portion of the new polygon and the portion of the existing polygon are not in the same surface;

means for storing a coverage value and a color value of the portion of new polygon in the frame buffer entry associated with the internal edge pixel if the portion of the new polygon is in surface which is in front of a surface containing the portion of the existing polygon; and

means for rejecting information associated with the portion of the new polygon if the portion of the new polygon is not in the surface which is in front of a surface containing said existing polygon and is not in the same surface.

21. The system of claim 18, further comprising a video interface comprising:

means for retrieving a color for a silhouette edge pixel from the frame buffer;

means for estimating a background color of the silhouette edge pixel based on colors of neighboring pixels which are proximate to the silhouette edge pixel; and

means for interpolating between the retrieved color and the estimated background color to determine an output color of silhouette edge pixel.