Summer of Code 2012 - Line breaking

Yet an other week has passed and a lot of things have happened since my Summer of Code half-time post:

Itemizer

I noticed that the rendering I got from the text in bug #519 was totally wrong. I tracked it down to ICU’s bidi algorithm which returns text runs in visual order but I assumed they would be in logical order. Therefore all my offsets were wrong. Returning the runs in visual order makes much more sense as no further reordering is necessary. While working on the itemizer I also updated it to operate on parts of the input text for processing lines after line breaking.

This brings me to the next topic:

Line breaking

I finally got line breaking done. It was easier than I originally thought because I had the idea that I don’t need a 1:1 character to glyph width mapping. It is enough when I know how wide the sum of all characters forming a glyph cluster is. Now I build a map which assigns the sum of the width of all glyphs forming a cluster to the first character of this cluster. All other characters get a width of zero.

After this map is built line breaking is pretty straight forward. Sum all widths till the length is longer than the maximum length, then find the last or next break position and break the line.

Afterwards reshape each line to get a correct rendering.

Kerning

I noticed small differences in glyph spacing between texts rendered with Mapnik trunk and this branch. I found the cause of this behavior:

HarfBuzz uses the kerning tables in the fonts and produces better spacing.

Before and after example:

Infrastructure work

I removed almost all code from the old text rendering system. It had grown from a simple solution to a complex, hard to maintain one. The new system should be much easier to understand.

HarfBuzz

HarfBuzz also has made large steps last week. There was a hackfest in Toronto and problems with Indic languages were addressed. After the hackfest was over the failure rates for the following languages were down to less than 0.19%. Before they were as high as 87.7% (Khmer).

• Amil
• Telugu
• Gujarati
• Oriya
• Devanagari
• Gurmukhi
• Bengali
• Kannada
• Malayalam
• Khmer
• Sinhala

Next steps

Next week I will reimplement as much as possible of the placement finder functionality.