1/***************************************************************************/ 2/* */ 3/* afhints.c */ 4/* */ 5/* Auto-fitter hinting routines (body). */ 6/* */ 7/* Copyright 2003-2007, 2009-2013 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 static const char* 148 af_dir_str( AF_Direction dir ) 149 { 150 const char* result; 151 152 153 switch ( dir ) 154 { 155 case AF_DIR_UP: 156 result = "up"; 157 break; 158 case AF_DIR_DOWN: 159 result = "down"; 160 break; 161 case AF_DIR_LEFT: 162 result = "left"; 163 break; 164 case AF_DIR_RIGHT: 165 result = "right"; 166 break; 167 default: 168 result = "none"; 169 } 170 171 return result; 172 } 173 174 175#define AF_INDEX_NUM( ptr, base ) ( (ptr) ? ( (ptr) - (base) ) : -1 ) 176 177 178#ifdef __cplusplus 179 extern "C" { 180#endif 181 void 182 af_glyph_hints_dump_points( AF_GlyphHints hints ) 183 { 184 AF_Point points = hints->points; 185 AF_Point limit = points + hints->num_points; 186 AF_Point point; 187 188 189 FT_TRACE7(( "Table of points:\n" 190 " [ index | xorg | yorg | xscale | yscale" 191 " | xfit | yfit | flags ]\n" )); 192 193 for ( point = points; point < limit; point++ ) 194 FT_TRACE7(( " [ %5d | %5d | %5d | %6.2f | %6.2f" 195 " | %5.2f | %5.2f | %c%c%c%c%c%c ]\n", 196 point - points, 197 point->fx, 198 point->fy, 199 point->ox / 64.0, 200 point->oy / 64.0, 201 point->x / 64.0, 202 point->y / 64.0, 203 ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) ? 'w' : ' ', 204 ( point->flags & AF_FLAG_INFLECTION ) ? 'i' : ' ', 205 ( point->flags & AF_FLAG_EXTREMA_X ) ? '<' : ' ', 206 ( point->flags & AF_FLAG_EXTREMA_Y ) ? 'v' : ' ', 207 ( point->flags & AF_FLAG_ROUND_X ) ? '(' : ' ', 208 ( point->flags & AF_FLAG_ROUND_Y ) ? 'u' : ' ')); 209 FT_TRACE7(( "\n" )); 210 } 211#ifdef __cplusplus 212 } 213#endif 214 215 216 static const char* 217 af_edge_flags_to_string( AF_Edge_Flags flags ) 218 { 219 static char temp[32]; 220 int pos = 0; 221 222 223 if ( flags & AF_EDGE_ROUND ) 224 { 225 ft_memcpy( temp + pos, "round", 5 ); 226 pos += 5; 227 } 228 if ( flags & AF_EDGE_SERIF ) 229 { 230 if ( pos > 0 ) 231 temp[pos++] = ' '; 232 ft_memcpy( temp + pos, "serif", 5 ); 233 pos += 5; 234 } 235 if ( pos == 0 ) 236 return "normal"; 237 238 temp[pos] = '\0'; 239 240 return temp; 241 } 242 243 244 /* Dump the array of linked segments. */ 245 246#ifdef __cplusplus 247 extern "C" { 248#endif 249 void 250 af_glyph_hints_dump_segments( AF_GlyphHints hints ) 251 { 252 FT_Int dimension; 253 254 255 for ( dimension = 1; dimension >= 0; dimension-- ) 256 { 257 AF_AxisHints axis = &hints->axis[dimension]; 258 AF_Point points = hints->points; 259 AF_Edge edges = axis->edges; 260 AF_Segment segments = axis->segments; 261 AF_Segment limit = segments + axis->num_segments; 262 AF_Segment seg; 263 264 265 FT_TRACE7(( "Table of %s segments:\n", 266 dimension == AF_DIMENSION_HORZ ? "vertical" 267 : "horizontal" )); 268 if ( axis->num_segments ) 269 FT_TRACE7(( " [ index | pos | dir | from" 270 " | to | link | serif | edge" 271 " | height | extra | flags ]\n" )); 272 else 273 FT_TRACE7(( " (none)\n" )); 274 275 for ( seg = segments; seg < limit; seg++ ) 276 FT_TRACE7(( " [ %5d | %5.2g | %5s | %4d" 277 " | %4d | %4d | %5d | %4d" 278 " | %6d | %5d | %11s ]\n", 279 seg - segments, 280 dimension == AF_DIMENSION_HORZ 281 ? (int)seg->first->ox / 64.0 282 : (int)seg->first->oy / 64.0, 283 af_dir_str( (AF_Direction)seg->dir ), 284 AF_INDEX_NUM( seg->first, points ), 285 AF_INDEX_NUM( seg->last, points ), 286 AF_INDEX_NUM( seg->link, segments ), 287 AF_INDEX_NUM( seg->serif, segments ), 288 AF_INDEX_NUM( seg->edge, edges ), 289 seg->height, 290 seg->height - ( seg->max_coord - seg->min_coord ), 291 af_edge_flags_to_string( (AF_Edge_Flags)seg->flags ) )); 292 FT_TRACE7(( "\n" )); 293 } 294 } 295#ifdef __cplusplus 296 } 297#endif 298 299 300 /* Fetch number of segments. */ 301 302#ifdef __cplusplus 303 extern "C" { 304#endif 305 FT_Error 306 af_glyph_hints_get_num_segments( AF_GlyphHints hints, 307 FT_Int dimension, 308 FT_Int* num_segments ) 309 { 310 AF_Dimension dim; 311 AF_AxisHints axis; 312 313 314 dim = ( dimension == 0 ) ? AF_DIMENSION_HORZ : AF_DIMENSION_VERT; 315 316 axis = &hints->axis[dim]; 317 *num_segments = axis->num_segments; 318 319 return FT_Err_Ok; 320 } 321#ifdef __cplusplus 322 } 323#endif 324 325 326 /* Fetch offset of segments into user supplied offset array. */ 327 328#ifdef __cplusplus 329 extern "C" { 330#endif 331 FT_Error 332 af_glyph_hints_get_segment_offset( AF_GlyphHints hints, 333 FT_Int dimension, 334 FT_Int idx, 335 FT_Pos* offset ) 336 { 337 AF_Dimension dim; 338 AF_AxisHints axis; 339 AF_Segment seg; 340 341 342 if ( !offset ) 343 return FT_THROW( Invalid_Argument ); 344 345 dim = ( dimension == 0 ) ? AF_DIMENSION_HORZ : AF_DIMENSION_VERT; 346 347 axis = &hints->axis[dim]; 348 349 if ( idx < 0 || idx >= axis->num_segments ) 350 return FT_THROW( Invalid_Argument ); 351 352 seg = &axis->segments[idx]; 353 *offset = ( dim == AF_DIMENSION_HORZ ) ? seg->first->ox 354 : seg->first->oy; 355 356 return FT_Err_Ok; 357 } 358#ifdef __cplusplus 359 } 360#endif 361 362 363 /* Dump the array of linked edges. */ 364 365#ifdef __cplusplus 366 extern "C" { 367#endif 368 void 369 af_glyph_hints_dump_edges( AF_GlyphHints hints ) 370 { 371 FT_Int dimension; 372 373 374 for ( dimension = 1; dimension >= 0; dimension-- ) 375 { 376 AF_AxisHints axis = &hints->axis[dimension]; 377 AF_Edge edges = axis->edges; 378 AF_Edge limit = edges + axis->num_edges; 379 AF_Edge edge; 380 381 382 /* 383 * note: AF_DIMENSION_HORZ corresponds to _vertical_ edges 384 * since they have a constant X coordinate. 385 */ 386 FT_TRACE7(( "Table of %s edges:\n", 387 dimension == AF_DIMENSION_HORZ ? "vertical" 388 : "horizontal" )); 389 if ( axis->num_edges ) 390 FT_TRACE7(( " [ index | pos | dir | link" 391 " | serif | blue | opos | pos | flags ]\n" )); 392 else 393 FT_TRACE7(( " (none)\n" )); 394 395 for ( edge = edges; edge < limit; edge++ ) 396 FT_TRACE7(( " [ %5d | %5.2g | %5s | %4d" 397 " | %5d | %c | %5.2f | %5.2f | %11s ]\n", 398 edge - edges, 399 (int)edge->opos / 64.0, 400 af_dir_str( (AF_Direction)edge->dir ), 401 AF_INDEX_NUM( edge->link, edges ), 402 AF_INDEX_NUM( edge->serif, edges ), 403 edge->blue_edge ? 'y' : 'n', 404 edge->opos / 64.0, 405 edge->pos / 64.0, 406 af_edge_flags_to_string( (AF_Edge_Flags)edge->flags ) )); 407 FT_TRACE7(( "\n" )); 408 } 409 } 410#ifdef __cplusplus 411 } 412#endif 413 414#else /* !FT_DEBUG_AUTOFIT */ 415 416 /* these empty stubs are only used to link the `ftgrid' test program */ 417 /* if debugging is disabled */ 418 419#ifdef __cplusplus 420 extern "C" { 421#endif 422 423 void 424 af_glyph_hints_dump_points( AF_GlyphHints hints ) 425 { 426 FT_UNUSED( hints ); 427 } 428 429 430 void 431 af_glyph_hints_dump_segments( AF_GlyphHints hints ) 432 { 433 FT_UNUSED( hints ); 434 } 435 436 437 FT_Error 438 af_glyph_hints_get_num_segments( AF_GlyphHints hints, 439 FT_Int dimension, 440 FT_Int* num_segments ) 441 { 442 FT_UNUSED( hints ); 443 FT_UNUSED( dimension ); 444 FT_UNUSED( num_segments ); 445 446 return 0; 447 } 448 449 450 FT_Error 451 af_glyph_hints_get_segment_offset( AF_GlyphHints hints, 452 FT_Int dimension, 453 FT_Int idx, 454 FT_Pos* offset ) 455 { 456 FT_UNUSED( hints ); 457 FT_UNUSED( dimension ); 458 FT_UNUSED( idx ); 459 FT_UNUSED( offset ); 460 461 return 0; 462 } 463 464 465 void 466 af_glyph_hints_dump_edges( AF_GlyphHints hints ) 467 { 468 FT_UNUSED( hints ); 469 } 470 471#ifdef __cplusplus 472 } 473#endif 474 475#endif /* !FT_DEBUG_AUTOFIT */ 476 477 478 /* Compute the direction value of a given vector. */ 479 480 FT_LOCAL_DEF( AF_Direction ) 481 af_direction_compute( FT_Pos dx, 482 FT_Pos dy ) 483 { 484 FT_Pos ll, ss; /* long and short arm lengths */ 485 AF_Direction dir; /* candidate direction */ 486 487 488 if ( dy >= dx ) 489 { 490 if ( dy >= -dx ) 491 { 492 dir = AF_DIR_UP; 493 ll = dy; 494 ss = dx; 495 } 496 else 497 { 498 dir = AF_DIR_LEFT; 499 ll = -dx; 500 ss = dy; 501 } 502 } 503 else /* dy < dx */ 504 { 505 if ( dy >= -dx ) 506 { 507 dir = AF_DIR_RIGHT; 508 ll = dx; 509 ss = dy; 510 } 511 else 512 { 513 dir = AF_DIR_DOWN; 514 ll = dy; 515 ss = dx; 516 } 517 } 518 519 /* return no direction if arm lengths differ too much */ 520 /* (value 14 is heuristic, corresponding to approx. 4.1 degrees) */ 521 ss *= 14; 522 if ( FT_ABS( ll ) <= FT_ABS( ss ) ) 523 dir = AF_DIR_NONE; 524 525 return dir; 526 } 527 528 529 FT_LOCAL_DEF( void ) 530 af_glyph_hints_init( AF_GlyphHints hints, 531 FT_Memory memory ) 532 { 533 FT_ZERO( hints ); 534 hints->memory = memory; 535 } 536 537 538 FT_LOCAL_DEF( void ) 539 af_glyph_hints_done( AF_GlyphHints hints ) 540 { 541 FT_Memory memory = hints->memory; 542 int dim; 543 544 545 if ( !( hints && hints->memory ) ) 546 return; 547 548 /* 549 * note that we don't need to free the segment and edge 550 * buffers since they are really within the hints->points array 551 */ 552 for ( dim = 0; dim < AF_DIMENSION_MAX; dim++ ) 553 { 554 AF_AxisHints axis = &hints->axis[dim]; 555 556 557 axis->num_segments = 0; 558 axis->max_segments = 0; 559 FT_FREE( axis->segments ); 560 561 axis->num_edges = 0; 562 axis->max_edges = 0; 563 FT_FREE( axis->edges ); 564 } 565 566 FT_FREE( hints->contours ); 567 hints->max_contours = 0; 568 hints->num_contours = 0; 569 570 FT_FREE( hints->points ); 571 hints->num_points = 0; 572 hints->max_points = 0; 573 574 hints->memory = NULL; 575 } 576 577 578 /* Reset metrics. */ 579 580 FT_LOCAL_DEF( void ) 581 af_glyph_hints_rescale( AF_GlyphHints hints, 582 AF_ScriptMetrics metrics ) 583 { 584 hints->metrics = metrics; 585 hints->scaler_flags = metrics->scaler.flags; 586 } 587 588 589 /* Recompute all AF_Point in AF_GlyphHints from the definitions */ 590 /* in a source outline. */ 591 592 FT_LOCAL_DEF( FT_Error ) 593 af_glyph_hints_reload( AF_GlyphHints hints, 594 FT_Outline* outline ) 595 { 596 FT_Error error = FT_Err_Ok; 597 AF_Point points; 598 FT_UInt old_max, new_max; 599 FT_Fixed x_scale = hints->x_scale; 600 FT_Fixed y_scale = hints->y_scale; 601 FT_Pos x_delta = hints->x_delta; 602 FT_Pos y_delta = hints->y_delta; 603 FT_Memory memory = hints->memory; 604 605 606 hints->num_points = 0; 607 hints->num_contours = 0; 608 609 hints->axis[0].num_segments = 0; 610 hints->axis[0].num_edges = 0; 611 hints->axis[1].num_segments = 0; 612 hints->axis[1].num_edges = 0; 613 614 /* first of all, reallocate the contours array if necessary */ 615 new_max = (FT_UInt)outline->n_contours; 616 old_max = hints->max_contours; 617 if ( new_max > old_max ) 618 { 619 new_max = ( new_max + 3 ) & ~3; /* round up to a multiple of 4 */ 620 621 if ( FT_RENEW_ARRAY( hints->contours, old_max, new_max ) ) 622 goto Exit; 623 624 hints->max_contours = new_max; 625 } 626 627 /* 628 * then reallocate the points arrays if necessary -- 629 * note that we reserve two additional point positions, used to 630 * hint metrics appropriately 631 */ 632 new_max = (FT_UInt)( outline->n_points + 2 ); 633 old_max = hints->max_points; 634 if ( new_max > old_max ) 635 { 636 new_max = ( new_max + 2 + 7 ) & ~7; /* round up to a multiple of 8 */ 637 638 if ( FT_RENEW_ARRAY( hints->points, old_max, new_max ) ) 639 goto Exit; 640 641 hints->max_points = new_max; 642 } 643 644 hints->num_points = outline->n_points; 645 hints->num_contours = outline->n_contours; 646 647 /* We can't rely on the value of `FT_Outline.flags' to know the fill */ 648 /* direction used for a glyph, given that some fonts are broken (e.g., */ 649 /* the Arphic ones). We thus recompute it each time we need to. */ 650 /* */ 651 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_UP; 652 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_LEFT; 653 654 if ( FT_Outline_Get_Orientation( outline ) == FT_ORIENTATION_POSTSCRIPT ) 655 { 656 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_DOWN; 657 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_RIGHT; 658 } 659 660 hints->x_scale = x_scale; 661 hints->y_scale = y_scale; 662 hints->x_delta = x_delta; 663 hints->y_delta = y_delta; 664 665 hints->xmin_delta = 0; 666 hints->xmax_delta = 0; 667 668 points = hints->points; 669 if ( hints->num_points == 0 ) 670 goto Exit; 671 672 { 673 AF_Point point; 674 AF_Point point_limit = points + hints->num_points; 675 676 677 /* compute coordinates & Bezier flags, next and prev */ 678 { 679 FT_Vector* vec = outline->points; 680 char* tag = outline->tags; 681 AF_Point end = points + outline->contours[0]; 682 AF_Point prev = end; 683 FT_Int contour_index = 0; 684 685 686 for ( point = points; point < point_limit; point++, vec++, tag++ ) 687 { 688 point->fx = (FT_Short)vec->x; 689 point->fy = (FT_Short)vec->y; 690 point->ox = point->x = FT_MulFix( vec->x, x_scale ) + x_delta; 691 point->oy = point->y = FT_MulFix( vec->y, y_scale ) + y_delta; 692 693 switch ( FT_CURVE_TAG( *tag ) ) 694 { 695 case FT_CURVE_TAG_CONIC: 696 point->flags = AF_FLAG_CONIC; 697 break; 698 case FT_CURVE_TAG_CUBIC: 699 point->flags = AF_FLAG_CUBIC; 700 break; 701 default: 702 point->flags = AF_FLAG_NONE; 703 } 704 705 point->prev = prev; 706 prev->next = point; 707 prev = point; 708 709 if ( point == end ) 710 { 711 if ( ++contour_index < outline->n_contours ) 712 { 713 end = points + outline->contours[contour_index]; 714 prev = end; 715 } 716 } 717 } 718 } 719 720 /* set up the contours array */ 721 { 722 AF_Point* contour = hints->contours; 723 AF_Point* contour_limit = contour + hints->num_contours; 724 short* end = outline->contours; 725 short idx = 0; 726 727 728 for ( ; contour < contour_limit; contour++, end++ ) 729 { 730 contour[0] = points + idx; 731 idx = (short)( end[0] + 1 ); 732 } 733 } 734 735 /* compute directions of in & out vectors */ 736 { 737 AF_Point first = points; 738 AF_Point prev = NULL; 739 FT_Pos in_x = 0; 740 FT_Pos in_y = 0; 741 AF_Direction in_dir = AF_DIR_NONE; 742 743 744 for ( point = points; point < point_limit; point++ ) 745 { 746 AF_Point next; 747 FT_Pos out_x, out_y; 748 749 750 if ( point == first ) 751 { 752 prev = first->prev; 753 in_x = first->fx - prev->fx; 754 in_y = first->fy - prev->fy; 755 in_dir = af_direction_compute( in_x, in_y ); 756 first = prev + 1; 757 } 758 759 point->in_dir = (FT_Char)in_dir; 760 761 next = point->next; 762 out_x = next->fx - point->fx; 763 out_y = next->fy - point->fy; 764 765 in_dir = af_direction_compute( out_x, out_y ); 766 point->out_dir = (FT_Char)in_dir; 767 768 /* check for weak points */ 769 770 if ( point->flags & AF_FLAG_CONTROL ) 771 { 772 Is_Weak_Point: 773 point->flags |= AF_FLAG_WEAK_INTERPOLATION; 774 } 775 else if ( point->out_dir == point->in_dir ) 776 { 777 if ( point->out_dir != AF_DIR_NONE ) 778 goto Is_Weak_Point; 779 780 if ( ft_corner_is_flat( in_x, in_y, out_x, out_y ) ) 781 goto Is_Weak_Point; 782 } 783 else if ( point->in_dir == -point->out_dir ) 784 goto Is_Weak_Point; 785 786 in_x = out_x; 787 in_y = out_y; 788 prev = point; 789 } 790 } 791 } 792 793 Exit: 794 return error; 795 } 796 797 798 /* Store the hinted outline in an FT_Outline structure. */ 799 800 FT_LOCAL_DEF( void ) 801 af_glyph_hints_save( AF_GlyphHints hints, 802 FT_Outline* outline ) 803 { 804 AF_Point point = hints->points; 805 AF_Point limit = point + hints->num_points; 806 FT_Vector* vec = outline->points; 807 char* tag = outline->tags; 808 809 810 for ( ; point < limit; point++, vec++, tag++ ) 811 { 812 vec->x = point->x; 813 vec->y = point->y; 814 815 if ( point->flags & AF_FLAG_CONIC ) 816 tag[0] = FT_CURVE_TAG_CONIC; 817 else if ( point->flags & AF_FLAG_CUBIC ) 818 tag[0] = FT_CURVE_TAG_CUBIC; 819 else 820 tag[0] = FT_CURVE_TAG_ON; 821 } 822 } 823 824 825 /**************************************************************** 826 * 827 * EDGE POINT GRID-FITTING 828 * 829 ****************************************************************/ 830 831 832 /* Align all points of an edge to the same coordinate value, */ 833 /* either horizontally or vertically. */ 834 835 FT_LOCAL_DEF( void ) 836 af_glyph_hints_align_edge_points( AF_GlyphHints hints, 837 AF_Dimension dim ) 838 { 839 AF_AxisHints axis = & hints->axis[dim]; 840 AF_Segment segments = axis->segments; 841 AF_Segment segment_limit = segments + axis->num_segments; 842 AF_Segment seg; 843 844 845 if ( dim == AF_DIMENSION_HORZ ) 846 { 847 for ( seg = segments; seg < segment_limit; seg++ ) 848 { 849 AF_Edge edge = seg->edge; 850 AF_Point point, first, last; 851 852 853 if ( edge == NULL ) 854 continue; 855 856 first = seg->first; 857 last = seg->last; 858 point = first; 859 for (;;) 860 { 861 point->x = edge->pos; 862 point->flags |= AF_FLAG_TOUCH_X; 863 864 if ( point == last ) 865 break; 866 867 point = point->next; 868 } 869 } 870 } 871 else 872 { 873 for ( seg = segments; seg < segment_limit; seg++ ) 874 { 875 AF_Edge edge = seg->edge; 876 AF_Point point, first, last; 877 878 879 if ( edge == NULL ) 880 continue; 881 882 first = seg->first; 883 last = seg->last; 884 point = first; 885 for (;;) 886 { 887 point->y = edge->pos; 888 point->flags |= AF_FLAG_TOUCH_Y; 889 890 if ( point == last ) 891 break; 892 893 point = point->next; 894 } 895 } 896 } 897 } 898 899 900 /**************************************************************** 901 * 902 * STRONG POINT INTERPOLATION 903 * 904 ****************************************************************/ 905 906 907 /* Hint the strong points -- this is equivalent to the TrueType `IP' */ 908 /* hinting instruction. */ 909 910 FT_LOCAL_DEF( void ) 911 af_glyph_hints_align_strong_points( AF_GlyphHints hints, 912 AF_Dimension dim ) 913 { 914 AF_Point points = hints->points; 915 AF_Point point_limit = points + hints->num_points; 916 AF_AxisHints axis = &hints->axis[dim]; 917 AF_Edge edges = axis->edges; 918 AF_Edge edge_limit = edges + axis->num_edges; 919 AF_Flags touch_flag; 920 921 922 if ( dim == AF_DIMENSION_HORZ ) 923 touch_flag = AF_FLAG_TOUCH_X; 924 else 925 touch_flag = AF_FLAG_TOUCH_Y; 926 927 if ( edges < edge_limit ) 928 { 929 AF_Point point; 930 AF_Edge edge; 931 932 933 for ( point = points; point < point_limit; point++ ) 934 { 935 FT_Pos u, ou, fu; /* point position */ 936 FT_Pos delta; 937 938 939 if ( point->flags & touch_flag ) 940 continue; 941 942 /* if this point is candidate to weak interpolation, we */ 943 /* interpolate it after all strong points have been processed */ 944 945 if ( ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) && 946 !( point->flags & AF_FLAG_INFLECTION ) ) 947 continue; 948 949 if ( dim == AF_DIMENSION_VERT ) 950 { 951 u = point->fy; 952 ou = point->oy; 953 } 954 else 955 { 956 u = point->fx; 957 ou = point->ox; 958 } 959 960 fu = u; 961 962 /* is the point before the first edge? */ 963 edge = edges; 964 delta = edge->fpos - u; 965 if ( delta >= 0 ) 966 { 967 u = edge->pos - ( edge->opos - ou ); 968 goto Store_Point; 969 } 970 971 /* is the point after the last edge? */ 972 edge = edge_limit - 1; 973 delta = u - edge->fpos; 974 if ( delta >= 0 ) 975 { 976 u = edge->pos + ( ou - edge->opos ); 977 goto Store_Point; 978 } 979 980 { 981 FT_PtrDist min, max, mid; 982 FT_Pos fpos; 983 984 985 /* find enclosing edges */ 986 min = 0; 987 max = edge_limit - edges; 988 989#if 1 990 /* for a small number of edges, a linear search is better */ 991 if ( max <= 8 ) 992 { 993 FT_PtrDist nn; 994 995 996 for ( nn = 0; nn < max; nn++ ) 997 if ( edges[nn].fpos >= u ) 998 break; 999 1000 if ( edges[nn].fpos == u ) 1001 { 1002 u = edges[nn].pos; 1003 goto Store_Point; 1004 } 1005 min = nn; 1006 } 1007 else 1008#endif 1009 while ( min < max ) 1010 { 1011 mid = ( max + min ) >> 1; 1012 edge = edges + mid; 1013 fpos = edge->fpos; 1014 1015 if ( u < fpos ) 1016 max = mid; 1017 else if ( u > fpos ) 1018 min = mid + 1; 1019 else 1020 { 1021 /* we are on the edge */ 1022 u = edge->pos; 1023 goto Store_Point; 1024 } 1025 } 1026 1027 /* point is not on an edge */ 1028 { 1029 AF_Edge before = edges + min - 1; 1030 AF_Edge after = edges + min + 0; 1031 1032 1033 /* assert( before && after && before != after ) */ 1034 if ( before->scale == 0 ) 1035 before->scale = FT_DivFix( after->pos - before->pos, 1036 after->fpos - before->fpos ); 1037 1038 u = before->pos + FT_MulFix( fu - before->fpos, 1039 before->scale ); 1040 } 1041 } 1042 1043 Store_Point: 1044 /* save the point position */ 1045 if ( dim == AF_DIMENSION_HORZ ) 1046 point->x = u; 1047 else 1048 point->y = u; 1049 1050 point->flags |= touch_flag; 1051 } 1052 } 1053 } 1054 1055 1056 /**************************************************************** 1057 * 1058 * WEAK POINT INTERPOLATION 1059 * 1060 ****************************************************************/ 1061 1062 1063 /* Shift the original coordinates of all points between `p1' and */ 1064 /* `p2' to get hinted coordinates, using the same difference as */ 1065 /* given by `ref'. */ 1066 1067 static void 1068 af_iup_shift( AF_Point p1, 1069 AF_Point p2, 1070 AF_Point ref ) 1071 { 1072 AF_Point p; 1073 FT_Pos delta = ref->u - ref->v; 1074 1075 1076 if ( delta == 0 ) 1077 return; 1078 1079 for ( p = p1; p < ref; p++ ) 1080 p->u = p->v + delta; 1081 1082 for ( p = ref + 1; p <= p2; p++ ) 1083 p->u = p->v + delta; 1084 } 1085 1086 1087 /* Interpolate the original coordinates of all points between `p1' and */ 1088 /* `p2' to get hinted coordinates, using `ref1' and `ref2' as the */ 1089 /* reference points. The `u' and `v' members are the current and */ 1090 /* original coordinate values, respectively. */ 1091 /* */ 1092 /* Details can be found in the TrueType bytecode specification. */ 1093 1094 static void 1095 af_iup_interp( AF_Point p1, 1096 AF_Point p2, 1097 AF_Point ref1, 1098 AF_Point ref2 ) 1099 { 1100 AF_Point p; 1101 FT_Pos u; 1102 FT_Pos v1 = ref1->v; 1103 FT_Pos v2 = ref2->v; 1104 FT_Pos d1 = ref1->u - v1; 1105 FT_Pos d2 = ref2->u - v2; 1106 1107 1108 if ( p1 > p2 ) 1109 return; 1110 1111 if ( v1 == v2 ) 1112 { 1113 for ( p = p1; p <= p2; p++ ) 1114 { 1115 u = p->v; 1116 1117 if ( u <= v1 ) 1118 u += d1; 1119 else 1120 u += d2; 1121 1122 p->u = u; 1123 } 1124 return; 1125 } 1126 1127 if ( v1 < v2 ) 1128 { 1129 for ( p = p1; p <= p2; p++ ) 1130 { 1131 u = p->v; 1132 1133 if ( u <= v1 ) 1134 u += d1; 1135 else if ( u >= v2 ) 1136 u += d2; 1137 else 1138 u = ref1->u + FT_MulDiv( u - v1, ref2->u - ref1->u, v2 - v1 ); 1139 1140 p->u = u; 1141 } 1142 } 1143 else 1144 { 1145 for ( p = p1; p <= p2; p++ ) 1146 { 1147 u = p->v; 1148 1149 if ( u <= v2 ) 1150 u += d2; 1151 else if ( u >= v1 ) 1152 u += d1; 1153 else 1154 u = ref1->u + FT_MulDiv( u - v1, ref2->u - ref1->u, v2 - v1 ); 1155 1156 p->u = u; 1157 } 1158 } 1159 } 1160 1161 1162 /* Hint the weak points -- this is equivalent to the TrueType `IUP' */ 1163 /* hinting instruction. */ 1164 1165 FT_LOCAL_DEF( void ) 1166 af_glyph_hints_align_weak_points( AF_GlyphHints hints, 1167 AF_Dimension dim ) 1168 { 1169 AF_Point points = hints->points; 1170 AF_Point point_limit = points + hints->num_points; 1171 AF_Point* contour = hints->contours; 1172 AF_Point* contour_limit = contour + hints->num_contours; 1173 AF_Flags touch_flag; 1174 AF_Point point; 1175 AF_Point end_point; 1176 AF_Point first_point; 1177 1178 1179 /* PASS 1: Move segment points to edge positions */ 1180 1181 if ( dim == AF_DIMENSION_HORZ ) 1182 { 1183 touch_flag = AF_FLAG_TOUCH_X; 1184 1185 for ( point = points; point < point_limit; point++ ) 1186 { 1187 point->u = point->x; 1188 point->v = point->ox; 1189 } 1190 } 1191 else 1192 { 1193 touch_flag = AF_FLAG_TOUCH_Y; 1194 1195 for ( point = points; point < point_limit; point++ ) 1196 { 1197 point->u = point->y; 1198 point->v = point->oy; 1199 } 1200 } 1201 1202 point = points; 1203 1204 for ( ; contour < contour_limit; contour++ ) 1205 { 1206 AF_Point first_touched, last_touched; 1207 1208 1209 point = *contour; 1210 end_point = point->prev; 1211 first_point = point; 1212 1213 /* find first touched point */ 1214 for (;;) 1215 { 1216 if ( point > end_point ) /* no touched point in contour */ 1217 goto NextContour; 1218 1219 if ( point->flags & touch_flag ) 1220 break; 1221 1222 point++; 1223 } 1224 1225 first_touched = point; 1226 last_touched = point; 1227 1228 for (;;) 1229 { 1230 FT_ASSERT( point <= end_point && 1231 ( point->flags & touch_flag ) != 0 ); 1232 1233 /* skip any touched neighbours */ 1234 while ( point < end_point && 1235 ( point[1].flags & touch_flag ) != 0 ) 1236 point++; 1237 1238 last_touched = point; 1239 1240 /* find the next touched point, if any */ 1241 point++; 1242 for (;;) 1243 { 1244 if ( point > end_point ) 1245 goto EndContour; 1246 1247 if ( ( point->flags & touch_flag ) != 0 ) 1248 break; 1249 1250 point++; 1251 } 1252 1253 /* interpolate between last_touched and point */ 1254 af_iup_interp( last_touched + 1, point - 1, 1255 last_touched, point ); 1256 } 1257 1258 EndContour: 1259 /* special case: only one point was touched */ 1260 if ( last_touched == first_touched ) 1261 af_iup_shift( first_point, end_point, first_touched ); 1262 1263 else /* interpolate the last part */ 1264 { 1265 if ( last_touched < end_point ) 1266 af_iup_interp( last_touched + 1, end_point, 1267 last_touched, first_touched ); 1268 1269 if ( first_touched > points ) 1270 af_iup_interp( first_point, first_touched - 1, 1271 last_touched, first_touched ); 1272 } 1273 1274 NextContour: 1275 ; 1276 } 1277 1278 /* now save the interpolated values back to x/y */ 1279 if ( dim == AF_DIMENSION_HORZ ) 1280 { 1281 for ( point = points; point < point_limit; point++ ) 1282 point->x = point->u; 1283 } 1284 else 1285 { 1286 for ( point = points; point < point_limit; point++ ) 1287 point->y = point->u; 1288 } 1289 } 1290 1291 1292#ifdef AF_CONFIG_OPTION_USE_WARPER 1293 1294 /* Apply (small) warp scale and warp delta for given dimension. */ 1295 1296 FT_LOCAL_DEF( void ) 1297 af_glyph_hints_scale_dim( AF_GlyphHints hints, 1298 AF_Dimension dim, 1299 FT_Fixed scale, 1300 FT_Pos delta ) 1301 { 1302 AF_Point points = hints->points; 1303 AF_Point points_limit = points + hints->num_points; 1304 AF_Point point; 1305 1306 1307 if ( dim == AF_DIMENSION_HORZ ) 1308 { 1309 for ( point = points; point < points_limit; point++ ) 1310 point->x = FT_MulFix( point->fx, scale ) + delta; 1311 } 1312 else 1313 { 1314 for ( point = points; point < points_limit; point++ ) 1315 point->y = FT_MulFix( point->fy, scale ) + delta; 1316 } 1317 } 1318 1319#endif /* AF_CONFIG_OPTION_USE_WARPER */ 1320 1321/* END */ 1322