Saturday, February 28, 2009

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.


Anonymous said...

Nice. But why don't you just use HarfBuzz?

Jeffrey Stedfast said...

This is the first time I've even heard of HarfBuzz :(

Unfortunately, looks like HarfBuzz is more of a glyph shaper library than a layout engine (what I mean by "layout" is wrapping text to fit within a set of bounds).

Pango is actually pretty close to what I want, but since my software has to support SLED10 (which only has Pango 1.10), it's missing a lot of the functionality (and performance improvements) that I need for something like Moonlight :(

Looking forward, I definitely want to switch to Pango, although I'm hoping that some of my performance ideas might give the Pango devs some ideas for improving Pango's performance as well (the major performance bottleneck I had with Pango has already been fixed).

Jeffrey Stedfast said...

I should mention that basically all of my required features to use Pango have been pretty much met. The only remaining stumbling block that I know of for sure is that PangoWrapMode doesn't map very well to Silverlight's TextWrapping modes.

There's some other areas that I'd probably have to hack around, but I think they are doable.

Anonymous said...

Oh, I see now. I was just afraid that you gonna spend your time reinventing the wheel, effectively wasting many hours implementing yet-another layout engine. Good to know that your case is special. And true, supporting ancient distribution/software is real PITA.

Anonymous said...

How does Hulu work? Do I need to signup to watch any videos?

Code Snippet Licensing

All code posted to this blog is licensed under the MIT/X11 license unless otherwise stated in the post itself.