Scan conversion is a computer graphics process in which geometrical objects such as lines and polygons are converted into pixel data for displaying on a raster device. Scan conversion can either operate in a simple “aliased” or more sophisticated “anti-aliased” mode.
In aliased mode, each display pixel is assigned one of two values according to whether it is classified as being inside or outside of the object being scan converted. It is well known that in this mode, “aliasing” effects can occur along the edges of objects, which give rise to “jagged” appearance. Techniques aimed at reducing or eliminating this effect are referred to as anti-aliasing techniques. They work by blending the object's colour with the colour of the background along pixels lying on the edges of the object to create smooth transitions between pixels lying outside and inside the object. Scan conversion methods that incorporate these techniques are said to be operating in “anti-aliased” mode.
Existing anti-aliasing techniques generally fall into one of three types: filtering, multi-point sampling, and area sampling. Filtering techniques work by applying a low-pass filter to the pixel values produced by an aliased scan conversion of an object to remove the high spatial frequency components that give rise to the “jagged” appearance of edges. Since this requires a matrix multiplication at each pixel, filtering techniques are computationally expensive. Filtering also has the effect of blurring horizontal and vertical edges that fall exactly on pixel boundaries that would otherwise appear sharp when scan converted using other anti-aliasing techniques, which may be undesirable.
In multi-point sampling, each pixel is sampled at several different locations at which tests are made to identify which of these points lie inside the object being scan converted. The pixel is then assigned a value based on the number of such points. Variations of this technique also exist where sampling is performed along several continuous horizontal or vertical line segments within each pixel instead of at discrete locations. The pixel is assigned a value based on the total length of these line segments that lie inside the object being scan converted.
A disadvantage of multi-point sampling is that it does not handle thin edges well. Consider the examples shown in FIG. 1 and FIG. 2. The object being scan converted in both cases is a thin, near-horizontal line 10. In FIG. 1, sampling is performed at nine equally spaced points within each pixel. The white and black circles represent sampling points that lie outside and inside of the line 10 respectively. It can be seen that since all sampling points in pixels 3 and 6 lie outside of the line 10, these pixels will be treated as if they lie completely outside of the line 10, and hence the scan converted line 10 will appear broken.
A similar problem exists in FIG. 2, where sampling is performed over three horizontal line segments per pixel denoted by the dotted lines. The portion of these dotted line segments that lie inside the line 10 being scan converted is highlighted in solid black lines in FIG. 2. Again, the scan converted line 10 will appear broken at pixels 3 and 6.
The third type of anti-aliasing technique is area sampling, where each pixel is assigned a value according to the percentage area of the pixel that falls inside the object being drawn. Its advantage over multi-point sampling is that it does not suffer from the problem illustrated in FIG. 1 and FIG. 2 that arise when scan converting thin lines. The overriding disadvantage of area sampling is that whilst straight lines and simple polygons can easily be handled, complex, self-overlapping (or self-intersecting) polygons pose a problem because of the computational intensive nature of processing such polygons. It has been suggested to convert these complex and/or self-overlapping polygon into a plurality of simple mutually exclusive non-intersecting polygons prior to area sampling. However, the procedure involved is potentially time consuming since it requires the calculations of the intersections between every pair of edges of the polygon. This has the disadvantage of adding an extra burden to the already costly area sampling process.
When scan converting a complex or self-overlapping polygon, it is necessary to select a fill rule. A polygon is a set of one or more closed curves each comprising of a number of vertices connected by straight line segments. Each closed curve is also known as a contour and has an associated direction. A polygon is said to be simple if it comprises of only a single contour, otherwise it is said to be complex. A polygon is also said to be self-overlapping or self-intersecting if one or more of its contours crosses over itself or over other contours. Examples of the possible different types of polygons are shown in FIGS. 3(A), 3(B), 3(C), and 3(D).
Odd-even and non-zero winding are two fill rules well known to those skilled in the art based on the winding count of a point. The winding count of a point is defined as follows: draw an arbitrary path from any point outside of the polygon to this point. Count the number of times a contour crosses the path from one side of the path to the other, and the number of times a contour crosses the path in the opposite direction. The winding count of the point is the obtained by subtracting the second number from the first.
When using the odd-even fill rule, points that have odd winding counts are considered to be inside the polygon and are hence filled with the polygon's colour and opacity, whilst points with even winding counts are considered to be outside the polygon and are not filled.
When using the non-zero winding fill rule, points that have zero winding counts are considered to be outside the polygon, whilst points with non-zero winding counts are considered to be inside the polygon.
The publication U.S. Pat. No. 6,084,596 discloses a third fill rule, called “winding-counting”. Unlike the non-zero winding fill rules, in which all pixels classified as being inside the polygon are rendered with uniform colour and opacity, winding-counting assigns an opacity value to a pixel according to its absolute winding count. More specifically, pixels with a zero winding count are classified as being outside the polygon and are not filled, and pixels with a +1 or −1 winding count are filled in the same manner as in the odd-even and non-zero winding rule.
The pixels with a winding count of n, where |n|>1, are rendered by performing |n| repeated rendering operations, each time using a pixel with the colour and opacity of the polygon. For fully opaque polygons, this produces identical results to the non-zero winding fill rule. For partially transparent, complex and/or self-overlapping polygons however, winding-counting gives the effect of the polygons being made up of several overlapping layers.
A comparison between the three fill rules is shown in FIGS. 4(a), 4(b), and FIG. 4(c). In FIG. 4(a), a partially transparent polygon is rendered using the odd-even fill rule. In (b) and (c), the same polygon is rendered using the non-zero winding and the winding-counting fill rules respectively. The centre region of FIG. 4(c) has a winding count of 2 and hence has been drawn with a higher opacity than the surrounding region.
However, the scan conversion method of the publication U.S. Pat. No. 6,084,596 suffers from “aliasing” effects.