1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  afwarp.c                                                               */
   4 /*                                                                         */
   5 /*    Auto-fitter warping algorithm (body).                                */
   6 /*                                                                         */
   7 /*  Copyright 2006-2018 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_Int        num_segments )
  80   {
  81     FT_Int        idx_min, idx_max, idx0;
  82     FT_Int        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       if ( xx1max + w > warper->x2max )
 102         xx1max = warper->x2max - w;
 103 
 104       idx_min = xx1min - warper->t1;
 105       idx_max = xx1max - warper->t1;
 106 
 107       if ( idx_min < 0 || idx_min > idx_max || idx_max > 64 )
 108       {
 109         FT_TRACE5(( "invalid indices:\n"
 110                     "  min=%d max=%d, xx1=%ld xx2=%ld,\n"
 111                     "  x1min=%ld x1max=%ld, x2min=%ld x2max=%ld\n",
 112                     idx_min, idx_max, xx1, xx2,
 113                     warper->x1min, warper->x1max,
 114                     warper->x2min, warper->x2max ));
 115         return;
 116       }
 117     }
 118 
 119     for ( nn = 0; nn < num_segments; nn++ )
 120     {
 121       FT_Pos  len = segments[nn].max_coord - segments[nn].min_coord;
 122       FT_Pos  y0  = FT_MulFix( segments[nn].pos, scale ) + delta;
 123       FT_Pos  y   = y0 + ( idx_min - idx0 );
 124       FT_Int  idx;
 125 
 126 
 127       /* score the length of the segments for the given range */
 128       for ( idx = idx_min; idx <= idx_max; idx++, y++ )
 129         scores[idx] += af_warper_weights[y & 63] * len;
 130     }
 131 
 132     /* find best score */
 133     {
 134       FT_Int  idx;
 135 
 136 
 137       for ( idx = idx_min; idx <= idx_max; idx++ )
 138       {
 139         AF_WarpScore  score = scores[idx];
 140         AF_WarpScore  distort = base_distort + ( idx - idx0 );
 141 
 142 
 143         if ( score > warper->best_score         ||
 144              ( score == warper->best_score    &&
 145                distort < warper->best_distort ) )
 146         {
 147           warper->best_score   = score;
 148           warper->best_distort = distort;
 149           warper->best_scale   = scale;
 150           warper->best_delta   = delta + ( idx - idx0 );
 151         }
 152       }
 153     }
 154   }
 155 
 156 
 157   /* Compute optimal scaling and delta values for a given glyph and */
 158   /* dimension.                                                     */
 159 
 160   FT_LOCAL_DEF( void )
 161   af_warper_compute( AF_Warper      warper,
 162                      AF_GlyphHints  hints,
 163                      AF_Dimension   dim,
 164                      FT_Fixed      *a_scale,
 165                      FT_Pos        *a_delta )
 166   {
 167     AF_AxisHints  axis;
 168     AF_Point      points;
 169 
 170     FT_Fixed      org_scale;
 171     FT_Pos        org_delta;
 172 
 173     FT_Int        nn, num_points, num_segments;
 174     FT_Int        X1, X2;
 175     FT_Int        w;
 176 
 177     AF_WarpScore  base_distort;
 178     AF_Segment    segments;
 179 
 180 
 181     /* get original scaling transformation */
 182     if ( dim == AF_DIMENSION_VERT )
 183     {
 184       org_scale = hints->y_scale;
 185       org_delta = hints->y_delta;
 186     }
 187     else
 188     {
 189       org_scale = hints->x_scale;
 190       org_delta = hints->x_delta;
 191     }
 192 
 193     warper->best_scale   = org_scale;
 194     warper->best_delta   = org_delta;
 195     warper->best_score   = FT_INT_MIN;
 196     warper->best_distort = 0;
 197 
 198     axis         = &hints->axis[dim];
 199     segments     = axis->segments;
 200     num_segments = axis->num_segments;
 201     points       = hints->points;
 202     num_points   = hints->num_points;
 203 
 204     *a_scale = org_scale;
 205     *a_delta = org_delta;
 206 
 207     /* get X1 and X2, minimum and maximum in original coordinates */
 208     if ( num_segments < 1 )
 209       return;
 210 
 211 #if 1
 212     X1 = X2 = points[0].fx;
 213     for ( nn = 1; nn < num_points; nn++ )
 214     {
 215       FT_Int  X = points[nn].fx;
 216 
 217 
 218       if ( X < X1 )
 219         X1 = X;
 220       if ( X > X2 )
 221         X2 = X;
 222     }
 223 #else
 224     X1 = X2 = segments[0].pos;
 225     for ( nn = 1; nn < num_segments; nn++ )
 226     {
 227       FT_Int  X = segments[nn].pos;
 228 
 229 
 230       if ( X < X1 )
 231         X1 = X;
 232       if ( X > X2 )
 233         X2 = X;
 234     }
 235 #endif
 236 
 237     if ( X1 >= X2 )
 238       return;
 239 
 240     warper->x1 = FT_MulFix( X1, org_scale ) + org_delta;
 241     warper->x2 = FT_MulFix( X2, org_scale ) + org_delta;
 242 
 243     warper->t1 = AF_WARPER_FLOOR( warper->x1 );
 244     warper->t2 = AF_WARPER_CEIL( warper->x2 );
 245 
 246     /* examine a half pixel wide range around the maximum coordinates */
 247     warper->x1min = warper->x1 & ~31;
 248     warper->x1max = warper->x1min + 32;
 249     warper->x2min = warper->x2 & ~31;
 250     warper->x2max = warper->x2min + 32;
 251 
 252     if ( warper->x1max > warper->x2 )
 253       warper->x1max = warper->x2;
 254 
 255     if ( warper->x2min < warper->x1 )
 256       warper->x2min = warper->x1;
 257 
 258     warper->w0 = warper->x2 - warper->x1;
 259 
 260     if ( warper->w0 <= 64 )
 261     {
 262       warper->x1max = warper->x1;
 263       warper->x2min = warper->x2;
 264     }
 265 
 266     /* examine (at most) a pixel wide range around the natural width */
 267     warper->wmin = warper->x2min - warper->x1max;
 268     warper->wmax = warper->x2max - warper->x1min;
 269 
 270 #if 1
 271     /* some heuristics to reduce the number of widths to be examined */
 272     {
 273       int  margin = 16;
 274 
 275 
 276       if ( warper->w0 <= 128 )
 277       {
 278          margin = 8;
 279          if ( warper->w0 <= 96 )
 280            margin = 4;
 281       }
 282 
 283       if ( warper->wmin < warper->w0 - margin )
 284         warper->wmin = warper->w0 - margin;
 285 
 286       if ( warper->wmax > warper->w0 + margin )
 287         warper->wmax = warper->w0 + margin;
 288     }
 289 
 290     if ( warper->wmin < warper->w0 * 3 / 4 )
 291       warper->wmin = warper->w0 * 3 / 4;
 292 
 293     if ( warper->wmax > warper->w0 * 5 / 4 )
 294       warper->wmax = warper->w0 * 5 / 4;
 295 #else
 296     /* no scaling, just translation */
 297     warper->wmin = warper->wmax = warper->w0;
 298 #endif
 299 
 300     for ( w = warper->wmin; w <= warper->wmax; w++ )
 301     {
 302       FT_Fixed  new_scale;
 303       FT_Pos    new_delta;
 304       FT_Pos    xx1, xx2;
 305 
 306 
 307       /* compute min and max positions for given width,       */
 308       /* assuring that they stay within the coordinate ranges */
 309       xx1 = warper->x1;
 310       xx2 = warper->x2;
 311       if ( w >= warper->w0 )
 312       {
 313         xx1 -= w - warper->w0;
 314         if ( xx1 < warper->x1min )
 315         {
 316           xx2 += warper->x1min - xx1;
 317           xx1  = warper->x1min;
 318         }
 319       }
 320       else
 321       {
 322         xx1 -= w - warper->w0;
 323         if ( xx1 > warper->x1max )
 324         {
 325           xx2 -= xx1 - warper->x1max;
 326           xx1  = warper->x1max;
 327         }
 328       }
 329 
 330       if ( xx1 < warper->x1 )
 331         base_distort = warper->x1 - xx1;
 332       else
 333         base_distort = xx1 - warper->x1;
 334 
 335       if ( xx2 < warper->x2 )
 336         base_distort += warper->x2 - xx2;
 337       else
 338         base_distort += xx2 - warper->x2;
 339 
 340       /* give base distortion a greater weight while scoring */
 341       base_distort *= 10;
 342 
 343       new_scale = org_scale + FT_DivFix( w - warper->w0, X2 - X1 );
 344       new_delta = xx1 - FT_MulFix( X1, new_scale );
 345 
 346       af_warper_compute_line_best( warper, new_scale, new_delta, xx1, xx2,
 347                                    base_distort,
 348                                    segments, num_segments );
 349     }
 350 
 351     {
 352       FT_Fixed  best_scale = warper->best_scale;
 353       FT_Pos    best_delta = warper->best_delta;
 354 
 355 
 356       hints->xmin_delta = FT_MulFix( X1, best_scale - org_scale )
 357                           + best_delta;
 358       hints->xmax_delta = FT_MulFix( X2, best_scale - org_scale )
 359                           + best_delta;
 360 
 361       *a_scale = best_scale;
 362       *a_delta = best_delta;
 363     }
 364   }
 365 
 366 #else /* !AF_CONFIG_OPTION_USE_WARPER */
 367 
 368   /* ANSI C doesn't like empty source files */
 369   typedef int  _af_warp_dummy;
 370 
 371 #endif /* !AF_CONFIG_OPTION_USE_WARPER */
 372 
 373 /* END */