500px-Metal_type_kerning.svg[1] (image taken from Wikipedia)

I’m working on a text-on-path algorithm for Maperitive to be able to render things like street names. GDI+ does not have a built-in function for drawing texts on a path, so I’m stuck with writing my own.

Although there are a lot of implementations of such an algorithm out there, they all miss one important thing: kerning. Kerning is basically telling a character to move a bit closer to its neighbor if there is enough space for them to huddle together:

Kerning[1] (image taken from Wikipedia)

Since the path can consist of several line segments (and even curves), you need to render each character (glyph to be more precise) separately to be able to rotate it using the angle of the line segment it will be drawn on. The problem is determining how far from the previous character to place the next character. GDI+ offers a method called MeasureString, but calling it on a single isolated character returns a character width value without any kerning taken into account, so characters like V and A can appear too spread apart. There is another method, MeasureCharacterRanges, which can measure each individual character width for a given text, but it has a practical limit of 32 characters and is pretty processor- and resource-intensive. I’ve used it for the text-on-path algorithm for Kosmos but the results weren’t very satisfactory.

From my (basic) understanding of how kerning usually works on computer typography, a font which has kerning information stores kerning offsets for character pairs. So, for example, V and A will have a different (usually stronger) kerning than say, character pair V and T. The problem with GDI+ is that you don’t really have access to this information.

One option would be to use old GDI’s font and text functions to fetch the information about the kerning pairs, but these need to be P/invoked and thus will probably not work on Mono, which makes them unusable for Maperitive – I’m really trying to make Maperitive run on multiple platforms.

So after spending a day in brainstorming, I got an idea on how to handle kerning myself. It’s really simple: I will calculate the kerning myself (using the mentioned MeasureString method). The formula is simple:

<character kerned width> = <character non-kerned width> – (<character pair non-kerned width> – <character pair kerned width>)

I can get all of the three values on the right of the equation using the MeasureString: first I’ll measure each character’s individual (non-kerned) width and then I’ll measure the width when they are drawn together. The difference between these is the actual kerning, which is then used to calculate the kerned width of the first character.

The added twist to this tale is that I’ll keep this information in a cache, to keep the expensive calls to the MeasureString method to the minimum. This cache could even be persisted to the disk. Of course, each font family and font style dictates its own kerning, so the cache needs to be extended with this information.

One potential problem is how to handle kerning information for different font heights. Since Maperitive supports continuous zooming levels, the number of different font heights used is (almost) limitless. I’ve decided to cut some corners here: the kerning will be calculated (and stored) for some nominal font height (say 100 em) and then interpolated for any needed height. We’ll see how that goes… next time.