1 /***************************************************************************/
5 /* Auto-fitter warping algorithm (body). */
7 /* Copyright 2006-2018 by */
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */
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. */
16 /***************************************************************************/
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.
28 #ifdef AF_CONFIG_OPTION_USE_WARPER
30 /*************************************************************************/
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. */
37 #define FT_COMPONENT trace_afwarp
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. */
44 static const AF_WarpScore
45 af_warper_weights
[64] =
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,
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,
54 static const AF_WarpScore
55 af_warper_weights
[64] =
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,
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,
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'). */
72 af_warper_compute_line_best( AF_Warper warper
,
77 AF_WarpScore base_distort
,
81 FT_Int idx_min
, idx_max
, idx0
;
83 AF_WarpScore scores
[65];
86 for ( nn
= 0; nn
< 65; nn
++ )
89 idx0
= xx1
- warper
->t1
;
91 /* compute minimum and maximum indices */
93 FT_Pos xx1min
= warper
->x1min
;
94 FT_Pos xx1max
= warper
->x1max
;
98 if ( xx1min
+ w
< warper
->x2min
)
99 xx1min
= warper
->x2min
- w
;
101 if ( xx1max
+ w
> warper
->x2max
)
102 xx1max
= warper
->x2max
- w
;
104 idx_min
= xx1min
- warper
->t1
;
105 idx_max
= xx1max
- warper
->t1
;
107 if ( idx_min
< 0 || idx_min
> idx_max
|| idx_max
> 64 )
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
));
119 for ( nn
= 0; nn
< num_segments
; nn
++ )
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
);
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
;
132 /* find best score */
137 for ( idx
= idx_min
; idx
<= idx_max
; idx
++ )
139 AF_WarpScore score
= scores
[idx
];
140 AF_WarpScore distort
= base_distort
+ ( idx
- idx0
);
143 if ( score
> warper
->best_score
||
144 ( score
== warper
->best_score
&&
145 distort
< warper
->best_distort
) )
147 warper
->best_score
= score
;
148 warper
->best_distort
= distort
;
149 warper
->best_scale
= scale
;
150 warper
->best_delta
= delta
+ ( idx
- idx0
);
157 /* Compute optimal scaling and delta values for a given glyph and */
161 af_warper_compute( AF_Warper warper
,
173 FT_Int nn
, num_points
, num_segments
;
177 AF_WarpScore base_distort
;
181 /* get original scaling transformation */
182 if ( dim
== AF_DIMENSION_VERT
)
184 org_scale
= hints
->y_scale
;
185 org_delta
= hints
->y_delta
;
189 org_scale
= hints
->x_scale
;
190 org_delta
= hints
->x_delta
;
193 warper
->best_scale
= org_scale
;
194 warper
->best_delta
= org_delta
;
195 warper
->best_score
= FT_INT_MIN
;
196 warper
->best_distort
= 0;
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
;
204 *a_scale
= org_scale
;
205 *a_delta
= org_delta
;
207 /* get X1 and X2, minimum and maximum in original coordinates */
208 if ( num_segments
< 1 )
212 X1
= X2
= points
[0].fx
;
213 for ( nn
= 1; nn
< num_points
; nn
++ )
215 FT_Int X
= points
[nn
].fx
;
224 X1
= X2
= segments
[0].pos
;
225 for ( nn
= 1; nn
< num_segments
; nn
++ )
227 FT_Int X
= segments
[nn
].pos
;
240 warper
->x1
= FT_MulFix( X1
, org_scale
) + org_delta
;
241 warper
->x2
= FT_MulFix( X2
, org_scale
) + org_delta
;
243 warper
->t1
= AF_WARPER_FLOOR( warper
->x1
);
244 warper
->t2
= AF_WARPER_CEIL( warper
->x2
);
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;
252 if ( warper
->x1max
> warper
->x2
)
253 warper
->x1max
= warper
->x2
;
255 if ( warper
->x2min
< warper
->x1
)
256 warper
->x2min
= warper
->x1
;
258 warper
->w0
= warper
->x2
- warper
->x1
;
260 if ( warper
->w0
<= 64 )
262 warper
->x1max
= warper
->x1
;
263 warper
->x2min
= warper
->x2
;
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
;
271 /* some heuristics to reduce the number of widths to be examined */
276 if ( warper
->w0
<= 128 )
279 if ( warper
->w0
<= 96 )
283 if ( warper
->wmin
< warper
->w0
- margin
)
284 warper
->wmin
= warper
->w0
- margin
;
286 if ( warper
->wmax
> warper
->w0
+ margin
)
287 warper
->wmax
= warper
->w0
+ margin
;
290 if ( warper
->wmin
< warper
->w0
* 3 / 4 )
291 warper
->wmin
= warper
->w0
* 3 / 4;
293 if ( warper
->wmax
> warper
->w0
* 5 / 4 )
294 warper
->wmax
= warper
->w0
* 5 / 4;
296 /* no scaling, just translation */
297 warper
->wmin
= warper
->wmax
= warper
->w0
;
300 for ( w
= warper
->wmin
; w
<= warper
->wmax
; w
++ )
307 /* compute min and max positions for given width, */
308 /* assuring that they stay within the coordinate ranges */
311 if ( w
>= warper
->w0
)
313 xx1
-= w
- warper
->w0
;
314 if ( xx1
< warper
->x1min
)
316 xx2
+= warper
->x1min
- xx1
;
322 xx1
-= w
- warper
->w0
;
323 if ( xx1
> warper
->x1max
)
325 xx2
-= xx1
- warper
->x1max
;
330 if ( xx1
< warper
->x1
)
331 base_distort
= warper
->x1
- xx1
;
333 base_distort
= xx1
- warper
->x1
;
335 if ( xx2
< warper
->x2
)
336 base_distort
+= warper
->x2
- xx2
;
338 base_distort
+= xx2
- warper
->x2
;
340 /* give base distortion a greater weight while scoring */
343 new_scale
= org_scale
+ FT_DivFix( w
- warper
->w0
, X2
- X1
);
344 new_delta
= xx1
- FT_MulFix( X1
, new_scale
);
346 af_warper_compute_line_best( warper
, new_scale
, new_delta
, xx1
, xx2
,
348 segments
, num_segments
);
352 FT_Fixed best_scale
= warper
->best_scale
;
353 FT_Pos best_delta
= warper
->best_delta
;
356 hints
->xmin_delta
= FT_MulFix( X1
, best_scale
- org_scale
)
358 hints
->xmax_delta
= FT_MulFix( X2
, best_scale
- org_scale
)
361 *a_scale
= best_scale
;
362 *a_delta
= best_delta
;
366 #else /* !AF_CONFIG_OPTION_USE_WARPER */
368 /* ANSI C doesn't like empty source files */
369 typedef int _af_warp_dummy
;
371 #endif /* !AF_CONFIG_OPTION_USE_WARPER */