Anti-aliasing

Anti -aliasing (AA), and anti -aliasing or anti-aliasing, is the reduction of unwanted effects that may be caused by the limited resolution pixel grid in generating computer graphics, such as aliasing or jaggies. Anti-aliasing the image content are commonly evaluated not only on pixels, but also at other positions ( sampled ) and included in the calculation of the pixel color. In addition, reduce some of the techniques developed for real-time rendering the staircase effect by subsequent filtering or tracing of the image.

Antialiasing methods differ in the distribution of the sampling points used for the pattern, as well as by the choice of the reconstruction filter, which determines how the calculated color values ​​at the sample points are weighted.

• 2.1 Practical aspects
• 2.2 Prefiltering and area sampling
• 2.3 Mail Filtering and point sampling

Background

Sampling and Prealiasing

The generation of a raster image from an image description by scanning or imaging is ultimately to assign a color to each discrete pixel. This procedure can be interpreted in the framework of the theory of signal processing and sampling of a signal. Computer graphics is unique in that many signals are present here as an abstract image descriptions, which can be evaluated algorithmically only at individual points. An example are images that are calculated by ray tracing. Such signals may also be referred to as a procedural signals.

Dithering without antialiasing an image description will be evaluated solely on the pixels; other points of the image does not flow into the color of the pixels with a. A problem with this method is that small figures are not covered by the pixel grid, and thus do not show up in the rasterized image. If small image details are arranged regularly, they interfere with the pixel grid, which leads to aliasing. This is illustrated by standing next to a computer-generated image of an infinitely large chessboard.

The period length of the signal is here equal to the size of two projected checkerboard fields. As soon as the period length is less than two pixel pitches, that is, the Nyquist frequency is exceeded, the signal is subsampled. Certain checkerboard fields are no longer detected by the pixel grid; the checkerboard pattern is destroyed. According to the Nyquist -Shannon sampling theorem, aliasing occurs, in which a high frequency in the original sample is expressed as a misleading low frequency: Near the horizon creates the false impression that the original signal would contain large odd fields. The illustrative term " picket fence effect" sometimes used in German makes this clear: Examine the spatial frequency spectrum of the original image by the playback device, such as the screen, fixed predetermined frequency resolution - the picket fence. This type of aliasing, which are a result of the sampling technique Prealiasing is called.

Even though the image would be charged with higher image resolutions and thus higher sampling rates, disturbing aliasing effects would show up near the horizon, but only from a higher frequency. The reason is that in the chess scene in the fields at the horizon are towards ever smaller and thus the spatial frequency is unlimited.

Reconstruction and post- aliasing

In the signal processing means the reconstruction of a discrete transformation into a continuous signal by interpolating between the individual sample values ​​by means of a reconstruction filter. In computer graphics, the term is interpreted somewhat differently, since no continuous signal is generated. Rather reconstruction means in this context, to calculate the color of a pixel from the color values ​​in the vicinity of the pixel, for example for scaling a raster image. The reconstruction filters used in this case is a two-dimensional function, which is centered on the pixel to be calculated, and indicates how the samples are weighted. Thus, in a conical filter directly on the pixels determined color value is weighted the highest, while more distant values ​​have less influence. Located outside of the support of the reconstruction filter color values ​​are ignored. The color value of the pixel is the sum of the weighted color values. This operation corresponds to a convolution with a low pass filter of an order of the selected anti-aliasing level.

Anti-aliasing means of box filter, which computes the average of all the color values ​​within a set around the pixel square is referred to as the " unweighted area sampling " ( Unweighted Area Sampling). In other cases, one speaks of " weighted area sampling " (Weighted Area Sampling). Examples of reconstruction filters with weighted area sampling, the Mitchell - Netravali filter ( bicubic filter), the Lanczos filter or Gaussian filter.

• Antialiasing with different reconstruction filters

Mitchell - Netravali filter with parameter choices B = C = ⅓

Lanczos filter with radius 2

A sampled discrete signal is a series of frequency- shifted copies of the information signal in the frequency domain. The reconstruction may be interpreted as the isolation of the original useful signal to the exclusion of the copies. When the reconstruction filter, not only the desired signal isolation, but also portions of the copies involving (see scheme right), there is post- aliasing. So Post aliasing caused by the choice of an inappropriate reconstruction filter and can occur even if the original signal was sampled with a sufficient sampling rate and without Prealiasing.

Staircase effect

The term aliasing refers to the edgy, " stair-like " appearance of rasterized figures. In the literature it is often claimed that the staircase effect is a consequence of aliasing. However, this is wrong as it can be shown by comparing the Fourier transforms of the ideal and the halftoned image. The staircase effect is not manifested by a high frequency appears as a disturbing low frequency, but is a direct consequence of the limited resolution of the output device. Especially in animations of the staircase effect is striking, since characters move here seems jerky and very thin or small objects seem to flicker in the movement.

Method

Without the use of anti- aliasing is sampled for each pixel only once at a pixel relative to the constant position. The anti-aliasing, the image description is evaluated at a plurality of and / or relative to the pixels of different positions. From the values ​​thus determined, the color of the pixel is calculated according to a reconstruction filter. By choosing a suitable sampling method can be Prealiasing, reduce or avoid by choosing suitable reconstruction filter mail aliasing. The term " anti-aliasing " is misleading, as anti-aliasing is applied not only to aliasing effects, but also against the aliasing and other undesirable effects, such as the pixel grid falling small figures. Franklin Crow delivered in 1977 the first description of aliasing as a cause of image artifacts in computer graphics.

The traditional antialiasing techniques of signal processing can not be transferred easily to the computer graphics. This is because from the viewpoint of signal processing considered computer graphics in contrast to eg audio signals have the following features:

• The occurring in computer graphics signals are artificial, abstract image descriptions that are often not captured in their entirety, but can be evaluated only at discrete points.
• Computer graphics usually contain hard object edges, which corresponds to locally infinite spatial frequencies. Therefore, a perfect reconstruction of the output signal by means of an ideal low-pass ( sinc filter) is not possible.
• Picture descriptions are often not regular, but sampled at irregularly distributed positions.
• The human visual perception is particularly sensitive to the problems caused by less good anti -aliasing methods are artifacts.

Practical aspects

This antialiasing has the best effect, it is essential to apply gamma correction. And polygon edges which were screened with anti-aliasing, but without gamma correction, a tendency to " rope-like " appearance. Anti -aliasing can also be combined with sub-pixel rendering to take advantage of the horizontal subdivision of a screen pixel into adjacent colors. In the pixel-art anti-aliasing is not automatic, but is achieved directly by setting individual pixels of a graphic designer.

Antialiasing requires additional computing power to complete, which is not particularly during real-time rendering negligible. Another disadvantage is that a generated image with anti-aliasing can be perceived as out of focus; the blur also depends on how other defects from the reconstruction filter used. Conversely, is the mere subsequent softening a halftoned image not a conventional anti-aliasing, since in this case the original image description is not evaluated; yet some techniques from the real- time domain based on such a procedure (see section hardware implementation ). Images that already have Prealiasing effects, such as low-resolution raster scanned pressure, can be corrected to some extent later in the frequency domain by eliminating the annoying Fourier components. There also exist methods to remove aliasing effects in images, which have been produced without anti-aliasing.

Prefiltering and area sampling

In computer graphics Prefiltering refers to the determination of the color of a pixel, will be made without that individual samples. Rather, the color is calculated directly from the image description. As described above, corresponds to the color value of a pixel of the reconstruction filter weighted by the sum of all the color values ​​of the objects to be overlapped by the support of the filter. Prefiltering is only possible with image descriptions whose convolution with the reconstruction filter is calculated analytically, ie can be expressed in terms of known functions. These include simple geometric objects such as lines. Prefiltering to procedural signals can not be applied, however, as they may only be sampled at specific points.

One of the first Prefiltering method for computer graphics has been described in 1978 by Edwin Catmull. His algorithm uses Unweighted area sampling. The color of a pixel is calculated by dividing the polygons that make up the image are clipped against the pixel and so the area ratio can be determined. This process was so slow that it could only be used in two-dimensional computer animations with some great polygons. Later methods tried to approximate the surface portions of the object fragments using bit masks - including Carpenter's A- buffer, sometimes called multi-sampling - or to use lookup tables. In addition, tailored anti-aliasing methods have been developed for the screening of basic shapes such as lines and circles, see rasterization of lines and screening of circles. Also Prefiltering quality antialiasing arbitrary curves with different reconstruction filters is possible.

