Uniform 1D Red Noise & Blue Noise

The code that generated the data for this post is at https://github.com/Atrix256/TriangleToUniform

A previous blog post talked about how DSP filtering can make noise of various colors: https://blog.demofox.org/2019/07/30/dice-distributions-noise-colors/

That noise was not uniformly distributed though. It was binomial, so ranged from triangular to Gaussian.

Another blog post talked about how to convert uniform random numbers into other distributions, by inverting the CDF: https://blog.demofox.org/2017/08/05/generating-random-numbers-from-a-specific-distribution-by-inverting-the-cdf/

Inverting the CDF lets you convert from uniform to non uniform distributions, but you can also use the CDF to convert from the non uniform distribution to a uniform distribution.

This means that just like you can square root a uniform random number between 0 and 1 to get a “linear” distributed random number where larger numbers are more likely, you could also take linear distributed random numbers and square them to get uniform random numbers.

```float UniformToLinear(float x)
{
// PDF In:  y = 1
// PDF Out: y = 2x
// ICDF:    y = sqrt(x)
return std::sqrt(x);
}

float LinearToUniform(float x)
{
// PDF In:  y = 2x
// PDF Out: y = 1
// ICDF:    y = x*x
return x*x;
}
```

This can be useful when you use a two tap FIR filter which gives a triangle distribution out. You can adapt the LinearToUniform function to convert the first half of a triangle distribution back to uniform, the values between 0 and 0.5. For the second half of the triangle distribution, you can subtract it from 1.0, to get values between 0 and 0.5 again, convert from linear to uniform, and then subtract it from 1.0 again to flip it back around.

```float TriangleToUniform(float x)
{
if (x < 0.5f)
{
x = LinearToUniform(x * 2.0f) / 2.0f;
}
else
{
x = 1.0f - x;
x = LinearToUniform(x * 2.0f) / 2.0f;
x = 1.0f - x;
}
return x;
}
```

Let’s see how this works out in practice. In the first column below, it shows uniform being converted to linear and triangle, and back, to show that the round trip works.

In the second column, it shows red noise (low frequency random numbers) being made by adding two random numbers together, and then being made into uniform noise by converting from triangle to unfirom. It then also shows higher order red noise histograms.

The third column shows the same, but with blue noise (high frequency random numbers.

Here are the DFTs of the above, showing that the frequency content stays pretty similar through these various transformations.

So while we have the ability to convert 2 tap filtered noise from triangular distributed noise to uniform distributed noise, what about higher tap counts that give higher order binomial distributions?

It turns out the binomial quantile function (inverse CDF) doesn’t have a closed form that you can evaluate symbolically, which is unfortunate. Maybe two taps is good enough.

Here are some bread crumbs if you are interested in digging deeper
https://sigmoid.social/@demofox@mastodon.gamedev.place/109900303572389575
https://math.stackexchange.com/questions/2763270/quantile-function-for-binomial-distribution

Here are 20 values of each noise type to let you see what kind of values they actually have. The numbers are mapped to be between 0 and 1 even though these noise types naturally have other ranges. Order 2 red noise goes between 0 and 2 for example, and order 2 blue noise goes between -1 and 1.

Uniform
0.900403 0.246402 0.236748 0.057191 0.058894 0.434673 0.701137 0.261305 0.572679 0.643746 0.469458 0.77797 0.226739 0.181948 0.821556 0.661276 0.051249 0.769218 0.188764 0.43576

UniformToLinear
0.948896 0.496389 0.486568 0.239147 0.242681 0.659297 0.83734 0.51118 0.756755 0.802338 0.68517 0.882026 0.476172 0.426553 0.906397 0.813188 0.226382 0.877051 0.43447 0.660121

UniformToLinearToUniform
0.900403 0.246402 0.236748 0.057191 0.058894 0.434673 0.701137 0.261305 0.572679 0.643746 0.469458 0.77797 0.226739 0.181948 0.821556 0.661276 0.051249 0.769218 0.188764 0.43576

UniformToTriangle
0.776845 0.351 0.344056 0.169102 0.171601 0.466193 0.613437 0.361459 0.537766 0.577949 0.484488 0.666811 0.336704 0.301619 0.7013 0.588464 0.160076 0.660307 0.307216 0.466776

UniformToTriangleToUniform
0.900403 0.246402 0.236748 0.057191 0.058894 0.434673 0.701138 0.261305 0.572679 0.643746 0.469458 0.77797 0.226739 0.181948 0.821556 0.661276 0.051249 0.769218 0.188764 0.43576

order2RedNoise
0.321869 0.570975 0.546493 0.198164 0.559791 0.878273 0.800657 0.358752 0.356042 0.415941 0.459842 0.494419 0.215436 0.123045 0.267453 0.327641 0.485267 0.75219 0.67746 0.667561

order2RedNoiseToUniform
0.207199 0.631876 0.588662 0.078538 0.612432 0.970365 0.920525 0.257406 0.253531 0.346013 0.422909 0.4889 0.092826 0.03028 0.143062 0.214697 0.470969 0.877181 0.791936 0.778968

Order3RedNoise
0.335386 0.277424 0.53206 0.40188 0.502503 0.387789 0.390553 0.567394 0.547909 0.590254 0.429892 0.490403 0.391568 0.542284 0.545479 0.629202 0.582389 0.482149 0.442254 0.233653

Order4RedNoise
0.356291 0.356358 0.504111 0.503146 0.349194 0.316624 0.350564 0.329089 0.507805 0.555398 0.500458 0.643967 0.638761 0.659525 0.530838 0.450842 0.398863 0.407845 0.442873 0.324967

Order5RedNoise
0.595826 0.677254 0.591135 0.580018 0.482702 0.53669 0.367685 0.451726 0.454507 0.51374 0.631042 0.72763 0.538094 0.565055 0.51138 0.531387 0.568837 0.624056 0.469604 0.58843

order2BlueNoise
0.776161 0.416218 0.574676 0.125724 0.781581 0.530997 0.429622 0.484102 0.242817 0.766749 0.672426 0.275927 0.669314 0.290202 0.735534 0.523847 0.087859 0.822141 0.512319 0.419758

order2BlueNoiseToUniform
0.899792 0.346476 0.638198 0.031613 0.904586 0.560072 0.36915 0.46871 0.117921 0.891188 0.78539 0.152271 0.781293 0.168434 0.860115 0.546556 0.015438 0.936732 0.524335 0.352393

Order3BlueNoise
0.551499 0.366028 0.93273 0.481828 0.380887 0.495225 0.300059 0.51881 0.306799 0.356479 0.514701 0.498685 0.430205 0.573065 0.154976 0.667236 0.80882 0.616841 0.502323 0.426226

Order4BlueNoise
0.468794 0.473531 0.548515 0.461906 0.382252 0.692732 0.295499 0.523719 0.666799 0.415463 0.660763 0.362965 0.564584 0.371505 0.572822 0.494167 0.457531 0.420116 0.483063 0.526781

Order5BlueNoise
0.580763 0.461876 0.648067 0.466234 0.563966 0.455099 0.590905 0.252803 0.557458 0.306351 0.497475 0.618316 0.384632 0.56649 0.758528 0.412953 0.567208 0.330753 0.611306 0.330666