Blog 3.0 I make games.
Dithering About Dither
TL;DR
Dither can be helpful to make a thing appear more accurate than it really is.
Defining Dither
Dither is an interesting, and dead simple, technique which can help improve the perception of a signal - simply add noise! This can be used in audio, video, electronics, mechanical engineering and even high frequency trading!
When you see it in action it’s really quite intuitive how it works. Here’s the same picture of me processed in three different ways:



On the left is the original, a full colour image. In the middle is a rather awful image generated by simply clamping every pixel to either black or white. Finally on the right is another image which is also purely monochrome, however some of the pixels have been moved around.
This works with colour images too. Here’s the same photo again with a limited colour palette, causing terrible banding, and exactly the same colour palette on the right but some of the pixels have been moved around. The image on the right is almost perfect at first glance despite using such an extremely limited colour palette.


What’s happening here is that the quantization error is being diffused.
Quantization error is the error which comes from representing an infinitely variable signal, as usually found in nature, to a signal with a limited resolution, as usually found in computers. For example there are an infinite number of colours in the real world but my camera only captures 16,777,216 million distinct colours, so even the full colour image above isn’t completely accurate!
Diffusing error simply means to spread it out. There are the same number of black pixels in both of the monochrome images above, however the dithered images appear better because the error is spread out.
Anywhere that you suffer from limited precision dither can help you out - image processing, audio rendering, sensor measurements, precision timing just to name a few. In all these cases dither spreads out errors, reducing the impact from one very big error to many small errors. The applications I’m particularly interested in are for realtime rendering for games. For example if colours are only stored with a low precision they will suffer from banding, dithering the colours will reduce the banding (as shown above). In fact even if you have an absolutely perfect representation of the colours you can still benefit from dither because you have to display to an imperfect monitor which will introduce banding - dithering the image before displaying it will reduce this.
The example images above were generated using an algorithm called Floyd-Steinberg Dithering. This is a fairly complex algorithm which is not suitable for realtime rendering. Instead I’m going to go into the details of noise based dithering, which can be used in realtime rendering.
Noise Dither
Before diving into how noise based dither works I’m going to show some dead simple example code. Fundamentally all pixel shaders come down to something like this:
float4 PixelShader(float2 screen_coordinate)
{
return CalculateColour(screen_coordinate);
}
There are several ways we could dither this, depending on what we’re trying to achieve. For example let’s say we want to output to be monochrome. The naive way to do this is simply to convert it to grayscale and threshold the value to black or white:
bool PixelShader(float2 screen_coordinate)
{
float4 col = CalculateColour(screen_coordinate);
float gray = dot(col.rgb, float3(0.3, 0.59, 0.11)); //Magic conversion to grayscale
return gray > 0.5;
}
This will look terrible, like the second example image above. Instead of that threshold against 0.5 we could do this:
return gray > random_in_range(0.4, 0.5);
Now there will be a softer edge to the black/white border.
An important aspect of dither is that if you’re dithering multiple things random values must be independent. Don’t re-use the same random value twice. For example if you want to add two textures together, you’d dither it like so:
float4 Add_PixelShader(float2 screen_coordinate)
{
float4 tex1 = SampleTexture(Texture1, screen_coordinate + random_float2());
float4 tex2 = SampleTexture(Texture2, screen_coordinate + random_float2());
return tex1 + tex2;
}
The texture coordinates sampled from each texture are dithered slightly, using a different random value for each texture.
The really important thing in the above examples is exactly what kinda of randomness is in use. The type of noise has a large impact upon the quality of the dither.
The Shape Of Noise
When you think of random numbers you probably think of something like a dice roll; something where every value is equally likely i.e. it has a uniform distribution. However not all randomness is like this, you can get random numbers distributed in almost any way you imagine!
A probability density function (PDF) is a way to express how random numbers of distributed. It’s simply a function which returns the probability for a random number being equal to the given value. For a dice it’s pretty simple:
PDF_Dice(value) => 1 / 6
Of course every value on a dice is equally likely, so it’s just a constant one over six. If you were to roll a lot of dice, count up how often each number occurred, then graph the result the shape would be the same as graphing the probability density function.
For dither you probably want your noise not to be uniform. Something like a normal distribution (a.k.a bell curve) is more useful as it will distribute most of the samples over a small area and will fall off smoothly. There’s no hard cutoff to the dither which would introduce more visual artifacts.
Rapidly generating something approximating a normal distribution is surprisingly simple. The Irwin-Hall distribution is approximately the same shape and is generated by simply adding together uniform random values!
Here’s what 100 values of rand()
, rand()+rand()
and rand()+rand()+rand()
look like when graphed on a histogram:



