less_retarded_wiki/antialiasing.md

Antialiasing

Antialiasing (AA) means preventing aliasing, i.e. distortion of signal (images, audio, video, ...) caused by discrete sampling. Most people think antialiasing stands for "smooth edges in video game graphics", however that's a completely inaccurate understanding of antialiasing: yes, one of the most noticeable effects of 3D graphics antialiasing for a common human is that of having smooth edges, but smooth edges are not the primary goal, they are not the only effect and they are not even the most important effect of antialisng. Understanding antialiasing requires understanding what aliasing is, which is not a completely trivial thing to do (it's not the most difficult thing in the world either, but most people are just afraid of mathematics, so they prefer to stick with "antialiasing = smooth edges" simplification).

The basic sum up is following: aliasing is a negative effect which may arise when we try to sample (capture) continuous signals potentially containing high frequencies (the kind of "infinitely complex" data we encounter in real world such as images or sounds) in discrete (non-continuous) ways by capturing the signal values at specific points in time (as opposed to capturing integrals of intervals), i.e. in ways native and natural to computers. Note that the aliasing effect is mathematical and is kind of a "punishment" for our "cheating" which we do by trying to simplify capturing of very complex signals, i.e. aliasing has nothing to do with noise or recording equipment imperfections, and it may occur not only when recording real world data but also when simulating real world, for example during 3D graphics rendering (which simulates capturing real world with a camera). A typical example of such aliasing effect is a video of car wheels rotating very fast (with high frequency) with a relatively low FPS camera, which then seem to be rotating very slowly and in opposite direction -- a high frequency signal (fast rotating wheels) caused a distortion (illusion of wheels rotating slowly in opposite direction) due to simplified discrete sampling (recording video as a series of photographs taken at specific points in time in relatively low FPS). Similar undesirable effects may appear e.g. on high resolution textures when they're scaled down on a computer screen (so called Moiré effect), but also in sound or any other data. Antialiasing exploits the mathematical Nyquist–Shannon sampling theorem that says that aliasing cannot occur when the sampling frequency is high enough relatively to the highest frequency in the sampled data, i.e. antialiasing tries to prevent aliasing effects typically by either preventing high frequency from appearing in the sampled data (e.g. blurring textures, see MIP mapping) or by increasing the sampling frequency (e.g. multisampling). As a side effect of better sampling we also get things such as smoothly rendered edges etc.

Note that the word anti in antialising means that some methods may not prevent aliasing completely, they may just try to suppress it somehow. For example the FXAA (fast approximate antialiasing) method is a postprocessing algorithm which takes an already rendered image and tries to make it as if it was properly rendered in ways preventing aliasing, however it cannot be 100% successful as it doesn't know the original signal, all it can do is try to give us a good enough approximation.

How to do antialiasing? There are many ways, depending on the kind of data (e.g. the number of dimensions of the signal or what frequencies you expect in it) or required quality (whether you want to prevent aliasing completely or just suppress it). As stated above, most methods make use of the Nyquist–Shannon sampling theorem which states that aliasing cannot occur if the sampling frequency is at least twice as high as the highest frequency in the sampled signal. I.e. if you can make sure your sampling frequency is high enough relatively to the highest frequency in the signal, you will completely prevent aliasing -- you can do this by either processing the input signal with a low pass filter (e.g. blurring an image) or by increasing your sampling frequency (e.g. rendering at higher resolution). Some specific antialiasing methods include:

• avoiding aliasing: A pretty straightforward way :) Aliasing can be avoided e.g. simply by using low resolution textures as opposed to high resolution ones.
• multisampling (MSAA), supersampling (SSAA) etc.: Increasing sampling frequency, typically in computer graphics rendering. The specific methods differ by where and how they increase the number of samples (some methods increase sampling uniformly everywhere, some try to detect aliasing areas and only put more samples there etc). A simple (but expensive) way of doing this is rendering the image at higher resolution and then scaling it back down.
• FXAA: Cheating, approximation of antialiasing by postprocessing, usually in shaders, cheap but can be imperfect.
• MIP mapping: Way of preventing aliasing in rendering of scaled-down textures by having precomputed scaled-down antialiased versions of it.
• anisotrpic filtering: Improved version of MIP mapping.
• motion blur: Temporal antialiasing in video, basically increasing the number of samples in the time domain.
• ...

