The best dither through a filter, still and moving

The question

Dither is a small offset added to a value just before it is rounded, so that the rounding errors average out instead of forming bands. We write it as a threshold pattern d(p) over the pixels p, and the rounded value as

q = floor(v + d(p))

When a filter h (a set of non-negative weights that sum to 1) is applied afterwards, what matters is the error after the filter, e = (filtered q) − v. We score a dither by the RMS of e over all pixels and over all flat levels (the fractional part of v uniform), in levels of the 8-bit image being filtered (in Starlock, the linear render target, before the tone curve). With plain rounding and no dither the score is √(1/12) = 0.2887.

How low can that score go for a given filter, whatever the dither? And how close does the simplest kind of dither get? By the simplest we mean a lattice:

d(x, y) = (((A·x + B·y) mod N) + 1/2) / N        gcd(A, B, N) = 1

That is one line of integer arithmetic in a shader, exact at any screen size (unlike a float fract, which drifts on large screens). The filter, Starlock’s painterly pass, blends each pixel with its neighbours, keeping a large share of the pixel itself; what matters is how close that blend comes to the true level. Try one: pick A, B and N, then slide the level and watch which pixels round up and what is left after Starlock’s filter.

The thresholds

Rounded at this level

After the filter

A B N

No ditherStripes (1,0)/8Plus (2,1)/5Best (54,11)/56Kolås (119,43)/256

Stripes leave bands the filter can't hide. Press Best and what's left becomes a fine, faint texture, about half the error. No dither shows what plain rounding does.

Level (between two steps)

0.30

The thresholds repeat with N values; a pixel rounds up when the level plus its threshold reaches 1, so the share of light pixels follows the level. After the filter, mid grey is exactly right, and what's left is stretched 640 times, the same for every pattern, so you can compare them but shouldn't take the contrast literally: a good lattice leaves what's left at the fine detail the filter hides best. Errors are in levels of the 8-bit image being filtered (in Starlock, the linear render target, before the tone curve).

Part one answers those questions for a dither that holds still. A screen also shows about 60 frames a second, and the eye blends neighbouring frames, so a dither that changes every frame is averaged twice: by the filter over space and by the eye over time. Part two adds a time axis,

d(x, y, t) = (((A·x + B·y + C·t) mod N) + 1/2) / N        t = the frame

and asks the same things, plus one more: does the gain come with shimmer a viewer would see? A pattern that wins on average but shimmers doesn’t win.

Where it comes from

The previous entry changed the dither on Starlock’s glows from a sine hash to interleaved gradient noise (IGN) and measured the banding (its opening footage shows the cutscene before and after, which is what the banding looks like in the game). Two threads were left hanging.

The first: Starlock’s painterly pass is a smoothing filter, and under it IGN (0.067 at a pixel ratio of 2) beat blue noise (0.091), which is supposed to be the better noise. Why? (The previous entry found them tied on its own measure, lightness after a viewing blur; here the score is the error in linear levels right after the pass.) That pass is a generalised Kuwahara filter, radius 5, 81 taps. On a flat dithered input it is linear to within 2e-9 levels (the fresh check measured it; see Independent checks): the mean of 8 Gaussian-weighted sector means, with the centre tap in all 8, so the centre is heavy (weight 0.194). Its taps sit one CSS pixel apart, so on a 2× screen it reads every second device pixel, and on 3× every third. IGN and R2 (Roberts, 2018) are float relatives of the lattice above, so the answer might lie in the lattice’s structure.

The second: Starlock’s cutscene is soft glows on near-black space, and the glows’ noise held still from frame to frame. The game has two painterly levels that matter for a moving dither. With paint on, the pass averages those 81 taps. With paint off, which slow devices fall back to, the pass is a single tap: nothing smooths the dither in space, so grain is what’s left. Part two’s change can’t be filmed like the previous entry’s: it alternates every 60th of a second, faster than a video on this page plays.

What’s known

Our literature checks reached arxiv.org, wikipedia.org and a few raw files. These hosts did not load, so anything from them we saw only as search snippets or not at all: blog.demofox.org, extremelearning.com.au, iryoku.com, momentsingraphics.de, ea.com, dl.acm.org, jcgt.org, doi.org, developer.nvidia.com, cseweb.ucsd.edu, springer.com, users.ece.utexas.edu, ncbi.nlm.nih.gov, the Cambridge CSF pages, the patent pages and github.com.

