Tracing pixels

London, 2014-08-26

There are many reasons to use SVG: for sprites, fonts, vector graphics, etc. Currently developers are not giving it enough credit (we’re catching up). The use case we’ll be focusing here is somewhat different. After checking some research and own experimentation it turns out it might be also the best way to serve pixel art. Why? Because all other options require either <canvas>+JavaScript hacks or don’t work in all browsers (CSS solutions, which are still not supported by Chrome and IE).

tl; dr: This post describes a simple algorithm that SharpVG uses to trace pixelated shapes. Accidentally, at the same time we’re explaining a bit of the SVG’s path syntax and how to cut holes in shapes with the nonzero fill rule.

h1 h1 v1 h1 h-1 v1 h-1 v-1 v-1 v1

Intuition

Lets start with a simple shape and trace it intuitively. A pixelated letter “n” will do, shown on the figure 1. If we start from top left corner 0,0 and begin moving clockwise, the trace will look like on the figure 2.

fig. 1: Our hero: pixels of the letter “n”
(spaces between them are just for illustration purposes)
fig. 2: Steps of going around the letter “n”

Lets now list the steps and encode them with the moves they represent as in SVG paths (fig. 3). Horizontal moves are represented with letter h, vertical with v. Each time we move one pixel so it will have value either 1 or -1. Given that 0,0 is in the top left corner, h1 means right, h-1 is left, v1 means down and v-1 is up. (Think LOGO but without rotation.)

fig. 3: “n” steps with SVG directions

We can notice that is first h1 and then h-1. The direction in which we’ll go depends on where we’re coming from. It basically says “turn left”. If we come from above, we go right (h1). If we come from below, we go left (h-1). The same logic goes for where we’re also turning left, but we go v1 or v-1. These are the only two instances where we need to base next move on the previous one because we can get ourselves in to these situations from two directions. Other situations are free from this ambiguity.

We mark the starting point with absolute “move to” command, in this case to point 0,0 so in SVG it’ll be M 0 0. Because the last move is ending at the starting point, we might as well replace it with z to close the path.

The full path looks like on figure 4.

M 0 0 h1 h1 v1 h1 v1 v1 h-1 v-1 v-1 h-1 v1 v1 h-1 v-1 v-1 z
fig. 4: The full uncompressed path for the letter “n”

Path syntax is a little mini-language that’s meant to live inside the d (data) attribute of <path> elements. Full source of the image looks like on figure 5 and the image itself is the figure 6.

<svg width="3" height="3"
     xmlns="http://www.w3.org/2000/svg">
  <path d="M0 0h2v1h1v2h-1v-2h-1v2h-1z" fill="#777777"/>
</svg>
fig. 5: Full SVG source
fig. 6: The resulting SVG image (scaled up ×54)

You might notice that the path in the SVG image is a bit different. SharpVG is compressing the output by combining neighbouring moves if they’re the same, for example h1 h1 will become h2 in the output.

Extrapolation

Our “n” example doesn’t exhaust all possible moves but by rotating four base situations we can easily get all possible cases as in the figure 7. (We can notice that most of the moves in the “n” trace are in fact just other moves rotated.)

fig. 7: All possible moves

Algorithm’s outline

In the “n” example we just started in the point 0,0 but that’s usually not the case that our shape starts there. There also might more than one shape to trace in the image. To detect all of them, SharpVG is scanning the whole image, finding all the shapes and tracing them. The algorithm from top-level looks like this: (the “corner” here means any situation from the fig. 7)

  1. Scan the image, start with point 0,0, going through every row. Once a corner is found, start tracing.

  2. Trace the shape, marking every point we go through as visited.

  3. Continue scanning until we find another corner that was not yet visited or until we reach end of the image.

    1. If an unvisited corner is found, trace the new shape. (goto 2)
    2. If we reach end of the image, finish.

Marking as visited is necessary so that we never trace the same shape twice (from a different starting point, for example).

Holes

Paths found by the tracing algorithm will also include holes, like the ones in “o” of “B” letters. And now some SVG “magic”: If we put multiple paths (each starting with M and ending with z) in one SVG <path> element, SVG renderer will do the “smart thing” and cut the holes accordingly, with the default nonzero fill rule.

How it works? Intuitively: if a path inside another path is drawn in opposite direction, it’ll be cut out of the outer shape. So if the outer shape is drawn clockwise and the inner one is drawn counter-clockwise it’ll be cut out. For more precise definition, check the SVG docs on fill properties.

Notice that, the inside of the letter “n” runs counter-clockwise while the outside of “n” runs clockwise (fig 2.). If we close the “n”, we’ll get an “o” as on figure 8 and now it’s even more apparent which ways things go.

fig. 8: Inner shape cutting a hole in the outer shape

Actually, I’ve discovered the effects of nonzero by accident. I wasn’t thinking yet about hole-cutting but while trying to compress the output a bit by combining paths into one <path> element, it “magically” all came into place. Then I’ve started researching why it’s doing this much rightful thing :)

Colour

First version of SharpVG treated all colours as black. It was actually trivial to expand it to handle colours: we treat each colour as a separate 1-bit image. Resulting SVG image will have one path per colour.

Summing up

For me, converting pixelated graphics to SVGs and then manipulating them is perfect because it’s quick and fun to create a small pixelated image and it disguises my lack of proper drawing talent. Most of the examples in this article started as tiny images, drawn pixel-by-pixel, and then converted to SVG for further manipulation (like rotating similar cases).

SVG is currently quite underused by web developers. During writing this article I was very pleased with what you can do with it. The ease of reusing elements from different images is one shiny example: in any SVG image, we can take anything from another one provided it has an id attribute (so we can reference it). I makes for a very good solution for creating resource libraries (sprites). I highly recommend a very good article on use of the <use> element on Sara Soueidan’s blog.

Further reading