Mukund

Following my last post on this subject where only the raw algorithm for finding the largest rectangle was completed, the UI and PDB changes for using this functionality are also done now (and several edge cases were fixed in the process). I’ll commit it once it gets some external testing from some of our esteemed customers ;). All affine transformations now present a combo box with clipping modes:

GIMP toolbox

Here is an example with rotation, using the excellent Wilber splash draft by Paul Davey and Jimmac (still no window decoration in the screenshots):

Wilber before

Wilber during

Wilber after

GIMP now has working code to find the largest rectangle in the quadrilateral (aligned with the XY axes) which results after a transform (rotate, perspective, etc.). As an example, when a user rotates an image, she can decide to automatically crop the image to an rectangle aligned with the canvas so that no transparent areas are introduced (an often used use-case which is used usually often ). A UI for using this feature will be available soon.

The shapes below are from a GTK+ test program which uses Cairo to draw, but when I took screenshots, the window decoration disappeared (maybe because of desktop effects). The black polygon is the transformed quadrilateral and the green rectangle is the computed result. The function also accepts an aspect ratio to provide a properly sized rectangle.

Following up on the last post, we now have smoother loglog smoothing, for the Fractal Explorer plug-in of GIMP. Mmmm. Will be committed after some cleanups of the plug-in code though.

Classic smoothing (or lack of it)

loglog smoothing

I often tell my friends that cooking, unless one’s doing it for recreation, is crazy as one spends way too much time cooking and cleaning up than eating the result. Fixing bugs is something like this, but worse. It’s probably someone else’s code who wrote it back in 1999 and somehow the bug has been there all along undiscovered; you know where the bug is; you probably even know how to quick-fix it; but to really fix the bug knowing what you’re doing means having to understand the code. Take a graphics application and you spend more time following the code. You spend a few hours doing that, and then the patch to fix it is 6 lines long, and it’s something very very simple. You put an if somewhere to handle a condition.

Last week, the Fractal Explorer plug-in of GIMP had a bug like this. The code for handling the loglog checkbox was added back in 1999. It has never worked on the complete classic Mandelbrot set (or if it ever did work, that must have been due to a bug in some other product). Looks like nobody used it like that. Kevin Cozens was porting the plug-in to GEGL when he discovered that it crashed with the loglog setting (#372671).

GIMP Fractal Explorer plug-in

For a Mandelbrot set, the classic method of rendering the set is to map the escape loop counter (once the modulus has escaped) directly to a colormap. This counter is an integer and the method causes banding due to non-smooth shading. The loglog implementation uses a method by Linas Vepstas to renormalize the escape loop counter by finding out how far away the integer counter has strayed outside the escape radius. It involves calculating a double log to map z^(2^i) to i, i.e., log (log (|z|^(2^i))) / log (2). The final divide by log (2) is so that the outer logarithm is done to the base 2 to reduce the 2^i to i. For reference, the end-result normalized loop counter is calculated as: mu = N - log (log (|Z(N)|)) / log (2) where N is the integer escape counter.

The problem with this method was that in the “inner lake” of the Mandelbrot set, where for example c can be 0 + 0i, the loop always exits after a full run with the loop counter at the maximum value, and |z| < 2.0. When |z| < e, the double log starts returning negative values. When |z| < 1, the double log returns inf. This is then subtracted from N and the resulting value mu is used to lookup RGB values for the point from the colormap array. This caused the plug-in to crash (when inf is used or mu exceeds the length of the colormap array).

So what we did to fix this was check to see if |z| < e at the end of the escape loop and clamp mu to N - 1 in that case. The result:

Classic smoothing (or lack of it)

loglog smoothing

Open them in two tabs to see how they differ. Of course, as we still use entries directly from a colormap (after rounding), it isn’t as smooth as we’d really like, but interpolation using the real values should be an exercise for another day. Now fixing the actual bug was a 2-line if condition. Imagine hours spent studying the algorithm used, and a 2-line fix (and perhaps this lousy blog post). The plug-in still needs to be fixed as it’s got the code for the fractal algorithms repeated for the actual filter and for the dialog’s preview, which needs to be moved to a common function, and we’d like to implement the really smooth shading as well.

Do you find all this cooking interesting? Do you want to be a GIMP developer? Come and participate by picking an open bug and hacking it into submission. Join #gimp on irc.gimp.org to talk to developers, or the gimp-developer mailing list. Or you may want to try #gegl if you think you’ve got the skills.

Graphics Planet is a new “planet” website using the Planet Feed Reader and based on Planet GNOME’s silverorange theme which was generously sent to me by Steven Garrity for use with Graphics Planet.

Graphics Planet is about the world of people involved in free software development in the field of computer graphics and publishing. We are users and developers on programs such as GIMP, Blender, Inkscape, Scribus, Krita, and other related projects such as the Tango Desktop Project.

A couple of days ago, an Ubuntu user stopped by with a problem. He wanted to create an Ubuntu splash screen which was an indexed image with certain special colormap (palette) positions. These colormap positions contained specific colours which were used by applications for displaying text. His problem was that these indices in the colormap were already taken by the image he had. In order to clear up those positions, the image data needed to be modified so that these positions were unused by the image.

Such a facility did not exist in GIMP yet, so it was difficult to do. I wrote a quick C plug-in prototype for him which shifted the colormap by one slot so that he could run it multiple times and get on with business. But the prototype evolved into a full-fledged plug-in today. It’s called “Rearrange Colormap” and also comes with two PDB procedures plug-in-colormap-remap() (which accepts an array map) and plug-in-colormap-swap() (the simpler form which just swaps two entries in the colormap).

The core algorithm takes a map array which is of the same length as the colormap and depicts how the new colormap would look. Each slot contains the original index of a color which should be at that slot in the target image. Then the new colormap is simply:

/* Data types are provided for reference */
gint    i, j, num_entries;
guchar  *map;
guchar  *original_cmap, *new_cmap;

for (i = 0; i < num_entries; i++)
  {
    j = map[i] * 3;

    *new_cmap++ = original_cmap[j];
    *new_cmap++ = original_cmap[j + 1];
    *new_cmap++ = original_cmap[j + 2];
  }

Changing the image data is a bit tricky, because map[] cannot be used directly as a fast lookup table. So we first create another map called pixel_map[] which can be used as a lookup table:

/* Data types are provided for reference */
gint    i, ncols;
guchar  *map, *pixel_map;

for (i = 0; i < ncols; i++)
  pixel_map[map[i]] = i;

pixel_map[] is then used as follows for translating the large amount of pixel data (the real code is more complicated than this as it needs to handle alpha-transparency data, etc.):

/* Data types are provided for reference */
const guchar *src_row = src_rgn.data;
guchar       *dest_row = dest_rgn.data;
gint         i, j;

for (i = 0; i < src_rgn.h; i++)
  {
    const guchar *src  = src_row;
    guchar       *dest = dest_row;

    for (j = 0; j < src_rgn.w; j++)
      *dest++ = pixel_map[*src++];

    src_row += src_rgn.rowstride;
    dest_row += dest_rgn.rowstride;
  }

All this is of course a simple abstraction. The plug-in has to do a lot more like input validation, user interaction, etc. It is available in the CVS version of GIMP now for anyone who wants to try it. You can find it in the image menu at Colors→Map→Rearrange Colormap. As usual, pizzas are queued for mitch and neo. They refactored the plug-in code and made it better.

GIMP rearrange colormap plug-in