Inkscape gradients dithering hack

Last sunday at 22:00 I finished a cool weekend hacking project! This post tells how I tweaked the Inkscape source code to enhance its gradients with a dithering technique, to make them look better and avoid the so-called “banding” effect. It all started when I created a logo for my school department, rendered it in high resolution and was disappointed with how the gradient looked. So I challenged myself to implement a basic dithering into Inkscape’s gradient during the weekend. It seems to be working fine, I’ll show here some demonstration pictures and also provide a patch.

Dithering is a technique to reduce the number of color levels of an image, or its bit depth. It is based on the fact that if you smooth out a pattern with two different color tones you get an intermediary tone. There are different ways to create this pattern, the one I used is based on the Bayer matrix.

When you have an image with large depth, such as in floating point, the normal way to convert it to e.g. 8-bit depth is to simply round the value. To make a dithering you sum a certain signal to the image before rounding. You can sum a random uniform white noise for example. Or you can create patterns such as lines and circles. The Bayer matrix creates a pattern that looks like cross-stitches, and should look familiar to you if you like low-tech stuff.

To create a gradient, a program such as Inkscape has first to make a floating-point calculation that yields a floating-point representation of the color levels in all channels. It then rounds the value to the 8-bit palette. And if the colors from the beginning and end of the gradient are too close to each other compared to the length of the gradient, there will be regions of pixels that will be rounded to the same value. To implement dithering in this gradient rendering to prevent that, all we needed was to add that pattern matrix before the rounding.

Well, that is the theory, but there is a problem in practice. The way Inkscape and other similar programs work prevents us from doing that. Before calculating the pixel colors they first define a large vector where the colors from the gradient are calculated beforehand. That makes it faster and also easier to deal with all the stop point coordinates and stuff like that. But because this vector is created with colors in the final bit depth, the rounding has already been done by the time we are rendering the pixels, and know their coordinates to sum the proper value from the dithering matrix.

This is where the “hacking” part enters. If I wanted to make the program right, I would have to change a lot of things. I would probably make it work with floating point in all parts of the processing, and only convert to 8-bit or whatever in the last steps. But what I wanted was just a quick and dirty way to make it work. Really just hack”the code to make the dithering.

The key to make it work was to be able to store in the vector that is used in the rendering the same colors, but with more depth. I could have tried to change the whole code to use floating point instead of unsigned chars, but that is a lot of work. What I did instead was extending the vector size from 1024 to 2048 quadruplets of unsigned chars. On the first half of the extended vector I stored just the exact same numbers that were originally being written. On the second half I stored the next 8 most significant bits, 8 extra “binary places”, just like you would with decimal places. This is a fixed-point approach, different from floating-point.

So after I changed the procedure that initializes the color vector, I just modified the rendering part to read the color into a floating point quadruplet, and then performed the dithering normally. The next figures show the results. The first images show what happens with the original code. The image created on Inkscape is just a rectangle with a tilted gradient with just a few levels, varying from red to blue using just the levels from 124 to 132.

The first image looks just purple, because it is really hard to notice the bands in this case. Sometimes you can see it on LCD monitors when you look to it with an angle. The second and third images had their contrasts increased by different amounts to better show what happens. The third shows very clearly one of the bands in the middle, with a few pixels wide. Now compare these to the following three pictures, which are the corresponding ones with the dithering.

The second image still looks like a nice gradient if you smooth or reduce the picture, unlike the one without dithering that shows a staircase. The third image here also shows how the otherwise straight and solid band become something more diffuse, with fuzzy edges.

The next picture shows a part of the logo I had made. The right half is the original version, and the left is the corresponding segment with dithering, mirrored. The middle region is blown up in the box. It is interesting to notice that although the dithering is working fine, and does blur the edges between the bands, there is still some quantization visible. I believe this is because of the restricted number of colors in the gradient vector. While the dithering reduces the quantization noise by rendering the colors more precisely, the number of colors is still restricted, and a very high resolution will still have regions with the same color, even though this color is now dithered. I am still checking if that is the case, or if my implementation has any bugs.

That is it for today. At the end of the article I pasted a patch for the Inkscape 0.48.0 release that implements my changes. But before I conclude this article I just wanted to tell a few statistics, because whenever I see an article like this I wonder about the author… So here is some personal details of me.

Age? 29.75
Been coding since: forever
Time working on the project specifically: only started to work on the code in saturday, after I wrote a comment on “this page”:https://blueprints.launchpad.net/inkscape/+spec/dithered-gradients. My code finally worked on sunday 22:00, but in the meantime I did sleep, eat and even went to the mall with my girlfriend.
And last but most important, probability of having done this if Inkscape was not open source: zero.

I think to apply the patch you have to “patch -p0 < filename.patch" at Inkscape's source root.

