Floyd steinberg dithering in a shader

vvvv beta question
1

hello dear shader gods,

i’m fighting with hlsl for some time now, so - perhaps anyone can put me in the right direction.

what i want to achieve is a pixelshader that does dithering.

while there are many different dithering algorithms, a nice one is the so called floyd-steinberg algorithm but there is also this simpler ordered dithering algorithm.

so far, i thought i can base on the halftone-shader, but no success so far.

there’s this pseudocode that only has to be converted to hlsl:

for each y from top to bottom
   for each x from left to right
      oldpixel := pixel[x](x)[y](y)
      newpixel := find_closest_palette_color(oldpixel)
      pixel[x](x)[y](y) := newpixel
      quant_error := oldpixel - newpixel
      pixel[x+1](x+1)[y](y) := pixel[x+1](x+1)[y](y) + 7/16 * quant_error
      pixel[x-1](x-1)[y+1](y+1) := pixel[x-1](x-1)[y+1](y+1) + 3/16 * quant_error
      pixel[x](x)[y+1](y+1) := pixel[x](x)[y+1](y+1) + 5/16 * quant_error
      pixel[x+1](x+1)[y+1](y+1) := pixel[x+1](x+1)[y+1](y+1) + 1/16 * quant_error

so, i would be very thankfull for any advise, thanks

sebl

2

there is a good comparison between some algorithms

3 
newpixel := find_closest_palette_color(oldpixel)

do you really want to use a custom color palette? cos thats the only part i wouldn’t know how to translate easily…

4

sebl, its not that easy, the algorithm adds the error to the neighbour pixels wich will be visited in some of the next iterations. but pixelshaders have no order, they execute in parallel. so the error weighting has to be calculated for each of the 8 neighbours. so somehow you have to inverse the error weighting and you can’t use the optimization which most of the implementations use.

5

sry, my fault. didn’t read the wiki article…

judging from the pseudocode i assumed it is the usual neighbouring filtering thing.

6

so, here’s c# sourcecode for floyd-steinberg dithering:

public int[,](,) DitheringArray;

		private Bitmap Dithering(Bitmap Orginalbild)
		{
		    int Höhe = Orginalbild.Height;
		    int Breite = Orginalbild.Width;
		    DitheringArray = new int[Höhe, Breite](Höhe, Breite);
		    int Spalte = 0, Zeile = 0, temp = 0;
		    Bitmap neu = new Bitmap(Breite, Höhe);
		    int rot = 0, grün = 0, blau = 0, grau = 0;
		
		    for (Spalte = 0; Spalte < Breite; Spalte++)
		    {
		        for (Zeile = 0; Zeile < Höhe; Zeile++)
		        {
		            Color pixel = Orginalbild.GetPixel(Spalte, Zeile);
		            rot = pixel.R;
		            grün = pixel.G;
		            blau = pixel.B;
		            grau = GrauBerechnen(rot, grün, blau);
		            DitheringArray[Zeile, Spalte](Zeile, Spalte) = grau;
		        }
		    }
		    
		    for (Zeile = 1; Zeile < Höhe - 1; Zeile++)
		    {
		        for (Spalte = 1; Spalte < Breite - 1; Spalte++)
		        {
		            DitheringBerechnen(Zeile, Spalte);
		        }
		    }
		
		    for (Spalte = 0; Spalte < Breite; Spalte++)
		    {
		        for (Zeile = 0; Zeile < Höhe; Zeile++)
		        {
		            Color pixel = Orginalbild.GetPixel(Spalte, Zeile);
		            temp = DitheringArray[Zeile, Spalte](Zeile, Spalte);
		            if (temp == 0)
		                temp = 0;
		            else
		                temp = 255;
		            pixel = Color.FromArgb(temp, temp, temp);
		            neu.SetPixel(Spalte, Zeile, pixel);
		        }
		    }
		    return neu;
		}
		
		public int GrauBerechnen(int rot, int gruen, int blau)
		{
		    return (rot + gruen + blau) / 3;
		}
		
		public void DitheringBerechnen(int Zeile, int Spalte)
		{
		    int Teiler = 0;
		    if (DitheringArray[Zeile, Spalte](Zeile, Spalte) < 128)
		    {
		        Teiler = DitheringArray[Zeile, Spalte](Zeile, Spalte) / 16;
		        DitheringArray[Zeile, Spalte](Zeile, Spalte) = 0;
		    }
		    else
		    {
		        Teiler = (DitheringArray[Zeile, Spalte](Zeile, Spalte) - 255) / 16;
		        DitheringArray[Zeile, Spalte](Zeile, Spalte) = 1;
		    }
		    DitheringArray[Zeile + 1, Spalte - 1](Zeile + 1, Spalte - 1) += (Teiler * 3);
		    DitheringArray[Zeile + 1, Spalte](Zeile + 1, Spalte) += (Teiler * 5);
		    DitheringArray[Zeile + 1, Spalte + 1](Zeile + 1, Spalte + 1) += Teiler;
		    DitheringArray[Zeile, Spalte + 1](Zeile, Spalte + 1) += (Teiler * 7);
		}

but still no chance to get it working … see https://discourse.vvvv.org/t/6781

7

rgb to gray is usually calculated as follows:

luminance = r0.299 + g0.587 + b*0.114;

and i would do the division by 16 after the multiplication with the weigths, this will preserve the precision better… but i dont know if its worth 3 divisions more.

why do you set the DitheringArray to 0 or 1?

and really, you can do all that in one 2d for loop as its done in the pseudocode you posted, i would say that will speed up the calculation a lot…

8

yes, and there is this one (but i don’t how to use it…

so, mainly this code is from some website i don’t remember. and, of course there are a lot of improvements as you mentioned.

but i managed to build a very first crappy version…

next steps are:

  • do it all in one 2d loop as tf said (yes, it’s really slow atm)
  • build a texture out of it (like in the EX9.Texture template)
  • wait until the Plugins accept textures as input (will this ever come?)

floyd.rar (35.3 kB)

9

the ~ color operator is used like this:

code(lang=csharp):

var aColor = new RGBAColor(0.4, 0.6, 0.0, 1.0);

var gray = ~aColor;

10

ok, sinmplified version - but not so good results

floyd2.rar (216.3 kB)

11

packed the simplified thingy into ex9.texture

EX9TextureFloyd.zip (6.9 kB)

12

…for those who are interested - a freeframe version:

works in principle, but is still very slow. besides the asvideo --> freeframe --> videotexture bottleneck, that’s unoptimized code for sure.

perhaps, someone with better c++ skills wants to dig into the sources…

freeframe_floyd.rar (36.2 kB)