Antialiasing
Antialiasing (AA) means preventing [1]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 [2]integrals of intervals), i.e. in ways
native and natural to [3]computers. Note that the aliasing effect is
mathematical and is kind of a "punishment" for our "[4]cheating" which we
do by trying to simplify capturing of very complex signals, i.e. aliasing
has nothing to do with [5]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 [6]MIP mapping) or by increasing the sampling
frequency (e.g. [7]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 [8]FXAA (fast approximate antialiasing) method is a
[9]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 [10]good enough
[11]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.
* [12]multisampling (MSAA), [13]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.
* [14]FXAA: Cheating, approximation of antialiasing by
[15]postprocessing, usually in [16]shaders, cheap but can be
imperfect.
* [17]MIP mapping: Way of preventing aliasing in rendering of
scaled-down [18]textures by having precomputed scaled-down antialiased
versions of it.
* [19]anisotrpic filtering: Improved version of MIP mapping.
* [20]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 [21]supersampling (one of the
simplest antialiasing methods) in [22]C. We will draw a two dimensional
"fish eye" distorted [23]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 [24]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 [25]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.
Links:
1. aliasing.md
2. integral.md
3. computer.md
4. cheating.md
5. noise.md
6. mipmap.md
7. multisampling.md
8. fxaa.md
9. postprocessing.md
10. good_enough.md
11. approximation.md
12. multisampling.md
13. supersampling.md
14. fxaa.md
15. postprocessing.md
16. shader.md
17. mipmap.md
18. texture.md
19. anisotropic_filtering.md
20. motion_blur.md
21. supersampling.md
22. c.md
23. sin.md
24. ram.md
25. ascii_art.md