src/autofit/afwarp.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  afwarp.c                                                               */
   4 /*                                                                         */
   5 /*    Auto-fitter warping algorithm (body).                                */
   6 /*                                                                         */
   7 /*  Copyright 2006, 2007 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 #include "afwarp.h"
  20
  21 #ifdef AF_USE_WARPER
  22
  23 #if 1
  24   static const AF_WarpScore
  25   af_warper_weights[64] =
  26   {
  27     35, 32, 30, 25, 20, 15, 12, 10,  5,  1,  0,  0,  0,  0,  0,  0,
  28      0,  0,  0,  0,  0,  0, -1, -2, -5, -8,-10,-10,-20,-20,-30,-30,
  29
  30    -30,-30,-20,-20,-10,-10, -8, -5, -2, -1,  0,  0,  0,  0,  0,  0,
  31      0,  0,  0,  0,  0,  0,  0,  1,  5, 10, 12, 15, 20, 25, 30, 32,
  32   };
  33 #else
  34   static const AF_WarpScore
  35   af_warper_weights[64] =
  36   {
  37     30, 20, 10,  5,  4,  4,  3,  2,  1,  0,  0,  0,  0,  0,  0,  0,
  38      0,  0,  0,  0,  0,  0,  0, -1, -2, -2, -5, -5,-10,-10,-15,-20,
  39
  40    -20,-15,-15,-10,-10, -5, -5, -2, -2, -1,  0,  0,  0,  0,  0,  0,
  41      0,  0,  0,  0,  0,  0,  0,  0,  1,  2,  3,  4,  4,  5, 10, 20,
  42   };
  43 #endif
  44
  45
  46   static void
  47   af_warper_compute_line_best( AF_Warper     warper,
  48                                FT_Fixed      scale,
  49                                FT_Pos        delta,
  50                                FT_Pos        xx1,
  51                                FT_Pos        xx2,
  52                                AF_WarpScore  base_distort,
  53                                AF_Segment    segments,
  54                                FT_UInt       num_segments )
  55   {
  56     FT_Int        idx_min, idx_max, idx0;
  57     FT_UInt       nn;
  58     AF_WarpScore  scores[65];
  59
  60
  61     for ( nn = 0; nn < 65; nn++ )
  62       scores[nn] = 0;
  63
  64     idx0 = xx1 - warper->t1;
  65
  66     /* compute minimum and maximum indices */
  67     {
  68       FT_Pos  xx1min = warper->x1min;
  69       FT_Pos  xx1max = warper->x1max;
  70       FT_Pos  w      = xx2 - xx1;
  71
  72
  73       if ( xx1min + w < warper->x2min )
  74         xx1min = warper->x2min - w;
  75
  76       xx1max = warper->x1max;
  77       if ( xx1max + w > warper->x2max )
  78         xx1max = warper->x2max - w;
  79
  80       idx_min = xx1min - warper->t1;
  81       idx_max = xx1max - warper->t1;
  82
  83       if ( idx_min < 0 || idx_min > idx_max || idx_max > 64 )
  84       {
  85         AF_LOG(( "invalid indices:\n"
  86                  "  min=%d max=%d, xx1=%ld xx2=%ld,\n"
  87                  "  x1min=%ld x1max=%ld, x2min=%ld x2max=%ld\n",
  88                  idx_min, idx_max, xx1, xx2,
  89                  warper->x1min, warper->x1max,
  90                  warper->x2min, warper->x2max ));
  91         return;
  92       }
  93     }
  94
  95     for ( nn = 0; nn < num_segments; nn++ )
  96     {
  97       FT_Pos  len = segments[nn].max_coord - segments[nn].min_coord;
  98       FT_Pos  y0  = FT_MulFix( segments[nn].pos, scale ) + delta;
  99       FT_Pos  y   = y0 + ( idx_min - idx0 );
 100       FT_Int  idx;
 101
 102
 103       for ( idx = idx_min; idx <= idx_max; idx++, y++ )
 104         scores[idx] += af_warper_weights[y & 63] * len;
 105     }
 106
 107     /* find best score */
 108     {
 109       FT_Int  idx;
 110
 111
 112       for ( idx = idx_min; idx <= idx_max; idx++ )
 113       {
 114         AF_WarpScore  score = scores[idx];
 115         AF_WarpScore  distort = base_distort + ( idx - idx0 );
 116
 117
 118         if ( score > warper->best_score           ||
 119              ( score == warper->best_score    &&
 120                distort < warper->best_distort )   )
 121         {
 122           warper->best_score   = score;
 123           warper->best_distort = distort;
 124           warper->best_scale   = scale;
 125           warper->best_delta   = delta + ( idx - idx0 );
 126         }
 127       }
 128     }
 129   }
 130
 131
 132   FT_LOCAL_DEF( void )
 133   af_warper_compute( AF_Warper      warper,
 134                      AF_GlyphHints  hints,
 135                      AF_Dimension   dim,
 136                      FT_Fixed      *a_scale,
 137                      FT_Pos        *a_delta )
 138   {
 139     AF_AxisHints  axis;
 140     AF_Point      points;
 141
 142     FT_Fixed      org_scale;
 143     FT_Pos        org_delta;
 144
 145     FT_UInt       nn, num_points, num_segments;
 146     FT_Int        X1, X2;
 147     FT_Int        w;
 148
 149     AF_WarpScore  base_distort;
 150     AF_Segment    segments;
 151
 152
 153     /* get original scaling transformation */
 154     if ( dim == AF_DIMENSION_VERT )
 155     {
 156       org_scale = hints->y_scale;
 157       org_delta = hints->y_delta;
 158     }
 159     else
 160     {
 161       org_scale = hints->x_scale;
 162       org_delta = hints->x_delta;
 163     }
 164
 165     warper->best_scale   = org_scale;
 166     warper->best_delta   = org_delta;
 167     warper->best_score   = INT_MIN;
 168     warper->best_distort = 0;
 169
 170     axis         = &hints->axis[dim];
 171     segments     = axis->segments;
 172     num_segments = axis->num_segments;
 173     points       = hints->points;
 174     num_points   = hints->num_points;
 175
 176     *a_scale = org_scale;
 177     *a_delta = org_delta;
 178
 179     /* get X1 and X2, minimum and maximum in original coordinates */
 180     if ( num_segments < 1 )
 181       return;
 182
 183 #if 1
 184     X1 = X2 = points[0].fx;
 185     for ( nn = 1; nn < num_points; nn++ )
 186     {
 187       FT_Int  X = points[nn].fx;
 188
 189
 190       if ( X < X1 )
 191         X1 = X;
 192       if ( X > X2 )
 193         X2 = X;
 194     }
 195 #else
 196     X1 = X2 = segments[0].pos;
 197     for ( nn = 1; nn < num_segments; nn++ )
 198     {
 199       FT_Int  X = segments[nn].pos;
 200
 201
 202       if ( X < X1 )
 203         X1 = X;
 204       if ( X > X2 )
 205         X2 = X;
 206     }
 207 #endif
 208
 209     if ( X1 >= X2 )
 210       return;
 211
 212     warper->x1 = FT_MulFix( X1, org_scale ) + org_delta;
 213     warper->x2 = FT_MulFix( X2, org_scale ) + org_delta;
 214
 215     warper->t1 = AF_WARPER_FLOOR( warper->x1 );
 216     warper->t2 = AF_WARPER_CEIL( warper->x2 );
 217
 218     warper->x1min = warper->x1 & ~31;
 219     warper->x1max = warper->x1min + 32;
 220     warper->x2min = warper->x2 & ~31;
 221     warper->x2max = warper->x2min + 32;
 222
 223     if ( warper->x1max > warper->x2 )
 224       warper->x1max = warper->x2;
 225
 226     if ( warper->x2min < warper->x1 )
 227       warper->x2min = warper->x1;
 228
 229     warper->w0 = warper->x2 - warper->x1;
 230
 231     if ( warper->w0 <= 64 )
 232     {
 233       warper->x1max = warper->x1;
 234       warper->x2min = warper->x2;
 235     }
 236
 237     warper->wmin = warper->x2min - warper->x1max;
 238     warper->wmax = warper->x2max - warper->x1min;
 239
 240 #if 1
 241     {
 242       int  margin = 16;
 243
 244
 245       if ( warper->w0 <= 128 )
 246       {
 247          margin = 8;
 248          if ( warper->w0 <= 96 )
 249            margin = 4;
 250       }
 251
 252       if ( warper->wmin < warper->w0 - margin )
 253         warper->wmin = warper->w0 - margin;
 254
 255       if ( warper->wmax > warper->w0 + margin )
 256         warper->wmax = warper->w0 + margin;
 257     }
 258
 259     if ( warper->wmin < warper->w0 * 3 / 4 )
 260       warper->wmin = warper->w0 * 3 / 4;
 261
 262     if ( warper->wmax > warper->w0 * 5 / 4 )
 263       warper->wmax = warper->w0 * 5 / 4;
 264 #else
 265     /* no scaling, just translation */
 266     warper->wmin = warper->wmax = warper->w0;
 267 #endif
 268
 269     for ( w = warper->wmin; w <= warper->wmax; w++ )
 270     {
 271       FT_Fixed  new_scale;
 272       FT_Pos    new_delta;
 273       FT_Pos    xx1, xx2;
 274
 275
 276       xx1 = warper->x1;
 277       xx2 = warper->x2;
 278       if ( w >= warper->w0 )
 279       {
 280         xx1 -= w - warper->w0;
 281         if ( xx1 < warper->x1min )
 282         {
 283           xx2 += warper->x1min - xx1;
 284           xx1  = warper->x1min;
 285         }
 286       }
 287       else
 288       {
 289         xx1 -= w - warper->w0;
 290         if ( xx1 > warper->x1max )
 291         {
 292           xx2 -= xx1 - warper->x1max;
 293           xx1  = warper->x1max;
 294         }
 295       }
 296
 297       if ( xx1 < warper->x1 )
 298         base_distort = warper->x1 - xx1;
 299       else
 300         base_distort = xx1 - warper->x1;
 301
 302       if ( xx2 < warper->x2 )
 303         base_distort += warper->x2 - xx2;
 304       else
 305         base_distort += xx2 - warper->x2;
 306
 307       base_distort *= 10;
 308
 309       new_scale = org_scale + FT_DivFix( w - warper->w0, X2 - X1 );
 310       new_delta = xx1 - FT_MulFix( X1, new_scale );
 311
 312       af_warper_compute_line_best( warper, new_scale, new_delta, xx1, xx2,
 313                                    base_distort,
 314                                    segments, num_segments );
 315     }
 316
 317     {
 318       FT_Fixed  best_scale = warper->best_scale;
 319       FT_Pos    best_delta = warper->best_delta;
 320
 321
 322       hints->xmin_delta = FT_MulFix( X1, best_scale - org_scale )
 323                           + best_delta;
 324       hints->xmax_delta = FT_MulFix( X2, best_scale - org_scale )
 325                           + best_delta;
 326
 327       *a_scale = best_scale;
 328       *a_delta = best_delta;
 329     }
 330   }
 331
 332 #else /* !AF_USE_WARPER */
 333
 334 char  af_warper_dummy = 0;  /* make compiler happy */
 335
 336 #endif /* !AF_USE_WARPER */
 337
 338 /* END */