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 */
374