## Sobol' sequences

Practical and theoretical implementation discussion.
andersll
Posts: 22
Joined: Thu Mar 21, 2013 4:34 pm

### Sobol' sequences

I'm trying out Leonhard Gruenschloss's Sobol'-seqeunce generator from here: http://gruenschloss.org/

The first two dimensions look as expected (0,1):

but higher dimensions show the poor projections that I thought the "better 2d projections" paper was supposed to avoid. Have I misunderstood the what these are supposed to look like? Or should I be feeding it different pairs of dimensions to get a better result?

(14,15):

(24,25):

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

### Re: Sobol' sequences

Digging out old post, as i missed that apparently:
Unfortunately what you see is perfectly fine. Better 2D projections do not necessarily mean that each and every combination of two dimensions will look perfect at any amount of samples you decide to draw and visualize. It was just optimized to be (simplified speaking) awesome on the -average- for this use-case.

But it still remains unsure IMHO if this is actually what we need to optimize for in a rendering context. While each bounce in the simulation might be low-dimensional, overall we are still dealing with a high dimensional problem. And one of the issues with QMC is that it (again, simplified speaking) basically sucks at dealing with -real- high dimensional problems, especially when using only a small amount of samples.

That's why its really tricky to actually write a renderer that uses QMC -and- profits from it, while not showing (temporary) artifacts all over the place.
Better you leave here with your head still full of kitty cats and puppy dogs.

andersll
Posts: 22
Joined: Thu Mar 21, 2013 4:34 pm

### Re: Sobol' sequences

Thanks toxie. After thinking about it some more I'd sort of realised that was the case. I guess in the limit then the sequence explores the whole sample space in a nicely-distributed fashion, which isn't necessarily what I'm after.

What's considered "state of the art" these days?

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

### Re: Sobol' sequences

Thats another good question.

Sobol' is still top notch, but it comes with these nasty rectangular patterns in the projections by design. So no matter which construction variant you use, you will always have to scramble it, unless you do not care about intermediate patterns.
As you say, on the long run, all these gaps will be nicely filled, but that can take quite some samples, depending on which dimension(s) you look at.
Better you leave here with your head still full of kitty cats and puppy dogs.

cessen
Posts: 34
Joined: Sun Apr 14, 2013 9:34 pm

### Re: Sobol' sequences

andersll wrote:What's considered "state of the art" these days?
I don't know what's considered state of the art, but I've been quite happy with Leonhard Grünschloß's Faure-permuted Halton.

Here's 4096 points of 14,15:

Here's 4096 points of 24,25:

It's clearly not perfect, but it doesn't seem to fall apart as badly as the Sobol sampling you posted.

andersll
Posts: 22
Joined: Thu Mar 21, 2013 4:34 pm

### Re: Sobol' sequences

That does look a lot better, I'll give it a go, thanks! Does it have any bad 2d projections in other dimensions?

andersll
Posts: 22
Joined: Thu Mar 21, 2013 4:34 pm

### Re: Sobol' sequences

Actually looking back at my code, both examples were with 1024 samples. At 4096 samples the 14,15 space is completely covered, although I think the 24,25 space needs 8192 samples to be covered. How does the Faure-permuted Halton perform at lower sample counts?

cessen
Posts: 34
Joined: Sun Apr 14, 2013 9:34 pm

### Re: Sobol' sequences

I'm not at my machine where my test code is at the moment, but in the past I've done tests from 16 all the way up to over 64,000 samples (doubling the samples each time). IIRC they seemed to hold up just fine. There's definitely some uneven density in the higher dimensions, but not big holes (as I recall).

I may be misremembering, however. When I get home I'll try to remember to do some further tests and post some images of lower (and higher) sample counts.

andersll
Posts: 22
Joined: Thu Mar 21, 2013 4:34 pm

### Re: Sobol' sequences

I just tried halton this afternoon and found it to be slightly worse than sobol in a naive implementation. I also looked at your code and tried reordering the low dimensions as you do but found that gave me more noise than the default ordering. I think I need to spend some more time tweaking the implementation and testing projections etc.

cessen
Posts: 34
Joined: Sun Apr 14, 2013 9:34 pm

### Re: Sobol' sequences

Also, I don't have personal experience with this approach, but Pixar developed something they call "Multi-Jittered Sampling" that extends jittered sampling into high dimensions (if I'm remembering correctly): http://graphics.pixar.com/library/Multi ... dSampling/