misc/libfreetype/src/autofit/afwarp.c
changeset 5172 88f2e05288ba
equal deleted inserted replaced
5171:f9283dc4860d 5172:88f2e05288ba
       
     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 */