The quest for a perfect quasi-random sequence

We want a function that maps sequential values (entities concurrently living in a scene usually have ids that are sequential) into very different colors (the hue component of the color, to be specific)

What we are looking for is a so-called “low discrepancy” sequence. ie: a function f such as for integers in a given range (eg: 101, 102, 103…), f(i) returns a rational number in the [0..1] range, such as |f(i) - f(i±1)| ≈ 0.5 (maximum difference of images for neighboring preimages)

AHash is a good random hasher, but it has relatively high discrepancy, so we need something else. Known good low discrepancy sequences are:

The Van Der Corput sequence

fn van_der_corput(bits: u64) -> f32 {
    let leading_zeros = if bits == 0 { 0 } else { bits.leading_zeros() };
    let nominator = bits.reverse_bits() >> leading_zeros;
    let denominator = bits.next_power_of_two();

    nominator as f32 / denominator as f32
}

The Gold Kronecker sequence

Note that the implementation suggested in the linked post assumes floats, we have integers

fn gold_kronecker(bits: u64) -> f32 {
    const U64_MAX_F: f32 = u64::MAX as f32;
    // (u64::MAX / Φ) rounded down
    const FRAC_U64MAX_GOLDEN_RATIO: u64 = 11400714819323198485;
    bits.wrapping_mul(FRAC_U64MAX_GOLDEN_RATIO) as f32 / U64_MAX_F
}

Comparison of the sequences

So they are both pretty good. Both only have a single (!) division and two u64 as f32 conversions.

• Both do not care much about the generation (consider that entity.to_bits() will usually be a value in the form ‘x·2³² + y’)
• Kronecker is resilient to regular sequence (eg: 100, 102, 104, 106) while this kills Van Der Corput (consider that potentially one entity out of two spawned might be a mesh)

I made a small app to compare the two sequences, available at: https://gist.github.com/nicopap/5dd9bd6700c6a9a9cf90c9199941883e

At the top, we have Van Der Corput, at the bottom we have the Gold Kronecker. In the video, we spawn a vertical line at the position on screen where the x coordinate is the image of the sequence. The preimages are 1,2,3,4,… The ideal algorithm would always have the largest possible gap between each line (imagine the screen x coordinate as the color hue):

https://github.com/bevyengine/bevy/assets/26321040/349aa8f8-f669-43ba-9842-f9a46945e25c

Here, we repeat the experiment, but with with entity.to_bits() instead of a sequence:

https://github.com/bevyengine/bevy/assets/26321040/516cea27-7135-4daa-a4e7-edfd1781d119

Notice how Van Der Corput tend to bunch the lines on a single side of the screen. This is because we always skip odd-numbered entities.

The kronecker sequence seems better, so I used it.