
             Bitmap and Pixmap generation with FreeType

                   v 1.0 - D. Turner - 21/5/1998


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

                         Table Of Contents


                Introduction
                
                I.   The raster component
                
                II.  Bitmap & Pixmap descriptors
                    
                III. Rendering an outline

                IV.  Anti-aliasing palette and other concerns
                
                Conclusion

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

Intoduction:

  This document describes the steps that are needed to render a glyph
  outline into a bitmap or a pixmap with the FreeType library. It contains
  several important details needed to generate bitmaps correctly in all
  situations, including when an outline has been transformed or translated.


I. The raster component :

  In FreeType, the component in charge of performing bitmap and pixmap
  rendering is called the "raster". Generation is performed through
  traditional process called "scan-line conversion", but exhibits certain
  properties :

  - the raster doesn't allocate bitmaps :
  
    In fact, it is only able to render an outline into an existing bitmap
    or pixmap, which is passed to one of its rendering functions. This
    means that the target bitmap/pixmap must be set up correctly by the
    caller to achieve desired results. Setting up bitmap and pixmap
    descriptors is explained in section II.


  - it is able to render anti-aliased pixmaps directly :
  
    unlike other graphics packages, which render to a "large" bitmap which
    is then filtered down. Putting the anti-aliasing logic within the raster
    improves performance and reduces memory usage, as well as let the use
    of better algorithms which couldn't work in a "two-phase" process.


  The raster is located in the "ttraster.h" and "ttraster.c" files (or
  "ttraster.pas" for the Pascal one).

  The format of outlines isn't important for most developers and won't
  be discussed here. However, a few conventions must be explained regarding
  the vector outlines :


  1. Units :

   All point coordinates within an outline are stored in 32-bits fractional
   pixel values, using the 26.6 fixed float format (which uses 26 bits for
   the integer part, and 6 bits for the fractional ones). The following
   table gives some examples of real versus 26.6 coordinates :

   -----------------------------------------
     real        real coord     26.6 coord
    coord.         * 2^6
   ----------------------------------------- 
        0       0*64 =    0.0         0
      2.4     2.4*64 =  153.6       154
        3       3*64 =  192.0       192
     -1.7    -1.7*64 = -108.8      -109

   As you can see, conversions are relatively simple.

   In order to differentiate coordinates expressed in real or 26.6 systems,
   we'll use in the following lines some brackets, '[' and ']', for real
   coordinates, and simple parentheses, '(' and ')', for 26.6 ones so that

                      [ 1.0, 2.5 ] equals to ( 64, 160 )

                         [ 0, 0 ] equals to ( 0, 0 )

                      [ -2, 3 ] equals to ( -128, 192 )



  2. Orientation :

    The raster uses the so traditional convention of an X axis oriented
    from left to right, and of an Y one oriented from bottom to top.

         ^ Y
         |
         |
         |
        -*-----> X
         |

    You've probably already used it at school when doing math :-)
    
    Though the orientation of bitmap lines has an opposite direction on
    nearly all graphics systems, the former convention is the _right_ one
    when it comes to vector graphics. The reason is simply that when it
    comes to managing angles and vector cross-products/orientations in
    complex algorithms, a single convention, used in math as well as
    computing alike solves many headaches.
    
    And due to education, most people expect a 45 degrees angle to be in
    the top right quadrant, at coordinate (1,1).



  3. Pixels and the Grid :

    In a vector outline, a point is immaterial and has no size or width,
    just like in usual geometry. A "pixel" is an element of a computer
    image called a "map" ( like a bitmap or a pixmap ).

    The FreeType raster follows the convention defined by the TrueType
    regarding pixel placement :

    - the map can be seen as a 'grid' placed in the vector plane. The
      grid lines are set on integer real coordinates (i.e. on multiples
      of 64 in 26.6 ones).

      Each pixel is one "cell" of the grid, and can be 'lit' with any
      color. Hence, each pixel has a width and a height of [1.0] units,
      (i.e. 64 fixed float units..).

                     ^ Y
                     |
                     |                      The pixel grid with two
                     |                      points (not pixels !)
         +-----+-----+-----+-----+-----+    at coordinates [0,0] and
         |     |     |     |     |     |    [2,2].
         |     |     |     |     |     |
         |     |     |     |     |[2,2]|
         +-----+-----+-----+-----@-----+    The pixels are the grid's
         |     |     |11111|22222|     |    cells, and this example    
         |     |     |11111|22222|     |    show the four pixels enclosed
         |     |     |11111|22222|     |    within the rectangle delimited
         +-----+-----+-----+-----+-----+    by these two points.
         |     |     |33333|44444|     |
         |     |     |33333|44444|     |
         |     |     |33333|44444|     |
       --+-----+-----@-----+-----+-----+----> X
         |     |     |[0,0]|     |     |
         |     |     |     |     |     |    Note that the numbering of pixel
         |     |     |     |     |     |    isn't meaningful here, it's only
         +-----+-----+-----+-----+-----+    used to distinguish them.
         |     |     |     |     |     |
         |     |     |     |     |     |
         |     |     |     |     |     |
         +-----+-----+-----+-----+-----+
                     |
                     |

    - the "center" of each pixel is always located on a 'half-integer'
      coordinate, i.e. at -1.5, -0.5, 0.5, 1.5, etc...

    - when drawing a shape, the raster only "lits" a pixel when its
      center is placed _within_ the shape. This is important because
      an outline point may not be necessarily be on a grid line.

    - when a pixel center falls on the shape, the pixel is lit too.

      For example, the following graphics show the "lit" pixels
      corresponding to the rectangle enclosed by the points :

             [ -0.2, 0 ] and  [ 2.4, 2.7 ]


                     ^ Y                        As one can see, the newest
                     |                          pixels "1" and "2" are now
                     |                          lit, because their centers
                     |                          are located at coordinates :
         +-----+-----+-----+-----+--[2.4,2.7]                           
         |     |     |11111|22222| @   |         [0.5,2.5] and [1.5,2.5]
         |  .  |  .  |11.11|22.22|  .  |
         |     |     |11111|22222|     |        respectively.
         +-----+-----+-----+-----+-----+                              
         |     |     |33333|44444|     |        Note that pixel centers are
         |  .  |  .  |33.33|44.44|  .  |        represented with a dot on the
         |     |     |33333|44444|     |        graphics.                  
         +-----+-----+-----+-----+-----+                        
         |     |     |55555|66666|     |
         |  .  |  .  |55.55|66.66|  .  |
         |     |     |55555|66666|     |
       --+-----+----@+-----+-----+-----+----> X
         |     | [-0.2,0]  |     |     |
         |  .  |  .  |  .  |  .  |  .  |
         |     |     |     |     |     |        Note also that pixel numbering
         +-----+-----+-----+-----+-----+        is still meaningless there.
         |     |     |     |     |     |
         |  .  |  .  |  .  |  .  |  .  |
         |     |     |     |     |     |
         +-----+-----+-----+-----+-----+
                     |
                     |



  4. Drop-out control :

      Sometimes, a stroke is too thin to even contain a single pixel
      center. This results in "lost continuity" in the resulting bitmap,
      i.e. some unpleasant 'holes' or 'breaks' in the rendered shape, which
      are called a "drop-out".

      Because a glyph representation uses curves (bezier arcs), this
      case is not easily controlable during the 'hinting' of glyph outlines
      by the font driver, which means that the raster must be able to
      correct these 'artefacts'.

      This processing is called "drop-out control", and can be performed
      among several modes, defined by the TrueType spec, and which details
      do not belong to this paper. However, the important idea is that,
      in _some_ cases, a pixel may be lit, even if its center isn't part
      of the shape.

      This case is relatively rare, but is mentionned because it has
      consequences of the rendering of maps. More precisely, in the way
      an outline's sextent is computed (see below).


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

