ompf2.com

I am trying to figure out a way to generalize the golden ratio sequence to higher dimensions in a way that is extensible(does not make any assumption about the amount of samples that are going to taken), as well as scaling well to 6 or more dimensions.
The golden ratio sequence is desirable because it uses the irrationality of golden ratio to avoid the structured noise and moire artifacts of other sequences, and it is the cheapest low discrepancy sequence known, requiring only an addition and check for overflow.

update: I have tried doing 2 steps for the second, 1 for first, the result is that the diagonal resulting from using the same values for both x and y just repeats twice instead of once.

The original paper https://www.graphics.rwth-aachen.de/pub ... /2/jgt.pdf uses a permutation like the faure sequence to generalize sequence to 2 dimensions,
which assumes that i know how many samples are going to be taken, which I do not want to know.

A later paper http://www.researchgate.net/profile/Col ... 000000.pdf generalizes the sequence using a Hilbert Curve,
which I am not so confident about the performance in 32 bit precision, especially 6 or more dimensions(tell me if I am wrong) or the quality of it mapped to a sphere compared to the original.

One idea for the unit square i have is to take inspiration from the Halton sequence

What i would prefer is one generalization for the unit square and another one specifically for the unit sphere.

I cannot back this up with a citation or even only with plausible reasoning. But my first experiment would be bit interleaving, i.e. Z-order, also known as Morton code. In other words, instead of the Hilbert-Curve, I'd try a cheaper mapping from the unit interval to the unit square. I feel that the golden ratio's "maximal irrationality" should ensure that sample points are spread evenly across the "tiles" of any recursively defined self-similar curve. I would be surprised if that wasn't true on all scales of that fractal curve.

You need high precision arithmetic for the golden ratio constant and its wrap-around addition. If you want a mapping to 64 bit wide X and Y coordinates on the unit square, then 128 bits are required on the unit interval.

I cannot help you with the sphere mapping problem.

Thanks for your suggestion.

I gave golden ratio sampling along a Z-curve a try. It does cover the unit square nicely, but the sample spacing is less regular than true 2D low discrepancy sequences. I suspect that is due to the discontinuities of the Z-curve; the example images with the Hilbert curve looked a bit better in that regard. But overall the difference was not large. The Z-curve might well be good enough, depending on what exactly you need it for. It is certainly much better than purely random sample points; neither clusters nor gaps are nearly as bad.

More random remarks:
- Bit interleaving generalizes to an arbitrary number of dimensions, but the required precision for the golden ratio accumulator variable will grow fairly quickly.

- Independent threads of computation can be decorrelated nicely in the case of golden ratio sampling: just initialize each thread's accumulator independently at random. This is particularly neat for GPU computing, as each thread will continue to run identical code.

- Unfortunately, inverse bit interleaving isn't exactly cheap: http://graphics.stanford.edu/~seander/b ... bleObvious

- Some exotic RISC ISA extensions used to provide support for bit interleaving back in the 1990s. Not sure if any current (i.e. 'x86) machines still do.

- GPUs used to lay out textures in Z order. I don't know if they still do that, and if that address computation is available to programmers.

What I have figured out that I could do is take the Golden point set as described in the original paper and and then assume that a total of, for instance 2^64 will be generated, and then choose the index within the period with the van der corput sequence. The problem is however is given the how second coordinate is selected through a permutation, how to query the permuted index directly?