## Sampling

Last updated 2018/12/18

### The concept

Sampling is the process of collecting data points in an arbitrarily large amount of information. Instead of collecting all the available information, we only collect a few bits of it to make a (hopefully) representative statement about the content.

Let's make an example unrelated to graphics first, to show that it is universally applicable. Sampling the path of a car

1) A car drove from point blue to point green.

2) We can't say which path the car took to reach its destination. There are infinite possible ways to connect those two dots.

3) What we can do, however, is looking at the data the car's board computer collected and make a guess which route it took. We probably don't need to know where it has been at every single second of its journey, we just need to look at a small number of data points to get the idea. The more points we look at the more detailed our path becomes. In this example, we took 7 samples (red dots).
Each time we sample the data we spend a bit of time, so the precision we get is proportional to the time we invest in sampling. This means we have to make a tradeoff between cost and precision. We want to find the best possible precision for the least amount of work to put in.
In the real world, however, we wouldn't have an infinite number of possible (and sensible) paths the car would have been able to take. It is, after all, bound to roads. So based on our samples we can be confident that the car took the green road as seen in 2).

### So how does this translate to rendering? Sampling of a teapot with different resolution

In 3D rendering, we want to project a three-dimensional object onto a two-dimensional plane. Meaning, we want to show our 3D world in a 2D image. To do that, we need to decide how much resolution we want, how much detail our image should have. So the amount of pixels in the image determines the maximum detail we can have - and how much work we have to put in.
So, as seen on the left, the more pixels we use the more defined our teapot gets. But despite using 100x100 pixels we still have an ugly jagged outline which is not what we see on other small pictures like icons. So, what's the deal there?

### Multiple samples per pixel One sample per pixel

Instead of just sampling once per pixel we need to sample multiple times per pixel. To make clear why let's zoom into the image and just look at the edge of the object.
1) The first image on the right represents a 5x5 pixel grid. In the background, we can see the gray shape of the geometry we want to sample (e.g. the left side of the teapot).
2) So we sample the geometry from the center of each pixel, represented by a red dot. If the sample is on top of the geometry, we color the pixel in the color of the object. If we're not on top of the geometry we let the pixel be the color of the background.
3) The result is hard, jagged gray pixels. Multiple samples per pixel

So, now we will sample each pixel twice, using random positions inside the pixel.
This time, however, we will use the average of the two samples as a color for each pixel. That results in a much smoother edge and is what we, therefore, call anti-aliasing. Note that we need to do twice the work.

Why didn't we distribute the additional samples in a grid-like manner? Randomness sounds like it could produce very unpredictable results - especially in animations.
The short answer is that grid-like sample patterns often produce other undesirable effects like moiré and need to be comparably dense to resolve small intricate - in itself pattern-like - structures like wireframes or parallel lines.
The long answer involves more advanced topics like monte-carlo sampling and is way beyond the scope of this introduction. It is an ongoing quest for researches to find better and more efficient random sampling patterns and it's usually discussed in the context of raytracing and efficient distribution of samples within the 3d scene. 