Abstract:
A method, using a filter function, generates an anti-aliased discrete image from a continuous image including an edge. The method defines a line sample. A progressive convolution is derived from the filter function and the line sample. A pixel at a predetermined location in the discrete image is selected, and the line sample is oriented with respect to the selected pixel. A distance is measured from a point in the continuous image corresponding to the selected pixel to the edge along the oriented the line sample. The progressive convolution is evaluated at the measured distance to produce a weighted coverage value, and the weighted coverage value is associated with the pixel to anti-alias the pixel in the discrete image.

Description:
FIELD OF THE INVENTION 
     The present invention relates generally to image processing, and more particularly to removing aliasing effects that occur when sampling a continuous image. 
     BACKGROUND OF THE INVENTION 
     There are a wide variety of computer applications which generate images. These applications include games, graphic design, animation, simulation, visualization, modeling, and the like. In these applications, the generated images should be as realistic as possible. 
     In computer graphics, a generated image is represented as a regular array of discrete samples of a continuous image. This “discrete image” is a result of sampling the continuous image at some fixed and finite rate. The individual sample points are referred to as pixels. It is critical to remember that a pixel is a sampling point, not a rectangular area in the discrete image. 
     Because the sampling rate is finite, high frequencies present in the continuous image can “alias” as incorrect low frequencies. Some common features in continuous images, such as edges, contain infinitely high frequencies, so any finite sampling rate will invariably lead to aliasing. In computer-generated images, the aliasing appears as stair-stepped contours of image objects, i.e., so called “jaggies.” Other aliasing effects can cause moire patterns and the break-up of fine details. 
     Anti-aliasing is used to improve the appearance of discrete images. Anti-aliasing is accomplished by computing and sampling a convolution of the continuous image with some frequency-limiting filter. The pixels are samples of the filtered version of the continuous image. There are two common methods used to compute the samples of this convolution in the prior art: area sampling and point sampling. 
     Area Sampling Anti-aliasing 
     Area sampling anti-aliasing uses a processed but still continuous form of the continuous image to exactly compute the convolution of an anti-aliasing filter function and this continuous image. This convolution is sampled to produce a value to be used while determining a pixel in the discrete image. Typically, the filter function is a Gaussian filter having a radius R. The radius defines the “footprint” or “support” of the filter. 
     The processed form of the continuous image used by area sampling is usually a set of polygons visible in the filter footprint around each pixel. Unfortunately, in many cases the continuous image is defined by a three-dimensional scene description including geometric objects which can occlude or intersect one another. These occlusions and intersections make it difficult to efficiently process the continuous image into a form suitable for area sampling because complicated shapes can result from the interaction of even simple objects. 
     Point Sampling Anti-aliasing 
     Point sampling anti-aliasing uses multiple point sample locations in the vicinity of a pixel. The continuous image is evaluated at points corresponding to the pixel locations, and the resulting values are combined according to some weighting function in an attempt to approximate the convolution of the filter with the continuous image. Point sampling is the most common method used for anti-aliasing because of its simplicity and ease of implementation. Point sampling simplifies the occlusion problem present in area sampling of three-dimensional scenes, but suffers from slow convergence to the correct solution. 
     In general, N point samples are required to compute the value of a pixel with an accuracy of 1/N. Because the point sample locations are separated from each other and not connected, fine details can be missed entirely in the sampling. Consequently, the missed details fail to contribute to the discrete image. 
     Combined Point and Area Sampling 
     Area and point sampling methods are often combined in rendering systems. Area sampling can be applied efficiently to two-dimensional sampled images, such as texture maps, while point sampling is generally used to anti-alias the edges and intersections of polygons. Point sampling is used to generate weighted coverage values (WCVs) for polygons that lie within the filter footprint of some pixel, which are then associated with that pixel. A WCV is the result of the convolution of the visible portion of a polygon with the anti-aliasing filter at a pixel that weights the color contribution of that polygon to the color of that pixel. An area sampling method is used to produce colors for the polygons, which are also associated with that pixel. The WCVs and colors associated with that pixel are then combined to produce the final color for the pixel in the discrete image. 
     Other Anti-aliasing Method 
     Max, in “Anti-aliasing Scan-Line Data,” IEEE Computer Graphics &amp; Applications, 10(1): 18-30, January 1990, describes a hybrid method. His hybrid method provides continuous anti-aliasing in one direction, by approximating area sampling, while using supersampling to anti-alias the other direction. Edges that run substantially parallel to the continuous direction are anti-aliased less effectively than edges that are substantially perpendicular to the continuous direction. 
     Accordingly, there are numerous drawbacks and disadvantages of prior art area and point sampling anti-aliasing methods. Therefore, there is a need to provide an improved anti-aliasing method without a large increase in memory or a decrease in drawing speed while generating discrete images. 
     SUMMARY OF THE INVENTION 
     The invention provides a method that uses a filter function to generate an anti-aliased discrete image sampled from a continuous image including an edge. The method defines a line sample. A progressive convolution is derived from the filter function and the line sample. A pixel at a predetermined location in the discrete image is selected, and the line sample is oriented with respect to the selected pixel. 
     A distance is measured from a point in the continuous image corresponding to the selected pixel to the edge along the oriented line sample. The progressive convolution is evaluated at the measured distance to produce a weighted coverage value, and the weighted coverage value is associated with the pixel to anti-alias the pixel in the discrete image. 
     In one aspect of the invention, only visible edges are anti-aliased, and only pixels within a predetermined distance from the edge are considered, for example, the distance is less than or equal to a length of the line sample. 
     In another aspect of the invention, the line sample is straight, centered on the pixel, and substantially perpendicular to the edge. 
     In yet another aspect of the invention, the filter function is a Gaussian function, and the progressive convolution is a cumulative integral of the filter function for various distances. The progressive convolution can be defined by a continuous function, or alternatively, the values of the progressive convolution are stored in a table for a finite number of distances. 
     In yet another aspect of the invention, multiple line samples are defined for each pixel and the weighted coverage values of the line samples are combined to produce a combined weighted coverage value which is associated with the pixel. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIGS. 1 a - 1   e  are diagrams of a filter footprint for line samples centered on a pixel at various distances to an edge of a graphic object; 
     FIG. 1 f  is a graph of a filter function; 
     FIG. 2 is a graph of a progressive convolution; 
     FIG. 3 a  is a diagram of a line sample intersecting two edges of an object; 
     FIG. 3 b  is a graph showing segment information; 
     FIG. 3 c  is a graph showing a difference of two evaluations of the progressive convolution; 
     FIGS. 3 d - 3   f  are diagrams of the difference between two coverage evaluations; 
     FIGS. 4 a - 4   c  are diagrams of line sampling occluding objects; 
     FIGS. 5 a - 5   c  are diagrams of line sampling intersecting objects; 
     FIGS. 6 a - 6   b  are diagrams of a line sample oriented parallel to an edge; 
     FIGS. 7 a - 7   b  are diagrams of line sampling using two orthogonal line samples; 
     FIG. 8 is a diagram of line sampling visible and non-visible edges of adjoining objects; 
     FIG. 9 is a diagram of line sampling visible and non-visible edges of occluding objects; 
     FIGS. 10 a - 10   b  are diagrams of weighting multiple line samples for line sampling according to a normalized edge vector; 
     FIGS. 11 a - 11   b  are diagrams of line sampling data generation at pixel grid positions; 
     FIG. 12 is a diagram of line sampling a bounding curve with an orientation perpendicular to a tangential direction; and 
     FIG. 13 is a diagram of line sampling using a low resolution image and edge detection. 
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     The present invention uses line samples to provide an improved method for generating weighted coverage values (WCVs) that can be used to anti-alias a discrete image. The WCVs are the result of a convolution of a visible portion of a polygon with an anti-aliasing filter at a pixel that weights the color contribution of that polygon to the color of that pixel. 
     Line sampling according to the invention lies between area and point sampling methods of the prior art in terms of efficiency and accuracy. The line sampling method of the present invention can be used for calculating WCVs from shape information, i.e., edges, occlusions and intersections, and can be combined with area sampling of shade information, i.e., color and texture as in the prior art. Therefore, the present invention enables the production of high quality anti-aliased images. 
     The key insights underlying line sampling rely on the following properties. The convolution of a finite filter and a straight edge can be efficiently and accurately determined given the intersection of the edge with a line sample at least spanning the footprint of the filter having an orientation substantially perpendicular to that edge. In addition, occlusion and intersection determinations are much simpler to perform on line samples than on area samples. This is true because these interactions produce less complicated primitives. In addition, occlusions can be resolved for large sections of a line sample with a single calculation. These properties give line sampling better convergence than point sampling, and accuracy similar to area sampling but at a lower computational cost. 
     Efficiently computing convolutions with line samples requires deriving a progressive convolution (PC) from the desired filter function. If the desired filter function is radially symmetric, then a single PC suffices for all line sample orientations. Otherwise, a PC must be determined for each possible line sample orientation, or at a sufficient number of separate orientations to allow interpolation at other, intermediate orientations. The determination of a PC according to the invention is shown in FIGS. 1 and 2. 
     As shown diagrammatically in FIG. 1, a pixel  100  is located at various distances, e.g., −1.5, −0.8, 0.0, +0.8, and +1.5, from an edge  101  of a graphic object  104  with a shaded interior. A footprint of a filter function, see FIG. 1 f , centered at the pixel is indicated by a circle  102 . The footprint is the “support” of the filter function, i.e., the area where the filter function has non-zero values. 
     The graph  103  of FIG. 1 f  is an example Gaussian filter function that represents the values produced by the filter with the x-axis indicating the distance from the pixel, and the y-axis the intensity (I) of the function. It should be understood that other filter functions can be used by the present invention. 
     The pixel and edge are shown at multiple distances from each other. The line segment  105  represents a line sample according to the invention. Preferably, the line sample is straight and centered on the pixel, the orientation of the line sample is selected to be perpendicular to the edge  101 , and the length of the line sample  105  at least spans the diameter of the footprint  102 . 
     It should be understood that the line sample can have other linear configurations, for example, a circle, a Bezier curve, etc. It should also be understood that the line sample can have other positions, lengths and orientations. The placement of the line sample can be off-center, or near the pixel when this is computationally advantageous. 
     FIG. 2 shows a PC  200  derived from the filter function  103 . Distances for pixels outside the object are indicated by negative numbers, the distance of a pixel on the edge of the object is zero, and distances for pixels inside the object are positive. The distances are shown along the x-axis  201 . The weighted coverage values of the PC are along the y-axis  202 . The WCVs are in the range 0.0 to 1.0. For example, if the pixel is located on the edge, then the WCV of the PC is 0.5 indicating half coverage of the filter footprint  102  by the edge  101 . When the filter footprint is located entirely inside the object there is full coverage, and there is no coverage when the filter footprint is entirely outside the object. The value of the PC  200  decreases from 0.5 to zero as the pixel moves away from the edge, and increases from 0.5 to one as the pixel moves in the opposite direction. Full coverage represents the area under the curve  103  of FIG. 1 f . Essentially, the progressive convolution according to the invention expresses cumulative integrals of the filter function for various distances from the edge. 
     The PC  200  derived from the filter  103  convoluted with the edge  101  can be efficiently evaluated. If the filter is simple, then the PC  200  can be functionally evaluated as needed. When the filter is complex, some subset of the values of the PC  200  at varying distances from the edge can be precomputed and stored in a table for interpolation at intermediate distances. In a tabular form, the PC is indexed by the distance, and intermediate values can be interpolated. Although the PC  200  of FIG. 2 shows WCVs for all possible distances, i.e., from negative infinity to positive infinity, it should be understood that in a practical application, the WCV varies only over a very small range of distances, i.e., −2.0 to +2.0, where one unit is equal to the spacing between pixels. 
     If the filter is radially asymmetric, then PCs can be generated for each line sample orientation. However, in practice, most commonly used filters have a simple structure and are radially symmetric, which obviates the need for tables and allows a single PC to suffice for all line sample orientations. 
     FIGS. 3 a-f  show how a desired convolution of an object and a PC for a desired filter can be efficiently and accurately determined with a line sample according to the invention. An object  300  has edges a, b  301 - 302 . A line sample  303  is centered on a pixel  304  located between the edges a,b  301 - 302 . The line sample  303  has endpoints e 1   305  and e 2   306 . The desired convolution is the WCV for the object  300  at the pixel  304 . The line sample  303  spans the filter footprint  309 . As shown, the line sample  303  is oriented substantially perpendicular to the multiple edges a, b. The distances d 1    307  and d 2    308  indicate respectively the relative distances between the pixel and edges a and b along the line sample  303 . 
     The graph  310  of FIG. 3 b  shows segment information for the intersection of the object  300  with the line sample  303 . The relative positions of the edge intersections along the line sample determine a segment  320  on the line sample bounded by the two distances d 1  and d 2 . The exact convolution of the interior of the object  300  with the filter  306 , shown in FIG. 3 d , can be evaluated as the difference in the convolution of the filter with edge b, as shown in FIG. 3 e  and the convolution of the filter with edge a as shown in FIG. 3 f . As shown in FIG. 3 c , this difference is equivalent to the difference  331  between the values of the PC  330  evaluated at d 2  and d 1 . This difference is exactly the WCV for the object  300  at the pixel  304 . 
     The extension of the method shown in FIG. 3 to more than two edges would be obvious to one of ordinary skill in the art. 
     Occlusion and intersection of multiple polygons can produce very complex shapes when some polygons partially occlude or intersect each other. This is true even with simple polygons such as triangles. Determining the anti-aliasing convolution along a line sample, rather than for an area sample of the prior art, simplifies the problem significantly for occlusion as shown in FIGS. 4 a - 4   c , and for intersection as shown in FIGS. 5 a - 5   c.    
     In FIG. 4 a , a polygon a  401  partially occludes a polygon b  402 . FIG. 4 b  shows example depth information (Z)  403  along a line sample  404  for the segments corresponding to polygons a, b. Where the line sample overlaps both a and b, occlusion occurs. This occlusion can be resolved by comparing the depth information at all points on the line sample and retaining only the information for the segment with the smallest depth at each point, and discarding the information for the segment with the largest depth at each point. Along line samples, occlusion can be resolved for entire sections of segments efficiently. Such occlusion might truncate or split existing segments. FIG. 4 c  shows the result of the occlusion of a and b along the line sample  404 . The occlusion for an entire section  405  in  4   b  has been resolved by selectively retaining and discarding, leaving the remainder  406  in FIG. 4 c.    
     FIG. 5 a  shows polygons a  501  and b  502  intersecting each other. FIG. 5 b  shows depth information (Z)  503  along a line sample  504  for the segments corresponding to polygons a, b. The intersection of the two polygons results in a corresponding intersection  505  in the depth information for the corresponding segments. This intersection can be located and used to resolve the mutual occlusion of a and b by selective retaining and discarding based on depth information as described above. The intersection of segments might also truncate or split existing segments as above. The result of this intersection and occlusion is shown in FIG. 5 c.    
     Line sampling provides a more accurate determination of the anti-aliasing filter convolution than point sampling. For instance, N point samples provide accuracy proportional to roughly 1/N. A line sample oriented perpendicular to an edge calculates the convolution for that edge with perfect accuracy, and with reasonable accuracy when the line sample and edge are oriented substantially perpendicular to each other. 
     If the line sample and the edge are oriented parallel to each other, then the line sample acts as a single point sample as shown in FIGS. 6 a  and  6   b . In the FIG. 6 a , a line sample  600  is centered on a pixel  603 , and oriented parallel to an edge  601  of an object  602 . Here, there is no coverage between the line sample and the object (WCV=0). A slight change in the position of the edge, i.e., as soon as the object covers the line sample, causes a drastic change in the appearance from no coverage to full coverage (WCV=1) as shown in FIG. 6 b.    
     For this reason, it is beneficial to either take multiple line samples with different orientations and combine their resulting WCVs, or to choose the orientation of line samples depending on the orientation of edges in the continuous image. 
     Using multiple line samples requires a method for weighting the contributions of the individual line samples. One method weights the contributions equally, averaging the values from the line samples to produce the end result. Better approximations of the convolution are generated by weighting the line samples based on some measure of how well they are oriented for sampling the edges in the underlying continuous image as described below. 
     It is possible to determine the convolution with sufficient accuracy for edges of any orientation with two line samples that are perpendicular to each other. The weights for the contribution of each sample can then be determined based on several criteria. The relative orientation of each edge and the line samples that intersect that edge can be considered. The number of edges that intersect each line sample can be a factor. The variance, or other statistical measure, of the visible segments of the line sample can be used. 
     In FIG. 7 a , two line samples  701  and  702  for a pixel  709  are arranged perpendicular to each other. Line sample  701  partially intersects an object  700 , and line sample  702  is completely outside the object. The segment information corresponding to object  700  for the line samples  701  and  702  is respectively shown in graphs  704  and  705 . In FIG. 7 b , the object  700  has moved relative to the line samples  701  and  702 . Line sample  702  is entirely within the object  700 , and a larger portion of line sample  701  intersects object  700 . 
     The respective segment information is shown in graphs  706  and  707 . The edge  708  is anti-aliased more accurately by the line sample  701  because of its perpendicular orientation to the edge. The line samples  701  and  702  compute two WCVs for the object  700  at the pixel  709 . Because the edge  708  is anti-aliased more accurately by line sample  701 , the computed WCV from line sample  701  should contribute more to the combined WCV for object  700  at pixel  709  than the WCV computed by line sample  702 . 
     As shown in FIG. 8, it is useful to limit the consideration of edges affecting sample weights along a line sample  803  only to those edges that are “visible.” Visible edges  801  are the edges that are produced by the edge of a polygon not matched (in, for example, color) by another polygon (of the same color), or an occlusion, or an intersection. An edge  802  that occurs where two polygons of the same color join is not as likely to be visible in the generated image, and therefore should be treated as “non-visible” to prevent those edges from affecting the weighting of line samples that intersect them. For instance, an object made up of multiple adjoining polygons should have the edges making up its silhouette anti-aliased according to the orientation of those silhouette edges without the interior edges between polygons affecting the result. 
     FIG. 9 shows a polygon a  901  partially occluding another polygon b  902 . An edge  903  of polygon  901  is not matched by an edge of polygon  902 . The edge  903  is visible in the discrete image, and should affect the anti-aliasing calculation. Therefore, edge  903  should be treated as a visible edge for the purposes of calculating sample weights using line sample  904 . 
     FIG. 10 a  shows how weights can be determined for two perpendicular, axis-aligned line samples  1001  and  1002  near an edge  1003  of an object  1000 . Here, the orientation of the edge  1003  is not perpendicular to either line sample  1001 - 1002 . A vector running along the edge  1003  can be calculated. FIG. 10 b  shows edge vector  1004  for the edge  1003 , with a horizontal component V x    1005  and a vertical component V y    1006 . 
     The method first determines the normalized vector (V nx , V ny ) for each visible edge that intersects either of the line samples. Then, for a normalized edge vector with components ( nx , V ny ), add V nx   2  to the total weight of the vertical sample, and add V ny   2  to the total weight of the horizontal sample. The squares of the values of the components are used to keep the total contribution of any edge equal to unity. After all of the contributions of the relevant edges have been weighted, the relative weights of the vertical and horizontal line samples can be determined, and the relative weights are used to blend the WCVs of the two line samples. The blending can use any suitable blending function, such as linear blending, cubic blending, or the selection of the WCV with greater weight. 
     As shown in FIG. 11 a , it is possible to use conventional rasterization techniques to speed up line sample evaluation for two perpendicular, axis-aligned line samples. In FIG. 11 a , it is desired to sample at pixel  1101  of a pixel grid  1100  with line samples  1102  and  1103 . When using an anti-aliasing filter with a radius equal to the distance between pixels, which is a common choice, fast rasterization techniques currently used for point sampling can also be used to generate edge distance values at the line sample endpoints  1109 , which lie exactly on pixel grid locations. The edge distance value for a line sample endpoint and an edge is defined as the shortest distance between the line sample endpoint and that edge. 
     As shown in FIG. 11 b , the “solid” pixels  1104  are used, and the “open” pixels  1105  are not used for the line samples  1102  and  1103 . Pineda arithmetic can be used to efficiently generate the edge distance values for polygons in the image at the line sample endpoints, see Pineda, “A Parallel Algorithm for Polygon Rasterization,” Proceedings of SIGGRAPH, Computer Graphics, Vol.22. NO.4, pp. 17-20, 1988. Since these edge distance values vary linearly in the image, segments for line samples can be efficiently generated using basic geometric or algebraic methods (e.g., similar triangles) given only the edge distance values at the endpoints of the line samples. Segments are the portion of the line sample where the edge distance values are all positive. 
     Line samples can be generated for entire rows and columns of pixels in the discrete image using conventional scan-line rasterization techniques. Using these techniques, all visible segments on a line spanning the entire continuous image can be generated. A line sample for a pixel, with the same orientation as the line spanning the entire continuous image, is then generated by considering the portion of the visible segments within the filter footprint of the pixel. 
     If information about the edges in the underlying continuous image is known, then a single line sample per pixel with the correct orientation is sufficient to properly generate WCVs for pixels sampling that image. The edge information can be taken from the continuous image itself. For example as shown in FIG. 12, many objects  1200 , e.g., fonts, are specified by bounding curves  1201 . Tangent information  1202  for a curve  1203  can be computed from the curve description. Line sample  1205  is oriented perpendicularly to the direction of the tangent  1202 . 
     In an alternative method shown in FIG. 13, a low resolution point sampled image  1302  is generated from a continuous image  1301 . The low resolution image  1302  is processed with an edge detection operator to generate edge information  1303 . The detected edges  1303  indicate orientations of appropriate line samples  1304 . The properly oriented line samples are then applied to the continuous image to produce the WCVs used to generate an anti-aliased discrete image  1305 . 
     While this invention has been described in terms of a preferred embodiment and various modifications thereof for several different applications, it will be apparent to persons of ordinary skill in this art, based on the foregoing description together with the drawing, that other modifications may also be made within the scope of this invention, particularly in view of the flexibility and adaptability of the invention whose actual scope is set forth in the following claims.