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