Code Example

Here is a quite primitive example of supersampling (one of the simplest antialiasing methods) in C. We will draw a two dimensional "fish eye" distorted sine pattern (similar to checkerboard pattern but smooth, to show that aliasing happens even with smooth images!) that gets smaller towards the edges, i.e. the pattern is quite big in the center but near the edges the brightness oscillates with subpixel frequency which will lead to aliasing. First we'll draw the pattern as is, i.e. taking one sample per each pixel, letting aliasing happen; then we'll try to suppress aliasing by taking multiple samples per each pixel and averaging them -- this effectively increases our sampling frequency. It is basically equivalent to drawing the picture in increased resolution and then smoothly downsizing it (but in practice we don't do this as we'd waste a lot of RAM on storing the big resolution picture, which is completely unnecessary). Let's see the code.

#include <stdio.h>
#include <math.h>

#define W 64  // image width
#define H 32  // image height
#define S 9.0 // pattern scale

const char palette[] = "#OVaxsflc/!;,.- ";

double sample(double x, double y) // function sampling our pattern
{
  return sin(S / (x < 0 ? (x + 1) : (1 - x))) *
         sin(S / (y < 0 ? (y + 1) : (1 - y)));
}

char doubleToChar(double x) // maps <-1,1> brightness to palette character
{
  int i = ((x + 1) / 2.0) * 15;
  return palette[i < 0 ? 0 : (i > 15 ? 15 : i)];
}

void draw(int antialiasSamples)
{
  #define OFFSET 0.0001 // this tiny offset makes the pictures a bit nicer

  double
    x, y = -1 + OFFSET,
    stepX = 2.0 / W,
    stepY = 2.0 / H;

  double
    aaStepX = stepX / antialiasSamples,
    aaStepY = stepX / antialiasSamples;

  for (int j = 0; j < H; ++j) // draw rows
  {
    x = -1 + OFFSET;

    for (int i = 0; i < W; ++i) // draw columns
    {
      double r = 0;

      for (int l = 0; l < antialiasSamples; ++l)
        for (int k = 0; k < antialiasSamples; ++k)
          r += sample(x + k * aaStepX,y + l * aaStepY);

      putchar(doubleToChar(r / (antialiasSamples * antialiasSamples)));  
      x += stepX;
    }

    y += stepY;
    putchar('\n');
  }
}

int main(void)
{
  draw(1);
  putchar('\n');
  draw(8);
  return 0;
}

Here are the results, first picture is without any antialiasing, second one with 8x8 supersampling (i.e. taking 64 samples per pixel):

