Crate sobol_burley

A seedable Owen-scrambled Sobol sequence.

This crate is based on the paper Practical Hash-based Owen Scrambling by Brent Burley, but with an improved hash from Building a Better LK Hash and more dimensions due to Kuo et al.

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

• The maximum sequence length is 2^16.
• The maximum number of dimensions is 256 (although this can be worked around with seeding).
• Only f32 output is supported.

These are all trade-offs for the sake of better performance and a smaller memory footprint.

Basic usage

Basic usage is pretty straightforward:

use sobol_burley::sample;

// Print 1024 3-dimensional points.
for i in 0..1024 {
    let x = sample(i, 0, 0);
    let y = sample(i, 1, 0);
    let z = sample(i, 2, 0);
    println!("({}, {}, {})", x, y, z);
}

The first parameter of sample() is the index of the sample you want, and the second parameter is the index of the dimension you want. The parameters are zero-indexed, and outputs are in the interval [0, 1).

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

Seeding

(Note: the sample() function automatically uses a different Owen scramble for each dimension, so seeding is unnecessary if you just want a single Sobol sequence.)

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

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. By changing the seed we can re-use the same dimensions over and over to create an arbitrarily high-dimensional sequence. For example:

// Print 10000 dimensions of a single sample.
for dimension in 0..10000 {
    let seed = dimension / 4;
    let n = sample(0, dimension % 4, seed);
    println!("{}", n);
}

In this example we change seeds every 4 dimensions. This allows us to re-use the same 4 dimensions over and over, extending the sequence to as many dimensions as we like. Each set of 4 dimensions is stratified within itself, but is randomly decorrelated from the other sets.

See Burley’s paper for justification of this padding approach as well as recommendations about its use.

SIMD

You can use sample_4d() to compute four dimensions at once, returned as an array of floats.

On x86-64 architectures sample_4d() utilizes SIMD for a roughly 4x speed-up. On other architectures it still computes correct results, but SIMD isn’t supported yet.

Importantly, sample() and sample_4d() always compute identical results:

for dimension_set in 0..10 {
    let a = [
        sample(0, dimension_set * 4, 0),
        sample(0, dimension_set * 4 + 1, 0),
        sample(0, dimension_set * 4 + 2, 0),
        sample(0, dimension_set * 4 + 3, 0)
    ];
    let b = sample_4d(0, dimension_set, 0);

    assert_eq!(a, b);
}

The difference is only in performance and how the dimensions are indexed.

Constants

NUM_DIMENSIONS	The number of available dimensions.
NUM_DIMENSION_SETS_4D	The number of available 4d dimension sets.

Functions

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