Crate sobol_burley

A seedable Owen-scrambled Sobol sequence.

This is based on the paper Practical Hash-based Owen Scrambling by Brent Burley, with an improved hash from Building a Better LK Hash, and a larger set of direction vectors due to Kuo et al.

This crate is geared towards use in practical graphics applications, and as such has some limitations:

• The maximum sequence length is 2^16.
• The maximum number of supported dimensions is 256.
• It produces 32-bit floats rather than higher-precision 64-bit floats.

Basic usage

Basic usage is pretty straightforward. The first parameter of sample_4d() is the index of the sample you want, and the second parameter is the index of the set (of four) dimensions you want. The parameters are zero-indexed, and the outputs are in the interval [0, 1).

// Print the first sixteen dimensions of sample 1.
for d in 0..4 {
    let [w, x, y, z] = sample_4d(0, d, 0);
    println!("{} {} {} {}", w, x, y, z);
}

// Print the first sixteen dimensions of sample 2.
for d in 0..4 {
    let [w, x, y, z] = sample_4d(1, d, 0);
    println!("{} {} {} {}", w, x, y, z);
}

If all you want is a single standard Owen-scrambled Sobol sequence, then this is all you need. You can ignore the third parameter.

Advanced usage and seeding

The third parameter of sample_4d() is a seed that produces statistically independent Sobol sequences via the scrambling+shuffling technique in Brent Burley’s paper (linked above).

One of the applications for this is to decorrelate the error between related integral estimates. For example, in a 3d renderer you might pass a different seed to each pixel so that error in the pixel colors shows up as noise instead of as structured artifacts.

Another important application is “padding” the dimensions of a Sobol sequence with another Sobol sequence. For example, if you need more than 256 dimensions you can do this:

use sobol_burley::{sample_4d, NUM_DIMENSION_SETS};

// Generate 40000 dimensions.  (Remember the dimensions
// are generated in sets of four.)
for n in 0..10000 {
    let dimension_set_index = n % NUM_DIMENSION_SETS;
    let seed = n / NUM_DIMENSION_SETS;

    let sample = sample_4d(0, dimension_set_index, seed);
}

In this example, each contiguous set of 256 dimensions has a different seed, and is therefore only randomly associated with the other sets even though each set is stratified within itself.

At first blush, being randomly associated might sound like a bad thing. Being stratified is better, and is the whole point of using something like the Sobol sequence. However, at practical sample counts the stratification of the Sobol sequence in high dimensions breaks down badly, and randomness is often better.

In fact, often using sets of just 2 to 4 stratified dimensions or so, and mapping them carefully to your problem space, avoids artifacts and is a win for convergence at practical sample counts. See Burley’s paper for details.

Constants

NUM_DIMENSION_SETS

The number of available dimension sets.

Functions

sample_4d

Compute four dimensions of a single sample in the Sobol sequence.