c//xfs/c!fcs/lxf//cfssflc/!//cllfllc//!/clfssfc//fxl/scf!c/sfscl
/,!Vsa;c,x!a,cVs;,cxVVxl!;,,;/cfsfc/;,,;!lxVVxc,;sVc,a!x,/;afVcc
fss/c/sfscf/sl/cssfc//clfssssfllcllfssssflc//cfssc/ls/fcsfs/l/fl
/,;OsV;/.x!V,cOs;,/xVVxl!,.,;!cfsfc!;,.,!lxVVx/,;sOc,V!x./;VfV/c
!-,#sO./-a;O-c#x.-/a##al;.--.;cfxfc;.--.;la##a/-.x#c-O;a-/.#f#/c
c!!afx!c;s/x!caf!!csaxsl/!;;!/clslc/!;;!/lsxasc!!fac!x/s;c!xfacl
/.,#sO,/-a!O.c#s,./a#Oxl;.-.,!cfxfc!,.-.;lxO#a/.,s#c.O!a-/,Of#/c
x#V-/.Os#;a.#f-!O#s;--;laO##Oafc!cfaO##Oal;--;s#O!-f#.a;#sO-c-sf
/,;OsV;/.x!V,cOs;,/xVVxl!,.,;!cfsfc!;,.,!lxVVx/,;sOc,V!x./;VfV/c
c/csfs/c/fcs/lsf//cfssflc////cllfllc////clfssfc//fsl/scf/c/slscl
s#V-/.Vs#;a.#f-/V#s;--;laO##Vafc!cfaO##Oal;--;s#V!-f#.a;#sO.c-sf
fxx;c!xfa/s!xf;cxaf/;!/lsxaaxsfc/lfsxaaxsl/!;/faxc;fx!s/afx!c;fl
c;!afx!c;s/x;caf!;csaasl/!;;!/cfsfc/!;;!/lsaasc;!fac;a/s;c!afacl
!-,#sO./-a;O-c#x.-/a##al;.--.;cfxfc;.--.;la##a/-.x#c-#;a-/.#f#/c
/,;OsV;/.x!V,cOs;,/xVVxl!,.,;!cfsfc!;,.,!lxVVx/,;sOc,V!x./;VfV/c
lccflfclcfcfclflcclfffflccccccllfllcccccclfffflcclflcfcfclcflfll
fxs!c!sfx/s!xl!csxf/!!/lsxxxsfflclffsxxxsl/!!/fxsc!fx!s/xfs!c!fl
lccflfclcfcfclflcclfffflccccccllfllcccccclfffflcclflcfcfclcflfll
/,;OsV;/.x!V,cOs;,/xOVxl!,.,;!cfsfc!;,.,!lxVVx/,;sOc,V!x./;VfV/c
!-,#sO./-a;O-c#x.-/a##al;.--.;cfxfc;.--.;la##a/-.x#c-#;a-/.#f#/c
c;!afx!c;s/x;caf!;csaasl/!;;!/cfsfc/!;;!/lsaasc;!fac;x/s;c!afacl
fax;c!xfa/s!xf;cxaf/;!/lsxaaxsfc/cfsxaaxsl/!;/faxc;fx!s/afx!c;fl
s#V-/.Vs#;a.#f-/V#s;--;laO##Vafc!cfaV##Oal;--;s#V!-f#.a;#sO.c-sf
c/csfs/c/fcs/lsf//cfssflc////cllfllc////clfssfc//fsl/scf/c/slscl
/,;OsV;/.x!V,cOs;,/xVVxl!,.,;!cfsfc!;,.,!lxVVx/,;sOc,V!x./;VfV/c
x#V-/.Os#;a.#f-!O#s;--;laO##Oafc!cfaO##Oal;--;s#O!-f#.a;#sO-c-sf
/.,#sO,/-a!O.c#s,./a#Oxl;.-.,!cfxfc!,.-.;lxO#a/.,s#c.O!a-/,Of#/c
c;!afx!c;s/x!caf!;csaxsl/!;;!/cfsfc/!;;!/lsxasc;!fac!x/s;c!xfacl
!-,#sO./-a;O-c#x.-/a##al;.--.;cfxfc;.--.;la##a/-.x#c-O;a-/.#f#/c
/,;OsV;/.x!V,cOs;./xOVxl!,..;!cfsfc!;..,!lxVOx/.;sOc,V!x./,VfO/c
fffclcflfcfcflccfflcccclffffffllcllfffffflcccclffcclfcfcflfclcll
c/csfs/c/fcs/lsf//cfssflc////cllfllc////clfssfc//fsl/scf/c/slscl

