## 8.5 Stratified Sampler

The `IndependentSampler`’s weakness is that it makes no effort to ensure
that its sample points have good coverage of the sampling domain. All
the subsequent `Sampler`s in this chapter are based on various ways of
ensuring that. As we saw in Section 2.2.1,
stratification is one such approach. The `StratifiedSampler` applies
this technique, subdividing the sampling domain into
regions and generating a single sample inside each one.
Because a sample is taken in each region, it is less
likely that important features in the integrand will be missed, since the
samples are guaranteed not to all be close together.

The `StratifiedSampler` places each sample at a random point inside each
stratum by jittering the center point of the stratum by a uniform random
amount so that all points inside the stratum are sampled with equal
probability. The nonuniformity that results from this jittering helps turn
aliasing into noise, as discussed in Section 8.1.6.
The sampler also offers an unjittered mode, which gives uniform sampling in
the strata; this mode is mostly useful for comparisons between different
sampling techniques rather than for rendering high-quality images.

Direct application of stratification to high-dimensional sampling quickly
leads to an intractable number of samples. For example, if we divided the
5D image, lens, and time sample space into four strata in
each dimension, the total number of samples per pixel would be . We could reduce this impact by taking fewer samples in some
dimensions (or not stratifying some dimensions, effectively using a single
stratum), but we would then lose the benefit of having well-stratified
samples in those dimensions. This problem with stratification is known as
the *curse of dimensionality*.

We can reap most of the benefits of stratification without paying the price
in excessive total sampling by computing lower-dimensional stratified
patterns for subsets of the domain’s dimensions and then randomly
associating samples from each set of dimensions. (This process is
sometimes called *padding*.)
Figure 8.22 shows the basic idea: we might want to take
just four samples per pixel but still require the samples to be stratified over
all dimensions. We independently generate four 2D stratified image
samples, four 1D stratified time samples, and four 2D stratified lens
samples. Then we randomly associate a time and lens sample value with
each image sample. The result is that each pixel has
samples that together have good coverage of the sample space.

Rendering a scene without complex lighting but including defocus blur due to a finite aperture is useful for understanding the behavior of sampling patterns. This is a case where the integral is over four dimensions—more than just the two of the image plane, but not the full high-dimensional integral when complex light transport is sampled. Figure 8.23 shows the improvement in image quality from using stratified lens and image samples versus using unstratified independent samples when rendering such a scene.

`StratifiedSampler`, which stratified both the image and, more importantly for this image, the lens samples. Stratification gives a substantial improvement and a reduction in mean squared error.

Figure 8.24 shows a comparison of a few sampling
patterns. The first is an independent uniform random pattern generated by
the `IndependentSampler`. The result
is terrible; some regions have few samples and other
areas have clumps of many samples. The second is an unjittered stratified
pattern. In the last, the uniform pattern has been jittered, with a random
offset added to each sample’s location, keeping it inside its cell. This
gives a better overall distribution than the purely random pattern while
preserving the benefits of stratification, though there are still some
clumps of samples and some regions that are undersampled.

Figure 8.25 shows images rendered using the
`StratifiedSampler` and shows how jittered sample positions turn
aliasing artifacts into less objectionable noise.

`stratum`index for current pixel and dimension>>

`stratum`index for current pixel and dimension>>

The `StratifiedSampler` constructor takes a specification of how many
2D strata should be used via specification of and sample counts.
Parameters that specify whether jittering is enabled and a seed for the
random number generator can also be provided to the constructor.

The total number of samples in each pixel is the product of the two dimensions’ sample counts.

This sampler needs to keep track of the current pixel, sample index, and
dimension for use in the sample generation methods. After recording them
in member variables, the `RNG` is seeded so that deterministic values
are returned for the sample point, following the same approach as was used
in `IndependentSampler::StartPixelSample()`.

The `StratifiedSampler`’s implementation is made more complex by the
fact that its task is not to generate a full set of sample points for all
of the pixel samples at once. If that was the task of the sampler, then
the following code suggests how 1D stratified samples for some dimension
might be generated: each array element is first initialized with a random
point in its corresponding stratum and then the array is randomly shuffled.

This shuffling operation is necessary for padding, so that there is no correlation between the pixel sample index and which stratum its sample comes from. If this shuffling was not done, then the sample dimensions’ values would be correlated in a way that would lead to errors in images—for example, the first 2D sample used to choose the film location, as well as the first 2D lens sample, would always each be in the lower left stratum adjacent to the origin.

In the context of `pbrt`’s sampling interface, we would like to perform this
random sample shuffling without explicitly representing all the
dimension’s sample values. The `StratifiedSampler` therefore uses a random
permutation of the sample index to determine which stratum to sample.
Given the stratum index, generating a 1D sample is easy.

`stratum`index for current pixel and dimension>>

It is possible to perform the sample index permutation without representing the permutation
explicitly thanks to the `PermutationElement()` routine, which is
defined in Section B.2.8. It takes an index,
a total permutation size, and a random seed, and returns the element that
the given index is mapped to, doing so in such a way that a valid permutation is
returned across all indices up to the permutation size. Thus, we just need
to compute a consistent seed value that is the same whenever a
particular dimension is sampled at a particular pixel. `Hash()` takes
care of this, though note that `sampleIndex` must not be included in
the hashed values, as
doing so would lead to different permutations for different samples in a
pixel.

`stratum`index for current pixel and dimension>>=

Generating a 2D sample follows a similar approach, though the stratum index has to be mapped into separate and stratum coordinates. Given these, the remainder of the sampling operation is straightforward.

`stratum`index for current pixel and dimension>>

The pixel sample is not handled differently than other 2D samples with this
sampler, so the `GetPixel2D()` method just calls `Get2D()`.

With a -dimensional stratification, the star discrepancy of jittered points has been shown to be

which means that stratified samples do not qualify as having low discrepancy.

The PSD of 2D stratified samples was plotted earlier, in Figure 8.17(a). Other than the central spike at the origin (at the center of the image), power is low at low frequencies and settles in to be fairly constant at higher frequencies, which means that this sampling approach is effective at transforming aliasing into high-frequency noise.