.. _rfc98:

=========================================================================
MS RFC 98: Label/Text Rendering Overhaul
=========================================================================

:Date:  2013/06
:Author: Thomas Bonfort
:Contact: thomas.bonfort@gmail.com
:Status: Adopted
:Version: MapServer 7.0

1. The current situation
========================

1.1 Text rendering pipeline
---------------------------

When a feature needs to be labelled, the following (simplified) steps are undertaken:

- the string eventually goes through iconv to be converted to utf8
- the string goes through fribidi to reorder the glyphs from "logical order" to "visual order",
  to support languages that are written from right to left. e.g. supposing capital letters are
  arabic letters, the text which is stored in the feature as ``this is some ARABIC text`` is
  transformed into ``this is some CIBARA text`` in order to be fed transparently to the
  renderers that currently layout glyphs from left to right
- the string goes through line breaking, which is currently broken for RTL
  scripts for line breaking as we render (for ``arabic \n text``)

  ::

    TXET
    CIBARA

  instead of the required

  ::

    CIBARA
    TXET

- the string goes through alignment, which is currently hacky and unprecise (thanks
  to yours faithfully) as we (try to) achieve alignment by padding with spaces instead
  of using precise offsets per line

- the string is then passed to the renderers as-is, who are responsible for the whole
  laying out of each glyph

1.2 Limitations
---------------

While the current situation is simple to understand, and works reasonable well for latin
languages, it has a number of shortcomings that this RFC aims to resolve:

- All the renderers are duplicating layout logic:

  - splitting the utf8 string into individual glyphs
  - looking up a given glyph inside a font file
  - laying out a glyph with respect to the previous one (this includes spacing between
    subsequent characters, or determining how many pixels should be vertically added
    when a linebreak is encountered)

- While latin languages have a 1-to-1 mapping between string characters and font glyphs,
  this is not the case for complex languages, where ligature glyphs need to be inserted
  depending on context (see the `wikipedia complex text layout page
  <http://en.wikipedia.org/wiki/Complex_text_layout>`_ for a more complete explanation).
  While this is partly taken care of for us by fribidi for arabic (which has a shaping
  algorithm that inserts ligatures for us), we currently fail hard for other complex
  text languages.

- We don't support double spacing or line spacing at all, and our text alignment
  (center, right) is imprecise, as implementation for these would need to be added
  to each individual renderer.


2. Proposed Overhaul
====================

For the big picture, see `the state of text rendering <http://behdad.org/text/>`_.

In short, instead of passing a string of text and a starting position to the renderers,
we pass a list of glyphs (i.e. a glyph is a specific entry inside a specific font file)
along with their precise positioning, very similarly to what we do currently when
rendering ``FOLLOW`` labels, as is already outlined in `bug 3611
<https://github.com/mapserver/mapserver/issues/3611>`_ . The actual shaping and layout
happens in a single mapserver function, and the renderers just dumbly place glyphs where
they are told to.

2.1 Architecture Implications
-----------------------------

Architecturaly, this modification is significant, as the whole label rendering chain
needs to be refactored in order to take a list of positioned glyphs into account instead
of just plain text strings.

2.1.1 Dependencies
..................

- Freetype becomes a central mapserver dependency, as we need the information about glyph
  sizes at a higher level than currently (where freetype is a dependency of the individual
  renderers). We also need a single central glyph cache to be used across harfbuzz and the
  renderers. ``fontsetObj`` will likely need to be extended to be more than a simple
  filename hashtable. 
- Fribidi (which has some thread safety issues) is kept as the library that handles the 
  bidi algorithm for us. We do not use it for shaping anymore.
- Bring in Harfbuzz to support complex script shaping (to simplify: the tool that will
  insert ligatures between characters). Harfbuzz algorithms will be applied on text strings
  that have been determined to not be latin (i.e. the slowdown induced by harfbuzz is limited
  to those languages that actually require shaping).