Mail Filtering and point sampling

Post Filtering or supersampling is mainly applied when the image description can be evaluated only at discrete points. To several samples are used to calculate the color of each pixel, which are weighted by means of a reconstruction filter. Mathematically post filtering is a method for the numerical approximation of the convolution integral.

Multi -sampling methods differ in the number and distribution of sampling positions per pixel. When real- time rendering, the same pattern is usually used for all pixels. Some patterns set for the samples fixed weighted differently, which is why they can be considered as linear reconstruction filter. When the support of a reconstruction filter over several pixels ranges and several pixels share some samples, one speaks of sample sharing.

The following ordered patterns are commonly used:

In contrast to the ordered patterns, the scan pattern is varied in relation to the stochastic sampling pixels. Characterized aliasing be replaced by noise, which is perceived as less disturbing. At the same time, however, it is desirable to keep the sampling points far away from each other to ensure a representative sample as possible. Stochastic sampling pattern are mainly used in realistic image synthesis.

Another method is adaptive supersampling. The number of sampling points is varied over the image. The decision whether more samples should be made is based on local criteria like as contrast. Such techniques, however, are generally not expected true and can lead to artifacts.

Instead of distributing the sample points more or less evenly and to weight the values ​​determined there by a reconstruction filter can be applied for the calculation of pixel color importance sampling. Here, the samples are according to the shape of the reconstruction filter distributed (more sampling points close to the pixel) and equally weighted. This method leads to a less noisy result.

Hardware Implementation

For real-time rendering using graphics cards antialiasing can be implemented directly in hardware. First, only very high quality and expensive graphics cards supported this technique in graphics interfaces such as OpenGL. With the advent of affordable desktop graphics chips with high performance such as the 3dfx VSA - 100 or the Nvidia NV10 real-time anti -aliasing was also available for the normal user.

The conceptually simplest method is full-scene antialiasing ( FSAA). The images are rendered at a higher resolution and then downscaled. Another method uses the accumulation buffer. To render an image with four sample points per pixel, four successive pictures are written into the buffer, which are offset by a fraction of a pixel pitch in all directions. A variation of the accumulation buffer, the T buffer. It consists of two, four or more image - and Z - buffers, each of which can be used for rendering. A mask determines where a triangle is sent; at the end of all buffers are combined. If a screen offset is set individually for each buffer to anti-aliasing can be achieved by each triangle is sent in parallel to all buffers. The advantage of the accumulation buffer, and the T buffer, that is not only higher-level scanning positions are possible. Often so-called multi-sampling is used, which differs from supersampling, as shader calculations are not performed for each scan.

Prefiltering algorithm as well as the A buffer may be implemented in hardware. Were published more hardware-based Prefiltering algorithms, including the Z ³ method which was introduced in a similar way by the name of Matrox fragment antialiasing (FAA). The advantage of Prefiltering is that only those areas with polygon edges actually anti-aliasing is applied.

In practice, only a few samples per pixel and the box filter or simple linear reconstruction filters are used in the real-time anti -aliasing often. At least one graphics card, the Wildcat by 3Dlabs, used with jittering a stochastic sampling method. The professional SAGE graphics system from Sun Microsystems allows a 128 × 128 pixel -ranging, programmable scan patterns with weighted reconstruction filter.

Another method is supported by DirectX Edge antialiasing. Here, after rendering the scene, the object edges are traced in a second pass with smoothed lines. During deferred shading, a technique used in some newer computer games, the geometry of the objects is calculated regardless of their lighting. Since in this case no conventional hardware antialiasing is applicable, the staircase effect can be masked by edge detection and blur the edges of objects. A similar method is Morphological Anti-Aliasing ( MLAA ). This determines the pixel pattern on the edges of the type of blurring.

The perspective view of textures during real-time rendering is sometimes referred to as " texture antialiasing ". However, the techniques used, such as mip mapping and anisotropic filtering through no anti- aliasing in the usual sense, since no new images are generated from a mathematical description of picture. Rather, the texture mapping existing raster graphics are scaled perspective, except for procedural textures, which are calculated during the rendering process.