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 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 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 ) af_warper_compute(AF_Warper warper,AF_GlyphHints hints,AF_Dimension dim,FT_Fixed * a_scale,FT_Pos * a_delta)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