Update freetype sources (2.6.2) in third party.

third_party/freetype2/src/docs/raster.txt

Index: third_party/freetype2/src/docs/raster.txt
diff --git a/third_party/freetype2/src/docs/raster.txt b/third_party/freetype2/src/docs/raster.txt
new file mode 100644
index 0000000000000000000000000000000000000000..dc55d64e593072ad5b387c78505aec31904800d7
--- /dev/null
+++ b/third_party/freetype2/src/docs/raster.txt
@@ -0,0 +1,635 @@
+
+                   How FreeType's rasterizer work
+
+                          by David Turner
+
+                        Revised 2007-Feb-01
+
+
+This file  is an  attempt to explain  the internals of  the FreeType
+rasterizer.  The  rasterizer is of  quite general purpose  and could
+easily be integrated into other programs.
+
+
+  I. Introduction
+
+ II. Rendering Technology
+     1. Requirements
+     2. Profiles and Spans
+        a. Sweeping the Shape
+        b. Decomposing Outlines into Profiles
+        c. The Render Pool
+        d. Computing Profiles Extents
+        e. Computing Profiles Coordinates
+        f. Sweeping and Sorting the Spans
+
+
+I. Introduction
+===============
+
+  A  rasterizer is  a library  in charge  of converting  a vectorial
+  representation of a shape  into a bitmap.  The FreeType rasterizer
+  has  been  originally developed  to  render  the  glyphs found  in
+  TrueType  files, made  up  of segments  and second-order  Béziers.
+  Meanwhile it has been extended to render third-order Bézier curves
+  also.   This  document  is   an  explanation  of  its  design  and
+  implementation.
+
+  While  these explanations start  from the  basics, a  knowledge of
+  common rasterization techniques is assumed.
+
+
+II. Rendering Technology
+========================
+
+1. Requirements
+---------------
+
+  We  assume that  all scaling,  rotating, hinting,  etc.,  has been
+  already done.  The glyph is thus  described by a list of points in
+  the device space.
+
+  - All point coordinates  are in the 26.6 fixed  float format.  The
+    used orientation is:
+
+
+       ^ y
+       |         reference orientation
+       |
+       *----> x
+      0
+
+
+    `26.6' means  that 26 bits  are used for  the integer part  of a
+    value   and  6   bits  are   used  for   the   fractional  part.
+    Consequently, the `distance'  between two neighbouring pixels is
+    64 `units' (1 unit = 1/64th of a pixel).
+
+    Note  that, for  the rasterizer,  pixel centers  are  located at
+    integer   coordinates.   The   TrueType   bytecode  interpreter,
+    however, assumes that  the lower left edge of  a pixel (which is
+    taken  to be  a square  with  a length  of 1  unit) has  integer
+    coordinates.
+
+
+        ^ y                                        ^ y
+        |                                          |
+        |            (1,1)                         |      (0.5,0.5)
+        +-----------+                        +-----+-----+
+        |           |                        |     |     |
+        |           |                        |     |     |
+        |           |                        |     o-----+-----> x
+        |           |                        |   (0,0)   |
+        |           |                        |           |
+        o-----------+-----> x                +-----------+
+      (0,0)                             (-0.5,-0.5)
+
+   TrueType bytecode interpreter          FreeType rasterizer
+
+
+    A pixel line in the target bitmap is called a `scanline'.
+
+  - A  glyph  is  usually  made  of several  contours,  also  called
+    `outlines'.  A contour is simply a closed curve that delimits an
+    outer or inner region of the glyph.  It is described by a series
+    of successive points of the points table.
+
+    Each point  of the glyph  has an associated flag  that indicates
+    whether  it is  `on' or  `off' the  curve.  Two  successive `on'
+    points indicate a line segment joining the two points.
+
+    One `off' point amidst two `on' points indicates a second-degree
+    (conic)  Bézier parametric  arc, defined  by these  three points
+    (the `off' point being the  control point, and the `on' ones the
+    start and end points).  Similarly, a third-degree (cubic) Bézier
+    curve  is described  by four  points (two  `off'  control points
+    between two `on' points).
+
+    Finally,  for  second-order curves  only,  two successive  `off'
+    points  forces the  rasterizer to  create, during  rendering, an
+    `on'  point amidst them,  at their  exact middle.   This greatly
+    facilitates the  definition of  successive Bézier arcs.
+
+  The parametric form of a second-order Bézier curve is:
+
+      P(t) = (1-t)^2*P1 + 2*t*(1-t)*P2 + t^2*P3
+
+      (P1 and P3 are the end points, P2 the control point.)
+
+  The parametric form of a third-order Bézier curve is:
+
+      P(t) = (1-t)^3*P1 + 3*t*(1-t)^2*P2 + 3*t^2*(1-t)*P3 + t^3*P4
+
+      (P1 and P4 are the end points, P2 and P3 the control points.)
+
+  For both formulae, t is a real number in the range [0..1].
+
+  Note  that the rasterizer  does not  use these  formulae directly.
+  They exhibit,  however, one very  useful property of  Bézier arcs:
+  Each  point of  the curve  is a  weighted average  of  the control
+  points.
+
+  As all weights  are positive and always sum up  to 1, whatever the
+  value  of t,  each arc  point lies  within the  triangle (polygon)
+  defined by the arc's three (four) control points.
+
+  In  the following,  only second-order  curves are  discussed since
+  rasterization of third-order curves is completely identical.
+
+  Here some samples for second-order curves.
+
+
+                                        *            # on curve
+                                                     * off curve
+                                     __---__
+        #-__                      _--       -_
+            --__                _-            -
+                --__           #               \
+                    --__                        #
+                        -#
+                                 Two `on' points
+         Two `on' points       and one `off' point
+                                  between them
+
+                      *
+        #            __      Two `on' points with two `off'
+         \          -  -     points between them. The point
+          \        /    \    marked `0' is the middle of the
+           -      0      \   `off' points, and is a `virtual
+            -_  _-       #   on' point where the curve passes.
+              --             It does not appear in the point
+              *              list.
+
+
+2. Profiles and Spans
+---------------------
+
+  The following is a basic explanation of the _kind_ of computations
+  made  by  the   rasterizer  to  build  a  bitmap   from  a  vector
+  representation.  Note  that the actual  implementation is slightly
+  different, due to performance tuning and other factors.
+
+  However, the following ideas remain  in the same category, and are
+  more convenient to understand.
+
+
+  a. Sweeping the Shape
+
+    The best way to fill a shape is to decompose it into a number of
+    simple  horizontal segments,  then turn  them on  in  the target
+    bitmap.  These segments are called `spans'.
+
+                __---__
+             _--       -_
+           _-            -
+          -               \
+         /                 \
+        /                   \
+       |                     \
+
+                __---__         Example: filling a shape
+             _----------_                with spans.
+           _--------------
+          ----------------\
+         /-----------------\    This is typically done from the top
+        /                   \   to the bottom of the shape, in a
+       |           |         \  movement called a `sweep'.
+                   V
+
+                __---__
+             _----------_
+           _--------------
+          ----------------\
+         /-----------------\
+        /-------------------\
+       |---------------------\
+
+
+    In  order  to draw  a  span,  the  rasterizer must  compute  its
+    coordinates, which  are simply the x coordinates  of the shape's
+    contours, taken on the y scanlines.
+
+
+                   /---/    |---|   Note that there are usually
+                  /---/     |---|   several spans per scanline.
+        |        /---/      |---|
+        |       /---/_______|---|   When rendering this shape to the
+        V      /----------------|   current scanline y, we must
+              /-----------------|   compute the x values of the
+           a /----|         |---|   points a, b, c, and d.
+      - - - *     * - - - - *   * - - y -
+           /     / b       c|   |d
+
+
+                   /---/    |---|
+                  /---/     |---|  And then turn on the spans a-b
+                 /---/      |---|  and c-d.
+                /---/_______|---|
+               /----------------|
+              /-----------------|
+           a /----|         |---|
+      - - - ####### - - - - ##### - - y -
+           /     / b       c|   |d
+
+
+  b. Decomposing Outlines into Profiles
+
+    For  each  scanline during  the  sweep,  we  need the  following
+    information:
+
+    o The  number of  spans on  the current  scanline, given  by the
+      number of  shape points  intersecting the scanline  (these are
+      the points a, b, c, and d in the above example).
+
+    o The x coordinates of these points.
+
+    x coordinates are  computed before the sweep, in  a phase called
+    `decomposition' which converts the glyph into *profiles*.
+
+    Put it simply, a `profile'  is a contour's portion that can only
+    be either ascending or descending,  i.e., it is monotonic in the
+    vertical direction (we also say  y-monotonic).  There is no such
+    thing as a horizontal profile, as we shall see.
+
+    Here are a few examples:
+
+
+      this square
+                                          1         2
+         ---->----     is made of two
+        |         |                       |         |
+        |         |       profiles        |         |
+        ^         v                       ^    +    v
+        |         |                       |         |
+        |         |                       |         |
+         ----<----
+
+                                         up        down
+
+
+      this triangle
+
+             P2                             1          2
+
+             |\        is made of two       |         \
+          ^  | \  \                         |          \
+          | |   \  \      profiles         |            \      |
+         |  |    \  v                  ^   |             \     |
+           |      \                    |  |         +     \    v
+           |       \                   |  |                \
+        P1 ---___   \                     ---___            \
+                 ---_\                          ---_         \
+             <--__     P3                   up           down
+
+
+
+      A more general contour can be made of more than two profiles:
+
+              __     ^
+             /  |   /  ___          /    |
+            /   |     /   |        /     |       /     |
+           |    |    /   /    =>  |      v      /     /
+           |    |   |   |         |      |     ^     |
+        ^  |    |___|   |  |      ^   +  |  +  |  +  v
+        |  |           |   v      |                 |
+           |           |          |           up    |
+           |___________|          |    down         |
+
+                <--               up              down
+
+
+    Successive  profiles are  always joined  by  horizontal segments
+    that are not part of the profiles themselves.
+
+    For  the  rasterizer,  a  profile  is  simply  an  *array*  that
+    associates  one  horizontal *pixel*  coordinate  to each  bitmap
+    *scanline*  crossed  by  the  contour's section  containing  the
+    profile.  Note that profiles are *oriented* up or down along the
+    glyph's original flow orientation.
+
+    In other graphics libraries, profiles are also called `edges' or
+    `edgelists'.
+
+
+  c. The Render Pool
+
+    FreeType  has been designed  to be  able to  run well  on _very_
+    light systems, including embedded systems with very few memory.
+
+    A render pool  will be allocated once; the  rasterizer uses this
+    pool for all  its needs by managing this  memory directly in it.
+    The  algorithms that are  used for  profile computation  make it
+    possible to use  the pool as a simple  growing heap.  This means
+    that this  memory management is  actually quite easy  and faster
+    than any kind of malloc()/free() combination.
+
+    Moreover,  we'll see  later that  the rasterizer  is  able, when
+    dealing with profiles too large  and numerous to lie all at once
+    in  the render  pool, to  immediately decompose  recursively the
+    rendering process  into independent sub-tasks,  each taking less
+    memory to be performed (see `sub-banding' below).
+
+    The  render pool doesn't  need to  be large.   A 4KByte  pool is
+    enough for nearly all renditions, though nearly 100% slower than
+    a more comfortable 16KByte or 32KByte pool (that was tested with
+    complex glyphs at sizes over 500 pixels).
+
+
+  d. Computing Profiles Extents
+
+    Remember that a profile is an array, associating a _scanline_ to
+    the x pixel coordinate of its intersection with a contour.
+
+    Though it's not exactly how the FreeType rasterizer works, it is
+    convenient  to think  that  we need  a  profile's height  before
+    allocating it in the pool and computing its coordinates.
+
+    The profile's height  is the number of scanlines  crossed by the
+    y-monotonic section of a contour.  We thus need to compute these
+    sections from  the vectorial description.  In order  to do that,
+    we are  obliged to compute all  (local and global)  y extrema of
+    the glyph (minima and maxima).
+
+
+           P2             For instance, this triangle has only
+                          two y-extrema, which are simply
+           |\
+           | \               P2.y  as a vertical maximum
+          |   \              P3.y  as a vertical minimum
+          |    \
+         |      \            P1.y is not a vertical extremum (though
+         |       \           it is a horizontal minimum, which we
+      P1 ---___   \          don't need).
+               ---_\
+                     P3
+
+
+    Note  that the  extrema are  expressed  in pixel  units, not  in
+    scanlines.   The triangle's  height  is certainly  (P3.y-P2.y+1)
+    pixel  units,   but  its  profiles'  heights   are  computed  in
+    scanlines.  The exact conversion is simple:
+
+      - min scanline = FLOOR  ( min y )
+      - max scanline = CEILING( max y )
+
+    A problem  arises with Bézier  Arcs.  While a segment  is always
+    necessarily y-monotonic (i.e.,  flat, ascending, or descending),
+    which makes extrema computations easy,  the ascent of an arc can
+    vary between its control points.
+
+
+                          P2
+                         *
+                                       # on curve
+                                       * off curve
+                   __-x--_
+                _--       -_
+          P1  _-            -          A non y-monotonic Bézier arc.
+             #               \
+                              -        The arc goes from P1 to P3.
+                               \
+                                \  P3
+                                 #
+
+
+    We first  need to be  able to easily detect  non-monotonic arcs,
+    according to  their control points.  I will  state here, without
+    proof, that the monotony condition can be expressed as:
+
+      P1.y <= P2.y <= P3.y   for an ever-ascending arc
+
+      P1.y >= P2.y >= P3.y   for an ever-descending arc
+
+    with the special case of
+
+      P1.y = P2.y = P3.y     where the arc is said to be `flat'.
+
+    As  you can  see, these  conditions can  be very  easily tested.
+    They are, however, extremely important, as any arc that does not
+    satisfy them necessarily contains an extremum.
+
+    Note  also that  a monotonic  arc can  contain an  extremum too,
+    which is then one of its `on' points:
+
+
+        P1           P2
+          #---__   *         P1P2P3 is ever-descending, but P1
+                -_           is an y-extremum.
+                  -
+           ---_    \
+               ->   \
+                     \  P3
+                      #
+
+
+    Let's go back to our previous example:
+
+
+                          P2
+                         *
+                                       # on curve
+                                       * off curve
+                   __-x--_
+                _--       -_
+          P1  _-            -          A non-y-monotonic Bézier arc.
+             #               \
+                              -        Here we have
+                               \              P2.y >= P1.y &&
+                                \  P3         P2.y >= P3.y      (!)
+                                 #
+
+
+    We need to  compute the vertical maximum of this  arc to be able
+    to compute a profile's height (the point marked by an `x').  The
+    arc's equation indicates that  a direct computation is possible,
+    but  we rely  on a  different technique,  which use  will become
+    apparent soon.
+
+    Bézier  arcs have  the  special property  of  being very  easily
+    decomposed into two sub-arcs,  which are themselves Bézier arcs.
+    Moreover, it is easy to prove that there is at most one vertical
+    extremum on  each Bézier arc (for  second-degree curves; similar
+    conditions can be found for third-order arcs).
+
+    For instance,  the following arc  P1P2P3 can be  decomposed into
+    two sub-arcs Q1Q2Q3 and R1R2R3:
+
+
+                    P2
+                   *
+                                    # on  curve
+                                    * off curve
+
+
+                                    original Bézier arc P1P2P3.
+                __---__
+             _--       --_
+           _-             -_
+          -                 -
+         /                   \
+        /                     \
+       #                       #
+     P1                         P3
+
+
+
+                    P2
+                   *
+
+
+
+                   Q3                 Decomposed into two subarcs
+          Q2                R2        Q1Q2Q3 and R1R2R3
+            *   __-#-__   *
+             _--       --_
+           _-       R1    -_          Q1 = P1         R3 = P3
+          -                 -         Q2 = (P1+P2)/2  R2 = (P2+P3)/2
+         /                   \
+        /                     \            Q3 = R1 = (Q2+R2)/2
+       #                       #
+     Q1                         R3    Note that Q2, R2, and Q3=R1
+                                      are on a single line which is
+                                      tangent to the curve.
+
+
+    We have then decomposed  a non-y-monotonic Bézier curve into two
+    smaller sub-arcs.  Note that in the above drawing, both sub-arcs
+    are monotonic, and that the extremum is then Q3=R1.  However, in
+    a  more general  case,  only  one sub-arc  is  guaranteed to  be
+    monotonic.  Getting back to our former example:
+
+
+                    Q2
+                   *
+
+                   __-x--_ R1
+                _--       #_
+          Q1  _-        Q3  -   R2
+             #               \ *
+                              -
+                               \
+                                \  R3
+                                 #
+
+
+    Here, we see that,  though Q1Q2Q3 is still non-monotonic, R1R2R3
+    is ever  descending: We  thus know that  it doesn't  contain the
+    extremum.  We can then re-subdivide Q1Q2Q3 into two sub-arcs and
+    go  on recursively,  stopping  when we  encounter two  monotonic
+    subarcs, or when the subarcs become simply too small.
+
+    We  will finally  find  the vertical  extremum.   Note that  the
+    iterative process of finding an extremum is called `flattening'.
+
+
+  e. Computing Profiles Coordinates
+
+    Once we have the height of each profile, we are able to allocate
+    it in the render pool.   The next task is to compute coordinates
+    for each scanline.
+
+    In  the case  of segments,  the computation  is straightforward,
+    using  the  Euclidean   algorithm  (also  known  as  Bresenham).
+    However, for Bézier arcs, the job is a little more complicated.
+
+    We assume  that all Béziers that  are part of a  profile are the
+    result of  flattening the curve,  which means that they  are all
+    y-monotonic (ascending  or descending, and never  flat).  We now
+    have  to compute the  intersections of  arcs with  the profile's
+    scanlines.  One  way is  to use a  similar scheme  to flattening
+    called `stepping'.
+
+
+                                 Consider this arc, going from P1 to
+      ---------------------      P3.  Suppose that we need to
+                                 compute its intersections with the
+                                 drawn scanlines.  As already
+      ---------------------      mentioned this can be done
+                                 directly, but the involved
+          * P2         _---# P3  algorithm is far too slow.
+      ------------- _--  --
+                  _-
+                _/               Instead, it is still possible to
+      ---------/-----------      use the decomposition property in
+              /                  the same recursive way, i.e.,
+             |                   subdivide the arc into subarcs
+      ------|--------------      until these get too small to cross
+            |                    more than one scanline!
+           |
+      -----|---------------      This is very easily done using a
+          |                      rasterizer-managed stack of
+          |                      subarcs.
+          # P1
+
+
+  f. Sweeping and Sorting the Spans
+
+    Once all our profiles have  been computed, we begin the sweep to
+    build (and fill) the spans.
+
+    As both the  TrueType and Type 1 specifications  use the winding
+    fill  rule (but  with opposite  directions), we  place,  on each
+    scanline, the present profiles in two separate lists.
+
+    One  list,  called  the  `left'  one,  only  contains  ascending
+    profiles, while  the other `right' list  contains the descending
+    profiles.
+
+    As  each glyph  is made  of  closed curves,  a simple  geometric
+    property ensures that  the two lists contain the  same number of
+    elements.
+
+    Creating spans is thus straightforward:
+
+    1. We sort each list in increasing horizontal order.
+
+    2. We pair  each value of  the left list with  its corresponding
+       value in the right list.
+
+
+                   /     /  |   |          For example, we have here
+                  /     /   |   |          four profiles.  Two of
+                >/     /    |   |  |       them are ascending (1 &
+              1//     /   ^ |   |  | 2     3), while the two others
+              //     //  3| |   |  v       are descending (2 & 4).
+              /     //4   | |   |          On the given scanline,
+           a /     /<       |   |          the left list is (1,3),
+      - - - *-----* - - - - *---* - - y -  and the right one is
+           /     / b       c|   |d         (4,2) (sorted).
+
+                                   There are then two spans, joining
+                                   1 to 4 (i.e. a-b) and 3 to 2
+                                   (i.e. c-d)!
+
+
+    Sorting doesn't necessarily  take much time, as in  99 cases out
+    of 100, the lists' order is  kept from one scanline to the next.
+    We can  thus implement it  with two simple  singly-linked lists,
+    sorted by a classic bubble-sort, which takes a minimum amount of
+    time when the lists are already sorted.
+
+    A  previous  version  of  the  rasterizer  used  more  elaborate
+    structures, like arrays to  perform `faster' sorting.  It turned
+    out that  this old scheme is  not faster than  the one described
+    above.
+
+    Once the spans  have been `created', we can  simply draw them in
+    the target bitmap.
+
+------------------------------------------------------------------------
+
+Copyright 2003-2015 by
+David Turner, Robert Wilhelm, and Werner Lemberg.
+
+This  file  is  part  of the  FreeType  project, and may  only be  used,
+modified,  and  distributed  under  the  terms of  the FreeType  project
+license, LICENSE.TXT.   By continuing to use, modify, or distribute this
+file you  indicate that  you have  read the  license and understand  and
+accept it fully.
+
+
+--- end of raster.txt ---
+
+Local Variables:
+coding: utf-8
+End: