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