1 /***************************************************************************/

     2 /*                                                                         */

     3 /*  ftgrays.c                                                              */

     4 /*                                                                         */

     5 /*    A new `perfect' anti-aliasing renderer (body).                       */

     6 /*                                                                         */

     7 /*  Copyright 2000-2003, 2005-2011 by                                      */

     8 /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */

     9 /*                                                                         */

    10 /*  This file is part of the FreeType project, and may only be used,       */

    11 /*  modified, and distributed under the terms of the FreeType project      */

    12 /*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */

    13 /*  this file you indicate that you have read the license and              */

    14 /*  understand and accept it fully.                                        */

    15 /*                                                                         */

    16 /***************************************************************************/

    17 

    18   /*************************************************************************/

    19   /*                                                                       */

    20   /* This file can be compiled without the rest of the FreeType engine, by */

    21   /* defining the _STANDALONE_ macro when compiling it.  You also need to  */

    22   /* put the files `ftgrays.h' and `ftimage.h' into the current            */

    23   /* compilation directory.  Typically, you could do something like        */

    24   /*                                                                       */

    25   /* - copy `src/smooth/ftgrays.c' (this file) to your current directory   */

    26   /*                                                                       */

    27   /* - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the */

    28   /*   same directory                                                      */

    29   /*                                                                       */

    30   /* - compile `ftgrays' with the _STANDALONE_ macro defined, as in        */

    31   /*                                                                       */

    32   /*     cc -c -D_STANDALONE_ ftgrays.c                                    */

    33   /*                                                                       */

    34   /* The renderer can be initialized with a call to                        */

    35   /* `ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated  */

    36   /* with a call to `ft_gray_raster.raster_render'.                        */

    37   /*                                                                       */

    38   /* See the comments and documentation in the file `ftimage.h' for more   */

    39   /* details on how the raster works.                                      */

    40   /*                                                                       */

    41   /*************************************************************************/

    42 

    43   /*************************************************************************/

    44   /*                                                                       */

    45   /* This is a new anti-aliasing scan-converter for FreeType 2.  The       */

    46   /* algorithm used here is _very_ different from the one in the standard  */

    47   /* `ftraster' module.  Actually, `ftgrays' computes the _exact_          */

    48   /* coverage of the outline on each pixel cell.                           */

    49   /*                                                                       */

    50   /* It is based on ideas that I initially found in Raph Levien's          */

    51   /* excellent LibArt graphics library (see http://www.levien.com/libart   */

    52   /* for more information, though the web pages do not tell anything       */

    53   /* about the renderer; you'll have to dive into the source code to       */

    54   /* understand how it works).                                             */

    55   /*                                                                       */

    56   /* Note, however, that this is a _very_ different implementation         */

    57   /* compared to Raph's.  Coverage information is stored in a very         */

    58   /* different way, and I don't use sorted vector paths.  Also, it doesn't */

    59   /* use floating point values.                                            */

    60   /*                                                                       */

    61   /* This renderer has the following advantages:                           */

    62   /*                                                                       */

    63   /* - It doesn't need an intermediate bitmap.  Instead, one can supply a  */

    64   /*   callback function that will be called by the renderer to draw gray  */

    65   /*   spans on any target surface.  You can thus do direct composition on */

    66   /*   any kind of bitmap, provided that you give the renderer the right   */

    67   /*   callback.                                                           */

    68   /*                                                                       */

    69   /* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on   */

    70   /*   each pixel cell.                                                    */

    71   /*                                                                       */

    72   /* - It performs a single pass on the outline (the `standard' FT2        */

    73   /*   renderer makes two passes).                                         */

    74   /*                                                                       */

    75   /* - It can easily be modified to render to _any_ number of gray levels  */

    76   /*   cheaply.                                                            */

    77   /*                                                                       */

    78   /* - For small (< 20) pixel sizes, it is faster than the standard        */

    79   /*   renderer.                                                           */

    80   /*                                                                       */

    81   /*************************************************************************/

    82 

    83 

    84   /*************************************************************************/

    85   /*                                                                       */

    86   /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */

    87   /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */

    88   /* messages during execution.                                            */

    89   /*                                                                       */

    90 #undef  FT_COMPONENT

    91 #define FT_COMPONENT  trace_smooth

    92 

    93 

    94 #ifdef _STANDALONE_

    95 

    96 

    97   /* define this to dump debugging information */

    98 /* #define FT_DEBUG_LEVEL_TRACE */

    99 

   100 

   101 #ifdef FT_DEBUG_LEVEL_TRACE

   102 #include <stdio.h>

   103 #include <stdarg.h>

   104 #endif

   105 

   106 #include <stddef.h>

   107 #include <string.h>

   108 #include <setjmp.h>

   109 #include <limits.h>

   110 #define FT_UINT_MAX  UINT_MAX

   111 #define FT_INT_MAX   INT_MAX

   112 

   113 #define ft_memset   memset

   114 

   115 #define ft_setjmp   setjmp

   116 #define ft_longjmp  longjmp

   117 #define ft_jmp_buf  jmp_buf

   118 

   119 typedef ptrdiff_t  FT_PtrDist;

   120 

   121 

   122 #define ErrRaster_Invalid_Mode      -2

   123 #define ErrRaster_Invalid_Outline   -1

   124 #define ErrRaster_Invalid_Argument  -3

   125 #define ErrRaster_Memory_Overflow   -4

   126 

   127 #define FT_BEGIN_HEADER

   128 #define FT_END_HEADER

   129 

   130 #include "ftimage.h"

   131 #include "ftgrays.h"

   132 

   133 

   134   /* This macro is used to indicate that a function parameter is unused. */

   135   /* Its purpose is simply to reduce compiler warnings.  Note also that  */

   136   /* simply defining it as `(void)x' doesn't avoid warnings with certain */

   137   /* ANSI compilers (e.g. LCC).                                          */

   138 #define FT_UNUSED( x )  (x) = (x)

   139 

   140 

   141   /* we only use level 5 & 7 tracing messages; cf. ftdebug.h */

   142 

   143 #ifdef FT_DEBUG_LEVEL_TRACE

   144 

   145   void

   146   FT_Message( const char*  fmt,

   147               ... )

   148   {

   149     va_list  ap;

   150 

   151 

   152     va_start( ap, fmt );

   153     vfprintf( stderr, fmt, ap );

   154     va_end( ap );

   155   }

   156 

   157   /* we don't handle tracing levels in stand-alone mode; */

   158 #ifndef FT_TRACE5

   159 #define FT_TRACE5( varformat )  FT_Message varformat

   160 #endif

   161 #ifndef FT_TRACE7

   162 #define FT_TRACE7( varformat )  FT_Message varformat

   163 #endif

   164 #ifndef FT_ERROR

   165 #define FT_ERROR( varformat )   FT_Message varformat

   166 #endif

   167 

   168 #else /* !FT_DEBUG_LEVEL_TRACE */

   169 

   170 #define FT_TRACE5( x )  do { } while ( 0 )     /* nothing */

   171 #define FT_TRACE7( x )  do { } while ( 0 )     /* nothing */

   172 #define FT_ERROR( x )   do { } while ( 0 )     /* nothing */

   173 

   174 #endif /* !FT_DEBUG_LEVEL_TRACE */

   175 

   176 

   177 #define FT_DEFINE_OUTLINE_FUNCS( class_,               \

   178                                  move_to_, line_to_,   \

   179                                  conic_to_, cubic_to_, \

   180                                  shift_, delta_ )      \

   181           static const FT_Outline_Funcs class_ =       \

   182           {                                            \

   183             move_to_,                                  \

   184             line_to_,                                  \

   185             conic_to_,                                 \

   186             cubic_to_,                                 \

   187             shift_,                                    \

   188             delta_                                     \

   189          };

   190 

   191 #define FT_DEFINE_RASTER_FUNCS( class_, glyph_format_,            \

   192                                 raster_new_, raster_reset_,       \

   193                                 raster_set_mode_, raster_render_, \

   194                                 raster_done_ )                    \

   195           const FT_Raster_Funcs class_ =                          \

   196           {                                                       \

   197             glyph_format_,                                        \

   198             raster_new_,                                          \

   199             raster_reset_,                                        \

   200             raster_set_mode_,                                     \

   201             raster_render_,                                       \

   202             raster_done_                                          \

   203          };

   204 

   205 #else /* !_STANDALONE_ */

   206 

   207 

   208 #include <ft2build.h>

   209 #include "ftgrays.h"

   210 #include FT_INTERNAL_OBJECTS_H

   211 #include FT_INTERNAL_DEBUG_H

   212 #include FT_OUTLINE_H

   213 

   214 #include "ftsmerrs.h"

   215 

   216 #include "ftspic.h"

   217 

   218 #define ErrRaster_Invalid_Mode      Smooth_Err_Cannot_Render_Glyph

   219 #define ErrRaster_Invalid_Outline   Smooth_Err_Invalid_Outline

   220 #define ErrRaster_Memory_Overflow   Smooth_Err_Out_Of_Memory

   221 #define ErrRaster_Invalid_Argument  Smooth_Err_Invalid_Argument

   222 

   223 #endif /* !_STANDALONE_ */

   224 

   225 #ifndef FT_MEM_SET

   226 #define FT_MEM_SET( d, s, c )  ft_memset( d, s, c )

   227 #endif

   228 

   229 #ifndef FT_MEM_ZERO

   230 #define FT_MEM_ZERO( dest, count )  FT_MEM_SET( dest, 0, count )

   231 #endif

   232 

   233   /* as usual, for the speed hungry :-) */

   234 

   235 #ifndef FT_STATIC_RASTER

   236 

   237 #define RAS_ARG   PWorker  worker

   238 #define RAS_ARG_  PWorker  worker,

   239 

   240 #define RAS_VAR   worker

   241 #define RAS_VAR_  worker,

   242 

   243 #else /* FT_STATIC_RASTER */

   244 

   245 #define RAS_ARG   /* empty */

   246 #define RAS_ARG_  /* empty */

   247 #define RAS_VAR   /* empty */

   248 #define RAS_VAR_  /* empty */

   249 

   250 #endif /* FT_STATIC_RASTER */

   251 

   252 

   253   /* must be at least 6 bits! */

   254 #define PIXEL_BITS  8

   255 

   256 #define ONE_PIXEL       ( 1L << PIXEL_BITS )

   257 #define PIXEL_MASK      ( -1L << PIXEL_BITS )

   258 #define TRUNC( x )      ( (TCoord)( (x) >> PIXEL_BITS ) )

   259 #define SUBPIXELS( x )  ( (TPos)(x) << PIXEL_BITS )

   260 #define FLOOR( x )      ( (x) & -ONE_PIXEL )

   261 #define CEILING( x )    ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL )

   262 #define ROUND( x )      ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL )

   263 

   264 #if PIXEL_BITS >= 6

   265 #define UPSCALE( x )    ( (x) << ( PIXEL_BITS - 6 ) )

   266 #define DOWNSCALE( x )  ( (x) >> ( PIXEL_BITS - 6 ) )

   267 #else

   268 #define UPSCALE( x )    ( (x) >> ( 6 - PIXEL_BITS ) )

   269 #define DOWNSCALE( x )  ( (x) << ( 6 - PIXEL_BITS ) )

   270 #endif

   271 

   272 

   273   /*************************************************************************/

   274   /*                                                                       */

   275   /*   TYPE DEFINITIONS                                                    */

   276   /*                                                                       */

   277 

   278   /* don't change the following types to FT_Int or FT_Pos, since we might */

   279   /* need to define them to "float" or "double" when experimenting with   */

   280   /* new algorithms                                                       */

   281 

   282   typedef long  TCoord;   /* integer scanline/pixel coordinate */

   283   typedef long  TPos;     /* sub-pixel coordinate              */

   284 

   285   /* determine the type used to store cell areas.  This normally takes at */

   286   /* least PIXEL_BITS*2 + 1 bits.  On 16-bit systems, we need to use      */

   287   /* `long' instead of `int', otherwise bad things happen                 */

   288 

   289 #if PIXEL_BITS <= 7

   290 

   291   typedef int  TArea;

   292 

   293 #else /* PIXEL_BITS >= 8 */

   294 

   295   /* approximately determine the size of integers using an ANSI-C header */

   296 #if FT_UINT_MAX == 0xFFFFU

   297   typedef long  TArea;

   298 #else

   299   typedef int   TArea;

   300 #endif

   301 

   302 #endif /* PIXEL_BITS >= 8 */

   303 

   304 

   305   /* maximal number of gray spans in a call to the span callback */

   306 #define FT_MAX_GRAY_SPANS  32

   307 

   308 

   309   typedef struct TCell_*  PCell;

   310 

   311   typedef struct  TCell_

   312   {

   313     TPos   x;     /* same with TWorker.ex */

   314     TCoord cover; /* same with TWorker.cover */

   315     TArea  area;

   316     PCell  next;

   317 

   318   } TCell;

   319 

   320 

   321   typedef struct  TWorker_

   322   {

   323     TCoord  ex, ey;

   324     TPos    min_ex, max_ex;

   325     TPos    min_ey, max_ey;

   326     TPos    count_ex, count_ey;

   327 

   328     TArea   area;

   329     TCoord  cover;

   330     int     invalid;

   331 

   332     PCell   cells;

   333     FT_PtrDist  max_cells;

   334     FT_PtrDist  num_cells;

   335 

   336     TCoord  cx, cy;

   337     TPos    x,  y;

   338 

   339     TPos    last_ey;

   340 

   341     FT_Vector   bez_stack[32 * 3 + 1];

   342     int         lev_stack[32];

   343 

   344     FT_Outline  outline;

   345     FT_Bitmap   target;

   346     FT_BBox     clip_box;

   347 

   348     FT_Span     gray_spans[FT_MAX_GRAY_SPANS];

   349     int         num_gray_spans;

   350 

   351     FT_Raster_Span_Func  render_span;

   352     void*                render_span_data;

   353     int                  span_y;

   354 

   355     int  band_size;

   356     int  band_shoot;

   357 

   358     ft_jmp_buf  jump_buffer;

   359 

   360     void*       buffer;

   361     long        buffer_size;

   362 

   363     PCell*     ycells;

   364     TPos       ycount;

   365 

   366   } TWorker, *PWorker;

   367 

   368 

   369 #ifndef FT_STATIC_RASTER

   370 #define ras  (*worker)

   371 #else

   372   static TWorker  ras;

   373 #endif

   374 

   375 

   376   typedef struct TRaster_

   377   {

   378     void*    buffer;

   379     long     buffer_size;

   380     int      band_size;

   381     void*    memory;

   382     PWorker  worker;

   383 

   384   } TRaster, *PRaster;

   385 

   386 

   387 

   388   /*************************************************************************/

   389   /*                                                                       */

   390   /* Initialize the cells table.                                           */

   391   /*                                                                       */

   392   static void

   393   gray_init_cells( RAS_ARG_ void*  buffer,

   394                    long            byte_size )

   395   {

   396     ras.buffer      = buffer;

   397     ras.buffer_size = byte_size;

   398 

   399     ras.ycells      = (PCell*) buffer;

   400     ras.cells       = NULL;

   401     ras.max_cells   = 0;

   402     ras.num_cells   = 0;

   403     ras.area        = 0;

   404     ras.cover       = 0;

   405     ras.invalid     = 1;

   406   }

   407 

   408 

   409   /*************************************************************************/

   410   /*                                                                       */

   411   /* Compute the outline bounding box.                                     */

   412   /*                                                                       */

   413   static void

   414   gray_compute_cbox( RAS_ARG )

   415   {

   416     FT_Outline*  outline = &ras.outline;

   417     FT_Vector*   vec     = outline->points;

   418     FT_Vector*   limit   = vec + outline->n_points;

   419 

   420 

   421     if ( outline->n_points <= 0 )

   422     {

   423       ras.min_ex = ras.max_ex = 0;

   424       ras.min_ey = ras.max_ey = 0;

   425       return;

   426     }

   427 

   428     ras.min_ex = ras.max_ex = vec->x;

   429     ras.min_ey = ras.max_ey = vec->y;

   430 

   431     vec++;

   432 

   433     for ( ; vec < limit; vec++ )

   434     {

   435       TPos  x = vec->x;

   436       TPos  y = vec->y;

   437 

   438 

   439       if ( x < ras.min_ex ) ras.min_ex = x;

   440       if ( x > ras.max_ex ) ras.max_ex = x;

   441       if ( y < ras.min_ey ) ras.min_ey = y;

   442       if ( y > ras.max_ey ) ras.max_ey = y;

   443     }

   444 

   445     /* truncate the bounding box to integer pixels */

   446     ras.min_ex = ras.min_ex >> 6;

   447     ras.min_ey = ras.min_ey >> 6;

   448     ras.max_ex = ( ras.max_ex + 63 ) >> 6;

   449     ras.max_ey = ( ras.max_ey + 63 ) >> 6;

   450   }

   451 

   452 

   453   /*************************************************************************/

   454   /*                                                                       */

   455   /* Record the current cell in the table.                                 */

   456   /*                                                                       */

   457   static PCell

   458   gray_find_cell( RAS_ARG )

   459   {

   460     PCell  *pcell, cell;

   461     TPos    x = ras.ex;

   462 

   463 

   464     if ( x > ras.count_ex )

   465       x = ras.count_ex;

   466 

   467     pcell = &ras.ycells[ras.ey];

   468     for (;;)

   469     {

   470       cell = *pcell;

   471       if ( cell == NULL || cell->x > x )

   472         break;

   473 

   474       if ( cell->x == x )

   475         goto Exit;

   476 

   477       pcell = &cell->next;

   478     }

   479 

   480     if ( ras.num_cells >= ras.max_cells )

   481       ft_longjmp( ras.jump_buffer, 1 );

   482 

   483     cell        = ras.cells + ras.num_cells++;

   484     cell->x     = x;

   485     cell->area  = 0;

   486     cell->cover = 0;

   487 

   488     cell->next  = *pcell;

   489     *pcell      = cell;

   490 

   491   Exit:

   492     return cell;

   493   }

   494 

   495 

   496   static void

   497   gray_record_cell( RAS_ARG )

   498   {

   499     if ( !ras.invalid && ( ras.area | ras.cover ) )

   500     {

   501       PCell  cell = gray_find_cell( RAS_VAR );

   502 

   503 

   504       cell->area  += ras.area;

   505       cell->cover += ras.cover;

   506     }

   507   }

   508 

   509 

   510   /*************************************************************************/

   511   /*                                                                       */

   512   /* Set the current cell to a new position.                               */

   513   /*                                                                       */

   514   static void

   515   gray_set_cell( RAS_ARG_ TCoord  ex,

   516                           TCoord  ey )

   517   {

   518     /* Move the cell pointer to a new position.  We set the `invalid'      */

   519     /* flag to indicate that the cell isn't part of those we're interested */

   520     /* in during the render phase.  This means that:                       */

   521     /*                                                                     */

   522     /* . the new vertical position must be within min_ey..max_ey-1.        */

   523     /* . the new horizontal position must be strictly less than max_ex     */

   524     /*                                                                     */

   525     /* Note that if a cell is to the left of the clipping region, it is    */

   526     /* actually set to the (min_ex-1) horizontal position.                 */

   527 

   528     /* All cells that are on the left of the clipping region go to the */

   529     /* min_ex - 1 horizontal position.                                 */

   530     ey -= ras.min_ey;

   531 

   532     if ( ex > ras.max_ex )

   533       ex = ras.max_ex;

   534 

   535     ex -= ras.min_ex;

   536     if ( ex < 0 )

   537       ex = -1;

   538 

   539     /* are we moving to a different cell ? */

   540     if ( ex != ras.ex || ey != ras.ey )

   541     {

   542       /* record the current one if it is valid */

   543       if ( !ras.invalid )

   544         gray_record_cell( RAS_VAR );

   545 

   546       ras.area  = 0;

   547       ras.cover = 0;

   548     }

   549 

   550     ras.ex      = ex;

   551     ras.ey      = ey;

   552     ras.invalid = ( (unsigned)ey >= (unsigned)ras.count_ey ||

   553                               ex >= ras.count_ex           );

   554   }

   555 

   556 

   557   /*************************************************************************/

   558   /*                                                                       */

   559   /* Start a new contour at a given cell.                                  */

   560   /*                                                                       */

   561   static void

   562   gray_start_cell( RAS_ARG_ TCoord  ex,

   563                             TCoord  ey )

   564   {

   565     if ( ex > ras.max_ex )

   566       ex = (TCoord)( ras.max_ex );

   567 

   568     if ( ex < ras.min_ex )

   569       ex = (TCoord)( ras.min_ex - 1 );

   570 

   571     ras.area    = 0;

   572     ras.cover   = 0;

   573     ras.ex      = ex - ras.min_ex;

   574     ras.ey      = ey - ras.min_ey;

   575     ras.last_ey = SUBPIXELS( ey );

   576     ras.invalid = 0;

   577 

   578     gray_set_cell( RAS_VAR_ ex, ey );

   579   }

   580 

   581 

   582   /*************************************************************************/

   583   /*                                                                       */

   584   /* Render a scanline as one or more cells.                               */

   585   /*                                                                       */

   586   static void

   587   gray_render_scanline( RAS_ARG_ TCoord  ey,

   588                                  TPos    x1,

   589                                  TCoord  y1,

   590                                  TPos    x2,

   591                                  TCoord  y2 )

   592   {

   593     TCoord  ex1, ex2, fx1, fx2, delta, mod, lift, rem;

   594     long    p, first, dx;

   595     int     incr;

   596 

   597 

   598     dx = x2 - x1;

   599 

   600     ex1 = TRUNC( x1 );

   601     ex2 = TRUNC( x2 );

   602     fx1 = (TCoord)( x1 - SUBPIXELS( ex1 ) );

   603     fx2 = (TCoord)( x2 - SUBPIXELS( ex2 ) );

   604 

   605     /* trivial case.  Happens often */

   606     if ( y1 == y2 )

   607     {

   608       gray_set_cell( RAS_VAR_ ex2, ey );

   609       return;

   610     }

   611 

   612     /* everything is located in a single cell.  That is easy! */

   613     /*                                                        */

   614     if ( ex1 == ex2 )

   615     {

   616       delta      = y2 - y1;

   617       ras.area  += (TArea)(( fx1 + fx2 ) * delta);

   618       ras.cover += delta;

   619       return;

   620     }

   621 

   622     /* ok, we'll have to render a run of adjacent cells on the same */

   623     /* scanline...                                                  */

   624     /*                                                              */

   625     p     = ( ONE_PIXEL - fx1 ) * ( y2 - y1 );

   626     first = ONE_PIXEL;

   627     incr  = 1;

   628 

   629     if ( dx < 0 )

   630     {

   631       p     = fx1 * ( y2 - y1 );

   632       first = 0;

   633       incr  = -1;

   634       dx    = -dx;

   635     }

   636 

   637     delta = (TCoord)( p / dx );

   638     mod   = (TCoord)( p % dx );

   639     if ( mod < 0 )

   640     {

   641       delta--;

   642       mod += (TCoord)dx;

   643     }

   644 

   645     ras.area  += (TArea)(( fx1 + first ) * delta);

   646     ras.cover += delta;

   647 

   648     ex1 += incr;

   649     gray_set_cell( RAS_VAR_ ex1, ey );

   650     y1  += delta;

   651 

   652     if ( ex1 != ex2 )

   653     {

   654       p    = ONE_PIXEL * ( y2 - y1 + delta );

   655       lift = (TCoord)( p / dx );

   656       rem  = (TCoord)( p % dx );

   657       if ( rem < 0 )

   658       {

   659         lift--;

   660         rem += (TCoord)dx;

   661       }

   662 

   663       mod -= (int)dx;

   664 

   665       while ( ex1 != ex2 )

   666       {

   667         delta = lift;

   668         mod  += rem;

   669         if ( mod >= 0 )

   670         {

   671           mod -= (TCoord)dx;

   672           delta++;

   673         }

   674 

   675         ras.area  += (TArea)(ONE_PIXEL * delta);

   676         ras.cover += delta;

   677         y1        += delta;

   678         ex1       += incr;

   679         gray_set_cell( RAS_VAR_ ex1, ey );

   680       }

   681     }

   682 

   683     delta      = y2 - y1;

   684     ras.area  += (TArea)(( fx2 + ONE_PIXEL - first ) * delta);

   685     ras.cover += delta;

   686   }

   687 

   688 

   689   /*************************************************************************/

   690   /*                                                                       */

   691   /* Render a given line as a series of scanlines.                         */

   692   /*                                                                       */

   693   static void

   694   gray_render_line( RAS_ARG_ TPos  to_x,

   695                              TPos  to_y )

   696   {

   697     TCoord  ey1, ey2, fy1, fy2, mod;

   698     TPos    dx, dy, x, x2;

   699     long    p, first;

   700     int     delta, rem, lift, incr;

   701 

   702 

   703     ey1 = TRUNC( ras.last_ey );

   704     ey2 = TRUNC( to_y );     /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */

   705     fy1 = (TCoord)( ras.y - ras.last_ey );

   706     fy2 = (TCoord)( to_y - SUBPIXELS( ey2 ) );

   707 

   708     dx = to_x - ras.x;

   709     dy = to_y - ras.y;

   710 

   711     /* XXX: we should do something about the trivial case where dx == 0, */

   712     /*      as it happens very often!                                    */

   713 

   714     /* perform vertical clipping */

   715     {

   716       TCoord  min, max;

   717 

   718 

   719       min = ey1;

   720       max = ey2;

   721       if ( ey1 > ey2 )

   722       {

   723         min = ey2;

   724         max = ey1;

   725       }

   726       if ( min >= ras.max_ey || max < ras.min_ey )

   727         goto End;

   728     }

   729 

   730     /* everything is on a single scanline */

   731     if ( ey1 == ey2 )

   732     {

   733       gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 );

   734       goto End;

   735     }

   736 

   737     /* vertical line - avoid calling gray_render_scanline */

   738     incr = 1;

   739 

   740     if ( dx == 0 )

   741     {

   742       TCoord  ex     = TRUNC( ras.x );

   743       TCoord  two_fx = (TCoord)( ( ras.x - SUBPIXELS( ex ) ) << 1 );

   744       TArea   area;

   745 

   746 

   747       first = ONE_PIXEL;

   748       if ( dy < 0 )

   749       {

   750         first = 0;

   751         incr  = -1;

   752       }

   753 

   754       delta      = (int)( first - fy1 );

   755       ras.area  += (TArea)two_fx * delta;

   756       ras.cover += delta;

   757       ey1       += incr;

   758 

   759       gray_set_cell( RAS_VAR_ ex, ey1 );

   760 

   761       delta = (int)( first + first - ONE_PIXEL );

   762       area  = (TArea)two_fx * delta;

   763       while ( ey1 != ey2 )

   764       {

   765         ras.area  += area;

   766         ras.cover += delta;

   767         ey1       += incr;

   768 

   769         gray_set_cell( RAS_VAR_ ex, ey1 );

   770       }

   771 

   772       delta      = (int)( fy2 - ONE_PIXEL + first );

   773       ras.area  += (TArea)two_fx * delta;

   774       ras.cover += delta;

   775 

   776       goto End;

   777     }

   778 

   779     /* ok, we have to render several scanlines */

   780     p     = ( ONE_PIXEL - fy1 ) * dx;

   781     first = ONE_PIXEL;

   782     incr  = 1;

   783 

   784     if ( dy < 0 )

   785     {

   786       p     = fy1 * dx;

   787       first = 0;

   788       incr  = -1;

   789       dy    = -dy;

   790     }

   791 

   792     delta = (int)( p / dy );

   793     mod   = (int)( p % dy );

   794     if ( mod < 0 )

   795     {

   796       delta--;

   797       mod += (TCoord)dy;

   798     }

   799 

   800     x = ras.x + delta;

   801     gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, (TCoord)first );

   802 

   803     ey1 += incr;

   804     gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );

   805 

   806     if ( ey1 != ey2 )

   807     {

   808       p     = ONE_PIXEL * dx;

   809       lift  = (int)( p / dy );

   810       rem   = (int)( p % dy );

   811       if ( rem < 0 )

   812       {

   813         lift--;

   814         rem += (int)dy;

   815       }

   816       mod -= (int)dy;

   817 

   818       while ( ey1 != ey2 )

   819       {

   820         delta = lift;

   821         mod  += rem;

   822         if ( mod >= 0 )

   823         {

   824           mod -= (int)dy;

   825           delta++;

   826         }

   827 

   828         x2 = x + delta;

   829         gray_render_scanline( RAS_VAR_ ey1, x,

   830                                        (TCoord)( ONE_PIXEL - first ), x2,

   831                                        (TCoord)first );

   832         x = x2;

   833 

   834         ey1 += incr;

   835         gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 );

   836       }

   837     }

   838 

   839     gray_render_scanline( RAS_VAR_ ey1, x,

   840                                    (TCoord)( ONE_PIXEL - first ), to_x,

   841                                    fy2 );

   842 

   843   End:

   844     ras.x       = to_x;

   845     ras.y       = to_y;

   846     ras.last_ey = SUBPIXELS( ey2 );

   847   }

   848 

   849 

   850   static void

   851   gray_split_conic( FT_Vector*  base )

   852   {

   853     TPos  a, b;

   854 

   855 

   856     base[4].x = base[2].x;

   857     b = base[1].x;

   858     a = base[3].x = ( base[2].x + b ) / 2;

   859     b = base[1].x = ( base[0].x + b ) / 2;

   860     base[2].x = ( a + b ) / 2;

   861 

   862     base[4].y = base[2].y;

   863     b = base[1].y;

   864     a = base[3].y = ( base[2].y + b ) / 2;

   865     b = base[1].y = ( base[0].y + b ) / 2;

   866     base[2].y = ( a + b ) / 2;

   867   }

   868 

   869 

   870   static void

   871   gray_render_conic( RAS_ARG_ const FT_Vector*  control,

   872                               const FT_Vector*  to )

   873   {

   874     TPos        dx, dy;

   875     int         top, level;

   876     int*        levels;

   877     FT_Vector*  arc;

   878 

   879 

   880     arc      = ras.bez_stack;

   881     arc[0].x = UPSCALE( to->x );

   882     arc[0].y = UPSCALE( to->y );

   883     arc[1].x = UPSCALE( control->x );

   884     arc[1].y = UPSCALE( control->y );

   885     arc[2].x = ras.x;

   886     arc[2].y = ras.y;

   887 

   888     dx = FT_ABS( arc[2].x + arc[0].x - 2 * arc[1].x );

   889     dy = FT_ABS( arc[2].y + arc[0].y - 2 * arc[1].y );

   890     if ( dx < dy )

   891       dx = dy;

   892 

   893     level = 0;

   894     while ( dx > ONE_PIXEL / 6 )

   895     {

   896       dx >>= 2;

   897       level++;

   898     }

   899 

   900     levels    = ras.lev_stack;

   901     levels[0] = level;

   902     top       = 0;

   903 

   904     do

   905     {

   906       level = levels[top];

   907       if ( level > 1 )

   908       {

   909         /* check that the arc crosses the current band */

   910         TPos  min, max, y;

   911 

   912 

   913         min = max = arc[0].y;

   914 

   915         y = arc[1].y;

   916         if ( y < min ) min = y;

   917         if ( y > max ) max = y;

   918 

   919         y = arc[2].y;

   920         if ( y < min ) min = y;

   921         if ( y > max ) max = y;

   922 

   923         if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < ras.min_ey )

   924           goto Draw;

   925 

   926         gray_split_conic( arc );

   927         arc += 2;

   928         top++;

   929         levels[top] = levels[top - 1] = level - 1;

   930         continue;

   931       }

   932 

   933     Draw:

   934       gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );

   935       top--;

   936       arc -= 2;

   937 

   938     } while ( top >= 0 );

   939   }

   940 

   941 

   942   static void

   943   gray_split_cubic( FT_Vector*  base )

   944   {

   945     TPos  a, b, c, d;

   946 

   947 

   948     base[6].x = base[3].x;

   949     c = base[1].x;

   950     d = base[2].x;

   951     base[1].x = a = ( base[0].x + c ) / 2;

   952     base[5].x = b = ( base[3].x + d ) / 2;

   953     c = ( c + d ) / 2;

   954     base[2].x = a = ( a + c ) / 2;

   955     base[4].x = b = ( b + c ) / 2;

   956     base[3].x = ( a + b ) / 2;

   957 

   958     base[6].y = base[3].y;

   959     c = base[1].y;

   960     d = base[2].y;

   961     base[1].y = a = ( base[0].y + c ) / 2;

   962     base[5].y = b = ( base[3].y + d ) / 2;

   963     c = ( c + d ) / 2;

   964     base[2].y = a = ( a + c ) / 2;

   965     base[4].y = b = ( b + c ) / 2;

   966     base[3].y = ( a + b ) / 2;

   967   }

   968 

   969 

   970   static void

   971   gray_render_cubic( RAS_ARG_ const FT_Vector*  control1,

   972                               const FT_Vector*  control2,

   973                               const FT_Vector*  to )

   974   {

   975     FT_Vector*  arc;

   976 

   977 

   978     arc      = ras.bez_stack;

   979     arc[0].x = UPSCALE( to->x );

   980     arc[0].y = UPSCALE( to->y );

   981     arc[1].x = UPSCALE( control2->x );

   982     arc[1].y = UPSCALE( control2->y );

   983     arc[2].x = UPSCALE( control1->x );

   984     arc[2].y = UPSCALE( control1->y );

   985     arc[3].x = ras.x;

   986     arc[3].y = ras.y;

   987 

   988     for (;;)

   989     {

   990       /* Check that the arc crosses the current band. */

   991       TPos  min, max, y;

   992 

   993 

   994       min = max = arc[0].y;

   995 

   996       y = arc[1].y;

   997       if ( y < min )

   998         min = y;

   999       if ( y > max )

  1000         max = y;

  1001 

  1002       y = arc[2].y;

  1003       if ( y < min )

  1004         min = y;

  1005       if ( y > max )

  1006         max = y;

  1007 

  1008       y = arc[3].y;

  1009       if ( y < min )

  1010         min = y;

  1011       if ( y > max )

  1012         max = y;

  1013 

  1014       if ( TRUNC( min ) >= ras.max_ey || TRUNC( max ) < ras.min_ey )

  1015         goto Draw;

  1016 

  1017       /* Decide whether to split or draw. See `Rapid Termination          */

  1018       /* Evaluation for Recursive Subdivision of Bezier Curves' by Thomas */

  1019       /* F. Hain, at                                                      */

  1020       /* http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf */

  1021 

  1022       {

  1023         TPos  dx, dy, dx_, dy_;

  1024         TPos  dx1, dy1, dx2, dy2;

  1025         TPos  L, s, s_limit;

  1026 

  1027 

  1028         /* dx and dy are x and y components of the P0-P3 chord vector. */

  1029         dx = arc[3].x - arc[0].x;

  1030         dy = arc[3].y - arc[0].y;

  1031 

  1032         /* L is an (under)estimate of the Euclidean distance P0-P3.       */

  1033         /*                                                                */

  1034         /* If dx >= dy, then r = sqrt(dx^2 + dy^2) can be overestimated   */

  1035         /* with least maximum error by                                    */

  1036         /*                                                                */

  1037         /*   r_upperbound = dx + (sqrt(2) - 1) * dy  ,                    */

  1038         /*                                                                */

  1039         /* where sqrt(2) - 1 can be (over)estimated by 107/256, giving an */

  1040         /* error of no more than 8.4%.                                    */

  1041         /*                                                                */

  1042         /* Similarly, some elementary calculus shows that r can be        */

  1043         /* underestimated with least maximum error by                     */

  1044         /*                                                                */

  1045         /*   r_lowerbound = sqrt(2 + sqrt(2)) / 2 * dx                    */

  1046         /*                  + sqrt(2 - sqrt(2)) / 2 * dy  .               */

  1047         /*                                                                */

  1048         /* 236/256 and 97/256 are (under)estimates of the two algebraic   */

  1049         /* numbers, giving an error of no more than 8.1%.                 */

  1050 

  1051         dx_ = FT_ABS( dx );

  1052         dy_ = FT_ABS( dy );

  1053 

  1054         /* This is the same as                     */

  1055         /*                                         */

  1056         /*   L = ( 236 * FT_MAX( dx_, dy_ )        */

  1057         /*       + 97 * FT_MIN( dx_, dy_ ) ) >> 8; */

  1058         L = ( dx_ > dy_ ? 236 * dx_ +  97 * dy_

  1059                         :  97 * dx_ + 236 * dy_ ) >> 8;

  1060 

  1061         /* Avoid possible arithmetic overflow below by splitting. */

  1062         if ( L > 32767 )

  1063           goto Split;

  1064 

  1065         /* Max deviation may be as much as (s/L) * 3/4 (if Hain's v = 1). */

  1066         s_limit = L * (TPos)( ONE_PIXEL / 6 );

  1067 

  1068         /* s is L * the perpendicular distance from P1 to the line P0-P3. */

  1069         dx1 = arc[1].x - arc[0].x;

  1070         dy1 = arc[1].y - arc[0].y;

  1071         s = FT_ABS( dy * dx1 - dx * dy1 );

  1072 

  1073         if ( s > s_limit )

  1074           goto Split;

  1075 

  1076         /* s is L * the perpendicular distance from P2 to the line P0-P3. */

  1077         dx2 = arc[2].x - arc[0].x;

  1078         dy2 = arc[2].y - arc[0].y;

  1079         s = FT_ABS( dy * dx2 - dx * dy2 );

  1080 

  1081         if ( s > s_limit )

  1082           goto Split;

  1083 

  1084         /* If P1 or P2 is outside P0-P3, split the curve. */

  1085         if ( dy * dy1 + dx * dx1 < 0                                     ||

  1086              dy * dy2 + dx * dx2 < 0                                     ||

  1087              dy * (arc[3].y - arc[1].y) + dx * (arc[3].x - arc[1].x) < 0 ||

  1088              dy * (arc[3].y - arc[2].y) + dx * (arc[3].x - arc[2].x) < 0 )

  1089           goto Split;

  1090 

  1091         /* No reason to split. */

  1092         goto Draw;

  1093       }

  1094 

  1095     Split:

  1096       gray_split_cubic( arc );

  1097       arc += 3;

  1098       continue;

  1099 

  1100     Draw:

  1101       gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );

  1102 

  1103       if ( arc == ras.bez_stack )

  1104         return;

  1105 

  1106       arc -= 3;

  1107     }

  1108   }

  1109 

  1110 

  1111   static int

  1112   gray_move_to( const FT_Vector*  to,

  1113                 PWorker           worker )

  1114   {

  1115     TPos  x, y;

  1116 

  1117 

  1118     /* record current cell, if any */

  1119     gray_record_cell( RAS_VAR );

  1120 

  1121     /* start to a new position */

  1122     x = UPSCALE( to->x );

  1123     y = UPSCALE( to->y );

  1124 

  1125     gray_start_cell( RAS_VAR_ TRUNC( x ), TRUNC( y ) );

  1126 

  1127     worker->x = x;

  1128     worker->y = y;

  1129     return 0;

  1130   }

  1131 

  1132 

  1133   static int

  1134   gray_line_to( const FT_Vector*  to,