The Tor Browser: modules/freetype2/docs/raster.txt@b8a032363ba2 (annotated)

modules/freetype2/docs/raster.txt@b8a032363ba2 (annotated)

modules/freetype2/docs/raster.txt

Thu, 22 Jan 2015 13:21:57 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Thu, 22 Jan 2015 13:21:57 +0100
branch: TOR_BUG_9701
changeset 15: b8a032363ba2
permissions: -rw-r--r--

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

                    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
 . Requirements
 . 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
 ========================
 . 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
 
     `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
 `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.
 . 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
 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:
 . We sort each list in increasing horizontal order.
 . 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 &
 //     /   ^ |   |  | 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
 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, 2007 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:

The Tor Browser / annotate

modules/freetype2/docs/raster.txt@b8a032363ba2 (annotated)

modules/freetype2/docs/raster.txt