Cheap Dithering?

[rain_storm]

Anyone know how dithering works, cos I havent a clue. Of course this is for the compo so its extreme dithering I need with only 4 colours to choose from. Any body here that can explain how to match a colour to a 4 colour pallet

[Shockwave]

It depends on how you're going about writing the program.

I am using software rendering so for the bits that will need dithering I'm going to have several pre-calculated buffers that I can copy dithered pixels straight out of.

[hellfire]

Wikipedia: Dithering in image processing.
Since you're aiming for a low-resolution, the dither-matrix shouldn't be too random.

[rain_storm]

Would it be easier if I sort of work backwards, If I start with my 4 colours then make many colours from them so I will have say 10 4x4 blocks for 10 different colours then use those blocks to make images. Rather than starting with the image and reducing the colours

[Jim]

That will work.  Maybe a 2x2, with each one having 1 of the 4 colours, that gives you a lot more combinations, but effectively it halves the screen resolution as your 'pixels' are now 2x2.

To work out which colour is the closest to another, you can use Pythagoras on the rgb values.  ie.
distance_between_colours = (r1-r2)^2  +  (g1-g2)^2 + (b1-b2)^2
(no need to do the square root)
pick the shortest distance.

A better visual result comes from converting both colours from RGB to HSV and doing Pythagoras on those values.

Jim

[rain_storm]

So I compute the distance between the colour I want to dither and all the colours in the pallete and choose the smallest distance.

Thanks Jim I will play around with this and see what I can do with it. I think I will stick with comparing rgb values for simplicity.

[hellfire]

I compute the distance between the colour I want to dither and all the colours in the pallete and choose the smallest distance.

That's quantization.
But you also want to quantize the surrounding pixels in such a manner that the pixels' average represent the desired colour as closely as possible.
Another tricky task is to select a colour-table which introduces the smallest average error (check neural networks).
And, as Jim pointed out already, you should perform all these operations in a colour-model which closely represents human perception.

[stormbringer]

some simple popular dithering methods:

http://en.wikipedia.org/wiki/Floyd-Steinberg_dithering
http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1/ordered_dithering.html

[Shockwave]

It's a really cool topic, however, if you are going to use dithering, you may find it's use limited

Don't forget that the resolution is pretty blocky for the competition and the colour blending side effect will be largely lost due to the big pixels.

Unless of course you intend to use a higher resolution (which is still legal for the comp as long as you only use 4 colours).

This task is a really tough challenge but it's good that anyone can have a go at it.