llllllllllllflclfflcccllfffffllllllfffffllccclfflccflcflllllllll
llllllllllllflclfflcccllfffffllllllfffffllccclfflccflcflllllllll
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
llllllllllllclflcclfffllccccclllllllccccllffflcclflclfllllllllll
lllllllllfclfcclfflcccllfffffllllllfffffllccclfflccflcfcllllllll
lllllllccs/lx/!fxsl!!!cfsxxxsflcclfsxxxxfc/!!csxf!/sf/scllfllcll
ffflllcff!xl,xVc.;fVOas/;..,;/lssl/;,..;/faOVf;./aa;ca;sllcflflf
ccclllfccx!lV!,fOac,.,/saOOVasl//lsaVOOVsc;.,caOs,;af;a/llfcfclc
ffflllcff!xl.xOc.,fV#Vs/,--.;/lssl/;.--,/fV#Of;-/Va,ca;xflcfcflf
llllllllllllflclflllcllllfffllllllllfffllllccllfllllllllllllllll
ccclllfcca!lO!.f#Vc.-./sV##OVxl//lsaO##Vsc,-.cV#s,;Vf,a!clscfclc
lllllllllfclsc/lsflc/ccffsssfflcclffsssfflc//lfsfccflcfcllllllll
ffflllcff!sl;sac,;laVafc;,,,!/lfsl/!;,,;/faVaf!,/ax;cx!sllcflflf
ffflllcff;xl.aOc-,fO#Os/,--.,!lssl/,.--,/fV#Of,-/OV,cV,xfl/fcflf
ffflllcff/sl;sac;!laVafc!,,;!/lffl/!;,,;/fxVaf!,cax!cx!sllcflflf
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
lllllllllfclsc/lssl///cfssssfflcclffssssfl///lfsf/cslcfcllllllll
lllllllllcfl/fsl//lsssfc/////clfflcc////clssslc/csf/lfcfllclllll
ffflllcff!xl,xVc.;fVOVs/;...;/lssl/;,..,/faOVf;./Va,ca;sllcfcflf
ffflllcff!xl.xOc-,fV#Vs/,--.,!lssl/;.--,/fV#Of;-/Va,ca;xfl/fcflf
lllllllllcfl/fsl//lsssfc/////clfflc/////clsssl//css/ls/fllclllll
ccclllfccx/la/;fVal;,;cfaVVVxslc/lsxaVVasc;,;cxVs;!af!x/llfclclc
ccclllfccx!lV!,fOac,.,/saOOVasl//lsaVOOasc;.,caOs,;af;a/llfclclc
ffflllcff/sl;sac;!laVxfc!;,;!/lfflc!;,;!/fxVaf!;cxx!cx!sllcllflf
lllllllllcfl/fsl//lsssfc////cclfflcc////clssslc/csf/lfcfllllllll
cccllllccs/la/;faxl!;!cfxaVaxslcclfxaaaxsc!;;cxaf!!xf!x/llfllclc
lllllllllcflcfflcclfffllcccccllllllcccccllffflcclffclfclllllllll
fffllllff/sl;sac;!lxaxfc!;,;!/lfflc!;;;!/fxaaf!;cxx!cx!sllcllflf
llllllllllllllllflllcllllffflllllllllffllllclllfllllllllllllllll
lllllllllcflcfflcclfsfllc//cccllllccc//cclfsflc/lffclfcfllllllll
llllllllllllllflclllfllllcccllllllllcccllllflllcllllllllllllllll
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

It's a bit harder to see with ASCII art but still it is noticeable even here (the more it will be seen in "real" graphics) -- the first version of the image is much noisier, despite the underlying pattern itself being smooth, just sampled differently. Notice the images really significantly differ near the edges where aliasing appears, the center is basically the same -- here we can spot an obvious weakness of supersampling: that we have wasted computational power on supersampling the part which didn't need it. You can think of ways how this could be improved. Also think for example about placing our samples within one pixel differently than in a uniform grid -- what effect would it have? Here are things for you to explore.