raster.txt

一个类似windows

    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 confortable 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閦ier  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閦ier 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閦ier 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閦ier  arcs have  the  special property  of  being very  easily
    decomposed into two sub-arcs,  which are themselves B閦ier arcs.
    Moreover, it is easy to prove that there is at most one vertical
    extremum on  each B閦ier 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閦ier 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閦ier 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  Euclidian   algorithm  (also  known  as  Bresenham).
    However, for B閦ier arcs, the job is a little more complicated.

    We assume  that all B閦iers 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 involed algorithm
          * P2         _---# P3  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 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: latin-1
End: