1 /***************************************************************************/ 2 /* */ 3 /* afhints.c */ 4 /* */ 5 /* Auto-fitter hinting routines (body). */ 6 /* */ 7 /* Copyright 2003-2007, 2009-2014 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 #include "afhints.h" 20 #include "aferrors.h" 21 #include FT_INTERNAL_CALC_H 22 #include FT_INTERNAL_DEBUG_H 23 24 25 /*************************************************************************/ 26 /* */ 27 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */ 28 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */ 29 /* messages during execution. */ 30 /* */ 31 #undef FT_COMPONENT 32 #define FT_COMPONENT trace_afhints 33 34 35 /* Get new segment for given axis. */ 36 37 FT_LOCAL_DEF( FT_Error ) 38 af_axis_hints_new_segment( AF_AxisHints axis, 39 FT_Memory memory, 40 AF_Segment *asegment ) 41 { 42 FT_Error error = FT_Err_Ok; 43 AF_Segment segment = NULL; 44 45 46 if ( axis->num_segments >= axis->max_segments ) 47 { 48 FT_Int old_max = axis->max_segments; 49 FT_Int new_max = old_max; 50 FT_Int big_max = (FT_Int)( FT_INT_MAX / sizeof ( *segment ) ); 51 52 53 if ( old_max >= big_max ) 54 { 55 error = FT_THROW( Out_Of_Memory ); 56 goto Exit; 57 } 58 59 new_max += ( new_max >> 2 ) + 4; 60 if ( new_max < old_max || new_max > big_max ) 61 new_max = big_max; 62 63 if ( FT_RENEW_ARRAY( axis->segments, old_max, new_max ) ) 64 goto Exit; 65 66 axis->max_segments = new_max; 67 } 68 69 segment = axis->segments + axis->num_segments++; 70 71 Exit: 72 *asegment = segment; 73 return error; 74 } 75 76 77 /* Get new edge for given axis, direction, and position. */ 78 79 FT_LOCAL( FT_Error ) 80 af_axis_hints_new_edge( AF_AxisHints axis, 81 FT_Int fpos, 82 AF_Direction dir, 83 FT_Memory memory, 84 AF_Edge *anedge ) 85 { 86 FT_Error error = FT_Err_Ok; 87 AF_Edge edge = NULL; 88 AF_Edge edges; 89 90 91 if ( axis->num_edges >= axis->max_edges ) 92 { 93 FT_Int old_max = axis->max_edges; 94 FT_Int new_max = old_max; 95 FT_Int big_max = (FT_Int)( FT_INT_MAX / sizeof ( *edge ) ); 96 97 98 if ( old_max >= big_max ) 99 { 100 error = FT_THROW( Out_Of_Memory ); 101 goto Exit; 102 } 103 104 new_max += ( new_max >> 2 ) + 4; 105 if ( new_max < old_max || new_max > big_max ) 106 new_max = big_max; 107 108 if ( FT_RENEW_ARRAY( axis->edges, old_max, new_max ) ) 109 goto Exit; 110 111 axis->max_edges = new_max; 112 } 113 114 edges = axis->edges; 115 edge = edges + axis->num_edges; 116 117 while ( edge > edges ) 118 { 119 if ( edge[-1].fpos < fpos ) 120 break; 121 122 /* we want the edge with same position and minor direction */ 123 /* to appear before those in the major one in the list */ 124 if ( edge[-1].fpos == fpos && dir == axis->major_dir ) 125 break; 126 127 edge[0] = edge[-1]; 128 edge--; 129 } 130 131 axis->num_edges++; 132 133 FT_ZERO( edge ); 134 edge->fpos = (FT_Short)fpos; 135 edge->dir = (FT_Char)dir; 136 137 Exit: 138 *anedge = edge; 139 return error; 140 } 141 142 143 #ifdef FT_DEBUG_AUTOFIT 144 145 #include FT_CONFIG_STANDARD_LIBRARY_H 146 147 /* The dump functions are used in the `ftgrid' demo program, too. */ 148 #define AF_DUMP( varformat ) \ 149 do \ 150 { \ 151 if ( to_stdout ) \ 152 printf varformat; \ 153 else \ 154 FT_TRACE7( varformat ); \ 155 } while ( 0 ) 156 157 158 static const char* 159 af_dir_str( AF_Direction dir ) 160 { 161 const char* result; 162 163 164 switch ( dir ) 165 { 166 case AF_DIR_UP: 167 result = "up"; 168 break; 169 case AF_DIR_DOWN: 170 result = "down"; 171 break; 172 case AF_DIR_LEFT: 173 result = "left"; 174 break; 175 case AF_DIR_RIGHT: 176 result = "right"; 177 break; 178 default: 179 result = "none"; 180 } 181 182 return result; 183 } 184 185 186 #define AF_INDEX_NUM( ptr, base ) ( (ptr) ? ( (ptr) - (base) ) : -1 ) 187 188 189 #ifdef __cplusplus 190 extern "C" { 191 #endif 192 void 193 af_glyph_hints_dump_points( AF_GlyphHints hints, 194 FT_Bool to_stdout ) 195 { 196 AF_Point points = hints->points; 197 AF_Point limit = points + hints->num_points; 198 AF_Point point; 199 200 201 AF_DUMP(( "Table of points:\n" 202 " [ index | xorg | yorg | xscale | yscale" 203 " | xfit | yfit | flags ]\n" )); 204 205 for ( point = points; point < limit; point++ ) 206 AF_DUMP(( " [ %5d | %5d | %5d | %6.2f | %6.2f" 207 " | %5.2f | %5.2f | %c%c%c%c%c%c ]\n", 208 point - points, 209 point->fx, 210 point->fy, 211 point->ox / 64.0, 212 point->oy / 64.0, 213 point->x / 64.0, 214 point->y / 64.0, 215 ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) ? 'w' : ' ', 216 ( point->flags & AF_FLAG_INFLECTION ) ? 'i' : ' ', 217 ( point->flags & AF_FLAG_EXTREMA_X ) ? '<' : ' ', 218 ( point->flags & AF_FLAG_EXTREMA_Y ) ? 'v' : ' ', 219 ( point->flags & AF_FLAG_ROUND_X ) ? '(' : ' ', 220 ( point->flags & AF_FLAG_ROUND_Y ) ? 'u' : ' ')); 221 AF_DUMP(( "\n" )); 222 } 223 #ifdef __cplusplus 224 } 225 #endif 226 227 228 static const char* 229 af_edge_flags_to_string( AF_Edge_Flags flags ) 230 { 231 static char temp[32]; 232 int pos = 0; 233 234 235 if ( flags & AF_EDGE_ROUND ) 236 { 237 ft_memcpy( temp + pos, "round", 5 ); 238 pos += 5; 239 } 240 if ( flags & AF_EDGE_SERIF ) 241 { 242 if ( pos > 0 ) 243 temp[pos++] = ' '; 244 ft_memcpy( temp + pos, "serif", 5 ); 245 pos += 5; 246 } 247 if ( pos == 0 ) 248 return "normal"; 249 250 temp[pos] = '\0'; 251 252 return temp; 253 } 254 255 256 /* Dump the array of linked segments. */ 257 258 #ifdef __cplusplus 259 extern "C" { 260 #endif 261 void 262 af_glyph_hints_dump_segments( AF_GlyphHints hints, 263 FT_Bool to_stdout ) 264 { 265 FT_Int dimension; 266 267 268 for ( dimension = 1; dimension >= 0; dimension-- ) 269 { 270 AF_AxisHints axis = &hints->axis[dimension]; 271 AF_Point points = hints->points; 272 AF_Edge edges = axis->edges; 273 AF_Segment segments = axis->segments; 274 AF_Segment limit = segments + axis->num_segments; 275 AF_Segment seg; 276 277 278 AF_DUMP(( "Table of %s segments:\n", 279 dimension == AF_DIMENSION_HORZ ? "vertical" 280 : "horizontal" )); 281 if ( axis->num_segments ) 282 AF_DUMP(( " [ index | pos | dir | from" 283 " | to | link | serif | edge" 284 " | height | extra | flags ]\n" )); 285 else 286 AF_DUMP(( " (none)\n" )); 287 288 for ( seg = segments; seg < limit; seg++ ) 289 AF_DUMP(( " [ %5d | %5.2g | %5s | %4d" 290 " | %4d | %4d | %5d | %4d" 291 " | %6d | %5d | %11s ]\n", 292 seg - segments, 293 dimension == AF_DIMENSION_HORZ 294 ? (int)seg->first->ox / 64.0 295 : (int)seg->first->oy / 64.0, 296 af_dir_str( (AF_Direction)seg->dir ), 297 AF_INDEX_NUM( seg->first, points ), 298 AF_INDEX_NUM( seg->last, points ), 299 AF_INDEX_NUM( seg->link, segments ), 300 AF_INDEX_NUM( seg->serif, segments ), 301 AF_INDEX_NUM( seg->edge, edges ), 302 seg->height, 303 seg->height - ( seg->max_coord - seg->min_coord ), 304 af_edge_flags_to_string( (AF_Edge_Flags)seg->flags ) )); 305 AF_DUMP(( "\n" )); 306 } 307 } 308 #ifdef __cplusplus 309 } 310 #endif 311 312 313 /* Fetch number of segments. */ 314 315 #ifdef __cplusplus 316 extern "C" { 317 #endif 318 FT_Error 319 af_glyph_hints_get_num_segments( AF_GlyphHints hints, 320 FT_Int dimension, 321 FT_Int* num_segments ) 322 { 323 AF_Dimension dim; 324 AF_AxisHints axis; 325 326 327 dim = ( dimension == 0 ) ? AF_DIMENSION_HORZ : AF_DIMENSION_VERT; 328 329 axis = &hints->axis[dim]; 330 *num_segments = axis->num_segments; 331 332 return FT_Err_Ok; 333 } 334 #ifdef __cplusplus 335 } 336 #endif 337 338 339 /* Fetch offset of segments into user supplied offset array. */ 340 341 #ifdef __cplusplus 342 extern "C" { 343 #endif 344 FT_Error 345 af_glyph_hints_get_segment_offset( AF_GlyphHints hints, 346 FT_Int dimension, 347 FT_Int idx, 348 FT_Pos *offset, 349 FT_Bool *is_blue, 350 FT_Pos *blue_offset ) 351 { 352 AF_Dimension dim; 353 AF_AxisHints axis; 354 AF_Segment seg; 355 356 357 if ( !offset ) 358 return FT_THROW( Invalid_Argument ); 359 360 dim = ( dimension == 0 ) ? AF_DIMENSION_HORZ : AF_DIMENSION_VERT; 361 362 axis = &hints->axis[dim]; 363 364 if ( idx < 0 || idx >= axis->num_segments ) 365 return FT_THROW( Invalid_Argument ); 366 367 seg = &axis->segments[idx]; 368 *offset = ( dim == AF_DIMENSION_HORZ ) ? seg->first->ox 369 : seg->first->oy; 370 if ( seg->edge ) 371 *is_blue = (FT_Bool)( seg->edge->blue_edge != 0 ); 372 else 373 *is_blue = FALSE; 374 375 if ( *is_blue ) 376 *blue_offset = seg->edge->blue_edge->cur; 377 else 378 *blue_offset = 0; 379 380 return FT_Err_Ok; 381 } 382 #ifdef __cplusplus 383 } 384 #endif 385 386 387 /* Dump the array of linked edges. */ 388 389 #ifdef __cplusplus 390 extern "C" { 391 #endif 392 void 393 af_glyph_hints_dump_edges( AF_GlyphHints hints, 394 FT_Bool to_stdout ) 395 { 396 FT_Int dimension; 397 398 399 for ( dimension = 1; dimension >= 0; dimension-- ) 400 { 401 AF_AxisHints axis = &hints->axis[dimension]; 402 AF_Edge edges = axis->edges; 403 AF_Edge limit = edges + axis->num_edges; 404 AF_Edge edge; 405 406 407 /* 408 * note: AF_DIMENSION_HORZ corresponds to _vertical_ edges 409 * since they have a constant X coordinate. 410 */ 411 AF_DUMP(( "Table of %s edges:\n", 412 dimension == AF_DIMENSION_HORZ ? "vertical" 413 : "horizontal" )); 414 if ( axis->num_edges ) 415 AF_DUMP(( " [ index | pos | dir | link" 416 " | serif | blue | opos | pos | flags ]\n" )); 417 else 418 AF_DUMP(( " (none)\n" )); 419 420 for ( edge = edges; edge < limit; edge++ ) 421 AF_DUMP(( " [ %5d | %5.2g | %5s | %4d" 422 " | %5d | %c | %5.2f | %5.2f | %11s ]\n", 423 edge - edges, 424 (int)edge->opos / 64.0, 425 af_dir_str( (AF_Direction)edge->dir ), 426 AF_INDEX_NUM( edge->link, edges ), 427 AF_INDEX_NUM( edge->serif, edges ), 428 edge->blue_edge ? 'y' : 'n', 429 edge->opos / 64.0, 430 edge->pos / 64.0, 431 af_edge_flags_to_string( (AF_Edge_Flags)edge->flags ) )); 432 AF_DUMP(( "\n" )); 433 } 434 } 435 #ifdef __cplusplus 436 } 437 #endif 438 439 #undef AF_DUMP 440 441 #endif /* !FT_DEBUG_AUTOFIT */ 442 443 444 /* Compute the direction value of a given vector. */ 445 446 FT_LOCAL_DEF( AF_Direction ) 447 af_direction_compute( FT_Pos dx, 448 FT_Pos dy ) 449 { 450 FT_Pos ll, ss; /* long and short arm lengths */ 451 AF_Direction dir; /* candidate direction */ 452 453 454 if ( dy >= dx ) 455 { 456 if ( dy >= -dx ) 457 { 458 dir = AF_DIR_UP; 459 ll = dy; 460 ss = dx; 461 } 462 else 463 { 464 dir = AF_DIR_LEFT; 465 ll = -dx; 466 ss = dy; 467 } 468 } 469 else /* dy < dx */ 470 { 471 if ( dy >= -dx ) 472 { 473 dir = AF_DIR_RIGHT; 474 ll = dx; 475 ss = dy; 476 } 477 else 478 { 479 dir = AF_DIR_DOWN; 480 ll = dy; 481 ss = dx; 482 } 483 } 484 485 /* return no direction if arm lengths differ too much */ 486 /* (value 14 is heuristic, corresponding to approx. 4.1 degrees) */ 487 ss *= 14; 488 if ( FT_ABS( ll ) <= FT_ABS( ss ) ) 489 dir = AF_DIR_NONE; 490 491 return dir; 492 } 493 494 495 FT_LOCAL_DEF( void ) 496 af_glyph_hints_init( AF_GlyphHints hints, 497 FT_Memory memory ) 498 { 499 FT_ZERO( hints ); 500 hints->memory = memory; 501 } 502 503 504 FT_LOCAL_DEF( void ) 505 af_glyph_hints_done( AF_GlyphHints hints ) 506 { 507 FT_Memory memory = hints->memory; 508 int dim; 509 510 511 if ( !( hints && hints->memory ) ) 512 return; 513 514 /* 515 * note that we don't need to free the segment and edge 516 * buffers since they are really within the hints->points array 517 */ 518 for ( dim = 0; dim < AF_DIMENSION_MAX; dim++ ) 519 { 520 AF_AxisHints axis = &hints->axis[dim]; 521 522 523 axis->num_segments = 0; 524 axis->max_segments = 0; 525 FT_FREE( axis->segments ); 526 527 axis->num_edges = 0; 528 axis->max_edges = 0; 529 FT_FREE( axis->edges ); 530 } 531 532 FT_FREE( hints->contours ); 533 hints->max_contours = 0; 534 hints->num_contours = 0; 535 536 FT_FREE( hints->points ); 537 hints->num_points = 0; 538 hints->max_points = 0; 539 540 hints->memory = NULL; 541 } 542 543 544 /* Reset metrics. */ 545 546 FT_LOCAL_DEF( void ) 547 af_glyph_hints_rescale( AF_GlyphHints hints, 548 AF_StyleMetrics metrics ) 549 { 550 hints->metrics = metrics; 551 hints->scaler_flags = metrics->scaler.flags; 552 } 553 554 555 /* Recompute all AF_Point in AF_GlyphHints from the definitions */ 556 /* in a source outline. */ 557 558 FT_LOCAL_DEF( FT_Error ) 559 af_glyph_hints_reload( AF_GlyphHints hints, 560 FT_Outline* outline ) 561 { 562 FT_Error error = FT_Err_Ok; 563 AF_Point points; 564 FT_UInt old_max, new_max; 565 FT_Fixed x_scale = hints->x_scale; 566 FT_Fixed y_scale = hints->y_scale; 567 FT_Pos x_delta = hints->x_delta; 568 FT_Pos y_delta = hints->y_delta; 569 FT_Memory memory = hints->memory; 570 571 572 hints->num_points = 0; 573 hints->num_contours = 0; 574 575 hints->axis[0].num_segments = 0; 576 hints->axis[0].num_edges = 0; 577 hints->axis[1].num_segments = 0; 578 hints->axis[1].num_edges = 0; 579 580 /* first of all, reallocate the contours array if necessary */ 581 new_max = (FT_UInt)outline->n_contours; 582 old_max = hints->max_contours; 583 if ( new_max > old_max ) 584 { 585 new_max = ( new_max + 3 ) & ~3; /* round up to a multiple of 4 */ 586 587 if ( FT_RENEW_ARRAY( hints->contours, old_max, new_max ) ) 588 goto Exit; 589 590 hints->max_contours = new_max; 591 } 592 593 /* 594 * then reallocate the points arrays if necessary -- 595 * note that we reserve two additional point positions, used to 596 * hint metrics appropriately 597 */ 598 new_max = (FT_UInt)( outline->n_points + 2 ); 599 old_max = hints->max_points; 600 if ( new_max > old_max ) 601 { 602 new_max = ( new_max + 2 + 7 ) & ~7; /* round up to a multiple of 8 */ 603 604 if ( FT_RENEW_ARRAY( hints->points, old_max, new_max ) ) 605 goto Exit; 606 607 hints->max_points = new_max; 608 } 609 610 hints->num_points = outline->n_points; 611 hints->num_contours = outline->n_contours; 612 613 /* We can't rely on the value of `FT_Outline.flags' to know the fill */ 614 /* direction used for a glyph, given that some fonts are broken (e.g., */ 615 /* the Arphic ones). We thus recompute it each time we need to. */ 616 /* */ 617 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_UP; 618 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_LEFT; 619 620 if ( FT_Outline_Get_Orientation( outline ) == FT_ORIENTATION_POSTSCRIPT ) 621 { 622 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_DOWN; 623 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_RIGHT; 624 } 625 626 hints->x_scale = x_scale; 627 hints->y_scale = y_scale; 628 hints->x_delta = x_delta; 629 hints->y_delta = y_delta; 630 631 hints->xmin_delta = 0; 632 hints->xmax_delta = 0; 633 634 points = hints->points; 635 if ( hints->num_points == 0 ) 636 goto Exit; 637 638 { 639 AF_Point point; 640 AF_Point point_limit = points + hints->num_points; 641 642 643 /* compute coordinates & Bezier flags, next and prev */ 644 { 645 FT_Vector* vec = outline->points; 646 char* tag = outline->tags; 647 AF_Point end = points + outline->contours[0]; 648 AF_Point prev = end; 649 FT_Int contour_index = 0; 650 651 652 for ( point = points; point < point_limit; point++, vec++, tag++ ) 653 { 654 point->in_dir = (FT_Char)AF_DIR_NONE; 655 point->out_dir = (FT_Char)AF_DIR_NONE; 656 657 point->fx = (FT_Short)vec->x; 658 point->fy = (FT_Short)vec->y; 659 point->ox = point->x = FT_MulFix( vec->x, x_scale ) + x_delta; 660 point->oy = point->y = FT_MulFix( vec->y, y_scale ) + y_delta; 661 662 switch ( FT_CURVE_TAG( *tag ) ) 663 { 664 case FT_CURVE_TAG_CONIC: 665 point->flags = AF_FLAG_CONIC; 666 break; 667 case FT_CURVE_TAG_CUBIC: 668 point->flags = AF_FLAG_CUBIC; 669 break; 670 default: 671 point->flags = AF_FLAG_NONE; 672 } 673 674 point->prev = prev; 675 prev->next = point; 676 prev = point; 677 678 if ( point == end ) 679 { 680 if ( ++contour_index < outline->n_contours ) 681 { 682 end = points + outline->contours[contour_index]; 683 prev = end; 684 } 685 } 686 } 687 } 688 689 /* set up the contours array */ 690 { 691 AF_Point* contour = hints->contours; 692 AF_Point* contour_limit = contour + hints->num_contours; 693 short* end = outline->contours; 694 short idx = 0; 695 696 697 for ( ; contour < contour_limit; contour++, end++ ) 698 { 699 contour[0] = points + idx; 700 idx = (short)( end[0] + 1 ); 701 } 702 } 703 704 { 705 /* 706 * Compute directions of `in' and `out' vectors. 707 * 708 * Note that distances between points that are very near to each 709 * other are accumulated. In other words, the auto-hinter 710 * prepends the small vectors between near points to the first 711 * non-near vector. All intermediate points are tagged as 712 * weak; the directions are adjusted also to be equal to the 713 * accumulated one. 714 */ 715 716 /* value 20 in `near_limit' is heuristic */ 717 FT_UInt units_per_em = hints->metrics->scaler.face->units_per_EM; 718 FT_Int near_limit = 20 * units_per_em / 2048; 719 FT_Int near_limit2 = 2 * near_limit - 1; 720 721 AF_Point* contour; 722 AF_Point* contour_limit = hints->contours + hints->num_contours; 723 724 725 for ( contour = hints->contours; contour < contour_limit; contour++ ) 726 { 727 AF_Point first = *contour; 728 AF_Point next, prev, curr; 729 730 FT_Pos out_x, out_y; 731 732 FT_Bool is_first; 733 734 735 /* since the first point of a contour could be part of a */ 736 /* series of near points, go backwards to find the first */ 737 /* non-near point and adjust `first' */ 738 739 point = first; 740 prev = first->prev; 741 742 while ( prev != first ) 743 { 744 out_x = point->fx - prev->fx; 745 out_y = point->fy - prev->fy; 746 747 /* 748 * We use Taxicab metrics to measure the vector length. 749 * 750 * Note that the accumulated distances so far could have the 751 * opposite direction of the distance measured here. For this 752 * reason we use `near_limit2' for the comparison to get a 753 * non-near point even in the worst case. 754 */ 755 if ( FT_ABS( out_x ) + FT_ABS( out_y ) >= near_limit2 ) 756 break; 757 758 point = prev; 759 prev = prev->prev; 760 } 761 762 /* adjust first point */ 763 first = point; 764 765 /* now loop over all points of the contour to get */ 766 /* `in' and `out' vector directions */ 767 768 curr = first; 769 770 /* 771 * We abuse the `u' and `v' fields to store index deltas to the 772 * next and previous non-near point, respectively. 773 * 774 * To avoid problems with not having non-near points, we point to 775 * `first' by default as the next non-near point. 776 * 777 */ 778 curr->u = (FT_Pos)( first - curr ); 779 first->v = -curr->u; 780 781 out_x = 0; 782 out_y = 0; 783 784 is_first = 1; 785 786 for ( point = first; 787 point != first || is_first; 788 point = point->next ) 789 { 790 AF_Direction out_dir; 791 792 793 is_first = 0; 794 795 next = point->next; 796 797 out_x += next->fx - point->fx; 798 out_y += next->fy - point->fy; 799 800 if ( FT_ABS( out_x ) + FT_ABS( out_y ) < near_limit ) 801 { 802 next->flags |= AF_FLAG_WEAK_INTERPOLATION; 803 continue; 804 } 805 806 curr->u = (FT_Pos)( next - curr ); 807 next->v = -curr->u; 808 809 out_dir = af_direction_compute( out_x, out_y ); 810 811 /* adjust directions for all points inbetween; */ 812 /* the loop also updates position of `curr' */ 813 curr->out_dir = (FT_Char)out_dir; 814 for ( curr = curr->next; curr != next; curr = curr->next ) 815 { 816 curr->in_dir = (FT_Char)out_dir; 817 curr->out_dir = (FT_Char)out_dir; 818 } 819 next->in_dir = (FT_Char)out_dir; 820 821 curr->u = (FT_Pos)( first - curr ); 822 first->v = -curr->u; 823 824 out_x = 0; 825 out_y = 0; 826 } 827 } 828 829 /* 830 * The next step is to `simplify' an outline's topology so that we 831 * can identify local extrema more reliably: A series of 832 * non-horizontal or non-vertical vectors pointing into the same 833 * quadrant are handled as a single, long vector. From a 834 * topological point of the view, the intermediate points are of no 835 * interest and thus tagged as weak. 836 */ 837 838 for ( point = points; point < point_limit; point++ ) 839 { 840 if ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) 841 continue; 842 843 if ( point->in_dir == AF_DIR_NONE && 844 point->out_dir == AF_DIR_NONE ) 845 { 846 /* check whether both vectors point into the same quadrant */ 847 848 FT_Pos in_x, in_y; 849 FT_Pos out_x, out_y; 850 851 AF_Point next_u = point + point->u; 852 AF_Point prev_v = point + point->v; 853 854 855 in_x = point->fx - prev_v->fx; 856 in_y = point->fy - prev_v->fy; 857 858 out_x = next_u->fx - point->fx; 859 out_y = next_u->fy - point->fy; 860 861 if ( ( in_x ^ out_x ) >= 0 && ( in_y ^ out_y ) >= 0 ) 862 { 863 /* yes, so tag current point as weak */ 864 /* and update index deltas */ 865 866 point->flags |= AF_FLAG_WEAK_INTERPOLATION; 867 868 prev_v->u = (FT_Pos)( next_u - prev_v ); 869 next_u->v = -prev_v->u; 870 } 871 } 872 } 873 874 /* 875 * Finally, check for remaining weak points. Everything else not 876 * collected in edges so far is then implicitly classified as strong 877 * points. 878 */ 879 880 for ( point = points; point < point_limit; point++ ) 881 { 882 if ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) 883 continue; 884 885 if ( point->flags & AF_FLAG_CONTROL ) 886 { 887 /* control points are always weak */ 888 Is_Weak_Point: 889 point->flags |= AF_FLAG_WEAK_INTERPOLATION; 890 } 891 else if ( point->out_dir == point->in_dir ) 892 { 893 if ( point->out_dir != AF_DIR_NONE ) 894 { 895 /* current point lies on a horizontal or */ 896 /* vertical segment (but doesn't start or end it) */ 897 goto Is_Weak_Point; 898 } 899 900 { 901 AF_Point next_u = point + point->u; 902 AF_Point prev_v = point + point->v; 903 904 905 if ( ft_corner_is_flat( point->fx - prev_v->fx, 906 point->fy - prev_v->fy, 907 next_u->fx - point->fx, 908 next_u->fy - point->fy ) ) 909 { 910 /* either the `in' or the `out' vector is much more */ 911 /* dominant than the other one, so tag current point */ 912 /* as weak and update index deltas */ 913 914 prev_v->u = (FT_Pos)( next_u - prev_v ); 915 next_u->v = -prev_v->u; 916 917 goto Is_Weak_Point; 918 } 919 } 920 } 921 else if ( point->in_dir == -point->out_dir ) 922 { 923 /* current point forms a spike */ 924 goto Is_Weak_Point; 925 } 926 } 927 } 928 } 929 930 Exit: 931 return error; 932 } 933 934 935 /* Store the hinted outline in an FT_Outline structure. */ 936 937 FT_LOCAL_DEF( void ) 938 af_glyph_hints_save( AF_GlyphHints hints, 939 FT_Outline* outline ) 940 { 941 AF_Point point = hints->points; 942 AF_Point limit = point + hints->num_points; 943 FT_Vector* vec = outline->points; 944 char* tag = outline->tags; 945 946 947 for ( ; point < limit; point++, vec++, tag++ ) 948 { 949 vec->x = point->x; 950 vec->y = point->y; 951 952 if ( point->flags & AF_FLAG_CONIC ) 953 tag[0] = FT_CURVE_TAG_CONIC; 954 else if ( point->flags & AF_FLAG_CUBIC ) 955 tag[0] = FT_CURVE_TAG_CUBIC; 956 else 957 tag[0] = FT_CURVE_TAG_ON; 958 } 959 } 960 961 962 /**************************************************************** 963 * 964 * EDGE POINT GRID-FITTING 965 * 966 ****************************************************************/ 967 968 969 /* Align all points of an edge to the same coordinate value, */ 970 /* either horizontally or vertically. */ 971 972 FT_LOCAL_DEF( void ) 973 af_glyph_hints_align_edge_points( AF_GlyphHints hints, 974 AF_Dimension dim ) 975 { 976 AF_AxisHints axis = & hints->axis[dim]; 977 AF_Segment segments = axis->segments; 978 AF_Segment segment_limit = segments + axis->num_segments; 979 AF_Segment seg; 980 981 982 if ( dim == AF_DIMENSION_HORZ ) 983 { 984 for ( seg = segments; seg < segment_limit; seg++ ) 985 { 986 AF_Edge edge = seg->edge; 987 AF_Point point, first, last; 988 989 990 if ( edge == NULL ) 991 continue; 992 993 first = seg->first; 994 last = seg->last; 995 point = first; 996 for (;;) 997 { 998 point->x = edge->pos; 999 point->flags |= AF_FLAG_TOUCH_X; 1000 1001 if ( point == last ) 1002 break; 1003 1004 point = point->next; 1005 } 1006 } 1007 } 1008 else 1009 { 1010 for ( seg = segments; seg < segment_limit; seg++ ) 1011 { 1012 AF_Edge edge = seg->edge; 1013 AF_Point point, first, last; 1014 1015 1016 if ( edge == NULL ) 1017 continue; 1018 1019 first = seg->first; 1020 last = seg->last; 1021 point = first; 1022 for (;;) 1023 { 1024 point->y = edge->pos; 1025 point->flags |= AF_FLAG_TOUCH_Y; 1026 1027 if ( point == last ) 1028 break; 1029 1030 point = point->next; 1031 } 1032 } 1033 } 1034 } 1035 1036 1037 /**************************************************************** 1038 * 1039 * STRONG POINT INTERPOLATION 1040 * 1041 ****************************************************************/ 1042 1043 1044 /* Hint the strong points -- this is equivalent to the TrueType `IP' */ 1045 /* hinting instruction. */ 1046 1047 FT_LOCAL_DEF( void ) 1048 af_glyph_hints_align_strong_points( AF_GlyphHints hints, 1049 AF_Dimension dim ) 1050 { 1051 AF_Point points = hints->points; 1052 AF_Point point_limit = points + hints->num_points; 1053 AF_AxisHints axis = &hints->axis[dim]; 1054 AF_Edge edges = axis->edges; 1055 AF_Edge edge_limit = edges + axis->num_edges; 1056 AF_Flags touch_flag; 1057 1058 1059 if ( dim == AF_DIMENSION_HORZ ) 1060 touch_flag = AF_FLAG_TOUCH_X; 1061 else 1062 touch_flag = AF_FLAG_TOUCH_Y; 1063 1064 if ( edges < edge_limit ) 1065 { 1066 AF_Point point; 1067 AF_Edge edge; 1068 1069 1070 for ( point = points; point < point_limit; point++ ) 1071 { 1072 FT_Pos u, ou, fu; /* point position */ 1073 FT_Pos delta; 1074 1075 1076 if ( point->flags & touch_flag ) 1077 continue; 1078 1079 /* if this point is candidate to weak interpolation, we */ 1080 /* interpolate it after all strong points have been processed */ 1081 1082 if ( ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) && 1083 !( point->flags & AF_FLAG_INFLECTION ) ) 1084 continue; 1085 1086 if ( dim == AF_DIMENSION_VERT ) 1087 { 1088 u = point->fy; 1089 ou = point->oy; 1090 } 1091 else 1092 { 1093 u = point->fx; 1094 ou = point->ox; 1095 } 1096 1097 fu = u; 1098 1099 /* is the point before the first edge? */ 1100 edge = edges; 1101 delta = edge->fpos - u; 1102 if ( delta >= 0 ) 1103 { 1104 u = edge->pos - ( edge->opos - ou ); 1105 goto Store_Point; 1106 } 1107 1108 /* is the point after the last edge? */ 1109 edge = edge_limit - 1; 1110 delta = u - edge->fpos; 1111 if ( delta >= 0 ) 1112 { 1113 u = edge->pos + ( ou - edge->opos ); 1114 goto Store_Point; 1115 } 1116 1117 { 1118 FT_PtrDist min, max, mid; 1119 FT_Pos fpos; 1120 1121 1122 /* find enclosing edges */ 1123 min = 0; 1124 max = edge_limit - edges; 1125 1126 #if 1 1127 /* for a small number of edges, a linear search is better */ 1128 if ( max <= 8 ) 1129 { 1130 FT_PtrDist nn; 1131 1132 1133 for ( nn = 0; nn < max; nn++ ) 1134 if ( edges[nn].fpos >= u ) 1135 break; 1136 1137 if ( edges[nn].fpos == u ) 1138 { 1139 u = edges[nn].pos; 1140 goto Store_Point; 1141 } 1142 min = nn; 1143 } 1144 else 1145 #endif 1146 while ( min < max ) 1147 { 1148 mid = ( max + min ) >> 1; 1149 edge = edges + mid; 1150 fpos = edge->fpos; 1151 1152 if ( u < fpos ) 1153 max = mid; 1154 else if ( u > fpos ) 1155 min = mid + 1; 1156 else 1157 { 1158 /* we are on the edge */ 1159 u = edge->pos; 1160 goto Store_Point; 1161 } 1162 } 1163 1164 /* point is not on an edge */ 1165 { 1166 AF_Edge before = edges + min - 1; 1167 AF_Edge after = edges + min + 0; 1168 1169 1170 /* assert( before && after && before != after ) */ 1171 if ( before->scale == 0 ) 1172 before->scale = FT_DivFix( after->pos - before->pos, 1173 after->fpos - before->fpos ); 1174 1175 u = before->pos + FT_MulFix( fu - before->fpos, 1176 before->scale ); 1177 } 1178 } 1179 1180 Store_Point: 1181 /* save the point position */ 1182 if ( dim == AF_DIMENSION_HORZ ) 1183 point->x = u; 1184 else 1185 point->y = u; 1186 1187 point->flags |= touch_flag; 1188 } 1189 } 1190 } 1191 1192 1193 /**************************************************************** 1194 * 1195 * WEAK POINT INTERPOLATION 1196 * 1197 ****************************************************************/ 1198 1199 1200 /* Shift the original coordinates of all points between `p1' and */ 1201 /* `p2' to get hinted coordinates, using the same difference as */ 1202 /* given by `ref'. */ 1203 1204 static void 1205 af_iup_shift( AF_Point p1, 1206 AF_Point p2, 1207 AF_Point ref ) 1208 { 1209 AF_Point p; 1210 FT_Pos delta = ref->u - ref->v; 1211 1212 1213 if ( delta == 0 ) 1214 return; 1215 1216 for ( p = p1; p < ref; p++ ) 1217 p->u = p->v + delta; 1218 1219 for ( p = ref + 1; p <= p2; p++ ) 1220 p->u = p->v + delta; 1221 } 1222 1223 1224 /* Interpolate the original coordinates of all points between `p1' and */ 1225 /* `p2' to get hinted coordinates, using `ref1' and `ref2' as the */ 1226 /* reference points. The `u' and `v' members are the current and */ 1227 /* original coordinate values, respectively. */ 1228 /* */ 1229 /* Details can be found in the TrueType bytecode specification. */ 1230 1231 static void 1232 af_iup_interp( AF_Point p1, 1233 AF_Point p2, 1234 AF_Point ref1, 1235 AF_Point ref2 ) 1236 { 1237 AF_Point p; 1238 FT_Pos u; 1239 FT_Pos v1 = ref1->v; 1240 FT_Pos v2 = ref2->v; 1241 FT_Pos d1 = ref1->u - v1; 1242 FT_Pos d2 = ref2->u - v2; 1243 1244 1245 if ( p1 > p2 ) 1246 return; 1247 1248 if ( v1 == v2 ) 1249 { 1250 for ( p = p1; p <= p2; p++ ) 1251 { 1252 u = p->v; 1253 1254 if ( u <= v1 ) 1255 u += d1; 1256 else 1257 u += d2; 1258 1259 p->u = u; 1260 } 1261 return; 1262 } 1263 1264 if ( v1 < v2 ) 1265 { 1266 for ( p = p1; p <= p2; p++ ) 1267 { 1268 u = p->v; 1269 1270 if ( u <= v1 ) 1271 u += d1; 1272 else if ( u >= v2 ) 1273 u += d2; 1274 else 1275 u = ref1->u + FT_MulDiv( u - v1, ref2->u - ref1->u, v2 - v1 ); 1276 1277 p->u = u; 1278 } 1279 } 1280 else 1281 { 1282 for ( p = p1; p <= p2; p++ ) 1283 { 1284 u = p->v; 1285 1286 if ( u <= v2 ) 1287 u += d2; 1288 else if ( u >= v1 ) 1289 u += d1; 1290 else 1291 u = ref1->u + FT_MulDiv( u - v1, ref2->u - ref1->u, v2 - v1 ); 1292 1293 p->u = u; 1294 } 1295 } 1296 } 1297 1298 1299 /* Hint the weak points -- this is equivalent to the TrueType `IUP' */ 1300 /* hinting instruction. */ 1301 1302 FT_LOCAL_DEF( void ) 1303 af_glyph_hints_align_weak_points( AF_GlyphHints hints, 1304 AF_Dimension dim ) 1305 { 1306 AF_Point points = hints->points; 1307 AF_Point point_limit = points + hints->num_points; 1308 AF_Point* contour = hints->contours; 1309 AF_Point* contour_limit = contour + hints->num_contours; 1310 AF_Flags touch_flag; 1311 AF_Point point; 1312 AF_Point end_point; 1313 AF_Point first_point; 1314 1315 1316 /* PASS 1: Move segment points to edge positions */ 1317 1318 if ( dim == AF_DIMENSION_HORZ ) 1319 { 1320 touch_flag = AF_FLAG_TOUCH_X; 1321 1322 for ( point = points; point < point_limit; point++ ) 1323 { 1324 point->u = point->x; 1325 point->v = point->ox; 1326 } 1327 } 1328 else 1329 { 1330 touch_flag = AF_FLAG_TOUCH_Y; 1331 1332 for ( point = points; point < point_limit; point++ ) 1333 { 1334 point->u = point->y; 1335 point->v = point->oy; 1336 } 1337 } 1338 1339 for ( ; contour < contour_limit; contour++ ) 1340 { 1341 AF_Point first_touched, last_touched; 1342 1343 1344 point = *contour; 1345 end_point = point->prev; 1346 first_point = point; 1347 1348 /* find first touched point */ 1349 for (;;) 1350 { 1351 if ( point > end_point ) /* no touched point in contour */ 1352 goto NextContour; 1353 1354 if ( point->flags & touch_flag ) 1355 break; 1356 1357 point++; 1358 } 1359 1360 first_touched = point; 1361 1362 for (;;) 1363 { 1364 FT_ASSERT( point <= end_point && 1365 ( point->flags & touch_flag ) != 0 ); 1366 1367 /* skip any touched neighbours */ 1368 while ( point < end_point && 1369 ( point[1].flags & touch_flag ) != 0 ) 1370 point++; 1371 1372 last_touched = point; 1373 1374 /* find the next touched point, if any */ 1375 point++; 1376 for (;;) 1377 { 1378 if ( point > end_point ) 1379 goto EndContour; 1380 1381 if ( ( point->flags & touch_flag ) != 0 ) 1382 break; 1383 1384 point++; 1385 } 1386 1387 /* interpolate between last_touched and point */ 1388 af_iup_interp( last_touched + 1, point - 1, 1389 last_touched, point ); 1390 } 1391 1392 EndContour: 1393 /* special case: only one point was touched */ 1394 if ( last_touched == first_touched ) 1395 af_iup_shift( first_point, end_point, first_touched ); 1396 1397 else /* interpolate the last part */ 1398 { 1399 if ( last_touched < end_point ) 1400 af_iup_interp( last_touched + 1, end_point, 1401 last_touched, first_touched ); 1402 1403 if ( first_touched > points ) 1404 af_iup_interp( first_point, first_touched - 1, 1405 last_touched, first_touched ); 1406 } 1407 1408 NextContour: 1409 ; 1410 } 1411 1412 /* now save the interpolated values back to x/y */ 1413 if ( dim == AF_DIMENSION_HORZ ) 1414 { 1415 for ( point = points; point < point_limit; point++ ) 1416 point->x = point->u; 1417 } 1418 else 1419 { 1420 for ( point = points; point < point_limit; point++ ) 1421 point->y = point->u; 1422 } 1423 } 1424 1425 1426 #ifdef AF_CONFIG_OPTION_USE_WARPER 1427 1428 /* Apply (small) warp scale and warp delta for given dimension. */ 1429 1430 FT_LOCAL_DEF( void ) 1431 af_glyph_hints_scale_dim( AF_GlyphHints hints, 1432 AF_Dimension dim, 1433 FT_Fixed scale, 1434 FT_Pos delta ) 1435 { 1436 AF_Point points = hints->points; 1437 AF_Point points_limit = points + hints->num_points; 1438 AF_Point point; 1439 1440 1441 if ( dim == AF_DIMENSION_HORZ ) 1442 { 1443 for ( point = points; point < points_limit; point++ ) 1444 point->x = FT_MulFix( point->fx, scale ) + delta; 1445 } 1446 else 1447 { 1448 for ( point = points; point < points_limit; point++ ) 1449 point->y = FT_MulFix( point->fy, scale ) + delta; 1450 } 1451 } 1452 1453 #endif /* AF_CONFIG_OPTION_USE_WARPER */ 1454 1455 /* END */ 1456