1 /***************************************************************************/ 2 /* */ 3 /* afwarp.c */ 4 /* */ 5 /* Auto-fitter warping algorithm (body). */ 6 /* */ 7 /* Copyright 2006-2017 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 af_warper_compute_line_best(AF_Warper warper,FT_Fixed scale,FT_Pos delta,FT_Pos xx1,FT_Pos xx2,AF_WarpScore base_distort,AF_Segment segments,FT_Int num_segments)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 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 ) af_warper_compute(AF_Warper warper,AF_GlyphHints hints,AF_Dimension dim,FT_Fixed * a_scale,FT_Pos * a_delta)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_Int 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 = FT_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