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