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