• Filter-adapted noise exists. FAST (Donnelly, Wolfe et al., 2024; arXiv 2310.15364, code at electronicarts/fastnoise) optimises textures for a post-filter in space and time by annealing, including a decaying average like a game’s temporal anti-aliasing. It uses the same expected filtered error we use, but numerically, with no lattice formula and no floor. Alan Wolfe has hand-designed lattices for a filter footprint on his blog (IGN for a 3×3 footprint, a “plus” lattice (x + 3y)/5).
• R2 (Roberts, 2018; the post) is justified by low discrepancy. IGN is Jimenez, 2014.
• Lattice rules in numerical integration have the same error structure, a sum over the dual lattice (Sloan and Joe; Korobov; Zaremba; for example arXiv 1608.08687 and arXiv 1805.09106). Our formula is that structure applied to a dither’s sawtooth seen through a filter. We found no one making the dithering application.
• Linear-congruential dithers are used in practice without this analysis, for example Øyvind Kolås’s “a dither”, ((x + 237y)·119) & 255, which is the lattice (119,43)/256. The fresh check found that it scores 0.0694 through Starlock’s pass.
• Halftoning work (direct binary search, Analoui and Allebach; Lau, Ulichney and Arce) uses a filtered error but, as far as we found, no bound through the filter’s smallest response. Ulichney’s blue noise and Bayer’s 1973 matrix are the classics.
• Moving dithers in games. IGN is animated by shifting the pixel position each frame, ign(x + 5.588238·(t mod 64), y + 5.588238·(t mod 64)) (Wolfe’s blog, seen only as snippets). Adding the golden ratio each frame, fract(noise + 0.618034·t), is the other common recipe (Wolfe, 2017; a write-up by Bart Wronski we saw only as a search result).
• Spatiotemporal blue noise (Wolfe, Morrical, Akenine-Möller and Ramamoorthi, arXiv 2112.09629, EGSR 2022) is blue noise in each frame and over time at each pixel. It names golden-ratio animation as a rank-1 lattice in time, and notes it strobes. Christoph Peters explains why plain 3D blue noise fails over time.
• Displays do this in hardware: a 6-bit panel with frame-rate control flips between two levels to fake a third. Wikipedia’s Frame rate control page notes a 30 Hz flicker visible in dark tones. Video halftoning (Gotsman 1993; Rehman and Evans 2010 and 2012) treats flicker as an artefact traded against others.
• How the eye sees flicker. Sensitivity peaks near 8 to 10 Hz (de Lange; Watson’s 1986 fit). It falls steeply at fine spatial detail and in the dark: Krajancich, Kellnhofer and Wetzstein (arXiv 2104.13514) measured how the fastest visible flicker falls with spatial frequency and luminance.

We did not find anywhere: the closed form for lattice dithers through a filter, in space or in space and time; the floors below (especially the floor for any dither, still or through a box over frames); the collapse of Bayer and blue noise when the filter strides; or R2’s mediocre rank. So the claim is: new, as far as we could find, in the sources we could reach. The moving dithers we compare are all published; what’s new there is which one is best for this game, measured.

Part one: a still dither

Everything is in code/.

An exact formula

A lattice dither is periodic, so its error can be summed exactly in frequency. With H the filter’s frequency response and (A,B)/N the lattice:

mean e² = 1/(12N²) + Σ  |H(m·(A,B)/N)|² / (2N² sin²(πm/N))        m = 1 … N−1

and as N grows without bound, for an irrational direction α:

mean e² → Σ  |H(kα)|² / (π²k²)                                     k = 1, 2, 3 …

So only the filter’s response at the lattice’s harmonics kα matters, and the first harmonic counts most. We proved it, and checked it against brute force (check.py, out/check.txt). When a lattice tiles its filter’s window exactly (a box n×n with (n,1)/n², or the 13-point Lee ball with (1,8)/13) the error is exactly 1/(12|S|²), where |S| is the number of points in the window.

Three floors

• Any threshold array (a fixed pattern): RMS ≥ √(Σh³/12). Each pixel’s output climbs in steps equal to the tap weights. For Starlock that is 0.0249.
• Any irrational lattice: RMS ≥ √(Σh³/6), 0.0352 for Starlock.
• Any dither or rounding rule at all: ordered, blue noise, error diffusion, per-level patterns, anything that produces integers. At level f the squared error is at least the minimum over f′ of (f′−f)² + m²·f′(1−f′), where m is the smallest |H| at any nonzero frequency. The reason is Parseval: an integer image with mean f′ has variance at least f′(1−f′), that variance is spread over the nonzero frequencies, and the filter keeps at least m of every one of them. For Starlock m = 0.1267, at (0.1954, 0.0454) cycles per tap, and the floor is RMS 0.0515.

We tried to break the third floor. Annealed binary patterns stayed 1.14 to 1.70 times above the per-level bound, and Floyd–Steinberg error diffusion scores 0.0707.

A stronger floor

The floor above uses one fact about the rounded image: its variance is f(1−f). But each pixel is 0 or 1 (it rounds to one of the two levels around the input), and that constrains how pixels can correlate. Two pixels can’t both be on with negative probability, and the 16 pixels of any 4×4 window must, on average, look like a mix of the 65,536 ways a 4×4 patch of 0s and 1s can look. Those constraints make a linear program, one per level, whose dual is a certificate: a set of weights on pixel pairs whose Fourier series stays under |H|². Any certificate proves a floor at every level at once.

floor/solve_lp.py finds them (it needs scipy’s LP solver). floor/check_floor.py checks them with numpy alone. It recomputes each window’s exact minimum over all its configurations. It checks the Fourier inequality on a 4096² grid with a proved margin for the points between nodes. It finds each level’s worst mean exactly (the floor is a maximum of quadratics, so the minimum sits at their crossings, their stationary points or the ends). And it bounds the integral over levels from below. The certificates are 22 small JSON entries (floor/certs.json).

