Avoiding correlation patterns in Sobol sampling?

Practical and theoretical implementation discussion.
Post Reply
Thammuz
Posts: 22
Joined: Mon Nov 28, 2011 8:36 am
Location: Stockholm

Avoiding correlation patterns in Sobol sampling?

Post by Thammuz » Sat Nov 17, 2012 9:35 pm

Hi,

I recently started using Sobol sequences for sampling, and I was quite blown away of how they improved convergence speed...truly mind blowing.

That said, I do have some questions.

1. The correlation patterns are quite heavy in the beginning and I find them quite distracting (they disappear completely later on though) , is there a good way to break up the correlation pattern while still enjoying the full benefit of the sequence? (I tried pre-generating 1D and 2D samples and scrambling them for each pixel, and it was quite evident that this was not a good way). Right now I'm playing "choose your favorite correlation pattern" by changing the starting dimension...

2. Right now, I'm running a sequence generator for each render thread, for both pixel position, bounce direction and decision parameter generation. I use different scramble values for each thread. So I'm wondering, is this the "correct" way to generate different sequences for different threads or is there some other, better, way?

3. What is a "good" way of advancing in the sequence (not advancing through dimensions, but indices), I've looked at many different implementations....and not knowing any better I'd say they all look arbitrary (I might be wrong here), it's always some combination of current pixel index, pass count, some constants combined together and incremented somehow. Needless to say, my current implementation is quite arbitrary, but it works (at least judging from the rendered images). So yeah, is there a "standard", "good" way of advancing through the indices?

Thanks

Mario

toxie
Posts: 118
Joined: Mon Nov 28, 2011 12:30 pm
Location: germany
Contact:

Re: Avoiding correlation patterns in Sobol sampling?

Post by toxie » Mon Nov 19, 2012 3:33 pm

1) scrambling by definition usually jeopardizes the distribution of the points, at least if you look at the distribution of certain subsequences, and not just "in the limit" (i.e. picking an infinite number of samples), so unfortunately there is no general help with that without impacting the distribution characteristics, so in general i'm against using scramblings if possible.. a very simple thing you can do though is to just pick a different (random) offset for each pixel (-> what you call pass count), this can resolve -some- correlations.. another simple thing to try is XORing a different (random) value for each pixel to either the "pass count" or the integer that drops out of the sobol generator (-> before it is converted to float), again this can resolve some correlations, but note that this is much more agressive (it's one kind of scrambling after all, not just using a different subsequence) than the offset trick.. then there is a ton more stuff, but it just gets trickier and trickier..

2) no, that's fine (from what i understand what you're -actually- doing), or how do you use the sobol generator for generating pixel pos (2 samples/dimensions), bounce (i guess 2 samples/dimensions for sampling the hemisphere plus x?) and "decision"?

3) there is basically only one way to do so (plus implementation/optimization magic), so which implementation do you use?
Better you leave here with your head still full of kitty cats and puppy dogs.

Thammuz
Posts: 22
Joined: Mon Nov 28, 2011 8:36 am
Location: Stockholm

Re: Avoiding correlation patterns in Sobol sampling?

Post by Thammuz » Mon Nov 19, 2012 10:01 pm

Thanks for your suggestions, they really helped me, and I now have an implementation that both converges super fast and that has an acceptable correlation pattern that doesn't interfere between threads. It also gives good results even for the most pathological test scenes that I have. I basically switched from just assigning a random scramble value to each thread and scrambling the "old" way, i.e before xor-ing with the matrix values, to scrambling in the way you suggested (before converting to float).
So, what I do now is:

At thread startup:
1. generate 2 scramble values per thread (one for the sequence, and one for the pixels), also these 2 values never change during the course of rendering
2. generate a starting position for the index counter unique between threads by: index = (Long.MAX_VALUE / numthreads) * threadNum

At rendering (also answering your question in bullet 2)

For every sample/new pixel:
1. set dimension = 0
2. generate sobolIndex = index ^ indexScramble
4. generate pixel coordinate = Point2f(sobol(sobolIndex, dimension++, scramble), sobol(sobolIndex, dimension++, scramble)
5. generate the rest of the samples (1D & 2D) just as above when they're requested by the integrator, by just increasing the dimension and ensuring dimension < MAX_DIMENSIONS
6. index++
Next sample: go to 1.

I'm not sure that the above is the correct way of doing it (please do enlighten me if it isn't), but it produces good results, and it beats the pure random sampler by far. Also, as for your question in 3, I was just arbitrarily doing someIndex++ and just progressing in sequence, not knowing any better. But I'm curious, what is this "only one way to do so" that you speak of in 3, I must say I'm clueless.

Thanks again

toxie
Posts: 118
Joined: Mon Nov 28, 2011 12:30 pm
Location: germany
Contact:

Re: Avoiding correlation patterns in Sobol sampling?

Post by toxie » Tue Nov 20, 2012 9:48 am

So far this looks fine, i just don't get why you scramble both the index and the output (it's valid, but doesn't look necessary except for introducing more chaos)..

As for the last question: The scheme to generate sobol points is always the same: Have a set of polynomials and direction numbers that fulfill certain properties over all the wanted dimensions, then use these to generate the samples from.. Then there are various ways to implement the generator.. Either you don't wanna spend more memory and go for a construction directly from these (potential optimizations: use gray code scrambled input indices, but this only works if you draw indices one after another for one dimension (only one bit changes then each time, so less opcodes necessary), so useless in your case) or you generate matrices from these for the (bit-)multiplication in a pre-process (potential optimizations: can exploit SIMD easily during runtime) at the price of a bit of additional memory..
But as you just use your sobol generator as a blackbox, everything seems to be fine already.. ;)
Better you leave here with your head still full of kitty cats and puppy dogs.

Thammuz
Posts: 22
Joined: Mon Nov 28, 2011 8:36 am
Location: Stockholm

Re: Avoiding correlation patterns in Sobol sampling?

Post by Thammuz » Fri Nov 23, 2012 9:57 pm

Thanks for the help Toxie, but for the moment my conclusion is that
Image

So, until I've waded through what seems to be the required heap of papers required for one to properly generate proper sequences across threads, I'll take a break from them.
On the upside though, I've found permuted Halton sequences quite to my liking, so I'm sticking to them until I've become wiser on the sobol issue.

Thammuz
Posts: 22
Joined: Mon Nov 28, 2011 8:36 am
Location: Stockholm

Re: Avoiding correlation patterns in Sobol sampling?

Post by Thammuz » Fri Nov 30, 2012 8:55 am

Ok, so a small update. The problems I were having were related to me trying to do it across 8 threads without first making sure it works for one thread. So, now I managed to find a way to generate the sequence across 8 threads in graycode order and no scrambling (I'm using a shared index counter with synchronized access...which to my surprise gave me a performance increase). It's working like a charm, and the correlation patterns aren't as bad or stubborn any more. The convergence rates are unlike anything I've seen before and even beats my metropolis sampler (at least visually) on some scenes with caustics. Thanks for pointing me in the right direction Toxie! Btw, I'm using the direction numbers from http://web.maths.unsw.edu.au/~fkuo/sobol/ ("new-joe-kuo-6.21201 "), which I then process for random access, like Gruenschloss. I've also verified my generator against the sample C++ program provided on their website, that also generates the sequence in graycode order.

Post Reply