II. Bitmap and Pixmap descriptors :

  The Freetype raster only supports bitmaps and 8-bit pixmaps. In order
  to render an outline, a map descriptor must be sent to its rendering
  functions, along with a vectorial outline.


 1. Bitmap Properties :

   This section explains how to set up a bitmap descriptor, and how vector
   coordinates in the outline plane relate to pixel positions within the
   bitmap buffer.

   A bitmap's "raw data" is made of a simple bit buffer, where each bit
   corresponds to a monochrome pixel. For the sake of simplicity, the
   FreeType raster uses the following convention to store bitmaps in a
   buffer :


   -  the value 0 is used for "unlit" pixels, usually the "background"
      when rendering text. Hence 1 is used for "lit".


   -  lines are padded to 8-bits, i.e. bytes. A bitmap row thus takes
      an integral number of bytes in its buffer. No further alignement
      is required.

      ( some systems compress bitmaps by _not_ padding bit rows to
        byte boundaries. It is not possible to render in such a bitmap
        buffer with FreeType ).


   -  in a bitmap buffer byte, the left-most pixel is represented by
      the most significant bit (i.e. 0x80).
      
      The opposite convention is not supported by the FreeType raster,
      though it may eventually be implemented too if this ever comes useful..
      (ask the developers, for now, nobody did :-)


   -  increasing offsets within a row correspond to right-most positions
      in the bitmap (i.e. byte 1 contains the 8 bits/pixels that are
      located on the right of the 8 bits/pixels of byte 0).


   -  a bitmap can be oriented in two ways :


      o when increasing row addresses within the buffer correspond to
        lower vertical lines, the bitmap is said to go "down". This is,
        for example, the case of nearly all video RAMs.              


      o when increasing row addresses within the buffer correspond to
        higher vertical lines, the bitmap is said to go "up". This is
        the case, for example, of OS/2 bitmaps..


      The 'direction' of a bitmap is called is _flow_ to avoid any
      confusion.

      In all cases, the raster ALWAYS matches the vector coordinate (0,0)
      with the lower-left corner of the *lower-left* pixel in the bitmap.

      The following graphics illustrate these ideas :



         Y ^
           |                                  A "down-flow" bitmap.
           +--+--+--+--+--+--+--+--+          On the left is each row's
           |  |  |  |  |  |  |  |  |          number and its offset in
  0:  0    |  |  |  |  |  |  |  |  |          the bitmap buffer ( where
           +--+--+--+--+--+--+--+--+          "w" is the width, in bytes,
           |  |  |  |  |  |  |  |  |          of a single bitmap row ).
  1:  w    |  |  |  |  |  |  |  |  |
           +--+--+--+--+--+--+--+--+          Note that the origin is
           |  |  |  |  |  |  |  |  |          located at the lower-left,
  2:  2*w  |  |  |  |  |  |  |  |  |          i.e. near the left-most bit of
           +--+--+--+--+--+--+--+--+          the last bitmap row.
           |  |  |  |  |  |  |  |  |
  3:  3*w  |  |  |  |  |  |  |  |  |
          -@--+--+--+--+--+--+--+-----> X
           |[0,0]                          
      




         Y ^
           |                                  An "up-flow" bitmap.
           +--+--+--+--+--+--+--+--+          On the left is each row's
           |  |  |  |  |  |  |  |  |          number and its offset in
  3:  3*w  |  |  |  |  |  |  |  |  |          the bitmap buffer ( where
           +--+--+--+--+--+--+--+--+          "w" is the width, in bytes,
           |  |  |  |  |  |  |  |  |          of a single bitmap row ).
  2:  2*w  |  |  |  |  |  |  |  |  |
           +--+--+--+--+--+--+--+--+          Note that the origin is
           |  |  |  |  |  |  |  |  |          located at the lower-left,
  1:  w    |  |  |  |  |  |  |  |  |          i.e. near the first bit in
           +--+--+--+--+--+--+--+--+          the buffer.
           |  |  |  |  |  |  |  |  |
  0:  0    |  |  |  |  |  |  |  |  |          The first buffer bit           
          -@--+--+--+--+--+--+--+-----> X     corresponds to the rectangle
           |[0,0]                             [0,0]-[1,1] in the vector plane
      
      
  2. Bitmap descriptors :

   Now that you understand all these details, a bitmap can be described
   to the raster through a raster, which structure must be set up by
   client application, and which is :

      struct  TT_Raster_Map_
      {
        int    rows;    /* number of rows                    */
        int    cols;    /* number of columns (bytes) per row */
        int    width;   /* number of pixels per line         */
        int    flow;    /* bitmap orientation                */
    
        void*  bitmap;  /* bit/pixmap buffer                 */
        long   size;    /* bit/pixmap size in bytes          */
      };

   where the fields stand for :

     rows  ::  
        simply the number of rows within the bitmap buffer
  
  
     cols  ::  
        the number of columns, i.e. bytes per row within the buffer.
        It corresponds to the 'w' value used in the above graphics.
  
     width ::  
        the number of pixels (i.e. bits) per row in the buffer.
        The raster always clip its rendering to the bit width specified
        in this field, even if the "cols" fields corresponds to a larger
        width.
  
     flow  ::
        the bitmap flow. Uses the constants TT_Flow_Up and TT_Flow_Down
        exclusively for this field.
  
     bitmap ::
        a typeless pointer to the bit buffer.
  
     size ::
        the total size of the bit buffer in bytes. This is not used
        directly by the raster, so applications can use it.


   Note that the "cols" field should always be bigger than the value
   of "width" multiplied by 8. The raster always clip the generated
   bitmap to the 'width' first bits in a row.


   Note also that it is perfectly possible to create, for example,
   a Windows or X11 bitmap through a normal system-specific API, then
   create a TT_Raster_Map that describes it to the raster. It is thus
   be possible to draw directly into such surface.


   *******************************************************************
   ****             *******
   ***  IMPORTANT :  ******
   ****             *******
   ************************

   When rendering a bitmap, the raster always OR-es the shape on the
   target bitmap. It is thus possible to draw several shapes into a
   single surface which successive calls to the render functions.

   *******************************************************************


  1. Pixmap properties :

   The raster only supports 8-bit pixmaps, where a pixel is represented
   by a single byte. They must conform to the following rules :


   -  a 5-entries palette is used to generate an outline's pixmap
      in the buffer. They correspond to :

         palette[0]  -> background
         palette[1]  -> "light"
         palette[2]  -> "medium"
         palette[3]  -> "dark"
         palette[4]  -> foreground

      where the terms "light", "medium" and "dark" correspond to
      intermediate values between the first (background) and last
      (foreground) entry.

      The upcoming FreeType 2.0 will feature an additional anti-aliasing
      logic with a 17-entries palette.


   -  lines are padded to 32-bits, i.e. 4 bytes. A pixmap row thus takes
      a multiple of 4 bytes in its buffer.


   -  increasing offsets within a row correspond to right-most positions
      in the bitmap (i.e. byte/pixel 1 is to the right of byte/pixel 0)


   -  a pixmap can be oriented in two ways, following the same rules
      than a bitmap regarding its flow.


   - IMPORTANT : *********************************************************

       in order to improve performance when rendering large outlines
       with anti-aliasing, the raster draws pixels in runs of 4-bytes,
       ONLY when at least one of their "colour" isn't 0 (background).

       This means that you should ALWAYS CLEAR the pixmap buffer before
       calling the rendering function, you may otherwise experience ugly
       artefacts, which are "rest" of the previous render !

       In general, it is not possible to do colour compositing with the
       FreeType raster ( compositing is when you want to superpose a
       transparent coloured layer on top of an image ). This is mainly
       due to the fact that :

          - there are too many pixel formats to support

          - there is not a single portable way to do it anyway

          - it really is a graphics processing question, not one that
            should be solved by a text rendering engine..

     *********************************************************************


  2. Pixmap descriptors :


    Pixmaps use the same descriptor structure than bitmaps, with a
    few difference in interpretation :

    - the "cols" field is used to indicate the number of _bytes_ in
      a pixmap row. It must thus be a multiple of 4 !

    - the raster clips the outline to the first "width" pixels/width
      within each buffer row.


    As usual, it should be possible to use a system-specific pixmap
    and render directly into it, as long as you set-up a descriptor for
    it..

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

