As a follow-up to my post about random numbers, I'd like to ramble a bit about low discrepancy sequences.
Low discrepency sequences (or LDS's as I'll refer to them) are deterministic sequences of points in an n-dimensional space that attempt to be as well distributed and evenly spaced as possible. That's quite a mouthful, but the high-level idea is pretty simple. For a more complete introduction to LDS's I recommend reading chapter 7 of Physically Based Rendering: From Theory to Implementation by Matt Pharr and Greg Humphreys (it's an amazing book, by the way, which you should totally buy if you're at all interested in 3d rendering).
But, suffice it to say, LDS's are really useful. In many contexts they can be used as a drop-in replacement for random numbers to reduce variance. In my case, with a unidirectional path tracer like Psychopath, if I plug an LDS where I otherwise would use random numbers, I get some nice reductions in noise.
Random numbers @ 16spp:
Low discrepency sequence @ 16spp:
Notice the significant reduction in variance in the LDS render compared to the random one. But also notice the patterned appearance of the variance in the LDS render, especially around the edges of shadows. This is an artifact of using the LDS directly.
Another drawback of using LDS's directly is that you have to decide ahead of time how many samples you're taking. A lot of the time this doesn't matter. But if you're doing progressive rendering or adaptive sampling that can be a real limitation.
Fortunately there is a single solution that addresses both of these problems, and that is to decorrelate the samples between pixels. The idea is that each pixel still draws from a single continuous LDS sequence, but the pixels are each randomized with respect to each other. That way you still have good convergance within each pixel, but each pixel is random with respect to all other pixels.
One popular way to do this is called "Cranley Patterson Rotation". The idea behind Cranley Patterson Rotation is to randomly generate a vector, and use that vector to offset the values of all the LDS points. To keep the resulting values within the interval [0,1], you do the offset modulo 1.0 so that resulting values greater than 1 wrap back to start at zero again.
If you do Cranley Patterson Rotation using the same vector for all pixels, you don't gain anything. But if you use a different random vector for each pixel then you get a noisy non-patterned image that still has less noise and converges faster than a truly randomly sampled image.
But Psychopath doesn't use Cranley Patterson Rotation. It uses a different technique to accomplish essentially the same thing.
Some LDS sequences are endless. You can keep drawing points from them forever, and they will never run out. Such LDS's have an interesting property: any contiguous subset of the sequence is also an LDS. A cool implication of this is that you can start drawing samples from anywhere in the sequence, and it's just as good as if you started at the beginning.
Psychopath exploits that by giving each pixel a random offset into the LDS. So, for example, the first pixel might have an offset of 42, meaning that it starts drawing samples at the 42nd sample. The second pixel might have an offset of 518,364,163, meaning that it starts drawing samples at the 518,364,163rd sample. Both pixels will get equally good samples, but they are both totally random with respect to each other.
The end result is this (@16spp):
It's slightly higher variance than using the LDS sequence directly (but still much lower variance than random sampling), but it has the same convergence properties and it avoids the pattern artifacts. It also allows us to draw endless samples for each pixel without worrying about the number of samples being drawn for other pixels, which is a big win if you want to do e.g. adaptive sampling.
The main benefit of this technique over Cranley Patterson Rotation is computation. You only need to generate a single random value with this technique, and do a single integer addition. With Cranley Patterson Rotation you have to generate an entire vector of random values, and as many floating point additions and modulo.
The main drawback compared to Cranley Patterson Rotation is that this only works with endless LDS's. But in practice that's not a significant restriction, because most practical LDS's (at least that I'm aware of) are endless.
Finally, credit and a huge thanks must go to Leonhard Grünschloß for the LDS code I'm using. Psychopath uses his Faure-permuted Halton sequence, which is available on his site. I am extremely grateful to him for making his LDS code freely available, because I am, frankly, not smart enough to implement anything more complex than a simple Halton sequence.