Text Layout Engines

As many of my loyal followers know, I wrote a really fast text layout engine for Moonlight 1.0 which was able to layout text in more-or-less a single pass over the string. Hard to do better than that, especially with my superbly (I'm allowed to stroke my own ego, right?) designed font/glyph caches.

That said, the code had also been superbly disgusting and unmaintainable. Made worse when I had to add hacks to render text selection (Silverlight 1.0's TextBlock is like a GtkLabel in that it just renders text, but Silverlight 2.0's TextBox supports editing and selection and so is therefor more akin to a multi-line GtkEntry widget).

Well, Thursday night, as I was watching House on Hulu, I had one of those "House moments" where he suddenly realizes what the patient is suffering from and how to solve the problem (usually when his friend, Wilson, is talking to him about something random).

I spent all day yesterday (and I mean all day, until 11pm last night) putting together my thoughts for a new design and working out the details and I think I now have a vastly improved solution that not only uses less memory in all but the pathological cases (I now use a UTF-8 string instead of a UCS4 string), but also doesn't require:

• a pass over the text to break on CR/LF to construct a list of text runs which were what the old TextLayout engine I wrote used instead of a char* (because the layout engine now handles CR/LFs)
• a whole new set of text runs every time selection boundaries change in a TextBox (because selection is no longer represented by text runs)

Of course, the same brilliance of the old design still apply: no need to re-layout when most text properties (underline, foreground, background, etc) change (obviously we still have to re-layout if font properties change because they change the metrics).

With my new design, my TextLayout class has a Select() method which allows the consumer to change the selected region of text. When you change the selection, my new logic can simply clear the cached glyph clusters for the affected area(s).

A "glyph cluster" is a cached (sub)run of glyphs in a particular text run. A "text run" is a substring of text that share all the same text attributes which does not span across line boundaries.

To break it down, a layout contains a list of lines. Each line contains a list of runs. Each run contains a list of glyph clusters.

Normally, a run will consist of only a single glyph cluster unless it overlaps the selection.

For example, if the first half of the run is within the selection, then the run will contain 2 glyph clusters (one for the selected portion and one for the non-selected portion). However, if the selection is fully contained within a single run but doesn't span the entire run, then it's possible to have up to 3 glyph clusters for that run: pre-selection, selection, post-selection.

The brilliance of doing it this way is that it simplifies keeping track of kerning between selected regions, so that as you drag your selection across some text, the text following your mouse cursor doesn't appear to "jump" to the left or right as you move between characters that are kerned.