--- src/libnr/nr-gradient.cpp	2010-07-13 00:48:40.000000000 -0300
+++ src/libnr/nr-gradient.cpp	2010-11-28 22:31:15.000000000 -0200
@@ -34,11 +34,23 @@
 #define NRG_MASK (NR_GRADIENT_VECTOR_LENGTH - 1)
 #define NRG_2MASK ((long long) ((NR_GRADIENT_VECTOR_LENGTH << 1) - 1))
 
+
+double bayer[8][8]={
+    {-0.484615384615,    0.253846153846, -0.3 ,             0.438461538462 , -0.438461538462 ,   0.3 ,            -0.253846153846 ,   0.484615384615   },
+    { 0.00769230769231, -0.238461538462,  0.192307692308 , -0.0538461538462 , 0.0538461538462 , -0.192307692308 ,  0.238461538462 ,  -0.00769230769231 },
+    {-0.361538461538,    0.376923076923, -0.423076923077 ,  0.315384615385 , -0.315384615385 ,   0.423076923077 , -0.376923076923 ,   0.361538461538   },
+    { 0.130769230769,   -0.115384615385,  0.0692307692308, -0.176923076923 ,  0.176923076923 ,  -0.0692307692308 , 0.115384615385 ,  -0.130769230769   },
+    {-0.453846153846,    0.284615384615, -0.269230769231,   0.469230769231 , -0.469230769231 ,   0.269230769231 , -0.284615384615 ,   0.453846153846   },
+    { 0.0384615384615,  -0.207692307692,  0.223076923077,  -0.0230769230769 , 0.0230769230769 , -0.223076923077 ,  0.207692307692 ,  -0.0384615384615  },
+    {-0.330769230769,    0.407692307692, -0.392307692308,   0.346153846154 , -0.346153846154 ,   0.392307692308 , -0.407692307692 ,   0.330769230769   },
+    { 0.161538461538,   -0.0846153846154, 0.1 ,            -0.146153846154 ,  0.146153846154 ,  -0.1 ,             0.0846153846154 , -0.161538461538  }};
+
+
 namespace {
 inline unsigned char const *vector_index(int idx,
                                          unsigned char const *vector)
 {
-  return vector + 4 * idx;
+    return vector + 4 * idx;
 }
 
 template <NRGradientSpread spread> struct Spread;
@@ -278,8 +290,10 @@
 
     int x, y;
     unsigned char *d;
-    double pos;
+    double pos, dithering_increment;
     NRPixBlock spb;
+    NRPixBlock mypixel;
+    char mypixelvector[4];
     int x0, y0, width, height, rs;
 
     x0 = pb->area.x0;
@@ -288,17 +302,39 @@
     height = pb->area.y1 - pb->area.y0;
     rs = pb->rs;
 
+    // nr_pixblock_setup_extern(&spb, NR_PIXBLOCK_MODE_R8G8B8A8N,
+    //                          0, 0, NR_GRADIENT_VECTOR_LENGTH, 1,
+    //                          (unsigned char *) lgr->vector,
+    //                          4 * NR_GRADIENT_VECTOR_LENGTH, 0, 0);
     nr_pixblock_setup_extern(&spb, NR_PIXBLOCK_MODE_R8G8B8A8N,
-                             0, 0, NR_GRADIENT_VECTOR_LENGTH, 1,
+                             0, 0, 2*NR_GRADIENT_VECTOR_LENGTH, 1,
                              (unsigned char *) lgr->vector,
-                             4 * NR_GRADIENT_VECTOR_LENGTH, 0, 0);
+                             4 * 2*NR_GRADIENT_VECTOR_LENGTH, 0, 0);
+    nr_pixblock_setup_extern(&mypixel, NR_PIXBLOCK_MODE_R8G8B8A8N,
+                             0, 0, 1, 1,
+                             (unsigned char *) mypixelvector,
+                             4, 0, 0);
 
     for (y = 0; y < height; y++) {
         d = NR_PIXBLOCK_PX(pb) + y * rs;
         pos = (y + y0 - lgr->y0) * lgr->dy + (0 + x0 - lgr->x0) * lgr->dx;
         for (x = 0; x < width; x++) {
             unsigned char const *s=spread::color_at(pos, lgr->vector);
-            compose::compose(pb, d, &spb, s);
+            unsigned char const *sd=spread::color_at(pos, lgr->vector+4*NR_GRADIENT_VECTOR_LENGTH);
+            dithering_increment = bayer[y%8][x%8];
+            float levels[4];
+            levels[0] = (s[0] + (sd[0]-127.5)/255.)+dithering_increment;
+            levels[1] = (s[1] + (sd[1]-127.5)/255.)+dithering_increment;
+            levels[2] = (s[2] + (sd[2]-127.5)/255.)+dithering_increment;
+            levels[3] = (s[3] + (sd[3]-127.5)/255.)+dithering_increment;
+
+            mypixelvector[0] = floor(levels[0]+0.5);
+            mypixelvector[1] = floor(levels[1]+0.5);
+            mypixelvector[2] = floor(levels[2]+0.5);
+            mypixelvector[3] = floor(levels[3]+0.5);
+
+            // compose::compose(pb, d, &spb, s);
+            compose::compose(pb, d, &mypixel, (unsigned char const*)mypixelvector);
             d += compose::bpp;
             pos += lgr->dx;
         }
--- src/sp-gradient.cpp	2010-08-04 13:45:00.000000000 -0300
+++ src/sp-gradient.cpp	2010-11-28 22:31:03.000000000 -0200
@@ -1133,7 +1133,8 @@
 
     /// \todo Where is the memory freed?
     if (!color) {
-        color = g_new(guchar, 4 * NCOLORS);
+        // color = g_new(guchar, 4 * NCOLORS);
+        color = g_new(guchar, 2*4 * NCOLORS); // Double vector size, store decimal places at second half.
     }
 
     // This assumes that vector is a zero-order B-spline (box function) approximation of the "true" gradient.
@@ -1197,6 +1198,11 @@
                 color[4 * j + 1] = (unsigned char) floor(255*(g0 + f*(g1-g0)) + .5);
                 color[4 * j + 2] = (unsigned char) floor(255*(b0 + f*(b1-b0)) + .5);
                 color[4 * j + 3] = (unsigned char) floor(255*(a0 + f*(a1-a0)) + .5);
+                // Store 8 more precision bits for dithering
+                color[4*NCOLORS+4 * j + 0] = (unsigned char) floor( 128+255*((255*(r0 + f*(r1-r0)) )-color[4 * j + 0]) );
+                color[4*NCOLORS+4 * j + 1] = (unsigned char) floor( 128+255*((255*(g0 + f*(g1-g0)) )-color[4 * j + 1]) );
+                color[4*NCOLORS+4 * j + 2] = (unsigned char) floor( 128+255*((255*(b0 + f*(b1-b0)) )-color[4 * j + 2]) );
+                color[4*NCOLORS+4 * j + 3] = (unsigned char) floor( 128+255*((255*(a0 + f*(a1-a0)) )-color[4 * j + 3]) );
             }
 
             // Now handle the beginning
