Blue Noise as a Lattice Gibbs Ensemble

Abstract

Blue-noise sampling is widely used in computer graphics, but existing methods separate statistical modeling from scalable generation. Optimization and transport methods produce high-quality point sets by coupling all samples together. Procedural and tile-based samplers are local, but define their output only implicitly. We formulate blue-noise generation as sampling from a Gibbs distribution over binary lattice occupancies with pairwise repulsive interactions. Density, repulsion strength, interaction scale, and kernel hardness are parameters of this distribution. Because the energy sums over pairs, distant interactions can be dropped with a bounded change to the distribution, leaving a Markov random field of bounded degree. To sample it, we trace the Markov chain backward from the state we want, following Coupling Towards The Past, and cut the trace at a fixed depth. This bounds the cost, and it bounds the region each sample depends on. A tile generated on its own, with a sufficient halo, is then bit-identical to the same region generated on any larger domain, in any order and with no communication between tiles. Memory is set by the tile size, not by the output size, and accuracy is traded against cost through parameters with a proven error bound rather than by switching algorithms. We validate the model, the sampler, and these guarantees separately. The ensemble reproduces standard blue-noise spectra and moves continuously between them as its parameters vary. The sampler matches its predicted work and memory. Tiled output is verified bit-identical to full-domain generation. We demonstrate adaptive stippling at 14K, where existing methods need memory proportional to the output, along with multi-class extensions.