Subversion Repositories Kolibri OS

rasterizer.  The  rasterizer is of  quite general purpose  and could

easily be integrated into other programs.

     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

===============

  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.

  common rasterization techniques is assumed.

========================

---------------

  already done.  The glyph is thus  described by a list of points in

  the device space.

    used orientation is:

       |         reference orientation

       |

       *----> x

      0

    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).

    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.

        |                                          |

        |            (1,1)                         |      (0.5,0.5)

        +-----------+                        +-----+-----+

        |           |                        |     |     |

        |           |                        |     |     |

        |           |                        |     o-----+-----> x

        |           |                        |   (0,0)   |

        |           |                        |           |

        o-----------+-----> x                +-----------+

      (0,0)                             (-0.5,-0.5)

    `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.

    whether  it is  `on' or  `off' the  curve.  Two  successive `on'

    points indicate a line segment joining the two points.

    (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).

    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.

  They exhibit,  however, one very  useful property of  Bézier arcs:

  Each  point of  the curve  is a  weighted average  of  the control

  points.

  value  of t,  each arc  point lies  within the  triangle (polygon)

  defined by the arc's three (four) control points.

  rasterization of third-order curves is completely identical.

                                                     * 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.

---------------------

  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.

  more convenient to understand.

    simple  horizontal segments,  then turn  them on  in  the target

    bitmap.  These segments are called `spans'.

             _--       -_

           _-            -

          -               \

         /                 \

        /                   \

       |                     \

             _----------_                with spans.

           _--------------

          ----------------\

         /-----------------\    This is typically done from the top

        /                   \   to the bottom of the shape, in a

       |           |         \  movement called a `sweep'.

                   V

             _----------_

           _--------------

          ----------------\

         /-----------------\

        /-------------------\

       |---------------------\

    coordinates, which  are simply the x coordinates  of the shape's

    contours, taken on the y scanlines.

                  /---/     |---|   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

    information:

      number of  shape points  intersecting the scanline  (these are

      the points a, b, c, and d in the above example).

    `decomposition' which converts the glyph into *profiles*.

    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.

                                          1         2

         ---->----     is made of two

        |         |                       |         |

        |         |       profiles        |         |

        ^         v                       ^    +    v

        |         |                       |         |

        |         |                       |         |

         ----<----

          ^  | \  \                         |          \

          | |   \  \      profiles         |            \      |

         |  |    \  v                  ^   |             \     |

           |      \                    |  |         +     \    v

           |       \                   |  |                \

        P1 ---___   \                     ---___            \

                 ---_\                          ---_         \

             <--__     P3                   up           down

             /  |   /  ___          /    |

            /   |     /   |        /     |       /     |

           |    |    /   /    =>  |      v      /     /

           |    |   |   |         |      |     ^     |

        ^  |    |___|   |  |      ^   +  |  +  |  +  v

        |  |           |   v      |                 |

           |           |          |           up    |

           |___________|          |    down         |

    that are not part of the profiles themselves.

    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.

    `edgelists'.

    light systems, including embedded systems with very few memory.

    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.

    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).

    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).

    the x pixel coordinate of its intersection with a contour.

    convenient  to think  that  we need  a  profile's height  before

    allocating it in the pool and computing its coordinates.

    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).

                          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

    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:

      - max scanline = CEILING( max y )

    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.

                         *

                                       # on curve

                                       * off curve

                   __-x--_

                _--       -_

          P1  _-            -          A non y-monotonic Bézier arc.

             #               \

                              -        The arc goes from P1 to P3.

                               \

                                \  P3

                                 #

    according to  their control points.  I will  state here, without

    proof, that the monotony condition can be expressed as:

    They are, however, extremely important, as any arc that does not

    satisfy them necessarily contains an extremum.

    which is then one of its `on' points:

          #---__   *         P1P2P3 is ever-descending, but P1

                -_           is an y-extremum.

                  -

           ---_    \

               ->   \

                     \  P3

                      #

                         *

                                       # 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      (!)

                                 #

    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.

    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).

    two sub-arcs Q1Q2Q3 and R1R2R3:

                   *

                                    # on  curve

                                    * off curve

                __---__

             _--       --_

           _-             -_

          -                 -

         /                   \

        /                     \

       #                       #

     P1                         P3

                   *

          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.

    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:

                   *

                _--       #_

          Q1  _-        Q3  -   R2

             #               \ *

                              -

                               \

                                \  R3

                                 #

    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.

    iterative process of finding an extremum is called `flattening'.

    it in the render pool.   The next task is to compute coordinates

    for each scanline.

    using  the  Euclidean   algorithm  (also  known  as  Bresenham).

    However, for Bézier arcs, the job is a little more complicated.

    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'.

      ---------------------      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

    build (and fill) the spans.

    fill  rule (but  with opposite  directions), we  place,  on each

    scanline, the present profiles in two separate lists.

    profiles, while  the other `right' list  contains the descending

    profiles.

    property ensures that  the two lists contain the  same number of

    elements.

       value in the right list.

                  /     /   |   |          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).

                                   1 to 4 (i.e. a-b) and 3 to 2

                                   (i.e. c-d)!

    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.

    structures, like arrays to  perform `faster' sorting.  It turned

    out that  this old scheme is  not faster than  the one described

    above.

    the target bitmap.

David Turner, Robert Wilhelm, and Werner Lemberg.

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.

coding: utf-8

End: