Home | History | Annotate | Download | only in autofit
      1 /***************************************************************************/
      2 /*                                                                         */
      3 /*  afwarp.c                                                               */
      4 /*                                                                         */
      5 /*    Auto-fitter warping algorithm (body).                                */
      6 /*                                                                         */
      7 /*  Copyright 2006, 2007, 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    *  The idea of the warping code is to slightly scale and shift a glyph
     21    *  within a single dimension so that as much of its segments are aligned
     22    *  (more or less) on the grid.  To find out the optimal scaling and
     23    *  shifting value, various parameter combinations are tried and scored.
     24    */
     25 
     26 #include "afwarp.h"
     27 
     28 #ifdef AF_CONFIG_OPTION_USE_WARPER
     29 
     30   /*************************************************************************/
     31   /*                                                                       */
     32   /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
     33   /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
     34   /* messages during execution.                                            */
     35   /*                                                                       */
     36 #undef  FT_COMPONENT
     37 #define FT_COMPONENT  trace_afwarp
     38 
     39 
     40   /* The weights cover the range 0/64 - 63/64 of a pixel.  Obviously, */
     41   /* values around a half pixel (which means exactly between two grid */
     42   /* lines) gets the worst weight.                                    */
     43 #if 1
     44   static const AF_WarpScore
     45   af_warper_weights[64] =
     46   {
     47     35, 32, 30, 25, 20, 15, 12, 10,  5,  1,  0,  0,  0,  0,  0,  0,
     48      0,  0,  0,  0,  0,  0, -1, -2, -5, -8,-10,-10,-20,-20,-30,-30,
     49 
     50    -30,-30,-20,-20,-10,-10, -8, -5, -2, -1,  0,  0,  0,  0,  0,  0,
     51      0,  0,  0,  0,  0,  0,  0,  1,  5, 10, 12, 15, 20, 25, 30, 32,
     52   };
     53 #else
     54   static const AF_WarpScore
     55   af_warper_weights[64] =
     56   {
     57     30, 20, 10,  5,  4,  4,  3,  2,  1,  0,  0,  0,  0,  0,  0,  0,
     58      0,  0,  0,  0,  0,  0,  0, -1, -2, -2, -5, -5,-10,-10,-15,-20,
     59 
     60    -20,-15,-15,-10,-10, -5, -5, -2, -2, -1,  0,  0,  0,  0,  0,  0,
     61      0,  0,  0,  0,  0,  0,  0,  0,  1,  2,  3,  4,  4,  5, 10, 20,
     62   };
     63 #endif
     64 
     65 
     66   /* Score segments for a given `scale' and `delta' in the range */
     67   /* `xx1' to `xx2', and store the best result in `warper'.  If  */
     68   /* the new best score is equal to the old one, prefer the      */
     69   /* value with a smaller distortion (around `base_distort').    */
     70 
     71   static void
     72   af_warper_compute_line_best( AF_Warper     warper,
     73                                FT_Fixed      scale,
     74                                FT_Pos        delta,
     75                                FT_Pos        xx1,
     76                                FT_Pos        xx2,
     77                                AF_WarpScore  base_distort,
     78                                AF_Segment    segments,
     79                                FT_UInt       num_segments )
     80   {
     81     FT_Int        idx_min, idx_max, idx0;
     82     FT_UInt       nn;
     83     AF_WarpScore  scores[65];
     84 
     85 
     86     for ( nn = 0; nn < 65; nn++ )
     87       scores[nn] = 0;
     88 
     89     idx0 = xx1 - warper->t1;
     90 
     91     /* compute minimum and maximum indices */
     92     {
     93       FT_Pos  xx1min = warper->x1min;
     94       FT_Pos  xx1max = warper->x1max;
     95       FT_Pos  w      = xx2 - xx1;
     96 
     97 
     98       if ( xx1min + w < warper->x2min )
     99         xx1min = warper->x2min - w;
    100 
    101       xx1max = warper->x1max;
    102       if ( xx1max + w > warper->x2max )
    103         xx1max = warper->x2max - w;
    104 
    105       idx_min = xx1min - warper->t1;
    106       idx_max = xx1max - warper->t1;
    107 
    108       if ( idx_min < 0 || idx_min > idx_max || idx_max > 64 )
    109       {
    110         FT_TRACE5(( "invalid indices:\n"
    111                     "  min=%d max=%d, xx1=%ld xx2=%ld,\n"
    112                     "  x1min=%ld x1max=%ld, x2min=%ld x2max=%ld\n",
    113                     idx_min, idx_max, xx1, xx2,
    114                     warper->x1min, warper->x1max,
    115                     warper->x2min, warper->x2max ));
    116         return;
    117       }
    118     }
    119 
    120     for ( nn = 0; nn < num_segments; nn++ )
    121     {
    122       FT_Pos  len = segments[nn].max_coord - segments[nn].min_coord;
    123       FT_Pos  y0  = FT_MulFix( segments[nn].pos, scale ) + delta;
    124       FT_Pos  y   = y0 + ( idx_min - idx0 );
    125       FT_Int  idx;
    126 
    127 
    128       /* score the length of the segments for the given range */
    129       for ( idx = idx_min; idx <= idx_max; idx++, y++ )
    130         scores[idx] += af_warper_weights[y & 63] * len;
    131     }
    132 
    133     /* find best score */
    134     {
    135       FT_Int  idx;
    136 
    137 
    138       for ( idx = idx_min; idx <= idx_max; idx++ )
    139       {
    140         AF_WarpScore  score = scores[idx];
    141         AF_WarpScore  distort = base_distort + ( idx - idx0 );
    142 
    143 
    144         if ( score > warper->best_score         ||
    145              ( score == warper->best_score    &&
    146                distort < warper->best_distort ) )
    147         {
    148           warper->best_score   = score;
    149           warper->best_distort = distort;
    150           warper->best_scale   = scale;
    151           warper->best_delta   = delta + ( idx - idx0 );
    152         }
    153       }
    154     }
    155   }
    156 
    157 
    158   /* Compute optimal scaling and delta values for a given glyph and */
    159   /* dimension.                                                     */
    160 
    161   FT_LOCAL_DEF( void )
    162   af_warper_compute( AF_Warper      warper,
    163                      AF_GlyphHints  hints,
    164                      AF_Dimension   dim,
    165                      FT_Fixed      *a_scale,
    166                      FT_Pos        *a_delta )
    167   {
    168     AF_AxisHints  axis;
    169     AF_Point      points;
    170 
    171     FT_Fixed      org_scale;
    172     FT_Pos        org_delta;
    173 
    174     FT_UInt       nn, num_points, num_segments;
    175     FT_Int        X1, X2;
    176     FT_Int        w;
    177 
    178     AF_WarpScore  base_distort;
    179     AF_Segment    segments;
    180 
    181 
    182     /* get original scaling transformation */
    183     if ( dim == AF_DIMENSION_VERT )
    184     {
    185       org_scale = hints->y_scale;
    186       org_delta = hints->y_delta;
    187     }
    188     else
    189     {
    190       org_scale = hints->x_scale;
    191       org_delta = hints->x_delta;
    192     }
    193 
    194     warper->best_scale   = org_scale;
    195     warper->best_delta   = org_delta;
    196     warper->best_score   = INT_MIN;
    197     warper->best_distort = 0;
    198 
    199     axis         = &hints->axis[dim];
    200     segments     = axis->segments;
    201     num_segments = axis->num_segments;
    202     points       = hints->points;
    203     num_points   = hints->num_points;
    204 
    205     *a_scale = org_scale;
    206     *a_delta = org_delta;
    207 
    208     /* get X1 and X2, minimum and maximum in original coordinates */
    209     if ( num_segments < 1 )
    210       return;
    211 
    212 #if 1
    213     X1 = X2 = points[0].fx;
    214     for ( nn = 1; nn < num_points; nn++ )
    215     {
    216       FT_Int  X = points[nn].fx;
    217 
    218 
    219       if ( X < X1 )
    220         X1 = X;
    221       if ( X > X2 )
    222         X2 = X;
    223     }
    224 #else
    225     X1 = X2 = segments[0].pos;
    226     for ( nn = 1; nn < num_segments; nn++ )
    227     {
    228       FT_Int  X = segments[nn].pos;
    229 
    230 
    231       if ( X < X1 )
    232         X1 = X;
    233       if ( X > X2 )
    234         X2 = X;
    235     }
    236 #endif
    237 
    238     if ( X1 >= X2 )
    239       return;
    240 
    241     warper->x1 = FT_MulFix( X1, org_scale ) + org_delta;
    242     warper->x2 = FT_MulFix( X2, org_scale ) + org_delta;
    243 
    244     warper->t1 = AF_WARPER_FLOOR( warper->x1 );
    245     warper->t2 = AF_WARPER_CEIL( warper->x2 );
    246 
    247     /* examine a half pixel wide range around the maximum coordinates */
    248     warper->x1min = warper->x1 & ~31;
    249     warper->x1max = warper->x1min + 32;
    250     warper->x2min = warper->x2 & ~31;
    251     warper->x2max = warper->x2min + 32;
    252 
    253     if ( warper->x1max > warper->x2 )
    254       warper->x1max = warper->x2;
    255 
    256     if ( warper->x2min < warper->x1 )
    257       warper->x2min = warper->x1;
    258 
    259     warper->w0 = warper->x2 - warper->x1;
    260 
    261     if ( warper->w0 <= 64 )
    262     {
    263       warper->x1max = warper->x1;
    264       warper->x2min = warper->x2;
    265     }
    266 
    267     /* examine (at most) a pixel wide range around the natural width */
    268     warper->wmin = warper->x2min - warper->x1max;
    269     warper->wmax = warper->x2max - warper->x1min;
    270 
    271 #if 1
    272     /* some heuristics to reduce the number of widths to be examined */
    273     {
    274       int  margin = 16;
    275 
    276 
    277       if ( warper->w0 <= 128 )
    278       {
    279          margin = 8;
    280          if ( warper->w0 <= 96 )
    281            margin = 4;
    282       }
    283 
    284       if ( warper->wmin < warper->w0 - margin )
    285         warper->wmin = warper->w0 - margin;
    286 
    287       if ( warper->wmax > warper->w0 + margin )
    288         warper->wmax = warper->w0 + margin;
    289     }
    290 
    291     if ( warper->wmin < warper->w0 * 3 / 4 )
    292       warper->wmin = warper->w0 * 3 / 4;
    293 
    294     if ( warper->wmax > warper->w0 * 5 / 4 )
    295       warper->wmax = warper->w0 * 5 / 4;
    296 #else
    297     /* no scaling, just translation */
    298     warper->wmin = warper->wmax = warper->w0;
    299 #endif
    300 
    301     for ( w = warper->wmin; w <= warper->wmax; w++ )
    302     {
    303       FT_Fixed  new_scale;
    304       FT_Pos    new_delta;
    305       FT_Pos    xx1, xx2;
    306 
    307 
    308       /* compute min and max positions for given width,       */
    309       /* assuring that they stay within the coordinate ranges */
    310       xx1 = warper->x1;
    311       xx2 = warper->x2;
    312       if ( w >= warper->w0 )
    313       {
    314         xx1 -= w - warper->w0;
    315         if ( xx1 < warper->x1min )
    316         {
    317           xx2 += warper->x1min - xx1;
    318           xx1  = warper->x1min;
    319         }
    320       }
    321       else
    322       {
    323         xx1 -= w - warper->w0;
    324         if ( xx1 > warper->x1max )
    325         {
    326           xx2 -= xx1 - warper->x1max;
    327           xx1  = warper->x1max;
    328         }
    329       }
    330 
    331       if ( xx1 < warper->x1 )
    332         base_distort = warper->x1 - xx1;
    333       else
    334         base_distort = xx1 - warper->x1;
    335 
    336       if ( xx2 < warper->x2 )
    337         base_distort += warper->x2 - xx2;
    338       else
    339         base_distort += xx2 - warper->x2;
    340 
    341       /* give base distortion a greater weight while scoring */
    342       base_distort *= 10;
    343 
    344       new_scale = org_scale + FT_DivFix( w - warper->w0, X2 - X1 );
    345       new_delta = xx1 - FT_MulFix( X1, new_scale );
    346 
    347       af_warper_compute_line_best( warper, new_scale, new_delta, xx1, xx2,
    348                                    base_distort,
    349                                    segments, num_segments );
    350     }
    351 
    352     {
    353       FT_Fixed  best_scale = warper->best_scale;
    354       FT_Pos    best_delta = warper->best_delta;
    355 
    356 
    357       hints->xmin_delta = FT_MulFix( X1, best_scale - org_scale )
    358                           + best_delta;
    359       hints->xmax_delta = FT_MulFix( X2, best_scale - org_scale )
    360                           + best_delta;
    361 
    362       *a_scale = best_scale;
    363       *a_delta = best_delta;
    364     }
    365   }
    366 
    367 #else /* !AF_CONFIG_OPTION_USE_WARPER */
    368 
    369   /* ANSI C doesn't like empty source files */
    370   typedef int  _af_warp_dummy;
    371 
    372 #endif /* !AF_CONFIG_OPTION_USE_WARPER */
    373 
    374 /* END */
    375