A review. Sections 01 to 05 describe published work by others, with the code as they printed it and labs that run that code. Section 06 places our own articles, From Stateful to Stateless Blue Noise, Stateless Blue Noise Generators and Stateless Blue Noise in Space and Time, among them. Where a statement about a source has not yet been checked against the source, the page's source carries a note, and the page stays a draft.
01The Radical Inverse
Write the sample's index in binary and mirror it about the binary point: 1 becomes 0.1, 2 becomes 0.01, 3 becomes 0.11, 6 (110) becomes 0.011. This is the van der Corput sequence, from 1935. The lowest bit of the index becomes the highest bit of the sample, so consecutive samples land in opposite halves, every four in four different quarters, every 2k in 2k different intervals.
Mirror the indexDetails
Read the other way round, it is a dither matrix. The sequence says where sample t goes; an ordered dither says at which brightness cell x switches on. Mirroring the bits is its own inverse, so in one dimension the two tables are the same table: eight cells switch on in the order 0, 4, 2, 6, 1, 5, 3, 7. Bayer's matrix is the same construction in the plane: interleave the bits of y and of x XOR y, y above, and mirror the result.
The Sobol' sequence does the same in several dimensions at once: the first coordinate is the radical inverse, and each further coordinate multiplies the index bits by a matrix first, chosen so that the points are even not only along each axis but in every box of a power-of-two size. For two coordinates every such box is exact. That is a (0, 2)-sequence, and section 04 shows it.
02Owen's Nested Scrambling
A perfectly regular sequence has two faults as a source of samples. Its error is the same every time, so it cannot be averaged away or even estimated; and every pixel of an image makes the same error, which shows as a pattern. The sequence has to be randomized. The question is how far it can be randomized without losing its evenness.
The cheapest answer, random digit scrambling, XORs every sample with one random word. It moves the pattern and keeps its shape. Art Owen's answer, from 1995, goes as far as it is possible to go. What his scrambling promises:
Taken on its own, over the choice of seed, a scrambled sample is uniformly distributed. An average of them is an unbiased estimate, whatever is being averaged.
For every seed, every interval of a power-of-two size still holds exactly its share of any aligned power-of-two block of samples. In several dimensions, every box.
Burley: it "maximally randomizes low-discrepancy sequences while preserving multidimensional stratification." Everything the evenness does not force is left to chance.
What that buys is a better rate of convergence. In Burley's measurements, independent sampling "converges as O(N−1⁄2) in every case"; for smooth functions, "Sobol sampling with random digit scrambling converges as O(N−1), while Owen-scrambled Sobol approaches O(N−3⁄2) when N is a power of two." For functions that are not smooth it is never much worse than independent sampling, and it is "less susceptible to structured artifacts than random digit scrambling." The third card is what earns the extra half power: within each small interval the samples are placed at random, so the errors of the intervals cancel like noise instead of adding up like a pattern.
The construction is short. Each digit of the sample is permuted, and the permutation is chosen separately for every value of the digits above it. Burley states it for any base b: given x = 0.a1a2a3…, the scrambled digit is bj = πa1…aj−1(aj), "for each digit of the b-ary fraction, the digits to the left are used to select a permutation to be applied to the digit."
In base two a permutation of one bit is a flip or no flip, so the whole scramble is a binary tree with one random bit at every node. The first bit has one node. The second has two, one for each half. The third has four.
A tree of flipsDetails
The test behind those rates is the simplest use samples are put to. Take a function on the interval from 0 to 1, and estimate its average height by averaging its height at N sample points. The true average is known, so the error of the estimate can be measured, and measured again with another seed. The lab does that for three functions: a smooth bump, the parabola x², and a step that is 1 below 0.3 and 0 above it, which stands for an edge in an image.
What the scramble buysDetails
| Samples | Error at 1024 | Rate |
|---|
Random across seeds, regular along the index
It is worth being exact about where the randomness of a scrambled sequence lives. The flips are drawn once. After that the sequence is a fixed schedule: with one seed, samples 0 to 15 visit the sixteenths of the interval in some order, and samples 16 to 31 visit them in the same order again, and so on for ever, with only the finer bits differing. Each bit of the sample is periodic in the index, the top bit with period 2, the next with period 4. Nothing about it is noise in time, blue or otherwise. It is even in every window, aligned or sliding, more strictly than any random stream can be: at threshold ½, every window of 16 consecutive samples holds exactly 8 below it, wherever the window starts.
The randomness is between seeds. Two pixels with two seeds get two different schedules, and an average over seeds is unbiased, which is what a renderer needs: the samples of a pixel are used as a set, and the order in which they arrive is of no interest beyond each power-of-two prefix being a complete set. A stream that is random along the index as well is a different requirement, and it is the subject of section 06.
03One Hash for the Whole Tree
A tree of 232 random bits cannot be stored, and hashing the bits above each bit costs one hash per bit. Laine and Karras (2011) found a way to do all levels at once. Burley's account of it: "when multiplying an input value by an even constant, each input bit only affects bits to the left and thus performs a nested hash. And because each multiplication result is used only to select one of the two possible permutations of each bit (via the XOR operator), the result is a nested uniform permutation." As he prints it:
/* Burley 2020, Listing 1: the Laine-Karras permutation. */
uint32_t laine_karras_permutation(uint32_t x, uint32_t seed)
{
x += seed;
x ^= x * 0x6c50b47cu;
x ^= x * 0xb82f1e52u;
x ^= x * 0xc7afe638u;
x ^= x * 0x8d22f6e6u;
return x;
}In this function a bit is changed by the bits below it. Owen's scramble needs a bit to be changed by the bits above it, so Burley reverses the bits before and after:
/* Burley 2020, Listing 2: nested uniform scrambling in base two. */
uint32_t nested_uniform_scramble(uint32_t x, uint32_t seed)
{
x = reverseBits(x);
x = laine_karras_permutation(x, seed);
x = reverseBits(x);
return x;
}Which bits can change whichDetails
| Radical inverse | Laine-Karras | XOR first row |
|---|
Burley also shows what the permutation is not. On its own, he writes, "the result is not an Owen scramble as the hash serves primarily to permute the sample order, achieving only minimal randomization equivalent to random digit scrambling; thus, it is more appropriate to refer to the Laine-Karras permutation as a nested uniform shuffle." That distinction is the next section.
04Scramble the Values, Shuffle the Index
The same function can be applied in two places. Applied to a sample's value it is a scramble: the points move, and every box keeps its count. Applied to the sample's index, before the sequence is evaluated, it is a shuffle: the points of the sequence are visited in another order, and every power-of-two prefix is still a complete, even set. Burley's sampler does both, with different seeds (his Listing 3):
/* Burley 2020, Listing 3: shuffled scrambled Sobol sampling. */
void shuffled_scrambled_sobol4d(uint32_t index, uint32_t seed,
uint32_t X[4])
{
index = nested_uniform_scramble(index, seed);
sobol4d(index, X);
for (int i = 0; i < 4; i++) {
X[i] = nested_uniform_scramble(X[i], hash_combine(seed, i));
}
}The shuffle is what lets many pixels, or many uses within a pixel, share one sequence without sharing its order. In his words it enables "decorrelated reuse of the sequence for padding to higher dimensions", and the whole construction runs "on-the-fly" for "sequences of indeterminate length and dimension and in arbitrary sample order, readily permitting parallel, progressive, or adaptive integration."
What "even" means in two dimensions
Each index of the sequence gives a point with two coordinates, both between 0 and 1. Take the first N = 64 points in the unit square, and cut the square into 64 boxes of equal area. There are seven ways to do that with power-of-two sides: 64 thin columns, 32 by 2, 16 by 4, the 8 by 8 grid, and on to 64 flat rows. The first two dimensions of the Sobol' sequence put exactly one point in every box of every one of those seven cuts, with the same 64 points. That is the whole property, and it is a strong one. A regular 8 by 8 grid of points passes only the 8 by 8 cut: its thin columns hold eight points or none. One jittered point per grid cell passes only that cut too. One point per row and per column, the rooks pattern, passes only the two extreme cuts. Independent random points pass none.
Drag the Boxes slider from end to end with any of the first five choices selected: the grid sweeps from columns to rows and no box ever turns red. Select independent random points and every cut shows red. Then compare Scrambled with Shuffled and watch the amber rings, which mark the first half of the points: scrambling moves all the points and keeps their order, shuffling changes which points come first. In every case the ringed half is an even set on its own, in boxes twice the size, which is what lets a renderer stop early.
Two dimensions of Sobol', scrambled and shuffledDetails
05A Scrambled Order of Pixels
Ahmed and Wonka (2020) apply the same idea to the image plane. From their abstract: error is diffused automatically "by ordering the pixels in a way that preserves locality, such as Morton's Z-ordering" and assigning samples "from successive sub-sequences of a single low-discrepancy sequence", and "a blue-noise distribution of the error is attainable by scrambling the Z-ordering to induce isotropy." Neighbouring pixels get neighbouring stretches of one sequence, and a sequence puts neighbouring samples far apart, so neighbouring pixels make different errors.
Nathan Vegdahl's 2022 reimplementation reduces the scrambled ordering to one line: it "is, in fact, identical to base-4 Owen scrambling over Morton-ordered indices." Interleave the bits of x and y, take them two at a time, most significant first, and let a hash of the pairs above choose one of the 24 orders of the four quadrants. His loop:
// Nathan Vegdahl, psychopath.io, 2022 (CC BY-SA)
for (x, y) in pixels:
morton_i = morton_encode(x, y)
sample_offset = owen_scramble_base_4(morton_i, seed) * spp
for i in range(0, spp):
render_sample(x, y, sample_offset + i)One sample per pixel from one sequenceDetails
Vegdahl is plain about the limit, which he says the paper shares: "you only get a blue noise distribution at full sample counts." The order is tied to the number of samples per pixel it was laid out for.
06Where Our Generators Sit
Our blue noise generator came from error diffusion, not from sampling theory: a tree of small ditherers, one per bit of the output, then the same tree with nodes that only remember a pair. The step to nodes that remember nothing was proposed by the AI co-author of these articles when asked whether the machine could be made stateless, and it lands inside this literature, very likely because that is where it came from, through the model's training data.
| Output bit l of sample t is bit l of t, flipped by a hash of | |
|---|---|
| the output bits above it | Owen's scramble of the radical inverse (sections 02 and 03) |
| t >> (l + 1), the index bits above it | the Laine-Karras shuffle (section 04) |
| one of each, XORed | Burley's shuffled scrambled sequence, one dimension |
| both together, in one hash | our stateless generator |
So the stateless generator is Burley's sequence up to the hash, and up to one difference of construction. There, one flip serves every node of a level for the length of a pair, and each node adds a fixed flip of its own; here every node draws its own flip for every pair. In the numbers below the difference shows as steadiness, and that part is the hash. The Laine-Karras hash is built for speed, and the pairs it deals are not independent of one another: over twelve seeds its top bit repeats with probability 0.13 to 0.35 and its slope at threshold ½ runs from +5.6 to +7.4 dB per octave, where independent pairs give 0.25 and +6.0 every time; with the constants of PBRT's FastOwenScrambler in its place, the numbers match ours. In a sliding window the difference is one of kind, and that part is the construction: from one block to the next, every node of a level changes its flip by the same amount, so each half of a block is either the same set of bins as the half beside it or the complement of it. Over eight seeds the halves of neighbouring blocks of 16 are the same set 45 to 75% of the time, against under 1% for ours, and a window of 64 sliding between blocks can hold no exact bin at all, where ours stays above about 30%. For rendering none of this matters. For a stream it is the whole specification.
Splitting values and splitting places are one property
The population tree of our articles and the boxes of section 04 look like different ideas. The tree splits values: the samples whose value starts with 0 are one population, those that start with 1 another, and each population splits itself again, evenly over time. The boxes split places: every block of the square holds its share of points. They are the same statement about one picture. Draw a stream as points, across for when a sample was drawn and up for its value. A horizontal band is a population: all the samples whose value lies in that band. A vertical band is a block of consecutive samples. "Each population is spread evenly over time" and "each block of samples holds each value once" both say that every box, a band of values crossed with a block of samples, holds exactly one point. The radical inverse drawn this way is the oldest such point set. The stream of our generator, drawn this way, is another.
Slide Boxes from one end to the other: at the left the boxes are vertical bands, blocks of time, at the right horizontal bands, populations of values, and between them a population inside a block; with the window on one of the stream's own blocks, every box of every shape holds one sample. Then step the window forward, or press Auto, and there are three kinds of behaviour. The radical inverse and its scramble never show red at all, in any window: they are periodic, the same order of visits repeated for ever, and the dots can be seen marching in ranks. The streams that redraw their flips on a common grid, Burley's and ours, pulse: clean when the window is on a block, red half a block later, clean again N steps on, whatever the shape of box. The five-state tree as the reference starts it, and the stateless form with an offset per node, stay at the same steady level wherever the window is. White noise stays mostly red. The chart under the picture draws this for the chosen shape over three block lengths.
A stream as a point set: time across, value upDetails
From here the steps of the space and time article are changes of axis. Replace "when" by "where", one 2×2 cell per digit instead of one bit, and the same point set read as a function is a dither mask: each place has one value. Keep both, where and when, beside the value, and it is a net in three coordinates. A renderer's samples have no value axis at all: every coordinate is a place, on the pixel, the lens, the light. That is the real difference between the two lines of work. Theirs distributes points. Ours reads one coordinate of the same kind of point set as the answer.
The same sequences, read in index orderDetails
| Sequence | Next bit equal | Blocks of 256 exact | Slope | Low frequencies |
|---|
What is shared
- A tree of decisions keyed by the bits above, made by a hash instead of stored.
- No state, any sample directly, any order, in parallel.
- Every aligned block of a power-of-two length exactly even.
- In the plane: a base-4 scramble of a pixel's Z-order index is the field of section 02 of the space and time article with its digits in the other order. Most significant from the coarsest scale gives an order of pixels in which neighbours are close; most significant from the finest scale gives a dither mask, a scrambled Bayer matrix.
What is not in this line of work, as far as we have found
- The requirement itself: a stream that is random in time and even in a window that slides, with no blocks. The sequences of sections 01 to 05 get one or the other. The scrambled radical inverse is even in every window because it is periodic, which is no stream at all; the shuffled ones are random in time and deal by blocks, exact on a block and only roughly even across two, which is what a renderer wants. Error diffusion never deals: it keeps a running balance, and its evenness is the same wherever the window starts. The lab above shows all three.
- Reading the sequence as a stream in time and asking for its spectrum at every threshold. It is blue, +6 dB per octave where the threshold is a power of one half and about +3 elsewhere, for their construction as for ours.
- Nodes with memory: the five- and seven-state error diffusion machines, which carry an error from one pair to the next and lower the low frequencies by 2 to 3 dB.
- A net over place, frame and value read as a dither mask for every frame, exact in every aligned block of pixels over every run of frames. Whether it coincides with an element of NILE is not established either way; the space and time article says what has been compared.
What they have that ours do not
- Many dimensions that are even together. Our generators produce one number at a time.
- Proofs: Owen's variance results, and the convergence rates Burley measures for scrambled against merely shifted sequences.
07Sources
- B. Burley, "Practical Hash-based Owen Scrambling," Journal of Computer Graphics Techniques 9(4), 2020, 1–20. Listings 1 to 3, Table 1 and the quotations in sections 02 to 04.
- S. Laine, T. Karras, "Stratified Sampling for Stochastic Transparency," Computer Graphics Forum 30(4), 2011. The permutation of section 03 and the shuffling of section 04, as described by Burley.
- A. B. Owen, "Randomly Permuted (t,m,s)-Nets and (t,s)-Sequences," Lecture Notes in Statistics 106, Springer, 1995, 299–317.
- J. G. van der Corput, "Verteilungsfunktionen (Erste Mitteilung)," Proceedings of the Koninklijke Akademie van Wetenschappen te Amsterdam 38, 1935, 813–821.
- A. G. M. Ahmed, P. Wonka, "Screen-Space Blue-Noise Diffusion of Monte Carlo Sampling Error via Hierarchical Ordering of Pixels," ACM Transactions on Graphics 39(6), article 244, 2020.
- N. Vegdahl, "Owen Scrambling Based Blue-Noise Dithered Sampling," 2022, and "A Fast Hash for Base-4 Owen Scrambling," 2022, psychopath.io. The pseudocode of section 05, under CC BY-SA.
- M. Pharr, W. Jakob, G. Humphreys, Physically Based Rendering, 4th edition, section 8.7: a full per-bit Owen scrambler and a fast one built on the same principle, in a production code base.