Anti-Aliasing in Computer Graphics
1.Introduction
a.What is Aliasing?
i.Conversion of analog signals to digital signals

ii.Point sampling

iii.Nyquist Theorem

iv.Aliasing occurs when sampling rate is below Nyquist Limit

2.Aliasing in Computer Graphics

a.Mathematical image of a model is a continuous analog signal

i.Pixels are point sampling

ii.Sampling rate depends on screen resolution

iii.Sampling rate below Nyquist Limit produces artifacts

b.Aliasing Artifacts

i.?Jaggies?

ii.Improperly rendered detail

3.Anti-aliasing

a.Prefiltering

b.Postfiltering

i.Supersampling

ii.Final value of each pixel is averaged from oversampled pixels 

iii.Averaging determined by filter weights
 

1. Introduction

A fundamental caveat of digital technology lies in the fact that real world phenomena and the mathematical functions that describe them are most often continuous analog elements of infinite resolution and must be converted into digital elements of finiteresolution in order for our machines to process and store them.At best, digital technology can only approximate analog signals through a process known as sampling, where regular points of the analog signal are recorded or sampled.The more frequent the sampling the closer the digital approximation of the original analog signal becomes.Choosing an appropriate sampling rate depends on many factors such as data size restraints, need for accuracy, and in some cases the cost per sample.Much research has been devoted to this topic and one of the most important theories to come from these efforts aids in determining the lowest acceptable sampling rate. The Nyquist Theorem states that the sampling rate must be twice the frequency of the signal or an effect known as aliasing occurs. Generally, aliasing refers to the degradation of a sound, image, or other signal during the sampling process due to low-resolution sampling.The image below illustrates the simplest case of aliasing: the distortion that occurs when a sound wave is sampled at too low a rate: 


  The top wave is sampled at a frequency within the Nyquist limit and the digital sample produces the original frequency.  The bottom wave on the other hand is sampled beyond the Nyquist limit and the resulting sampled wave has a much lower frequency than the source.  The second sampled wave is aliased.
 

2.Aliasing in Computer Graphics

 
Aliasing is common in computer graphics because screen or file resolutions are finite whereas the mathematical models describing an image have infinite resolution.
The undesirable effects of aliasing in computer graphics are known as artifacts.  Artifacts lower the quality of an image in various ways as shown in the examples below.
 
Here is an example of "jaggies", also known as staircasing.   The continuous signal on the left becomes rough and jagged in the digital approximation on the right due to low resolution of the sampling grid.

 

Here is what happens when details of a signal are at a higher frequency than the pixel sampling.

3.  Anti-Aliasing Techniques

  Various techniques emerged to decrease the effects of aliasing in images.

Prefiltering

  This is a techinque that determines pixel intensity based on the amount that a particular pixel is covered by an object in the scene. Determining such areas requires extensive calculations and integral approximations. While the precision of prefiltering does generate more accurate antialiasing effects, its complexity and expensive calculations at times make it an undesirable method to minimize aliasing effects.

Weighted Prefiltering

  This is a subset of prefiltering that assigns different weights to the area calculations based on their position within the pixel. For example, if an object intersects a pixel along the pixel edge and covers 20% of the pixel, the pixel may only receive 10% of the total intensity for the object. If however, the same object intersected 10% of the pixel area but did so at the pixel's center, the pixel may receive 25% of the total intensity for the object. The weighting assignment is based on particular weight distribution curves that often follow a bell-curve pattern.

Postfiltering or Supersampling

  The concept of postfiltering as an implementation of antialiasing is to increase the sampling frequency of the rendering process. In doing so, a more accurate pixel grid can be generated if more samples of a scene are made. For this reason, postfiltering is commonly referred to as supersampling.  The generated supersampled image is then passed through a filter that will perform pixel averaging and reduce the supersampled grid back to the desired resolution.

This was the fundamental technique that we implemented for this project. The supersampling algorithm that we implemented is as follows:

 1.) Have a scan converter generate the supersample pixel grid.
 2.) Pass the grid to the lowpass filter.
 3.) Apply multiple filtering algorithms with various parameters.
 4.) Sample the pixel-averaged (antialiased) grid at the desired resolution.

  Theoretically, if the supersampling resolution approached infinity, the original scene would be rendered exactly. However, because of physical constraints such as storage, the size of the grid must be restricted. In fact, we found that due to memory allocation, we generally could not increase the supersampled resolution above 1600x1600, even with explicit calls to the Java garbage collector. Thus, supersampling is a prime example of the fundamental computing principal of time vs. space.

Filtering: method of averaging supersampled pixels to arrive at final image pixel
The three most common types of pixel averaging algorithms or filters are listed below:

Box Filter:  unweighted, that is all pixels of the supersampled set are averaged equally

Cone Filter:  center of pixel set gets higher weight; outer pixels get lower weight in a fixed linear progression

Gauss Filter: dome shaped weighting style that allows users to adjust parameters to vary how fast the weighting decreases non-linearly from the center of the supersampled pixels
 

Stochastic Sampling or "Jittering"
Another method of decreasing aliasing effects in images relies on the physiology of the human visual system.  In contrast to a computer screen's regularly spaced pixels, the receptors in our eyes are randomly destributed accross the retina.  The reason we do not notice aliasing is that high frequency image components beyond the Nyquist limit are perceived as noise which our brains have evolved to ignore.  Anti-aliasing algorithms can take advantage of this phenomenon by duplicating the randomly distributed sampling found in nature.  The process is formally known as stochastic sampling and commonly known as jittering.
 

Interactive Anti-Aliasing Applet
Here is an interactive java applet that allows users to manipulate parameters of a postfiltering anti-aliasing algorithm.  The user can choose from three filter types and apply jittering as well as adjust parameters for the filters and jittering.  The effect of the anti-aliasing technique can be seen by comparing before and after views of four pre-selected images.

  Link to the applet: http://www.prism.gatech.edu/~gt6671b/anti_alias/
 
 

Sources:

Texts:

Baker, Hearn, Computer Graphics, C version, 1996 Prentice Hall Publishing, New York
(filtering)

Feiner, Foley, Hughes, van Dam, Computer Graphics: Principles and Practice, second edition in C, 1996 Addison-Wesley Publishing Company, Inc., New York
(scan conversion, filtering, supersampling)

Web Links:

http://www.education.siggraph.org/materials/HyperGraph/aliasing/alias0.htm


(tutorial)

 http://java.sun.com/products/jdk/1.1/docs/api/packages.html
(java 1.1 api)

 http://www.gameprogrammer.com/archive/html/msg04930.html
(Bresenham cirlce algorithm)

 http://www.gvu.gatech.edu/gvu/multimedia/nsfmmedia/graphics/elabor/polyscan/polyscan2.html
(general polygon scan conversion)

Group Members:

Robert Crawford
Andrew Foster
Andy Kortz
Matt Wolenetz
James Roberts