Anti-Aliasing (Supersampling) and Mip-Mapping

Generally you want to look up articles and books on signal processing. For a more graphics-oriented slant, check out Heckbert's masters thesis ("Fundamentals of Texture Mapping and Image Warping") and also his paper "Survey of Texture Mapping". These will discuss texture mapping, sampling and filtering in a large amount of detail. They also touch on super-sampling as one (non-ideal) method of reducing aliasing due to texture resampling. The general theory of applying super-sampling at a framebuffer level is similar.

I'd start with those papers, and maybe look at Williams' "Pyramidal Parametrics" paper if you want to go to the source of mipmapping, although it is described in a broader and probably more useful sense in Heckbert's survey paper.

Thanks. I've briefly looked over those and I should clarify that I'm still very much a beginner to graphics programming and after the introduction I found them a bit beyond my scope... I guess I'm looking more for something that explains the theory in layman terms, without too much of the mathematics, with more of the code.. If that makes sense?

In extreme basic terms, Aliasing is a problem related to using discrete representations of signals. When we're talking about aliasing in graphics, the "signal" is the world we'd like to draw (which is made up of polygons) and the "discrete representation" is the pixels that we end up displaying on the screen. The problem here is pretty easy to figure out: we've only got so many pixels to work with, and they're not adequate for representing areas where the color changes very quickly (IE, high-frequency areas). When you try to recreate something high-frequency with not enough samples (pixels), you get low-frequency artifacts. In graphics, these artifacts are most visible as the dreaded "jaggies" that pop up at the edges of polygons.

One way to alleviate the effects of aliasing is to oversample the continuous function. This means you take more samples then you're able to represent, then filter and "shrink down" the data to the size you can work with. In graphics terms, this equates to rendering an image with more pixels than you can display and then down-sizing it. This is how super-sampling works. When you see a number listed after the words "super-sampling", this typically refers to the number of samples you take per actual pixel displayed. So for example if you were rendering to a 640 x 480 backbuffer and wanted 4x super-sampling, you'd first render to a 1280 x 960 surface and then downsize it back to 640 x 480. Or alternatively, you could render to 4 640 x 480 surfaces (each with a jittered projection matrix so that the same location isn't sampled each time) and then combine the corresponding samples from each surface to create the final image. The end result of this process is that the aliasing artifacts are moved into a higher frequency. Move the aliasing into a frequency above what the human eye can detect at that distance...and it's effectively gone completely. But of course each extra sample is expensive (since you need to do all work needed to process that pixel as well as have the space to store it), which is why super-sampling is really no longer used in modern 3D GPU's.

Now you might ask, how are those extra samples combined when creating the final image? Well what happens is the samples are filtered. There are several different kinds of filters you can apply each with different characteristics, but the simplest type is the box filter. With a box filter, each sample is weighted equally with the the weight being the reciprocal of the number of samples - or in other words, the values are averaged. This is pretty easy to conceptualize: if you need to come up with 1 pixel but have 4 sub-samples, you add up the 4 samples and divide by 4 to come up with 1 pixel that's "in-between" the 4 color values. If you want to see how these filters work when super-sampling, try down-sizing an image in Photoshop (or some other image-editing program) and choose different filters and sizes.


Okay now for mip-Mapping...mip-mapping is also a technique that deals with aliasing. However in this case the aliasing is what results from minifying a texture when the texture is applied to the 3D objects whose on-screen pixel size is lower than that of of the actual texture. Remember that I said before that images are filtered when being down-sized? Well this is exactly how mip-maps are made. Either when the texture is being loaded or when its being created, the image is minified to successively smaller images (512x512 -> 256x256 -> 128->128 -> 64x64...etc.) while being filtered each step of the way. The result is that the texture is effectively pre-filtered for a bunch of different sizes. This means that the GPU can automatically select which mip-map size to use when a texture is being mapped to a triangle, and it will already be filtered. GPU's can also filter the samples taken from two adjacent mip-map levels.

[Edited by - MJP on April 25, 2008 1:58:08 PM]

Ah, ok, I think I understand.. roughly.

How would one go about doing this with OpenGL? To create a backbuffer of a specified size? then.. draw the polygons to this increased resolution.. then averaging the colour values?

Theoretically, opengl ought to be doing this for you when you
turn on the appropriate options, only doing it more cleverly
and efficiently than you are likely to do yourself.

Mip Mapping: The basic idea is to represent an image as a hierarchy
of images at different resolutions, then, when you need a pixel from
the image, pick a few (usually two) samples from the most relevant levels
of detail and interpolate them. This allows you (for example) to
efficiently hang a picture of the mona lisa on a museum wall, and
walk up to it and stare at the nose with apparent glitches in the image
quality.

Thank you MJP nice explanation (made me understand the correlation between physics and others).
But I have a question :

Quote:

Original post by MJP [explaining "super-sampling"]

Don't you mean Over-Sampling ?
I thought Super-Sampling was the generic name, with too sub-methods being OverSampling (the one you're talking about in your post), and Anti-Aliasing (with x2 and x4 being the number of points distributed around the pixel to compute the final color).
Am I wrong ? It seems I am, since "anti aliasing" is a generic term too, but if SuperSampling (or OverSampling) is a sub-genre of Anti-Aliasing (it makes more sense now that I think about it), what's the name of the method I called Anti-Aliasing before (with 2 , 4, or 8 points) ? Thank you.

By the way, the topic title shows that the OP might be confused too, between Anti-Aliasing and SuperSampling (and/or the "2/4/8 points" method).

Anti-Aliasing is just the general name for trying to remove/decrease the effects of sampling. This can be achived by super sampling. I think over-sampling is a missleading word, since it usually means taking too many samples (not only more than one). Triangle edges, in computer graphics, has infinitly high frequency. Therefore we cannot over-sample them (we cannot sample with higher frequency since it's infinite).

So super-sampling is to use more than one sample/pixel to reduce the aliasing-effects. Hence, it's a anti-aliasing method. One super-sampling scheme is to "divide" each pixel into two as you said. Another is to divide it into four. Another is NVIDIA Quincux, where you use the corners and the center of the pixel. So each pixel is calculated from 5 samples, but the corner samples can of course be used in the neighbouring pixels aswell.

In general, jittered sampling achieves really good quality (jittered means that the samples you use for a pixel is random in some sense). This replace the aliasing-effects with noise, for which the human eye is less sensetive to.

Another scheme is RGSS (Rotated Grid Super sampling). This uses 4 samples per pixel, but they are not symmetrically distributed over the pixel, instead it's like a rotated quad. This is in some way more "random" than for instance Quincux, and it gives much better quality.

Another thing is Multi-sampling. This is the same as super sampling, with the exception that texture lookups (and fragment shaders) are only done once for each pixel. This technique removes the jagged edges of triangles, but it doesn't remove the other aliasing problems.

[Edited by - zurekx on April 25, 2008 6:43:04 PM]

Quote:

Original post by ddyer Theoretically, opengl ought to be doing this for you when you turn on the appropriate options, only doing it more cleverly and efficiently than you are likely to do yourself. Mip Mapping: The basic idea is to represent an image as a hierarchy of images at different resolutions, then, when you need a pixel from the image, pick a few (usually two) samples from the most relevant levels of detail and interpolate them. This allows you (for example) to efficiently hang a picture of the mona lisa on a museum wall, and walk up to it and stare at the nose with apparent glitches in the image quality.

Yeah but I'd like to do it myself in an API rather using a ready-made function so I can see how things work, i.e. I want to go through all the stages of the process.

Quote:

Original post by Side Winder Yeah but I'd like to do it myself in an API rather using a ready-made function so I can see how things work, i.e. I want to go through all the stages of the process.

Well I can't give you code because I'm not an OpenGL guy...but it shouldn't be too hard to do super-sampling yourself. Probably the easiest way to do it would be to just create a giant buffer and render your scene to that, then use a shader that will filter the buffer by taking the appropriate amount of samples and average them. Of course if you use 4x super-sampling, you can get the texture units to do the work for you by enabling linear filtering.

Also AFAIK OpenGL doesn't have any native support for super-sampling. It does allow you to enable hardware multi-sampling (through extensions), but that's a different technique altogether.