- UTHash (http://troydhanson.github.io/uthash/) is a header only hashtable
  implementation that works with arbitrary keys and values, and is used for
  accessing cached fonts and glyphs. Given some performance testing, we might
  want to replace our own hashtable implementation with this one some day.

Note that the Fribidi and Harfbuzz dependencies will remain optional and can be
disablable at compile time for those only treating latin scripts. Harfbuzz and Fribidi will
need to be enabled or disabled together.

2.1.2 Font and Glyph cache
...........................
(fontcache.c)
A global (thread protected if needed) glyph and font cache will 
ensure that cached glyphs are reusable across
multiple requests for the fastcgi case, but in turn requires some
thread-level protection and probably some pruning in order for it to
remain of reasonable size. Some APIs have changed in order to have the
fontcache accessible.
The fontcache contains caches for:

- font faces (i.e. the representation of of a truetype file)
- glyphs (i.e. the metrics of an individual glyph at a given size)


2.1.2 Transforming a string of text into a list of positioned glyphs
.....................................................................

This step will be added to mapserver, and consists in coordinating the outputs from freetype,
the bidi algorithm, harfbuzz, line-breaking, text alignment, and in the future text and line
spacing. This step could be in most part implemented transparently through pango, however
pango is hard to support across platforms, and, to my knowledge, has a hard dependency on
fontconfig which is incompatible with our fontset approach.

Text is represented by a "textPathObj" which is basically a list of
positioned glyphs. (e.g the word "Label" at size 10 for an arial font
is represented by arial font's glyph "L" at position (x,y)= (0,0),
glyph "a" at position (10,0) , "b" at (18,0), etc...). Multiline text
is handled transparently by having glyphs positioned at different y
values. A textPath can be either "absolute" (i.e. the glyph positions
are in absolute image coordinates, used to position glyphs for angle
follow labels), or "relative", in which case they must be offset by
their labeling point.

All the shaping happens in textlayout.c,
who's principal role is to take a string of text as input, and return
a list of positioned glyphs as output. The input string goes through
multiple steps, and is plit into multiple run. Each run will have a
distinct line number, bidi direction, and script "language".

As an example, we'll be working with the input unicode string "this is
some text in english, ARABIC and JAPANESE". Capital letters are used
to denote non latin glyphs, also note that ARABIC is stored in logical
(=reading) order, whereas it would be rendered as CIBARA.

- iconv encoding conversion to convert the string to unicode
  
::

    run1 = "this is some text in english, ARABIC and JAPANESE", line=0

- line wrapping: break on wrap character, break long lines on spaces

::
 
    run1 = "this is some text in english,", line=0
    run2 = "ARABIC and JAPANESE", line=1

- bidi levels, each run has a single bidi direction (i.e. left-to-right or right-to-left)

::

    run1 = "this is some text in english,", line=0, direction=LTR
    run2 = "ARABIC" line=1, direction=RTL
    run3 = " and JAPANESE", line=1, direction = LTR

- script detection is applied to enable language dependent shaping,
  and also to refine which fonts will be used (more on that later)

::

    run1 = "this is some text in english,", line=0, direction=LTR, script=latin
    run2 = "ARABIC" line=1, direction=RTL, script=arabic
    run3 = " and " line=1, direction=LTR, script=latin
    run4 = "JAPANESE" line=1, direction=LTR, script=hiragana

- for each run, we select which font should be used, in order to use
  the same font inside a given run. :ref:`rfc80` allowed to specify
  multiple fonts for a LABEL, this has been extended to be able to fine
  tune which fonts are to be preferably used for a given script:

::

    FONT "arialuni,arial,cjk,arabic"

can now be written prefixed by a script identifier, i.e.

::

    FONT "arialuni,en:arial,ja:cjk,ar:arabic"

  This is needed as there is and will be overlap between font glyph
  coverages, and it should be possible to prioritize which font is used
  for which language.

- Each run is then fed into harfbuzz, which returns a list of
  positioned glyphs. The number of returned glyphs is not meant to be
  identical to the number of glyphs we had in the unicode string, and
  are ordered from left to right. As a speedup, a run who's script is
  "latin" is not fed through harfbuzz, but instead uses cached glyph
  advances.

- The glyphs of each run are reassembled to account for line numbers
  and run positions (e.g. run 3 is offset down by one line, and placed
  to the right of run 2)

- Each line is horizontally offseted to account for ALIGN. LABEL ALIGN
  now stops defaulting to LEFT, so right-to-left runs will be right
  aligned instead of left as is now.

2.1.3 Handling glyphs at rendering phase
........................................

The labelcache and the renderers will need to be updated to work with a list of glyphs.
Changes here are extensive but should remain conceptually simple. Individual renderers are
substantially simplified.

Work has been done to trim down the labelcache computations as much as possible:

When inserting features into the labelcache:

- We'll insert a reference to the original labelObj instead of a copy
  if the labelObj and it's child styleObjs don't contain any bindings.
  This cuts dow on memory usage when attribute bindings aren't in use.
- We don't insert features that will never get rendered (e.g. out of
  scale, too large for their feature (minfeaturesize keyword) )

At the msDrawLabelCache phase:

- We delay computation of the label text bounding box to after we have
  checked conditions that would cause it not be renderered, i.e.
  
  - if they have a MINDISTANCE set and a neighbouring label with
    identical text has already been rendered
  - for labels without markers, we first check that the labelpoint
    doesn't collide with an existing label.

- The Collision detection has been optimized:
  
  - We keep a list of rendered labels and loop through those instead of
    checking the status of all the labels in the labelcache for each
    member
  - The bounding metrics for a label has been cut down from a full
    shapeObj to a struct containing a bounding rect and an optional
    lineObj. For non rotated labels, there's no information needed more
    than the bounding box, which makes intersection detection much easier
    for two labels like this (i.e. the overlapping of these two labels is
    the same as the overlapping of their bounding boxes, no need to go
    into further geometric intersection primitives).

  The speedups for these changes are extremely important for cluttered
  maps, c.f. https://plus.google.com/u/0/118271009221580171800/posts/PrwhFYSkhea
  (e.g. rendering time goes from 800 to 1 second for 500.000 labels)

2.2 Backwards Compatibility
---------------------------

- At a high (mapfile) level, none expected.
- Some mapscript APIs may change or may need to be wrapped. (TBD)
- Some subtle but widespread changes in character placement.
- :ref:`rfc99` is a collateral of most of these changes


2.3 Performance Implications
----------------------------

Potentially numerous:

- Existing performance on latin only text will need to be kept to
  the current level, by detecting and shortcutting these cases. If done correctly we may
  actually be able to speed up latin text rendering marginally.

- For other scripts, the cost of going through harfbuzz **will** come with a performance
  penalty.


3. Miscellaneous
================

3.1 Issue Tracking ID
---------------------

https://github.com/mapserver/mapserver/issues/4673


3.2 Voting History
------------------

+1 from MikeS, StephanM, TomK, JeffM, SteveW, SteveL and ThomasB

