Sampling Problems And Antialiasing
Ray tracing is a point sampling process; the rays used to assess light intensities are infinitely thin. However, each pixel of a rendered image has a finite width. Ray tracing in its basic form overcomes this incompatibility by tracing a single primary ray through the centre of each pixel and using the colour of that ray as the colour of the entire pixel.
Since the resultant colour of each pixel is based upon one infinitely small sample taken within the centre of each pixel and because pixels occur at regular intervals frequency based aliasing problems often arise. Aliasing refers to the inclusion of characteristics or artefacts in an image that could have come from more than one scene description.Example
The scene descriptions below both (a) and (b) lead to the same rendered image in (c). The scene in (a) and (b) consist of vertical bands of different widths, the dotted lines represent the pixel boundaries.
This is the most prevalent form of aliasing and occurs in regions of abrupt change in intensity. Examples of such regions are object or shadow boundaries or the boundaries of sharp highlights. The next figure illustrates the staircasing effect. (a) shows an example object as it should appear and (b) shows the rendered result. The dashed lines in are the pixel boundaries.. Most of the pixels spanning the object's boundaries end up being shaded incorrectly as either wholly within the object or not at all within the object. Note also that there are an infinite number of polygons which would generate the image in (b)
Another important aliasing problem occurs across whole regions of an image in which constituent objects alternate at a high frequency. The samples taken by a ray tracer can sometimes generate images containing what are called Moiré interference patterns. The following shows an example rendered image that contains Moiré interference patterns.
Antialiasing is the name given to the process that attempts to eliminate or reduce the impact of aliasing artefacts in rendered images. Antialiasing algorithms can be classified as either analytic or discrete.
Analytic algorithms perform a thorough analysis of the elements of a scene and filter out any high frequencies prior to sampling. Although very effective, these algorithms tend to be complicated and time consuming, requiring expensive analysis of the geometrical properties of the objects involved.
Discrete methods such as ray tracing treat a scene as a set of unrelated intensity values. To avoid the complications of incorporating an analytic filter, methods have been devised to improve the nature of the actual sampling performed to help reduce aliasing effects.Supersampling
The simplest discrete method available is known as supersampling. It involves casting more than one regularly spaced sample per pixel and using the average of the results for the pixel intensity. For example, a pixel could be subdivided into the grid illustrated in below. To render the pixel, primary rays are cast through each of the indicated sample points. The intensity value of the pixel is the average of all the samples.
Adaptive sampling is similar in nature to supersampling. Each pixel to be traced has a primary ray cast through each of its corners. If the intensity of any of the four rays varies significantly from the other three, then the pixel is split into four rectangular portions. Each of the new quadrants has primary rays cast through their corners. Any quadrant for which the new rays display any significant difference are further subdivided and the process is repeated for that quadrant. The subdivision process can be repeated to an arbitrary level. Note that quadrants at a new level have rays in common with the previous level and with each other thus reducing the amount of actual tracing that needs to be performed.
Adaptive sampling works very well on boundary edges. However, certain scenes will still cause problems since they can cause the sampler's subdivision phase to stop prematurely, e.g. failing to notice gaps between similarly coloured objects. In these circumstances aliased artefacts can occur in the final image.Stochastic Sampling
Stochastic sampling is another discrete antialiasing method. The method antialiases scenes through the use of a special sample distribution which replaces most aliased image artefacts with noise of the correct average intensity.
In order to determine the colour of a particular pixel the pixel is subdivided into a grid of a preset number of cells. A primary ray is then traced through some randomly determined location in each of the cells as shown below. This type of sample distribution closely resembles the 'Poisson disk' distribution of photoreceptors found in the extrafoveal region of the human retina.
The samples are combined into one value for the pixel. The weighting given to each sample should depend in some way on its distance from the centre of the pixel, for example a Gaussian function. It is usually acceptable however to use a 'box' filter, i.e. apply an equal weighting to all the samples.
Since the samples are not regularly spaced, aliasing artefacts that would otherwise have appeared in the image are for the most part converted to noise.
In conclusion however it should be noted that aliasing is an inherent part of any discrete process, its effect can be minimised but not eliminated.References
Robert L. Cook and Thomas Porter and Loren Carpenter,
Distributed Ray Tracing,
Computer Graphics v 18 no 3, Jul 1984 (SIGGRAPH '84 Proceedings), pp 137-145
Robert L. Cook,
Stochastic Sampling in Computer Graphics,
ACM Transactions on Graphics, v 5 no 1, 1986, pp 51-72
Aliasing is a general term given to artefacts that occur when a continuous signal or function is discretely sampled. This happens all the time when computers are used to acquire information from the real world for processing, a few examples:
Another artefact that occurs when objects are drawn onto a digital image (eg: the screen) is the so called "staircase" effect. Consider the drawing of a black line onto a white background at an angle other than horizontal or vertical. The line can only be drawn using the pixels of a finite size, this causes steps in the representation of the line. See the magnified version of the line in the following example and the curved parts of the letter "d".
As with the first type of aliasing, this staircase effect can be reduced (although not removed) by sampling the image at a higher resolution and then subsampling, with averaging, to the desired resolution. In the image below the same elements as above are known geometrically, essentially at an infinite resolution. There are techniques that can render these geometric objects antialiased.
The net effect is like a blurring of the object, note however that
antialiasing cannot be performed by simply blurring the original image.
Typically antialiasing of objects that aren't known to an infinite resolution
is performed using original images 2, 3, or 4
times the resolution of the final subsampled/averaged image.
The relative gain diminishes as the image resolution is increased
and obviously the process becomes more computationally unattractive
as the resolution increases.
The following is a line subsampled from high resolution renderings, scale factors are shown below the line.