(For yet another update on Psychopath's Sobol sampler, as well as significantly better LK hashes, please see the next post in this series: Building a Better LK Hash.)

Shortly after I wrote my last post about Sobol sampling, I got in contact with Brent Burley, who created the hash-based Owen scrambling used in the paper Progressive Multi-Jittered Sample Sequences. He was extremely kind, and spared some time to chat with me about his Sobol sampler. He has also now published a paper about it:

Practical Hash-based Owen Scrambling, by Brent Burley

Unsurprisingly, it goes beyond what I had figured out on my own, and improves upon existing Sobol samplers in multiple ways. It's really an amazing paper, and I highly recommend giving it a read.

As it says in the title, it presents an efficient hash-based Owen scrambling technique. But it also presents a way to efficiently shuffle the order of the points in the sequence using the same hashing approach.¹ The shuffling allows you to create as many statistically uncorrelated Sobol sequences as you like, which is crazy useful. For example, as described in the paper, you can pad a Sobol sequence with another Sobol sequence.

The combination of these two things—the shuffling and the Owen scrambling—creates a very powerful, very high-quality sampler. And it's efficient enough to be computed on-the-fly while rendering.

My Sobol sampler is now essentially the same as what's described in Burley's paper, so you can just read the paper to know what I'm doing. But my implementation does depart in one small way, which I believe is a tiny but worthwhile contribution, and is what the rest of this post is about.

The LK hash

The hash function used in Brent Burley's paper is taken from Stratified Sampling for Stochastic Transparency by Laine et al., and Burley variously refers to it as both the "Laine-Karras permutation" and the "Laine-Karras hash". For brevity, I'll be calling it the "LK hash". Here is the pseudo code:

function lk_hash(x, seed) {
    x += seed
    x ^= x * 0x6c50b47c
    x ^= x * 0xb82f1e52
    x ^= x * 0xc7afe638
    x ^= x * 0x8d22f6e6
    return x
}

The critical property of this function is that, unlike a normal hash, it only avalanches upward, from lower bits to higher bits. In other words, it's a hash function where each bit only affects bits higher than itself.

This is the opposite of Owen scrambling, which is equivalent to a hash that only avalanches downward. However, it's easy to turn it into an Owen scrambling function: just reverse the order of the bits both before and after it:

function owen_scramble(x, seed) {
    x = reverse_bits(x)
    x = lk_hash(x, seed)
    x = reverse_bits(x)
    return x
}

Burley also uses the LK hash for shuffling the order of the Sobol points. So functions with this upward-only-avalanche property are really useful: they can be used both for shuffling and for Owen scrambling.

The only problem is that this particular function isn't especially high-quality.² It seems to be good enough in practice for rendering, so it may not actually be worth improving. But it still bugs me. Let's take a look.

Here is a fully Owen scrambled sequence as ground-truth, computed using a much slower technique (from left-to-right are 64, 256, 1024, and 4096 points from the sequence, respectively):

And here is the bit-reversed LK hash:

It looks pretty good, but the higher sample counts are visibly different. In particular, at 1024 samples there is an obvious structure to it. And at 4096 samples the "texture" of the samples is different (though you may need to click to view the full-size images to see it clearly).

Making a better hash function

I first tried to improve this by optimizing the constants, using more permutation rounds, etc. That's where I was when I wrote my previous Sobol post. And although it did help some, all of the results still had obvious issues, especially when looking at other dimension pairs.³

After getting in touch with Brent Burley, however, I was inspired to take another crack at it. It was at that point that I tried different permutation operations. The first real success was adding x += x << 1 to each round:

function lk_improved_v1(x, seed) {
    x += seed
    x ^= x * 0x6c50b47c
    x += x << 1
    x ^= x * 0xb82f1e52
    x += x << 1
    x ^= x * 0xc7afe638
    x += x << 1
    x ^= x * 0x8d22f6e6
    x += x << 1
    return x
}

The result is this:

This is visibly much better than the original LK hash, especially at 1024 samples. The main problem is that it's also slower. Mind you, it's still plenty fast. But I really wanted to make a hash that works better and is at least as fast as the original LK hash.

The astute among you (more astute than I was at the time) may notice something a little fishy about the new operation I added. I originally came up with it by specifically trying to make something that only avalanches upward. But it also turns out to be the same as just multiplying x by 3.

When I finally noticed that, and after a bit more thought, I realized that multiplying by odd numbers is also a valid operation in a hash like this. So, all together, these are the permutations I'm currently aware of that are valid for constructing a hash like this:

1. x ^= constant
2. x += constant
3. x *= odd_constant
4. x ^= x * even_constant

You can mix and match these to try to create better hashes. There are likely even more valid permutations, but I don't know what they might be.

Playing around with those permutations, I came up with this hash:

function lk_improved_v2(x, seed) {
    x += seed
    x ^= 0xdc967795
    x *= 0x97b754b7
    x ^= 0x866350b1
    x *= 0x9e3779cd
    return x
}

(UPDATE: please do NOT use this hash. It turns out that it's not very good. Please see the next post in this series for hashes that are actually worth using.)

And here are the results:

It's not quite as good as the previous one, but it's close. And it's still much better than the original LK hash. Moreover, it's faster than both of them: this version only takes 5 CPU operations, compared to the 9 and 17 ops of the other two.

This version is what I'm now using in Psychopath. It works at least as well as the original LK hash, and is a bit faster.

In practice, I don't notice any difference in render quality between any of these different hashes, or even between them and full Owen scrambling for that matter. So... it probably doesn't really matter. But it makes me feel better that this is a bit closer to a full Owen scramble.

Final thoughts

I certainly don't think I've come up with the best possible hashes. There's clearly still room for improvement.

Moreover, a quantitative analysis of hash quality would be really useful here. I did measure upward avalanche with some bespoke throw-away testing code, and the results suggested that these new hashes do improve things. But my testing wasn't careful or thorough, and there could easily have been awful bugs in my testing code. So I don't actually trust the results.

I hope that this post can serve as a starting point for other people to develop even better LK-style hashes. And if someone does further work on this, I'd love to hear about it! But for the time being, I'm quite satisfied with what I've arrived at.

For the curious, here is my implementation.

Footnotes

1. In my previous post I said that you shouldn't offset into Sobol sequences, because it makes Sobol sampling slow. And yet that's more-or-less what shuffling does, just in a much more sophisticated way. Indeed, shuffling will also make the Sobol sampler slower in the same way that offsetting does. However, since writing my last post I've discovered a couple of ways to mitigate that performance impact. Moreover, it's trivial to evaluate multiple Sobol dimensions at once with SIMD, which my sampler now does. So, it's quite performant now.

2. Burley notes in his paper that measuring hash quality is a complex endeavor, and that he uses the original LK hash due to the testing and claims of the original authors. It's also important to note that in practice the LK hash seems to perform very well in rendering applications. So I think Burley's choice to use the hash as-is in his paper was a good one.

   However, looking at the actual points it generates, it obviously has room for improvement. Moreover, in the Laine-Karras paper I saw no indication that they developed the hash in any kind of rigorous way. Even further, they say this about the constants used in their hash:

   The multiplication constants are the ones used in generating the images in this paper, but they carry no particular significance beyond that.

   So my strong suspicion is that they essentially just eye-balled it until it worked well enough for their particular use-case.

3. For brevity, the images in this post only show the first two Sobol dimensions. In my testing, however, I looked at over 50 different dimension pairs, which revealed similar differences between the LK hash and the full Owen scramble. The improved hashes in this post fix those differences about as well as the differences in the first two dimensions. Which is to say, it's notably better, but certainly still has room for improvement.