@@ -1226,6 +1232,11 @@
                 color[4 * ob + 1] = (unsigned char) floor(255*(remainder[1] + dt*(g0 + f*(g1-g0))) + .5);
                 color[4 * ob + 2] = (unsigned char) floor(255*(remainder[2] + dt*(b0 + f*(b1-b0))) + .5);
                 color[4 * ob + 3] = (unsigned char) floor(255*(remainder[3] + dt*(a0 + f*(a1-a0))) + .5);
+                // Store 8 more precision bits for dithering
+                color[4*NCOLORS+4 * ob + 0] = (unsigned char) floor( 128+255*(255*(remainder[0] + dt*(r0 + f*(r1-r0))) -color[4 * ob + 0]));
+                color[4*NCOLORS+4 * ob + 1] = (unsigned char) floor( 128+255*(255*(remainder[1] + dt*(g0 + f*(g1-g0))) -color[4 * ob + 1]));
+                color[4*NCOLORS+4 * ob + 2] = (unsigned char) floor( 128+255*(255*(remainder[2] + dt*(b0 + f*(b1-b0))) -color[4 * ob + 2]));
+                color[4*NCOLORS+4 * ob + 3] = (unsigned char) floor( 128+255*(255*(remainder[3] + dt*(a0 + f*(a1-a0))) -color[4 * ob + 3]));
             }
 
             // Now handle the end, which should end up in remainder
@@ -1247,6 +1258,11 @@
         color[4 * (NCOLORS-1) + 1] = (unsigned char) floor(255*(remainder[1]+remainder_for_end[1]) + .5);
         color[4 * (NCOLORS-1) + 2] = (unsigned char) floor(255*(remainder[2]+remainder_for_end[2]) + .5);
         color[4 * (NCOLORS-1) + 3] = (unsigned char) floor(255*(remainder[3]+remainder_for_end[3]) + .5);
+        // Store 8 more precision bits for dithering
+        color[4*NCOLORS+4 * (NCOLORS-1) + 0] = (unsigned char) floor(128+255*(255*(remainder[0]+remainder_for_end[0]) -color[4 * (NCOLORS-1) + 0]));
+        color[4*NCOLORS+4 * (NCOLORS-1) + 1] = (unsigned char) floor(128+255*(255*(remainder[1]+remainder_for_end[1]) -color[4 * (NCOLORS-1) + 1]));
+        color[4*NCOLORS+4 * (NCOLORS-1) + 2] = (unsigned char) floor(128+255*(255*(remainder[2]+remainder_for_end[2]) -color[4 * (NCOLORS-1) + 2]));
+        color[4*NCOLORS+4 * (NCOLORS-1) + 3] = (unsigned char) floor(128+255*(255*(remainder[3]+remainder_for_end[3]) -color[4 * (NCOLORS-1) + 3]));
         break;
     case SP_GRADIENT_SPREAD_REFLECT:
         // The second half is the same as the first half, so multiply by 2.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s