Introduction to complex text layout

Complex text layout is, as the name says, a pretty complicated process. The term stands for various text transformations that need to be done to render scripts that require more than trivial codepoint-to-glyph mapping.

Generally, the following transformations are complex text layout:

• BiDi. Many languages do not write from left to right, but from right to left (e.g. Hebrew). Usually, numbers are still written from left to right, though. Sometimes you need to mix right to left text into left to right text. When there's any mix between directions, and that can happen quite quickly, the text needs to be split up into so-called runs with the same direction, and rendered accordingly. Unicode specifies such an algorithm, the Unicode Bidirectional Algorithm.
• Text shaping. Many scripts, especially cursive scripts (most importantly Arabic and derivatives) require contextual glyph substitutions. Depending on the position of a glyph inside a word, a certain variant needs to be used. Moreover, as it is a cursive script, the letters need to be repositioned so that they connect cleanly to each other. There are a lot more features referred to as shaping. Shaping requires runs of text with the same direction and script.
• Line breaking. Mixing text direction, language and script complicates line breaking. Unicode specifies the Unicode Line Breaking Algorithm to deal with that.

According to that, a full complex text layout engine needs to do a lot of work.

1. Split up text into runs according to style (font, size, decoration).
2. Split up runs further according to text direction (depending on script and language).
3. Shape runs that need it.
4. Break lines.

Complete and easy to use cross-platform engines already exist and work well. One example is the popular Pango library. However, Pango only offers a very high-level API for the complete engine. It's not flexible enough for libass, which does a lot of rather low-level font manipulations, and it's said to be slow, while performance is critical for libass.

So there's no way around doing all steps yourself. Fortunately, stable libraries for all of the critical steps are available. I'm going to describe the plans for the libass implementation in the next posts.