/***************************************************************************//*                                                                         *//*  ftgrays.c                                                              *//*                                                                         *//*    A new `perfect' anti-aliasing renderer (body).                       *//*                                                                         *//*  Copyright 2000-2001, 2002, 2003, 2005, 2006 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.                                        *//*                                                                         *//***************************************************************************/  /*************************************************************************/  /*                                                                       */  /* This file can be compiled without the rest of the FreeType engine, by */  /* defining the _STANDALONE_ macro when compiling it.  You also need to  */  /* put the files `ftgrays.h' and `ftimage.h' into the current            */  /* compilation directory.  Typically, you could do something like        */  /*                                                                       */  /* - copy `src/smooth/ftgrays.c' (this file) to your current directory   */  /*                                                                       */  /* - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the */  /*   same directory                                                      */  /*                                                                       */  /* - compile `ftgrays' with the _STANDALONE_ macro defined, as in        */  /*                                                                       */  /*     cc -c -D_STANDALONE_ ftgrays.c                                    */  /*                                                                       */  /* The renderer can be initialized with a call to                        */  /* `ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated  */  /* with a call to `ft_gray_raster.raster_render'.                        */  /*                                                                       */  /* See the comments and documentation in the file `ftimage.h' for more   */  /* details on how the raster works.                                      */  /*                                                                       */  /*************************************************************************/  /*************************************************************************/  /*                                                                       */  /* This is a new anti-aliasing scan-converter for FreeType 2.  The       */  /* algorithm used here is _very_ different from the one in the standard  */  /* `ftraster' module.  Actually, `ftgrays' computes the _exact_          */  /* coverage of the outline on each pixel cell.                           */  /*                                                                       */  /* It is based on ideas that I initially found in Raph Levien's          */  /* excellent LibArt graphics library (see http://www.levien.com/libart   */  /* for more information, though the web pages do not tell anything       */  /* about the renderer; you'll have to dive into the source code to       */  /* understand how it works).                                             */  /*                                                                       */  /* Note, however, that this is a _very_ different implementation         */  /* compared to Raph's.  Coverage information is stored in a very         */  /* different way, and I don't use sorted vector paths.  Also, it doesn't */  /* use floating point values.                                            */  /*                                                                       */  /* This renderer has the following advantages:                           */  /*                                                                       */  /* - It doesn't need an intermediate bitmap.  Instead, one can supply a  */  /*   callback function that will be called by the renderer to draw gray  */  /*   spans on any target surface.  You can thus do direct composition on */  /*   any kind of bitmap, provided that you give the renderer the right   */  /*   callback.                                                           */  /*                                                                       */  /* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on   */  /*   each pixel cell.                                                    */  /*                                                                       */  /* - It performs a single pass on the outline (the `standard' FT2        */  /*   renderer makes two passes).                                         */  /*                                                                       */  /* - It can easily be modified to render to _any_ number of gray levels  */  /*   cheaply.                                                            */  /*                                                                       */  /* - For small (< 20) pixel sizes, it is faster than the standard        */  /*   renderer.                                                           */  /*                                                                       */  /*************************************************************************//* experimental support for gamma correction within the rasterizer */#define xxxGRAYS_USE_GAMMA  /*************************************************************************/  /*                                                                       */  /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */  /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */  /* messages during execution.                                            */  /*                                                                       */#undef  FT_COMPONENT#define FT_COMPONENT  trace_smooth#define ErrRaster_MemoryOverflow   -4#ifdef _STANDALONE_#include <string.h>             /* for ft_memcpy() */#include <setjmp.h>#include <limits.h>#define FT_UINT_MAX  UINT_MAX#define ft_memset   memset#define ft_setjmp   setjmp#define ft_longjmp  longjmp#define ft_jmp_buf  jmp_buf#define ErrRaster_Invalid_Mode     -2#define ErrRaster_Invalid_Outline  -1#define FT_BEGIN_HEADER#define FT_END_HEADER#include "ftimage.h"#include "ftgrays.h"  /* This macro is used to indicate that a function parameter is unused. */  /* Its purpose is simply to reduce compiler warnings.  Note also that  */  /* simply defining it as `(void)x' doesn't avoid warnings with certain */  /* ANSI compilers (e.g. LCC).                                          */#define FT_UNUSED( x )  (x) = (x)  /* Disable the tracing mechanism for simplicity -- developers can      */  /* activate it easily by redefining these two macros.                  */#ifndef FT_ERROR#define FT_ERROR( x )  do ; while ( 0 )     /* nothing */#endif#ifndef FT_TRACE#define FT_TRACE( x )  do ; while ( 0 )     /* nothing */#endif#else /* _STANDALONE_ */#include <ft2build.h>#include "ftgrays.h"#include FT_INTERNAL_OBJECTS_H#include FT_INTERNAL_DEBUG_H#include FT_OUTLINE_H#include "ftsmerrs.h"#define ErrRaster_Invalid_Mode     Smooth_Err_Cannot_Render_Glyph#define ErrRaster_Invalid_Outline  Smooth_Err_Invalid_Outline#endif /* _STANDALONE_ */#ifndef FT_MEM_SET#define FT_MEM_SET( d, s, c )  ft_memset( d, s, c )#endif#ifndef FT_MEM_ZERO#define FT_MEM_ZERO( dest, count )  FT_MEM_SET( dest, 0, count )#endif  /* define this to dump debugging information */#define xxxDEBUG_GRAYS  /* as usual, for the speed hungry :-) */#ifndef FT_STATIC_RASTER#define RAS_ARG   PRaster  raster#define RAS_ARG_  PRaster  raster,#define RAS_VAR   raster#define RAS_VAR_  raster,#define ras       (*raster)#else /* FT_STATIC_RASTER */#define RAS_ARG   /* empty */#define RAS_ARG_  /* empty */#define RAS_VAR   /* empty */#define RAS_VAR_  /* empty */  static TRaster  ras;#endif /* FT_STATIC_RASTER */  /* must be at least 6 bits! */#define PIXEL_BITS  8#define ONE_PIXEL       ( 1L << PIXEL_BITS )#define PIXEL_MASK      ( -1L << PIXEL_BITS )#define TRUNC( x )      ( (TCoord)((x) >> PIXEL_BITS) )#define SUBPIXELS( x )  ( (TPos)(x) << PIXEL_BITS )#define FLOOR( x )      ( (x) & -ONE_PIXEL )#define CEILING( x )    ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL )#define ROUND( x )      ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL )#if PIXEL_BITS >= 6#define UPSCALE( x )    ( (x) << ( PIXEL_BITS - 6 ) )#define DOWNSCALE( x )  ( (x) >> ( PIXEL_BITS - 6 ) )#else#define UPSCALE( x )    ( (x) >> ( 6 - PIXEL_BITS ) )#define DOWNSCALE( x )  ( (x) << ( 6 - PIXEL_BITS ) )#endif  /* Define this if you want to use a more compact storage scheme.  This   */  /* increases the number of cells available in the render pool but slows  */  /* down the rendering a bit.  It is useful if you have a really tiny     */  /* render pool.                                                          */#undef GRAYS_COMPACT  /*************************************************************************/  /*                                                                       */  /*   TYPE DEFINITIONS                                                    */  /*                                                                       */  /* don't change the following types to FT_Int or FT_Pos, since we might */  /* need to define them to "float" or "double" when experimenting with   */  /* new algorithms                                                       */  typedef int   TCoord;   /* integer scanline/pixel coordinate */  typedef long  TPos;     /* sub-pixel coordinate              */  /* determine the type used to store cell areas.  This normally takes at */  /* least PIXEL_BITS*2 + 1 bits.  On 16-bit systems, we need to use      */  /* `long' instead of `int', otherwise bad things happen                 */#if PIXEL_BITS <= 7  typedef int   TArea;#else /* PIXEL_BITS >= 8 */  /* approximately determine the size of integers using an ANSI-C header */#if FT_UINT_MAX == 0xFFFFU  typedef long  TArea;#else  typedef int  TArea;#endif#endif /* PIXEL_BITS >= 8 */  /* maximal number of gray spans in a call to the span callback */#define FT_MAX_GRAY_SPANS  32#ifdef GRAYS_COMPACT  typedef struct  TCell_  {    short  x     : 14;    short  y     : 14;    int    cover : PIXEL_BITS + 2;    int    area  : PIXEL_BITS * 2 + 2;  } TCell, *PCell;#else /* GRAYS_COMPACT */  typedef struct  TCell_  {    TCoord  x;    TCoord  y;    int     cover;    TArea   area;  } TCell, *PCell;#endif /* GRAYS_COMPACT */  typedef struct  TRaster_  {    PCell   cells;    int     max_cells;    int     num_cells;    TPos    min_ex, max_ex;    TPos    min_ey, max_ey;    TArea   area;    int     cover;    int     invalid;    TCoord  ex, ey;    TCoord  cx, cy;    TPos    x,  y;    TPos    last_ey;    FT_Vector   bez_stack[32 * 3 + 1];    int         lev_stack[32];    FT_Outline  outline;    FT_Bitmap   target;    FT_BBox     clip_box;    FT_Span     gray_spans[FT_MAX_GRAY_SPANS];    int         num_gray_spans;    FT_Raster_Span_Func  render_span;    void*                render_span_data;    int                  span_y;    int  band_size;    int  band_shoot;    int  conic_level;    int  cubic_level;    void*       memory;    ft_jmp_buf  jump_buffer;#ifdef GRAYS_USE_GAMMA    unsigned char  gamma[257];#endif  } TRaster, *PRaster;  /*************************************************************************/  /*                                                                       */  /* Initialize the cells table.                                           */  /*                                                                       */  static void  gray_init_cells( RAS_ARG_ void*  buffer,                   long            byte_size )  {    ras.cells     = (PCell)buffer;    ras.max_cells = (int)( byte_size / sizeof ( TCell ) );    ras.num_cells = 0;    ras.area      = 0;    ras.cover     = 0;    ras.invalid   = 1;  }  /*************************************************************************/  /*                                                                       */  /* Compute the outline bounding box.                                     */  /*                                                                       */  static void  gray_compute_cbox( RAS_ARG )  {    FT_Outline*  outline = &ras.outline;    FT_Vector*   vec     = outline->points;    FT_Vector*   limit   = vec + outline->n_points;    if ( outline->n_points <= 0 )    {      ras.min_ex = ras.max_ex = 0;      ras.min_ey = ras.max_ey = 0;      return;    }    ras.min_ex = ras.max_ex = vec->x;    ras.min_ey = ras.max_ey = vec->y;    vec++;    for ( ; vec < limit; vec++ )    {      TPos  x = vec->x;      TPos  y = vec->y;      if ( x < ras.min_ex ) ras.min_ex = x;      if ( x > ras.max_ex ) ras.max_ex = x;      if ( y < ras.min_ey ) ras.min_ey = y;      if ( y > ras.max_ey ) ras.max_ey = y;    }    /* truncate the bounding box to integer pixels */    ras.min_ex = ras.min_ex >> 6;    ras.min_ey = ras.min_ey >> 6;    ras.max_ex = ( ras.max_ex + 63 ) >> 6;    ras.max_ey = ( ras.max_ey + 63 ) >> 6;  }  /*************************************************************************/  /*                                                                       */  /* Record the current cell in the table.                                 */  /*                                                                       */  static void  gray_record_cell( RAS_ARG )  {    PCell  cell;    if ( !ras.invalid && ( ras.area | ras.cover ) )    {      if ( ras.num_cells >= ras.max_cells )        ft_longjmp( ras.jump_buffer, 1 );      cell        = ras.cells + ras.num_cells++;      cell->x     = (TCoord)(ras.ex - ras.min_ex);      cell->y     = (TCoord)(ras.ey - ras.min_ey);      cell->area  = ras.area;      cell->cover = ras.cover;    }  }  /*************************************************************************/  /*                                                                       */  /* Set the current cell to a new position.                               */  /*                                                                       */  static void  gray_set_cell( RAS_ARG_ TCoord  ex,                          TCoord  ey )  {    int  invalid, record, clean;    /* Move the cell pointer to a new position.  We set the `invalid'      */    /* flag to indicate that the cell isn't part of those we're interested */    /* in during the render phase.  This means that:                       */    /*                                                                     */    /* . the new vertical position must be within min_ey..max_ey-1.        */    /* . the new horizontal position must be strictly less than max_ex     */    /*                                                                     */    /* Note that if a cell is to the left of the clipping region, it is    */    /* actually set to the (min_ex-1) horizontal position.                 */    record  = 0;    clean   = 1;    invalid = ( ey < ras.min_ey || ey >= ras.max_ey || ex >= ras.max_ex );    if ( !invalid )    {      /* All cells that are on the left of the clipping region go to the */      /* min_ex - 1 horizontal position.                                 */      if ( ex < ras.min_ex )        ex = (TCoord)(ras.min_ex - 1);      /* if our position is new, then record the previous cell */      if ( ex != ras.ex || ey != ras.ey )        record = 1;      else        clean = ras.invalid;  /* do not clean if we didn't move from */                              /* a valid cell                        */    }    /* record the previous cell if needed (i.e., if we changed the cell */    /* position, or changed the `invalid' flag)                         */    if ( ras.invalid != invalid || record )      gray_record_cell( RAS_VAR );    if ( clean )    {      ras.area  = 0;      ras.cover = 0;    }    ras.invalid = invalid;    ras.ex      = ex;    ras.ey      = ey;  }  /*************************************************************************/  /*                                                                       */  /* Start a new contour at a given cell.                                  */  /*                                                                       */  static void  gray_start_cell( RAS_ARG_  TCoord  ex,                             TCoord  ey )  {    if ( ex < ras.min_ex )      ex = (TCoord)(ras.min_ex - 1);    ras.area    = 0;    ras.cover   = 0;    ras.ex      = ex;    ras.ey      = ey;    ras.last_ey = SUBPIXELS( ey );    ras.invalid = 0;    gray_set_cell( RAS_VAR_ ex, ey );  }  /*************************************************************************/  /*                                                                       */  /* Render a scanline as one or more cells.                               */  /*                                                                       */  static void  gray_render_scanline( RAS_ARG_  TCoord  ey,                                  TPos    x1,                                  TCoord  y1,                                  TPos    x2,                                  TCoord  y2 )  {    TCoord  ex1, ex2, fx1, fx2, delta;    long    p, first, dx;    int     incr, lift, mod, rem;    dx = x2 - x1;    ex1 = TRUNC( x1 ); /* if (ex1 >= ras.max_ex) ex1 = ras.max_ex-1; */    ex2 = TRUNC( x2 ); /* if (ex2 >= ras.max_ex) ex2 = ras.max_ex-1; */    fx1 = (TCoord)( x1 - SUBPIXELS( ex1 ) );    fx2 = (TCoord)( x2 - SUBPIXELS( ex2 ) );    /* trivial case.  Happens often */    if ( y1 == y2 )    {      gray_set_cell( RAS_VAR_ ex2, ey );      return;    }    /* everything is located in a single cell.  That is easy! */    /*                                                        */    if ( ex1 == ex2 )    {      delta      = y2 - y1;      ras.area  += (TArea)( fx1 + fx2 ) * delta;      ras.cover += delta;      return;    }    /* ok, we'll have to render a run of adjacent cells on the same */    /* scanline...                                                  */    /*                                                              */