SimpleBlueNoise

A small, header-only blue noise texture generator in C99.

Usage

To use the library, simply #include the header file. You must #define the implementation in exactly one .c/.cpp file.

#define BLUE_NOISE_GENERATOR_IMPLEMENTATION
#include "blue_noise_generator.h"

The library includes two different algorithms to produce blue noise textures. Both functions expect a pointer to a contiguous array of unsigned int, the size of which should be equal to width × height.

int blue_noise_generator_create_void_and_cluster(unsigned int* buffer, int width, int height);
int blue_noise_generator_create_forced_random(unsigned int* buffer, int width, int height);

Each function returns 1 on success and 0 on failure. If successful, every value in the buffer will be given a unique rank starting from 0 counting up to width × height - 1. This should make it easy to normalise the values to fit your desired texture format.

The library uses its own psuedorandom number generator, and includes a function to set the current seed:

void blue_noise_generator_set_seed(unsigned int seed);

What is Blue Noise?

Blue noise is noise that contains mostly high-frequency components, meaning that the value difference between any two adjacent pixels is generally greater than that of white noise. This gives it a finer, more granular quality, as opposed to white noise which can appear more coarse.

White Noise	Blue Noise

Blue noise textures are useful whenever you need evenly distributed random samples. Some common use cases include image dithering and 3D rendering.

White Noise Dithering	Blue Noise Dithering

Implementation

Void-and-Cluster Algorithm

This library uses a variant of Robert Ulichney's Void-and-Cluster method for dither array generation¹. It makes use of a look-up table to simplify energy computations. The core of the algorithm involves evaluating the following Gaussian energy function:

$$\Huge{f(x) = e^{-{{r}^2}/{2\sigma^2}}}$$

Where $\large{r}$ is the wrap-around (toroidal) distance between pixels. The parameter $\large{\sigma}$ can be set via the following function:

void blue_noise_generator_set_void_and_cluster_sigma(double sigma);

When the binary pattern is first created, a number of pixels are randomly selected as minority pixels to set the initial state. The number of minority pixels can be controlled by a threshold parameter, which should range from 0.0 to 1.0:

void blue_noise_generator_set_void_and_cluster_threshold(double threshold);

Forced Random Algorithm

This algorithm is taken from the paper "Forced random dithering: improved threshold matrices for ordered dithering"². It is less thorough than the void-and-cluster method but is faster as a result. It uses the following energy function:

$$\Huge{f(x) = e^{-({r}/{d})^s}}$$

The parameters $\large{d}$ and $\large{s}$ control the deviation and steepness of the normal curve, respectively. They can be set via the following functions:

void blue_noise_generator_set_forced_random_deviation(double deviation);
void blue_noise_generator_set_forced_random_steepness(double steepness);

Every iteration, a random number of candidate pixels are selected and compared to determine the next sample point. The number of candidate pixels can be controlled by a threshold parameter, which should range from 0.0 to 1.0:

void blue_noise_generator_set_forced_random_threshold(double threshold);

Example Output

Below is a comparison between the output of each algorithm and their corresponding spectral densities. The energy parameters have been set so that the normal curve given by each energy function is approximately the same.

Void-and-Cluster, σ = 1.9, threshold = 0.1

Forced Random, s = 2.0, d = 2.7, threshold = 0.5

Performance

The table below shows the run time of each algorithm for various texture resolutions, taken as an average of 10 iterations. The parameters chosen are the same as above. We can see that Forced Random is about twice as fast as Void-and-Cluster given these parameters.

Platform: Intel(R) Core(TM) i7-8850H CPU @ 2.60GHz.

Resolution	Void-and-Cluster	Forced Random
16 x 16	1ms	<1ms
32 x 32	13ms	6ms
64 x 64	205ms	105ms
128 x 128	3.9s	1.7s
256 x 256	59.6s	31.7s
512 x 512	13m 53s	9m 0s

Additional Reading

Christoph Peters, "Free Blue Noise Textures."

Alan Wolfe, "What the Heck is Blue Noise?"

Alan Wolfe, "Using Blue Noise for Raytraced Soft Shadows."

Alan Wolfe, "Not All Blue Noise is Created Equal."

Footnotes

1. R. Ulichney, "The void-and-cluster method for dither array generation" (1993). ↩

2. W. Purgathofer, R.F. Tobler & M. Geiler, "Forced random dithering: improved threshold matrices for ordered dithering" (1994). ↩