(For an update on Psychopath's Sobol sampler, please also see the next post in this series: Sobol Sampling - Take 2.)
Up until recently I was using Leonhard Grünschloß's Faure-permuted Halton sampler as my main sampler in Psychopath. I even ported it to Rust when I made the switch from C++. And it works really well.
I've also had a Rust port of Grünschloß's Sobol sampler in Psychopath's git repo for a while, and from time to time I played with it. But it never seemed notably better than the Halton sampler in terms of variance, and it was significantly slower at generating samples. This confused me, because Sobol seems like the go-to low discrepancy sequence for 3d rendering, assuming you want to use low discrepancy sequences at all.
However, I recently stumbled across some new (to me) information, which ultimately sent me down a rabbit hole implementing my own Sobol sampler. I'd like to share that journey.
Incidentally, if you want to look at or use my Sobol sampler, you can grab it here. It's MIT licensed. (Note from the future: this link is to the code as of the writing of this post. See the above-linked second post for a significantly improved version.)
Don't Offset Sobol Samples
The first two things I learned are about what not to do. And the title of this section actually refers to both of those things simultaneously:
- Cranely Patterson Rotation.
- Randomly offseting your starting index into the sequence for each pixel.
These are two different strategies for decorrelating samples between pixels. The first offsets where the samples are in space, and the second offsets where you are in the sequence. Both are bad with Sobol sequences, but for different reasons.
Cranley Patterson Rotation is bad because it increases variance. Not just apparent variance, but actual variance. It's still not entirely clear to me why that's the case—it feels counter-intuitive. But I first found out about it in the slides of a talk by Heitz, et al. about their screen-space blue noise sampler. It's also been borne out in some experiments of my own since then.
So the first lesson is: don't use Cranley Patterson Rotation. It makes your variance worse.
Randomly offsetting what index you start at for each pixel is bad for a completely different reason: it's slow. Due to the way computing Sobol samples works, later samples in the sequence take longer to compute. This is what was making it slow for me. I already used this technique with the Halton sampler, to great success. So I assumed I could just apply it to Sobol as well. And you can. It works correctly. It just ends up being comparatively slow.
So the second lesson is: don't offset into your Sobol sequence (at least not by much).
The Right Way to Decorrelate
So if you can't do Cranley Patterson Rotation, and you can't offset into your sequence, how can you decorrelate your pixels with a Sobol sampler?
The answer is: scrambling.
There are two ways (that I'm aware of) to scramble a Sobol sequence while maintaining its good properties:
- Random Digit Scrambling
- Owen Scrambling
Random digit scrambling amounts to just xoring the samples with a random integer, using a different random integer for each dimension. The PBRT book covers this in more detail, but it turns out that doing this actually preserves all of the good properties of the Sobol sequence. So it's a very efficient way to decorrelate your pixels.
I gave that a try, and it immediately made the Sobol sampler comparable to the Halton sampler in terms of performance. So it's definitely a reasonable way to do things.
But then, due to a semi-unrelated discussion with the author of Raygon, I ended up re-reading the paper Progressive Multi-Jittered Sample Sequences by Christensen et al. The paper itself is about a new family of samplers, but in it they also compare their new family to a bunch of other samplers, including the Sobol sequence. And not just the plain Sobol sequence, but also the rotated, random-digit scrambled, and Owen-scrambled Sobol sequences.
The crazy thing that I had no idea about, and which they discuss at length in the paper, is that Owen scrambled Sobol actually converges faster than plain Sobol. That just seems nuts to me. Basically, Owen scrambling is the anti-Cranley-Patterson: it's a way of decorrelating your pixels while actually reducing variance. So even if you're not trying to decorrelate your pixels, it's still a good thing to do.
(As an interesting aside: random digit scrambling is a strict subset of Owen scrambling. Or, flipping that around, Owen scrambling is a generalization of random digit scrambling. But what's nice about that is you can use the same proof to show that both approaches preserve the good properties of Sobol sequences.)
Implementing Owen Scrambling Efficiently
The trouble with Owen scrambling is that it's slow. If you do some searches online, you'll find a few papers out there about implementing it. But most of them are really obtuse, and none of them are really trying to improve performance. Except, if I recall correctly, there's one paper about using the raw number crunching power of GPUs to try to make it faster. But that's not really that helpful, since you probably want to use your GPU for other number crunching.
So it basically seems like Owen-scrambling is too slow to be practical for 3d rendering.
Except! There's a single sentence in the "Progressive Multi-Jittered Sample Sequences" paper that almost seems like an afterthought. In fact, I almost missed it:
We do Owen scrambling efficiently with hashing – similar in spirit to Laine and Karras [LK11], but with a better hash function provided by Brent Burley.
"LK11" refers to the paper Stratified sampling for stochastic transparency by Laine et al. The really weird thing is that this paper isn't even about Sobol sampling. But they, too, have a one-liner that's really important:
This produces the same result as performing an Owen scramble [...]
What they're referring to here is a kind of hashing operation. They use it to decorrelate a standard base-2 radical inverse sequence, but the same approach applies just as well to Sobol sequences.
But you can't just use any hash function. In fact, you have to use a really specific, weird, special kind of hash function that would be a very poor choice for any application that you would typically use hashing for.
Here's the basic idea: the key insight Laine et al. provide is that Owen scrambling is equivalent to a hash function that only avalanches downward, from higher bits to lower bits. In other words, a hash function where each bit only affects bits lower than itself. This is a super cool insight! And it means that if we can design a high-quality, efficient hash function with this property, then we have efficient Owen scrambling as well.
It turns out, though, that developing a high-quality hash function that meets these criteria is pretty challenging. For example, the hash function they present in the paper, while fast, is pretty poor quality. Nevertheless, I decided to take a crack at it myself.
So far, I've stuck to the general approach from Laine et al., but worked on optimizing the constants and tweaking a few things. I don't think I've gained any real insights beyond their paper, but I have nevertheless made some improvements through those tweaks. At this point, I have a hash function that I would call "okay" for the purposes of Owen scrambling. But there is very clearly still a lot of room for improvement.
I'm extremely curious what the implementation from "Progressive Multi-Jittered Sample Sequences" looks like. And I'm especially curious if there are any interesting insights behind it regarding how to construct this bizarre kind of hash function.
My Sobol Sampler
Again, you can grab my Sobol sampler here if you like.
It includes implementations of all the (non-slow) decorrelation approaches I mentioned in this post:
- Cranley-Patterson rotation
- Random Digit Scrambling
- And hash-based Owen Scrambling
It also includes, of course, plain non-scrambled Sobol.
If you do make use of this somewhere, I strongly recommend using the Owen-scrambled version. But it can be fun to play with the others as well for comparison.
However, one thing I noticed in my testing is that Cranley-Patterson rotation seems to do a better job of decorrelating pixels. The two scrambling approaches seem to exhibit some correlation artifacts in the form of clusters of mildly higher-variance splotches in certain scenes. It's mild, and Owen scrambling still seems to win out variance-wise over Cranely-Patterson. But still. This is definitely a work in progress, so be warned.
Regardless, I've had a lot of fun with this, and I've learned a lot. Pretty much everything I talked about in this post was like black magic to me before diving head-first into all of it. I definitely recommend looking into these topics yourself if this post was at all interesting to you.