Fun with marching ants

on 2 Oct 2010 by Mukund (@muks)

When GIMP has to render selections, for performance reasons it draws the selection geometry once and then uses it as a mask on top of a Cairo source that is a tiled stipple pattern of diagonal stripes. Where the light shines through (the opaque places where the lines are :) ), you are shown that portion of the tiled stipple pattern below. The stipple pattern is changed often (rotated diagonally from the top-left to bottom-right) to give you the impression of marching ants. I guess this is how marching ants are implemented in most other applications too.

The current stipple pattern looks like 1/4 of the pattern labelled current in the image below. When it is tiled, you see the result. When the pattern is rotated diagonally, the diagonal stripes move towards the top-left corner.

Diagonal stripes stipple pattern

Another representation:

0 xxxx
1 xxx    x
2 xx    xx
3 x    xxx
4     xxxx
5    xxxx
6   xxxx
7  xxxx

The GIMP selection is made of manhattan (rectilinear) geometry, that surrounds the selected pixels. Even if you select a triangle of pixels, the selection is actually made around the individual pixels and all its segments are either vertical or horizontal. The diagonally striped stipple pattern works optimally in this case.

Manhattan selection geometry

However, if you are at a normal zoom level and a triangular selection has to be displayed, the selection doesn't appear as rectilinear segments, but can involve angled and curved segments. In this case, most of the selection is outlined, but there are some surprises. Because of the diagonal stripes pattern, any 45° parts of the selection are sometimes not rendered properly, and sometimes in full. This can lead to yucky results.

Ants with diagonal stripes pattern

The screenshot above is from GIMP master branch. This effect is seen in GIMP 2.6 as well, but because the stipple pattern is mirrored, the effect is seen in selection edges around 135°.

Ants with diagonal stripes pattern in GIMP 2.6

See the broken bits?

The approach of using a stipple pattern cannot be easily given up due to performance reasons. The selection geometry can be large, and while there can be other approaches such as reducing it when zoomed out and stroking it by walking, these are not as straightforward as the approach GIMP currently uses. As long as a stipple pattern is used, an optimal stipple pattern has to be found.

After a bit of play, a checkerboard pattern seems to give good results:

0 xxxx
1 xxxx
2 xxxx
3 xxxx
4     xxxx
5     xxxx
6     xxxx
7     xxxx

But the marching ants effect is not smooth. The ants jump a bit every now and then. But selections with the checkerboard pattern look very good. It looks just about the same with manhattan selections, and with curves and angles, you can see the results below. Because of the jumping ants behavior, is this better or worse? See bug #631106.

Ants with checkerboard pattern