III. Rendering an outline :

  Now that you understand how the raster sees the target bitmaps and
  pixmaps it renders to, this section will explain how the rendering
  eventually happen.


  1. Outline coordinates and extents :

    Let's first consider the case where we're rendering text directly
    into a huge single bitmap. To do that, we simply translate each
    glyph outline before calling the raster. Key ideas are that :


    - vectorial coordinates [0,0] are mapped to the lower left "corner"
      (in the grid) of the lower left pixel in the bitmap (whatever its
      flow is).

    - when the glyph loader returns an outline, the latter is placed
      so that the coordinate [0,0] correspond to the current cursor
      position.

    This means that :

    - if we use our own cursor (cx,cy) within the bitmap during text
      rendering, we must translate the outline to its position before
      rendering it; with a call like :
      
                TT_Translate_Outline( outline, cx, cy ).

      (and the cursor position must be incremented after rendering
       each glyph).


    - before translation (i.e. when it is returned by the glyph loader),
      the glyph outline doesn't necessarily lies on any of the coordinate
      axis, nor is it limited to the first quadrant (i.e. x>0 and y>0).

      Its extent can be computed with the function TT_Get_Outline_BBox,
      which returns the minimum and maximum values of its X and Y point
      coordinates (in 26.6 format, of course).


  2. Computing an outline's dimensions in pixels :

    In many cases, however, it is much better to render individual glyph
    bitmaps, then cache them with appropriate metrics in order to much
    more quickly render text at a given point size.

    To be able to render the smallest possible bitmap, the exact outline's
    extent dimensions in pixel are required. This operation looks like :


      - get the outline's bounding box in vector coordinates :

          simply call the TT_Get_Outline_BBox function, which will
          return the values of xMin, yMin, xMax and yMax in vector
          (i.e. fractional) coordinates.


      - grid-fit the bouding box :

          because of the way pixels are lit in the bitmaps relative to
          the position of their "centers" within the shape (see section I.),
          it is necessary to align the values of xMin, xMax, yMin and yMax
          to the pixel grid, in order to compute the width and height
          of the resulting bitmap. This can be done with :

             xMin = FLOOR  ( xMin );   with FLOOR(x)   == (x & -64)
             xMax = CEILING( xMax );        CEILING(x) == ((x+63) & -64)
             yMin = FLOOR  ( yMin );
             yMax = CEILING( yMax );

          the extents in pixels can then be computed simply as :

             pixel_width  = (xMax - xMin)/64;
             pixel_height = (yMax - yMin)/64;


          Note that because of drop-out control, and because the BBox
          computed currently includes all bezier control points from the
          outline, the bitmap may be slightly larger than necessary in
          some cases.

          Some improvements are planned for FreeType 2.0; for now, you
          should consider that finding the "exact" bitmap bounding box
          requires to scan the "borders" by hand to detect null columns
          or rows. However, the values are right in most cases.

          NOTE: It seems that in some *rare* cases, which relate to
                weird drop-out control situations, the above dimensions
                are not enough to store all bits from the outline (there
                are one of more bits "cut" on the edge).

                This being hard to study (it only appears in very
                poorly hinted fonts), solving this case is left for
                FreeType 2.0.

      - create/setup a bitmap with the computed dimensions.
        DON'T FORGET TO CLEAR ITS BUFFER TOO !!

      - translate the outline to stick it within the bitmap space.
        This is done easily by translating it by (-xMin,-yMin), where
        you should ALWAYS USE THE GRID-FITTED VALUES computed above
        for xMin and yMin.

                TT_Translate_Outline( outline, -xMin, -yMin );


        ****************************************************************
        ***** IMPORTANT ******                                         *
        **********************                                         *
        *                                                              *
        *  For technical reasons, you should never translate a hinted  *
        *  outline by a non-integer vector (i.e. one which coordinates *
        *  aren't multiples of 64 !). This would CERTAINLY completely  *
        *  RUIN the delicate HINTING of the glyph, and will result     *
        *  probably in pure GARBAGE at small point sizes..             *
        *                                                              *
        *  Of course, if you're not interested in hinting, like when   *
        *  displaying rotated text, you can ignore this rule and       *
        *  translate to any position freely..                          *
        *                                                              *
        ****************************************************************


      - render the bitmap (or pixmap).

        DON'T FORGET TO STORE THE GRID-FITTED xMin and yMin WITH THE
        BITMAP ! This will allow you later to place it correctly relative
        to your cursor position..


     Here's some example code :

       {
           ... load the glyph

           TT_Outline     outline;
           TT_BBox        bbox;
           TT_Raster_Map  bitmap;

           /* get the outline */
           TT_Get_Glyph_Outline( glyph, &outline );

           /* compute its extent */
           TT_Get_Outline_BBox( &outline, &bbox );

           /* Grid-fit it */
           bbox.xMin &= -64;  bbox.xMax = ( bbox.xMax + 63 ) & -64;
           bbox.yMin &= -64;  bbox.yMax = ( bbox.yMax + 63 ) & -64;

           /* compute pixel dimensions */
           width  = (bbox.xMax-bbox.xMin)/64;
           height = (bbox.yMax-bbox.yMin)/64;

           /* set up bitmap */
           bitmap.rows   = height;
           bitmap.width  = width;
           bitmap.cols   = (width+7) & -8;
           bitmap.size   = bitmap.rows * bitmap.cols;
           bitmap.buffer = malloc( bitmap.size );
           if (!bitmap.buffer)
             return error_memory....

           /* clear the bitmap buffer !! */
           memset( bitmap.buffer, 0, bitmap.size );

           /* translate outline */
           TT_Translate_Outline( &outline, -bbox.xMin, -bbox.yMin );

           /* render it within the bitmap */
           TT_Get_Outline_Bitmap( engine, &outline, &bitmap );
            
           /* we're done, don't forget to save bbox.xMin and bbox.yMin  */
           /* to adjust the bitmap position when rendering text with it */
           ....
         }




   3. The case of transformed/rotated glyphs :

        You may want to apply a transform other than a translation to your
        glyph outlines before rendering them. For example, a simple slant
        to synthetise italics, or a slight rotation.

        In all cases, it is possible to render individual glyph bitmaps.
        Just make sure to follow the same process, AFTER you have transformed
        you outline !!

        DON'T FORGET THAT YOU NEED TO RE-COMPUTE THE BBOX TO GET THE CORRECT
        PIXEL DIMENSIONS AFTER A TRANSFORM..


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

IV. Anti-aliasing palette and other concerns :

  When rendering pixmaps, with the TT_Get_Outline_Pixmap or
  TT_Get_Glyph_Pixmap functions, the raster uses a 5-entries palette
  of 8-bit "colors".

  By default, this palette is set to ( 0, 1, 2, 3, 4 ), but one can
  change it to suit its needs with TT_Set_Raster_Palette.

  While in bitmap mode, it simply or-es the pixel values to the target
  bitmap that has been passed to TT_Get_Outline_Bitmap, this is not the
  case in pixmap mode.

  In this case, it simply writes directly the palette entries corresponding
  to the "color" of the "lit" pixels it have computed. This means that it
  is NOT POSSIBLE to render text in a single pixmap with multiple calls
  to TT_Get_Outline_Pixmaps within the same target !!

  The reason is the "gray" pixels of two distinct outlines are not 'added'
  when they overlap (the operation called 'compositing'), as it could be
  expected by applications.

           The following graphics show this effect when rendering
           two overlapping anti-aliased shapes :


                ***                              ***
               .**                              .**
               **        **.               **.  **
              .*.         .*..              .*..*.
             .*.    +        .*.   =    --->  ..*.
            .*.                **      |     .*. **
            **                         |     **
           **.                         |    **.
          ***                          |   ***
                                       |

                                     missing black pixel after second
                                     rendering..



  there is no simple way to perform a composition within the raster. This
  would not be portable, moreover it would be extremely slow if it's too
  general. This operation is thus left to client applications, which
  can use their own system-specific API for transparently blitting the
  glyph pixmaps into a surface to form text.

  NOTE:

  If your system doesn't support transparent/alpha blits, you can still
  have a look at the source file "freetype/test/display.c". It uses a
  large pixmap, with a special palette trick to render all text quickly,
  then convert all of it to "real" colors for display..


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

Conclusion :

   We've seen how the FreeType raster sees bitmaps through descriptors,
   as well as the mapping existing between the vector coordinate space
   and the pixel position space.

   You should now be able to render outlines into bitmaps and pixmaps
   while applying transforms as translation, slanting or rotation.
   Don't forget a few rules, however :


       - always clear the bitmap/pixmap buffer before rendering
         (unless you want to render several glyphs in a single _bitmap_,
          which won't work on a pixmap).

       - a pixmap "cols" field, i.e. the size in bytes of each rows,
         must be a multiple of 4.

       - never translate a hinted outline by a non-integer vector
         if you want to preserve the hints (i.e. the vector's coordinates
         must be multiples of 64).

       - finally, don't expect the raster to composite transparent "grays"
         for you in a single target pixmap through multiple calls.


