Supersampling is a solution to a problem called aliasing (which is why supersampling often gets confused with "anti-aliasing", more on that later). Now before we can appreciate supersampling as a solution, we must struggle with the problem: aliasing.

Aliasing

Aliasing is the reason we buy that 5 megapixel digital camera instead of the 3 megapixel, the reason that car wheels seem like they're going backwards when going forward really fast, and the same reason that some people think vinyl records are better than CDs. It comes from trying to store a continuous object with a discrete approximation.

Let's examine how a digital picture works. A digital picture is simply a grid of many colored dots called pixels. When there are enough pixels, enough colors, and the pixels are small enough, the picture looks real. The reason that this works is that our eyes can only be so precise in seeing these pixels until they get all mushed together.

But what happens when there aren't enough pixels? What is supposed to be a continuous curve (like the face of a person) turns out to be jagged. Think of these jagged edges as a form of aliasing.

Now sometimes you still get bad aliasing even when you take enough pixels. This can happen when a curve in a picture is particularly complex, or there are many changes in colors near each other.

Aliasing doesn't have to happen in pictures, it can happen in terms of time as well. Think about a video camera for this: a camera doesn't record every movement it views, it only take many, many pictures of the scene and plays them back. With enough frames, the motions look seamless - until someone moves so fast that it looks like they've teleported! That's an example of aliasing.

Capturing at 4 frames per second.

Captured at 2 frames per second

Captured at 1 frame per second


Captured at 0.75 frames per second
(first 3 seconds) So how does the backwards wheel thing work? Let's go through the diagrams to the right. Imagine that we're capturing a wheel on camera that's spinning clockwise at a constant rate (1 revolution per second in this example). The first three rows show the frames for one second. The last frame shows the first 3 seconds.

Notice that we run into strange behavior when we decrease the samples to 2 per second. It looks like the wheel is just oscillating. Worse yet, when it's only 1 frame per second, it looks like the wheel is just standing still!

The worse case is when the camera captures the wheel at 3/4 of a frame per second. The second frame is C, then it's B from the next revolution, then A from the revolution after that, then D of the 4th revolution. As a result, the sequence of frames makes the wheel look like it's going backwards!

So when we see a car's wheel or a helicopter's blades spin faster and faster, we see it go backwards because our eye's sampling rate is too slow.

What if we increased the frames per second? Well, that doesn't always work. I believe we captured at 4.75 frames a second, we'd still get the backwards wheel issue. The problem lies not in taking many samples, but in taking the right, i.e. representative samples.

Supersampling

Increasing the sheer resolution of the samples is not the only way to combat aliasing. We can also increase the quality of our samples by taking more samples and averaging. This way, you can get a better idea of what each chunk looks like. Consider the following example.

A badly aliased sampling of a curve


Grid-based sampling with 4 samplesThe standard way to of sampling is to take one sample in the middle of the pixel - whichc creates a lot of aliasing as you can see. What's happening is that those samples really don't represent where the curve is! Samples A1 and A2 are really bad because they both have about half of their area under that curve, but one is colored and the other isn't. What is needed here is a more representative sample.

So why stop at 1 sample? Let's do 4 in a grid, then average the samples. Pixels A1,A2 are 1/2 green, A3 is 1/4 green, and B5 is 3/4 green. Our pixels represent the curve a lot better.

Now it's pretty obvious that the more samples we add, the better average we'll get. You can see this two ways: (1) you get a more representative sample for each pixel, and (2) you get more "in between" color combinations. More precisely, for n samples, you get
n-1 shades of your base color (green in this case).

Grid-based supersampling will make your pictures look much better, but they're only the tip of the ice-berg. For starters, grid-based sampling is too predictable. The entire space of the image is not being sample, only a set part.

Same object, different locations.

Object gets sampled differently
based on its location


Two possible random samplings, sampled
differently but with similar results.

The worst case of this with sharp objects that tend to "fit" between samples. Now the diagram here might seem a little contrived - and it is. Nevertheless, suppose your triangle is in an animation where it moves left to right. With this kind of sampling one would get a flickering triangle because it would just drop out of a few frames. So how do we get more bang for our samples?

Enter random sampling. Instead of deciding ahead of time where these samples are going to be, have each pixel scramble up its samples.

This method works well because it's based on randomness' advantage: it's unpredictable in the short run, but predictable in the long run. If one pixel gets a lot of clusters, then chances are that somewhere else there's a cluster in a compensating spot. It all evens out with randomness.

Predictable samples are also to blame in the spinning wheel example we saw earlier.

I will to refer to this method as random-based sampling.

But wait! There's more! We can do even better!

The cluster in the top-right
corner makes it look like
the entire pixel's green.It is still true that when samples cluster, they create a non-representative sample - but with randomness it all evens out eventually. Well, in a practical setting, those cluster can really mess up your picture. All it takes is a few pixels in a row that are clustered and the picture looks aliased again. So why don't we just get rid of those clusters?

In hindsight, this is where grid-based sampling shined. We knew that the samples were evenly spaced out over the pixels and so clusters aren't an issue. Why don't we try to space out our random samples like grid-based did? The result is what's called jitter-based sampling, which is pretty much a combination of grid-based and random-based sampling.

Jitter-based sampling.The idea is to subdivide a pixel into a grid, then sample in a random location within that grid. The more samples, the bigger the grid.

Another way to think of jitter-based sampling is that it takes the most representative subset of a random-based sampling. Every part of the pixel could be sampled, and it's more likely that every pixel will still be spread out, making the sample representative.

It turns out that this jitter-based is of the best methods of supersampling.

Now that we've taken representative samples of our object, how do make sense of all that data?

Making Sense of the Data

In an earlier example, we just took the average of all of our samples. This is based on the (safe) assumption that every sample is just as important as the others.

Scientists, however, have discovered that the way our eyes assemble pictures from pixels in our brains is not exactly uniform. One pixel kind of bleeds into another one, and we don't notice the edges of a pixel, but more of the middle. The middle of the pixel, then, is more important than the outer parts. Knowing that, we can weigh our averages toward the middle. There's a whole science behind how much you weigh the middle versus the outside, but we won't get into that here.

Adaptive Supersampling

Now in ray tracing, we don't usually worry too much about speed, just good pictures. If you're using supersampling, though, you're adding an enormous amount of calculations which could slow you down. Furthermore, we don't need many samples for every pixel. We only need extra samples for pixels representing something complicated - like an edge or a texture. This is called adaptive supersampling.

The idea here is to sample a pixel 4 times in a grid, then compare. If one sample is different than the others, then you subdivide that square 4 times. You keep going until all the samples are close to each other. The result is a set of sample that "zero in" along the complex edges.

It's unclear to me whether or not this is better than jitter-based sampling in terms of both performance and quality.

Conclusion

Anti-aliasing techniques are extremely important with today's technology - especially with this shift from analog to digital media. We usually associate "analog" as antiquated and poor, and "digital" is new and reliable, but the irony is that digital media has many drawbacks that analog does not. A scratch in a record is smooth, continuous surface. Converting that sound to a CD or an MP3 requires sampling of the sound - chopping up a continuous surface into a bunch of small chunks. Yes, as our technology increases and we can hold more digits to describe what the curve looks like, we won't be able to fully reproduce that sound.

Since sampling is such a ubiquitous method for capturing smooth surfaces like sound, anti-aliasing will become absolutely crucial in getting the most out of our precious digits.

 

 

Page last updated: February 04, 2008