As you can see it’s approaching a bell curve shape even with just three values.
All you need now is to generate some noise and add it together. I’ve talked before about generating noise on the GPU. However the noise I generate in that blog post is (approximately) white noise, which probably isn’t what you want to use for dithering.
The Colour Of Noise
The distribution of the noise isn’t the only aspect to consider, the “colour” of the noise is also important. The shape (distribution) of the noise relates to the likelihood of getting certain numbers, conversely the colour relates to how those values are distributed in a sequence. Here are two random sequences of dice rolls:
1, 6, 2, 4, 1, 1, 3, 1
1, 1, 1, 1, 2, 6, 3, 4
Since these two sequences have exactly the same numbers they obviously have the same shape. However something else about these sequences is different, the order of the numbers within the sequence has changed, they have a different colour.
Sequences of random numbers can be displayed as a simple line graph. Here’s some totally random, uniform distribution, noise:

A simple 1D wave like this could also be though of as an audio signal. Click here to listen to three seconds of the same white noise signal. Now the most important bit, here’s the spectrum analysis which shows what frequencies are in that signal:

The shape of this frequency distribution is the colour - this totally flat distribution is known as White Noise.
So why would we care about the colour of noise? Low frequency signals do not change much from one instant to the next, this means that if a random has a low frequency it will not change much from one value to the next. If a noise has a mix of frequencies (such as white noise) sometimes the low frequency component will become the domination one (purely by chance) causing a run of similarly valued numbers. This is pure randomness but it doesn’t feel random to a person - no doubt you’ve played a board game and been incredulous at someone rolling “too many” sixes in a row. The same problem occurs when rendering with noise. Humans are very good at detecting visual patterns even where they don’t exist. Notice how this texture of uniform white noise looks “clumpy” in places:

That doesn’t look nice, people will spot those clumps in the final render. We need something seemingly more random than pure randomness! Now that we know about the colour it’s pretty easy to understand what that means - we want to reduce or eliminate the low frequency components.
Here are the frequency plots of some other colours of noise, courtesy of wikipedia. White, Pink, Brown (no, this doesn’t have any special biological effects when listened to), Blue, Violet and grey:






Blue noise seems like it does what we want. Here’s what that looks like:

Back To The Dither
Let’s get back to dithering. Here’s a reminder of the pixel shader we’re trying to dither:
float4 Add_PixelShader(float2 screen_coordinate)
{
float4 tex1 = SampleTexture(Texture1, screen_coordinate + random_float2());
float4 tex2 = SampleTexture(Texture2, screen_coordinate + random_float2());
return tex1 + tex2;
}
Adding two textures together, with dithering on the texture coordinates. We now know that we want to use noise with an approximately bell curve distribution, and we want the noise to be blue noise to reduce clumpiness in the final output image.
First we create a random vector:
float2 random_float2()
{
// Create a vector 2 from 2 random numbers
return float2(random_float(), random_float());
}
So now we need 2 random numbers, with a normal distribution (bell curve). We can use the Bates Distribution to get approximately the right shape:
float random_float()
{
return random_blue() + random_blue();
}
Finally we need a random blue noise value. Generating blue noise is actually quite difficult, it’s probably not something you can do on the GPU in a pixel shader! The best approach to this is to keep a texture of blue noise and to sample from that. Check out this fantastic blog post about generating blue noise, there’s also a huge pack of blue noise textures in a variety of formats and sizes!
This does make things a little more complex. We need some kind of texture coordinate so we know where to sample from the blue noise texture - this is essentially the seed to the random number generator. The best way to do this is to use a single blue noise texture with different noise in each channel, that way you get 4 different independent blue noise values from one single “seed”. Our final random function would therefore look like this:
float2 random_float2(float2 seed)
{
// Get 4 blue noise values. Make sure this is using point sampling!
float4 blue = sample(blue_noise_texture, seed);
// Create 2 random numbers, using the bates distribution to make them triangular
return float2(
(blue.r + blue.g) / 2,
(blue.b + blue.a) / 2
);
}
Practical note: This is not the best way to create a random vector (although it will suffice for dithering). This will generate a box of samples around the center point but you disk of samples. Maybe I’ll do an article on that in the future. For now just Google “Poisson disk sampling”
Conclusion
I’ve covered the basics of dither in this article. It’s a much more complex topic than I first thought! If you’re interested in the topic make sure to read these other things:
Generating blue noise and free blue noise textures: Moments in Graphics
Colours of noise: Wikipedia
Probability Density Function: Wikipedia
Poisson Disk Sampling: Herman Tulleken - Dev.Mag
Comments »A purely monochrome game: Return of the Obra Dinn
archive
- Dithering About Dither 27 Mar 2018
- 2017 Retrospective 13 Jan 2018
- Unity Ongui 04 Dec 2017
- Dissonance Voip Pipeline 19 Feb 2017
- 2016 Retrospective 01 Jan 2017
- Dual Contouring In 2d 27 Dec 2016
- Procedural Generation For Dummies: Building Footprints 07 May 2016
- Procedural Generation For Dummies: Half Edge Geometry 30 Mar 2016
- Fixed Permalinks 21 Mar 2016
- Procedural Generation For Dummies: Galaxy Generation 14 Jan 2016
- 2015 Retrospective 04 Jan 2016
- Procedural Generation For Dummies: Lot Subdivision 27 Dec 2015
- Procedural Generation For Dummies 11 Dec 2015
- Procedural Generation For Dummies: Road Generation 11 Dec 2015
- Deferred Transparency 09 Oct 2015
- Xna In 2015 24 Aug 2015
- Node Machine 26 Jun 2015
- Procedural Generation Of Facades And Other Miscellania 29 May 2015
- This Path Was Made For Walking 23 Apr 2015
- Cross Chunk Navmeshes 27 Mar 2015
- Changelog 27 06 Mar 2015
- Drawing Stuff On Other Stuff With Deferred Screenspace Decals 27 Feb 2015
- Random Gibberish 22 Feb 2015
- This Wall Is Sticky 17 Feb 2015
- Changelog 25 08 Feb 2015
- 2014 Retrospective 13 Jan 2015
- Super Sonic Sound 08 Jan 2015
- Sandboxing Is Dead Long Live Sandboxing 22 Dec 2014
- Changelog 22 B 14 Dec 2014
- Changelog 22 07 Dec 2014
- Possible Interruption To Service 06 Dec 2014
- The Game Programmer Awakens (changelog 21b) 30 Nov 2014
- The Return Of The Programmer (changelog 21) 16 Nov 2014
- The Return Of The Vending Machines 26 Oct 2014
- There Are Vending Machines Everywhere 16 Oct 2014
- Changelog 20 12 Oct 2014
- Ragdolls Are Hard 05 Oct 2014
- Changelog 19 28 Sep 2014
- The Return Of The Game Programmer 21 Sep 2014
- The Ball Is Picked Back Up 17 Aug 2014
- It's Good To Be Back 03 Aug 2014
- Serious Injury 21 Jul 2014
- We Marveled At Our Own Magnificence As We Gave Birth To Ai 14 Jul 2014
- Changelog 17 06 Jul 2014
- Changelog 16 29 Jun 2014
- Happy Birthday 22 Jun 2014
- Changelog 14 15 Jun 2014
- Losing My Way 08 Jun 2014
- Wildcard 02 Jun 2014
- Changelog 13 25 May 2014
- Changelog 12 16 May 2014
- WAI NO VIDEO (Again) 11 May 2014
- Changelog 10 04 May 2014
- Changelog 9 27 Apr 2014
- Changelog 8 20 Apr 2014
- Long Overdue Style Upgrade 18 Apr 2014
- WAI NO VIDEO 13 Apr 2014
- Changelog 7 07 Apr 2014
- Changelog 6 30 Mar 2014
- Changelog 5 23 Mar 2014
- Changelog 4 16 Mar 2014
- This Is Madness! 11 Mar 2014
- Changelog 3 09 Mar 2014
- Changelog 2 02 Mar 2014
- Changelog 1 23 Feb 2014
- Changelog 0 15 Feb 2014
- Payday The Heist 2 13 Jan 2014
- 730 Days Later 01 Jan 2014
- I Just Needed A Rest 12 Nov 2013
- Splinter Cell Blacklist 27 Aug 2013
- Gruelling Homework Assignment 26 Aug 2013
- Scripting Is Dead Long Live Scripting 14 Aug 2013
- The Reports Of My Death Are Greatly Exaggerated 05 Aug 2013
- 27 Gigawatts Of Cake 11 Jun 2013
- Trees Are Well Behaved 22 May 2013
- A Brief Project Update 14 May 2013
- Finite State Machines (are Boring) 16 Apr 2013
- Pathfinding 10 Apr 2013
- Artificial Stupidity Series 08 Apr 2013
- Valve Need To Stop Reading My Mind (and Other Miscellanea) 20 Mar 2013
- Elements Of Style 26 Feb 2013
- Moving To Axmingholmesbury 23 Feb 2013
- The Future Is Steamy 08 Feb 2013
- Mathematical Trickery 22 Jan 2013
- Thinking Aloud About Release 09 Jan 2013
- Game Developers Don't Make Timetables 03 Jan 2013
- What Is Heist? 20 Dec 2012
- How Does Procedural Generation Work? 14 Dec 2012
- Why Does Heist Keep Crashing? 07 Dec 2012
- What Isn't Procedural Generation? 23 Nov 2012
- What Is Procedural Generation? 18 Nov 2012
- Procedural Generation Series 15 Nov 2012
- Packet Encoding(3) 12 Nov 2012
- Packet Encoding(2) 08 Nov 2012
- Packet Encoding 07 Nov 2012
- Deployment Hax 28 Oct 2012
- Wibbly Wobbly Pipey Wipey 24 Oct 2012
- New Release(2) 24 Oct 2012
- New Release 20 Oct 2012
- Say What? 17 Oct 2012
- Get Up And Initiate That Session 15 Oct 2012
- Topological My Dear Watson 14 Oct 2012
- Omg Wtf Multiplayer 13 Oct 2012
- Full Steam Ahead 24 Sep 2012
- You Should Check Out Greenlight 01 Sep 2012
- It's Full Of Entities 20 Aug 2012
- Persistence 06 Aug 2012
- I'll Be Back 01 Aug 2012
- Artificial Stupidity 24 Jul 2012
- Overindulgence 16 Jul 2012
- Not My Cup Of Tea 09 Jul 2012
- Artsy Stuff 02 Jul 2012
- This Was A Triumph 25 Jun 2012
- Multiplayer Release 18 Jun 2012
- Fortnightly Fun 10 Jun 2012
- New Blog 31 May 2012