raster.txt

freetype 2.3.5 文档,英文文件

                   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.