The result: any dither whose output at each pixel is one of the two levels around the input scores at least 0.0553 through Starlock’s pass (out/floor-certified.txt), up from 0.0515. That covers every dither of the form floor(v + d), whatever d is and however it changes with the level, and error diffusion on a flat field (its output stays between the two levels). The older 0.0515 still holds for rules that output any integers.

Exhaustive search

starlock.py scores every lattice up to 256 levels, and every one of the 786,432 lattices with 1024 levels. The best is (54,11)/56 at RMS 0.0581, which is 1.05 times the stronger floor, 0.0553, and 1.128 times the simpler one, 0.0515 (its rotation (11,2)/56 ties). Its first harmonic lands where the filter is weakest: the lattice’s k=1 point is (0.196, 0.037) and the minimum of |H| is at (0.195, 0.045). That one harmonic carries 48% of the error.

Click the left map to pick a lattice. The dots on the right are its first six harmonics; the RMS is computed live in your browser from the filter’s 81 taps. Click a bright spot on the left map, then the dark pocket where Best sits, and watch the error and where the numbered dots land on the right.

Error of each pattern (click to pick)

What the filter lets through

Best (54,11)/56R2Random

The map and the numbers are for Starlock's painterly pass, per tap, with the pixel ratio at 1. Dark on the right means the filter lets that pattern frequency through weakly; a good dither puts its numbered harmonics there. The floor (0.0553) is the best any dither could do if it rounds each pixel to one of its two nearest levels.

Each row below is a new record, through Starlock’s pass: nothing better appears past about 26 levels.

lattice	levels	RMS	times the floor (0.0553)
(2,1)/4	4	0.0957	1.73
(1,0)/5	5	0.0801	1.45
(3,1)/16	16	0.0610	1.10
(5,1)/24	24	0.0588	1.06
(25,5)/26	26	0.0583	1.05
(54,11)/56	56	0.0581	1.05

Of all 786,432 lattices with 1024 levels, the best scores 0.0583, the median 0.0736 and the worst 0.4057. R2 rounded to /1024 scores 0.0726, better than only 58% of them. The full listing is out/starlock.txt.

Ramps came out the same way: for gradients up to 0.1 levels per pixel at any angle, the tuned lattice stays best (0.058 to 0.066, against IGN 0.069 to 0.084, R2 0.073 to 0.080, white noise 0.090).

Can a general texture beat a line of arithmetic?

We annealed general threshold tiles (anneal.c, runs in out/anneal-runs.txt). From random starts the best were 16×16 at 0.0594, 24×24 at 0.0592 and 32×32 at 0.0618, all worse than the 56-level lattice. Then a greedy local search starting from the lattice (ranked into a 56×56 tile, 0.05830) reached only 0.05826: no single swap of thresholds does better than a hair.

Square tiles are a restriction, so we went further (cosets.c, out/cosets.txt). Any periodic threshold array is an ordering of the cells of its period lattice, and its error has an exact closed form. So for every period lattice with 20 to 125 cells we annealed the ordering, starting from the best lattice dither when there is one. The best found is 0.05798, with 104 levels on a non-square period ⟨(26,0),(20,4)⟩. That’s 0.25% below the 56-level lattice. Longer runs at 78, 104 and 130 cells found nothing better.

Where the gap lives

Between the stronger floor (0.0553) and the best dither (0.0580) is about 5%. To see which side is loose, we searched for the best single 0/1 pattern at each of 20 levels, with no requirement that the levels nest, over every period lattice up to 90 cells (binpat.c, out/single-level.txt). A floor that treats levels one at a time, as ours does, can never rise above those patterns.

• At sparse levels (f up to 0.05) the floor is within 0.9% of a real pattern: there it is nearly exact.
• At middle levels the best patterns sit 4 to 10% (in squared error) above the floor.
• Integrated over all levels: floor 0.0553, best single-level patterns about 0.0570, best nested dither 0.0580, the 56-level lattice 0.0581.

So about 3% of the remaining gap is the floor still being too weak at middle levels, and at most about 1.7% is the price of nesting (a real dither’s levels must nest: a pixel on at one level stays on at every higher one). A larger window could lift the floor further: adding a 13-point diamond to the 4×4 window changed nothing at f = 1/2.

Other filters

sweep.py repeats the search for a family of filters: a share c of the weight kept on the pixel plus a Gaussian of width σ. The ratio of the best lattice to the simpler floor (the one for any rounding rule) (out/sweep.txt):

c	σ = 2	σ = 1
0.05	1.13	2.26
0.10	1.05	1.51
0.20	1.02	1.20
0.40	1.05	1.10

Starlock’s lite pass (radius 2) gets (2,1)/5, the 5-point plus lattice, at 1.12 times its floor. For a box n×n, the lattice (n,1)/n² attains the threshold-array floor exactly (0.0722, 0.0321 and 0.0180 for n = 2, 3, 4).

The honest scope: the claim of near-optimality holds for filters that keep a real share of each pixel (a heavy centre, as in Kuwahara and bilateral-type filters, or blends that keep the current pixel). It does not hold for plain blurs. With c = 0 the floor is about zero, so it says nothing there.

Strides

Why did IGN beat blue noise? Part of the answer is the stride. strides.py runs each dither through the pass by brute force at pixel ratio 1, 2 and 3 (no dither: 0.2887):

dither	ratio 1	ratio 2	ratio 3
white noise	0.0896	0.0896	0.0896
Bayer 16×16	0.0700	0.3552	0.0700
blue noise (64×64 void-and-cluster)	0.0702	0.0907	0.0905
blue noise, one tile per coset	0.0702	0.0702	0.0702
interleaved gradient noise	0.0687	0.0674	0.0665
R2	0.0726	0.0718	0.0703
best lattice, scaled per stride	0.0580	0.0583	0.0584

out/strides.txt. At 2× Bayer is worse than no dither at all. In the standard Bayer matrix the finest 2×2 cell carries the top digit of the threshold, so every pixel a stride-2 filter reads holds thresholds from one quarter of the range. The fresh check derived the limit exactly: RMS √(1/8) = 0.354. Blue noise at 2× and 3× is about the same as white noise, because skipping pixels folds its high frequencies down onto low ones. Giving each coset (each set of every second pixel) its own independent tile fixes it. For the lattice, the constants must follow the pixel ratio: scaled per stride it is (54,11)/(56·s), while a single fixed (54,11)/56 gives 0.0673 at 2× and 0.0693 at 3×. Fractional pixel ratios are not covered.

Here is what a filter that skips pixels sees. Each output reads one set of pixels, the same position in every 2 × 2 (or 3 × 3) block:

Thresholds this filter reads

Bayer 8×8Interleaved gradient noiseLattice (54,11)/56

Every pixel (1×)Every second (2×)Every third (3×)

Back in Starlock’s real pipeline

We put the 56-level lattice into the previous entry’s scenes, with the nonlinear pass and the 8-bit screen write, against the shipped IGN. Banding changes by under about 15% and the grain goes slightly up. Both are far below visible, so no still pattern replaces IGN. What did change the game is in part two.

Part two: in time

Everything is in code/time/.

The simplest way time helps

In one frame a pixel rounds to 0 or 1. Blended over two frames, with thresholds d and d + ½ (wrapping past 1), it rounds to 0, ½ or 1, because floor(x) + floor(x + ½) = floor(2x): the blend is the still pattern doubled, fract(2d), on steps half as tall. Applied to IGN, this half-step flip is what the game ends up shipping. Slide the level:

Frame 1 (thresholds d)

Frame 2 (d + ½)

Blended by the eye

Level

0.36

The formula, with time

A lattice dither is periodic in space and time, so its error sums exactly in frequency, as in the still case. Harmonic m of the lattice sits at spatial frequency m·(A, B)/N and temporal frequency m·C/N (in cycles per frame). With G the eye’s response over frames:

mean e² = 1/(12N²) + Σ |H(m·(A,B)/N)|² · |G(m·C/N)|² / (2N² sin²(πm/N))     m = 1 … N−1

We used two families of eye models: a sliding box over the last k frames (G(τ) = sin(πkτ)/(k·sin πτ)), and a decay, where each frame keeps a share a of the memory before it (G(τ) = (1−a)/(1−a·e^(−2πiτ)), a = e^(−16.7 ms/T), for time constants T of 20, 40 and 80 ms at 60 frames a second).

The formula agrees with brute force (dither, round, filter in space, blend over frames, compare) in all 54 cases we ran (check.py, out/check.txt). Those cases cover Starlock’s full and lite passes, paint off, one frame, boxes, decays and the shimmer band.

Shimmer fits the same sum. The part of the error that changes over time is every harmonic with m·C/N not a whole number. Its power at the temporal frequencies a viewer could see as flicker is the same sum with |G|² replaced by a weight on those frequencies. At 60 frames a second, τ = 1/2 is 30 Hz. At 30 frames a second the same pattern changes at 15 Hz, in the band the eye sees best. Pick a dither and a frame rate to see where its change lands:

• how much of the error changes at that speed (a faint bar at 0 Hz: the part that holds still)
• how sensitive the eye is to flicker at that speed (bright, large-field data: generous for fine, faint grain)
• below 20 Hz, where flicker is easiest to see

StillHalf step every other frameGolden ratio each frameIGN + 5.588238·frame

30 fps60 fps120 fps

Each bar is one rhythm in the pattern; taller means more of the error changes at that speed (the pattern's harmonics, before Starlock's filter, which reweights them but doesn't move them in time). Halving the frame rate halves every speed: the flip's 30 Hz becomes 15 Hz, near the top of the curve.

Floors for any dither

Here “floor” means the simpler one, 0.0515 through Starlock’s pass, which holds for any rounding rule and extends to time; the stronger 0.0553 we haven’t carried over.

A box over k frames. The k frames a pixel shows add up to a whole number from 0 to k. So the eye’s view is a whole-number image divided by k, and the still floor’s argument runs on a level grid k times finer. The floor is the still floor divided by k: 0.0258, 0.0172, 0.0129 and 0.0086 for k = 2, 3, 4 and 6, through Starlock’s pass. This holds for any dither or rounding rule whatever (floors.py).

A decay. The eye’s blend is now a linear filter in space and time, so the still argument runs on the space-time image. The weakest response is a pattern that flips every frame, which a decay passes at (1−a)/(1+a). The floor is 0.0204, 0.0106 and 0.0054 for 20, 40 and 80 ms. A stronger estimate, from the best a single pixel’s 0/1 sequence can do over time (computed by dynamic programming, so not a certified bound), is 0.0224, 0.0132 and 0.0072.

Every lattice up to 64 levels

search.py scores every (A, B, C) for every N up to 64, under each eye model (out/search.txt). Through Starlock’s pass, against the floors:

eye	floor	best lattice	RMS	times the floor
one frame	0.0515 (the stronger floor: 0.0553)	(54,11,0)/56	0.0581	1.13 (1.05)
box 2	0.0258	(25,5,26)/52	0.0291	1.13
box 3	0.0172	(20,4,21)/63	0.0198	1.15
box 4	0.0129	(1,13,16)/64	0.0153	1.18
box 6	0.0086	(59,20,10)/61	0.0108	1.26
decay 20 ms	0.0204	(55,11,34)/57	0.0299	1.47
decay 40 ms	0.0106	(10,2,21)/51	0.0186	1.75
decay 80 ms	0.0054	(12,2,39)/63	0.0114	2.13

The box winners have a simple shape. (25,5,26)/52 is the still lattice (25,5)/52, which uses the whole range of thresholds in every frame, plus half a step every other frame. Doubled, (25,5)/52 is part one’s (25,5)/26, so the two-frame blend is that still winner on half-height steps. Averaged over k frames, a lattice whose time period is k is exactly a still lattice dither, with N/k levels, on a level grid k times finer. So for two frames the best lattice is the best still lattice with its error halved, at the same 1.13 times its floor. (Adding half a step to the still winner itself, (25,5,13)/26, scores 0.0342: blended, it acts like the winner doubled, (25,5)/13, a worse pattern. Start from the lattice whose double is the winner.) For three and four frames the winners are of the same kind, but with at most 64 levels in all they can only use still lattices of 21 or 16 levels, so they sit a little higher (1.15 and 1.18 times). For six frames the winner, (59,20,10)/61, is not of this kind at all: its time period is 61. With more levels allowed, a longer search found the same shape winning for k = 2, 3 and 4 up to 112 levels.

For a decay the best patterns turn in time by an amount near √2 − 1. Simply adding the golden ratio each frame to the best still lattice scores 0.0182 and 0.0105 through 40 and 80 ms decays (golden.py). That beats every rational lattice up to 64 levels.

What games do now

compare.py simulates the common recipes through Starlock’s pass (out/compare.txt). The spatiotemporal blue noise is our own 64×64×32 texture, made with Ulichney’s void-and-cluster method and the space-or-time energy of Wolfe et al. (stbn.c); we could not download theirs. RMS at a pixel ratio of 1:

dither	box 2	box 4	decay 40 ms	decay 80 ms	change below 20 Hz at 60 fps
IGN, still (the game before this run)	0.0687	0.0687	0.0687	0.0687	none
IGN + half a step every other frame	0.0337	0.0337	0.0358	0.0342	none
IGN + 5.588238·t (Wolfe)	0.0362	0.0227	0.0213	0.0134	0.037
IGN + golden ratio · t	0.0372	0.0238	0.0209	0.0120	0.038
spatiotemporal blue noise	0.0398	0.0206	0.0211	0.0124	0.050
white noise, new each frame	0.0634	0.0448	0.0406	0.0289	0.072
best lattice for box 2, (25,5,26)/52 (by the formula)	0.0291	0.0291	0.0316	0.0298	none

For IGN, the simple form works: fract(ign + 0.5·(t mod 2)). Blended over two frames it acts like IGN doubled, fract(2·ign), on steps half as tall, and IGN doubled is about as good a pattern as IGN, so the error halves (0.0687 to 0.0337). It puts all of its change at exactly half the frame rate. The moving recipes do better for an eye with a long memory, but some of their change always lands at slow frequencies. Here are the same numbers next to the floor, eye by eye:

Blends 2 framesBlends 4 framesFading memory, 40 msFading memory, 80 ms

Error left after Starlock's painterly pass and the eye's blend, in levels of the 8-bit image the pass filters, at a pixel ratio of 1 (lower is better; no dither at all: 0.29). The dashed line is the floor: no dither of any kind can go below it for this eye. "Flickers below 20 Hz" (at 60 fps) marks a dither with some of its change slow enough to see. A real eye is closer to the fading memories than to a neat two-frame blend; there the moving recipes leave less error on average, and the half step wins only once that flicker is counted (the table after the next section).

With paint off, the picture is the same with bigger numbers. Per pixel, a box over k frames can do no better than 1/(√12·k) (exact). Through a 40 ms decay the best 0/1 sequence we found scores 0.104, by dynamic programming and by the fresh check’s exhaustive search of every periodic sequence up to period 26 (a numerical optimum over 32 levels, not a proof) (temporal1d.py, out/temporal1d.txt).

How visible is the shimmer?

Error in levels doesn’t say what a viewer sees, so we built a yardstick for it (vis.py). Each piece of the error is weighted by the eye’s sensitivity at its spatial frequency (cycles per degree, for a phone at 30 cm) and its temporal frequency (Hz), and the pieces are pooled into just-noticeable differences (JND). The still part counts as grain, and the changing part as shimmer, on the same scale. So a moving dither can be compared fairly with a still one.

The model is deliberately generous: a peak sensitivity of 250 (a contrast of 0.4% just visible) at every spatial frequency up to 8 cycles per degree, and Watson’s bright-field flicker curve. Starlock’s scenes are dark, where the eye follows fast flicker less well, so we also ran a dark variant, stretched by Krajancich et al.’s luminance scaling for a dim glow (about 25 trolands). Kelly’s 1979 formula is in the code for comparison only: it reads full-screen flicker as invisible, which it is not.

Starlock’s real glow path, frame by frame

pipe_t.py runs the previous entry’s port of the glow path: the glow shaders, the 8-bit linear target, the painterly pass, the tone curve, and the screen write with its own dither. It runs frame after frame with each dither changing as it would in the game, in the glows’ noise and the screen write’s alike, then blends the frames in light, as the eye does (out/pipe.txt).

On the previous entry’s measures (low-frequency error and grain, in L*), the half-step flip cuts the grain by 25 to 43% through a two-frame blend in every scene, with paint on and off. On the JND yardstick, pooling grain and shimmer (generous model, 60 fps):

scene	paint	still	half-step flip (grain, shimmer)	golden ratio (grain, shimmer)
glow	on	2.9	2.0 (2.0, 0.4)	2.2 (0.6, 2.1)
faint glow	on	5.6	4.1 (4.0, 0.7)	4.3 (1.3, 4.1)
stacked glows	on	2.1	1.6 (1.5, 0.3)	1.5 (0.3, 1.5)
rings	on	7.1	5.2 (5.1, 0.9)	5.5 (1.6, 5.2)
glow	off	10.6	8.4 (8.3, 1.2)	8.9 (5.5, 6.9)
faint glow	off	23.7	20.5 (20.4, 2.3)	21.1 (17.1, 12.3)
stacked glows	off	8.7	6.8 (6.8, 1.0)	6.0 (2.3, 5.6)
rings	off	24.4	20.5 (20.4, 2.5)	21.2 (16.7, 13.1)

The same numbers as a picture, with 30 fps beside 60:

Paint onPaint off

60 fps30 fps

• grain: the error that holds still
• shimmer: the error that changes from frame to frame

How visible the error is in all, on Starlock's real glow path, in just-noticeable differences (our deliberately generous model of the eye). Shorter is better. Each bar's length is the total; the striped end is the shimmer's share of it. At 30 fps the flip's shimmer moves to 15 Hz and grows, which is why the game holds it still there.

The flip lowers the total in every scene. At 30 frames a second its shimmer moves to 15 Hz and grows four to five times, and the total still comes out below the still dither’s in every scene (rings with paint on: 6.6 against 7.1). In the dark variant, its shimmer at 60 fps is 0.03 to 0.12 JND with paint on and 0.13 to 0.32 with paint off.

The golden-ratio recipe wins on grain, and on the stacked glows its total is lower than the flip’s. But its shimmer is five to six times the flip’s, and at 30 frames a second it is barely below the still dither (7.0 against 7.1 on the rings).

(These are from the fixed estimator: 32 frames, and the mean offset counted once. The first run’s 6-frame window overstated the flip’s shimmer; see the independent checks below.)

The best lattice in the real path

If the best lattice beats IGN through the formula (0.0291 against 0.0337 for a two-frame eye), should the game use it? We ran it through the same real path (lattice_path.py, out/lattice-path.txt), scaled to the pixel ratio, as the painterly pass needs. Total visible error in JND (grain and shimmer, generous model):

paint on	IGN + flip (shipped)	best lattice + flip	the squeeze
glow	2.0 (2.7 at 30 fps)	2.2 (4.4)	6.5 (22.5)
faint glow	4.1 (5.2)	4.2 (8.6)	16.0 (44.9)
stacked glows	1.6 (1.9)	1.5 (2.8)	8.7 (37.2)
rings	5.2 (6.6)	5.3 (10.5)	14.9 (50.0)

The best lattice ties IGN on banding and grain through a two-frame blend. We think the two roundings, the tone curve and the filter’s nonlinearity eat the margin the formula promised, but we didn’t test which. Its flicker is about twice the IGN flip’s, perhaps because its pattern sits at coarser detail, where the eye sees flicker better. With paint off it wins only on the stacked glows, and only at 60 fps. So IGN stays.

The squeeze is a dead end we published for a few hours. Thresholds d/2 on even frames and d/2 + ½ on odd ones give exactly the same two-frame blend as the best lattice, so a perfect two-frame eye can’t tell them apart, and we wrote it up as the recipe. But every frame on its own is biased: at a level below ½, frame 0 rounds every pixel down and frame 1 rounds up twice the share it should, so the whole glow flickers at 30 Hz. In the real path it is three to six times worse than the flip with paint on (barely worse with paint off), and far worse at 30 fps.

The change to the game

So the game now flips: every dithered shader in the cutscene and the reveal adds half a step every other frame. That covers the glows, the warm light sprite and the painterly pass’s own write to the screen. One shared uniform, FLIP in reveal3d.js, steps once per animation frame. It holds at 0 whenever the smoothed frame time is above 20 ms. Below 50 frames a second, the flip would land at 25 Hz or lower and could be seen, so there the dither stands still, exactly as before. On a 120 Hz screen the flip runs at 60 Hz.

We checked it in a real browser (flipcheck.mjs.txt, out/flipcheck.txt): the cutscene in headless Chromium, held at one moment, with the animation clock stepped at 60 and at 30 frames a second. At 60 the uniform alternates and frames two apart are identical. At 30 it holds. Almost every pixel moves by 0 to 2 levels from frame to frame. But along the thin, bright edge of the shock ring, a few hundred pixels (0.1% of the frame) moved by 5 to 11 levels. There the painterly pass’s sectors are nearly tied, and the half step decides which one wins. Our flat-glow model can’t see this. On the generous model it scores 1.8 JND in a band around that ring, against 0.8 for the whole frame. In the cutscene the ring expands every frame, so the edge moves anyway. But a held picture would show it, so the flip is also off in calm motion (reduced motion’s stills and the table screen’s Calm motion).

Starlock’s 206 unit tests pass, and so does cutscene-shots in Chromium.

Results

• The formula. The exact error of any lattice dither through a filter is the sum in part one, and with a time axis the sum in part two. Both agree with brute force (part two in 54 of 54 cases).
• The still floor. Through Starlock’s pass no dither that rounds each pixel to one of its two nearest levels scores below 0.0553, proved by certificates that check with numpy alone; no rounding rule at all scores below 0.0515.
• The best still pattern. The one-line lattice (54,11)/56 scores 0.0581, within 5% of the stronger floor; the best of thousands of general periodic arrays scores 0.0580. Of the remaining 5%, about 3% is the floor’s weakness at middle levels and at most 1.7% the cost of nesting. The near-optimality claim is scoped to filters that keep a real share of each pixel.
• Strides. Bayer and blue noise break when the filter reads every second pixel; a lattice must scale its constants with the pixel ratio.
• The box floor. Through a box over k frames, no dither of any kind beats the still floor divided by k: 0.0258 for two frames. For two frames the best lattice reaches 1.13 times that, the same ratio as in space alone; for six frames, 1.26 times.
• The decay floor. Through a decay with a share a kept each frame, no dither beats the still floor computed with |H| scaled by (1−a)/(1+a). The best lattices sit 1.5 to 2.1 times above it, so this floor is looser.
• The best moving patterns. For a two-frame eye, add half a step every other frame to a still pattern whose doubled version is the best still one. For IGN, adding half a step to IGN itself does as well, fract(ign + ½·(t mod 2)), and that is what ships; through Starlock’s real glow path the best lattice only ties it. For a long memory, add the golden ratio (or √2 − 1) each frame.
• Through the real glow path, by our generous model of the eye, the half-step flip leaves less visible error than the still dither in every scene, at 60 and at 30 fps. Its shimmer at 60 fps is at most 0.32 JND by the dark variant. In a real browser it also makes a few pixels on sharp bright edges flicker in a held frame, so the game holds it still in calm motion as well as below 50 fps.

Independent checks

Each part was given to a fresh model with the claims and our code but none of our reasoning, and asked to break it. Each wrote its own code with different methods.

Part one

Its code is in code/independent/: its own taps (mytaps.py), an exact-integral test of the formula (c1.py), the floor by numerical optimisation (floor.py, needs scipy) and a C search over every lattice up to N = 256 (search.c).

• It confirmed the formula, re-proving it with Parseval on Z_N, and checked 48 cases including a random asymmetric filter and stride 2. The worst relative gap was 1.4e-14 (out/independent-formula.txt).
• It confirmed the floors, including the any-dither one: 0.05153 by optimisation against our 0.0515 (out/independent-floor.txt). It also confirmed the n×n box-filter cases, the Bayer value (analytically), and the linearisation of the pass (2e-9 levels).
• It did not find the result published, so novelty is as stated above.
• It corrected two overstatements. We had said the best lattice is “within 2 to 26%” of the floor across the sweep; it is 2 to 126%. And the stride figures needed the lattice rescaled per pixel ratio.
• It fixed a wrong comment in our code: the eight sectors do not have equal variance, they are just all tiny.
• It found a lattice used in practice, Kolås’s, scoring 0.0694.

A second fresh model then checked the stronger floor, again with its own code (floor/check_floor.py was what it tried to break):

• The argument holds for any pattern, periodic or not: the certificate’s inequality bounds the error over any growing box, up to edge terms.
• The margin between grid points is valid: the curvature bound is the right one, and the nearest grid node is at most half a cell’s diagonal away.
• It recomputed every certificate with its own enumeration and a different grid, and got the floor at 0.05533 to 0.05535 depending on the grid.
• It tried to break the floor with every point lattice up to N = 120, the 56-level lattice’s level sets, Bayer, a checkerboard and white noise. All 91 patterns sat on or above it; the tightest, density 1/47, was 2e-6 above.
• It confirmed the scope: Floyd–Steinberg on a flat field never leaves the two levels (it proved this by induction and tested it on 2001 levels).
• It caught a rigour gap: the checker’s first version took the worst mean on a grid, which can only overestimate. The version shipped now finds it exactly and bounds the integral from below.

Part two

Its code is in code/time/independent/.

• The formula: confirmed by a different exact method. Every tap, in space or time, only shifts the residue (Ax + By + Ct) mod N, so the error can be integrated exactly over the N + 1 level intervals. Over 400 random lattices, three filters (one deliberately lopsided) and every eye model, the worst relative gap was 6e-14 (out/independent-formula.txt).
• The floors: confirmed. Its own proof check and direct minimisation give the box floors 0.02576, 0.01718, 0.01288 and 0.00859, and the decay floors 0.0204, 0.0106 and 0.0054 (out/independent-floors.txt). It re-derived the stronger decay estimate and agrees it is an estimate.
• The search: confirmed, every number, with its own code. One sentence refuted: we had written that the best box-k lattice is always the best still lattice divided by k. That holds for two frames. For three and four it holds only against still lattices small enough to fit in 64 levels, and for six frames the winner is a different kind of pattern. The text above is corrected.
• The comparison: confirmed by its own simulation, which blends over frames first and filters after, at two places on the screen.
• Paint off: confirmed. Its exhaustive search of every periodic 0/1 sequence up to period 26 matched our dynamic programme’s optimum for decays.
• The real path: conclusion confirmed, estimator flawed. Our shimmer measure looked at only 6 frames, so a 30 Hz flip leaked into the 20 Hz bins, where the eye is more sensitive. That overstated the flip’s shimmer, by about 1.7 times on the bright model and 3.5 times on the dark one. It also counted a constant offset 1.25 times. Scored exactly (the still and flipped dithers both repeat, so two frames suffice), the flip beats the still dither in all 8 cases at 60 and at 30 fps. Its dark-model shimmer at 60 fps is 0.03 to 0.28 JND (out/independent-pipe.txt). We then fixed the estimator (32 frames, the mean offset counted once) and re-ran; the tables above are from the fixed run.
• The literature: two more searches found no statement of the box floor or of the space-time formula.

Limits

• One filter (Starlock’s pass, linearised) is studied closely. Others are a sweep, plus the identity for paint off.
• Flat levels and ramps in part one, the previous entry’s test scenes in part two (a third of the frame size, 320 pixels, to keep 16 frames each affordable), not photographs.
• Part one’s error is in levels, not a model of the eye. Part two’s eye is two models of the blend over frames (boxes and decays) and one sensitivity envelope with a dark variant, from published bright-field experiments. No real phone, and no viewer, was tested.
• The pass is linear on flat dithered input, not at edges, and the real pipeline rounds again at the screen write (see Back in Starlock’s real pipeline). In a held frame the flip makes a few pixels on sharp, bright edges change by several levels. We measured one moment of the cutscene, not the whole of it, nor the reveal.
• A frame rate between 30 and 50 that wobbles may flip on and off. The guard is smoothed, but we did not model a stuttering device.
• Part two’s searches stop at 64 levels, and 112 in a longer check of the box winners. Fractional pixel ratios are not covered.
• Some sources were snippet-only, so the survey is incomplete.

Where things stand

Through Starlock’s painterly pass no dither that rounds each pixel to one of its two nearest levels can score below 0.0553 levels, proved by certificates that check with numpy alone and confirmed independently. The best one-line lattice, (54,11)/56, scores 0.0581, within 5%, and in the game’s real pipeline it is no better than the IGN it already had. Bayer and blue noise break when the filter reads every second pixel.

With time added, the formula and the floors carry over, and a box over k frames divides the floor by k. For a two-frame eye the best pattern adds half a step every other frame, which puts all its change at 30 Hz; for IGN that simple flip does as well, and in the real glow path the best lattice only ties it. By our models of the eye, the IGN flip leaves less visible error than the still dither in every scene, so it ships, held still below 50 frames a second and in calm motion. Fresh models with their own code confirmed both parts, corrected three overstatements, and found a flaw in our shimmer measure that had worked against the flip. A later review led us to publish a “squeeze” recipe for a few hours; the real path showed every frame of it is biased, and it is written up above as a dead end. Visibility rests on published models of the eye, not on real phones.

What’s next

• A real phone. Film or photometer the flip at 60 and 120 Hz, and ask people whether they see it in the darkest glows; and see the stride behaviour on actual high-resolution screens.
• Close the last 5%. A larger window for the still floor (5×5 is 33 million configurations: it needs symmetry or column generation rather than our direct LP; a 3×6 strip was still solving when we stopped). And a floor that knows levels must nest (a joint relaxation of two levels, or quantised thresholds), for the last 1.7%.
• Certified floors in time: one for decays, and the still certificates carried to boxes (the window sums take k + 1 values, so the linear program needs bigger windows).
• The eye’s temporal response as a band-pass filter, which would make whole-screen flicker cost more than our low-pass models say.
• Motion. When the camera moves, the eye tracks the scene, not the pixel grid. A dither seen while tracking mixes space and time differently.
• Perceptual weighting in the search. Part two scores dithers by the eye’s contrast sensitivity; searching with the filter times that sensitivity, instead of the filter alone, is still open.
• A filter picker in the explorer, so the map and numbers are not only Starlock’s.