1 /***************************************************************************/ 2 /* */ 3 /* ahglyph.c */ 4 /* */ 5 /* Routines used to load and analyze a given glyph before hinting */ 6 /* (body). */ 7 /* */ 8 /* Copyright 2000-2001, 2002 Catharon Productions Inc. */ 9 /* Author: David Turner */ 10 /* */ 11 /* This file is part of the Catharon Typography Project and shall only */ 12 /* be used, modified, and distributed under the terms of the Catharon */ 13 /* Open Source License that should come with this file under the name */ 14 /* `CatharonLicense.txt'. By continuing to use, modify, or distribute */ 15 /* this file you indicate that you have read the license and */ 16 /* understand and accept it fully. */ 17 /* */ 18 /* Note that this license is compatible with the FreeType license. */ 19 /* */ 20 /***************************************************************************/ 21 22 23 #include <ft2build.h> 24 #include "ahglyph.h" 25 #include "ahangles.h" 26 #include "ahglobal.h" 27 #include "aherrors.h" 28 29 30 #ifdef AH_DEBUG 31 32 #include <stdio.h> 33 34 void ah_dump_edges(AH_Outline outline)35 ah_dump_edges( AH_Outline outline ) 36 { 37 AH_Edge edges; 38 AH_Edge edge_limit; 39 AH_Segment segments; 40 FT_Int dimension; 41 42 43 edges = outline->horz_edges; 44 edge_limit = edges + outline->num_hedges; 45 segments = outline->horz_segments; 46 47 for ( dimension = 1; dimension >= 0; dimension-- ) 48 { 49 AH_Edge edge; 50 51 52 printf ( "Table of %s edges:\n", 53 !dimension ? "vertical" : "horizontal" ); 54 printf ( " [ index | pos | dir | link |" 55 " serif | blue | opos | pos ]\n" ); 56 57 for ( edge = edges; edge < edge_limit; edge++ ) 58 { 59 printf ( " [ %5d | %4d | %5s | %4d | %5d | %c | %5.2f | %5.2f ]\n", 60 edge - edges, 61 (int)edge->fpos, 62 edge->dir == AH_DIR_UP 63 ? "up" 64 : ( edge->dir == AH_DIR_DOWN 65 ? "down" 66 : ( edge->dir == AH_DIR_LEFT 67 ? "left" 68 : ( edge->dir == AH_DIR_RIGHT 69 ? "right" 70 : "none" ) ) ), 71 edge->link ? ( edge->link - edges ) : -1, 72 edge->serif ? ( edge->serif - edges ) : -1, 73 edge->blue_edge ? 'y' : 'n', 74 edge->opos / 64.0, 75 edge->pos / 64.0 ); 76 } 77 78 edges = outline->vert_edges; 79 edge_limit = edges + outline->num_vedges; 80 segments = outline->vert_segments; 81 } 82 } 83 84 85 /* A function used to dump the array of linked segments */ 86 void ah_dump_segments(AH_Outline outline)87 ah_dump_segments( AH_Outline outline ) 88 { 89 AH_Segment segments; 90 AH_Segment segment_limit; 91 AH_Point points; 92 FT_Int dimension; 93 94 95 points = outline->points; 96 segments = outline->horz_segments; 97 segment_limit = segments + outline->num_hsegments; 98 99 for ( dimension = 1; dimension >= 0; dimension-- ) 100 { 101 AH_Segment seg; 102 103 104 printf ( "Table of %s segments:\n", 105 !dimension ? "vertical" : "horizontal" ); 106 printf ( " [ index | pos | dir | link | serif |" 107 " numl | first | start ]\n" ); 108 109 for ( seg = segments; seg < segment_limit; seg++ ) 110 { 111 printf ( " [ %5d | %4d | %5s | %4d | %5d | %4d | %5d | %5d ]\n", 112 seg - segments, 113 (int)seg->pos, 114 seg->dir == AH_DIR_UP 115 ? "up" 116 : ( seg->dir == AH_DIR_DOWN 117 ? "down" 118 : ( seg->dir == AH_DIR_LEFT 119 ? "left" 120 : ( seg->dir == AH_DIR_RIGHT 121 ? "right" 122 : "none" ) ) ), 123 seg->link ? (seg->link-segments) : -1, 124 seg->serif ? (seg->serif-segments) : -1, 125 (int)seg->num_linked, 126 seg->first - points, 127 seg->last - points ); 128 } 129 130 segments = outline->vert_segments; 131 segment_limit = segments + outline->num_vsegments; 132 } 133 } 134 135 #endif /* AH_DEBUG */ 136 137 138 /* compute the direction value of a given vector.. */ 139 static AH_Direction ah_compute_direction(FT_Pos dx,FT_Pos dy)140 ah_compute_direction( FT_Pos dx, 141 FT_Pos dy ) 142 { 143 AH_Direction dir; 144 FT_Pos ax = ABS( dx ); 145 FT_Pos ay = ABS( dy ); 146 147 148 dir = AH_DIR_NONE; 149 150 /* test for vertical direction */ 151 if ( ax * 12 < ay ) 152 { 153 dir = dy > 0 ? AH_DIR_UP : AH_DIR_DOWN; 154 } 155 /* test for horizontal direction */ 156 else if ( ay * 12 < ax ) 157 { 158 dir = dx > 0 ? AH_DIR_RIGHT : AH_DIR_LEFT; 159 } 160 161 return dir; 162 } 163 164 165 /* this function is used by ah_get_orientation (see below) to test */ 166 /* the fill direction of a given bbox extrema */ 167 static FT_Int ah_test_extrema(FT_Outline * outline,FT_Int n)168 ah_test_extrema( FT_Outline* outline, 169 FT_Int n ) 170 { 171 FT_Vector *prev, *cur, *next; 172 FT_Pos product; 173 FT_Int first, last, c; 174 FT_Int retval; 175 176 177 /* we need to compute the `previous' and `next' point */ 178 /* for these extrema */ 179 cur = outline->points + n; 180 prev = cur - 1; 181 next = cur + 1; 182 183 first = 0; 184 for ( c = 0; c < outline->n_contours; c++ ) 185 { 186 last = outline->contours[c]; 187 188 if ( n == first ) 189 prev = outline->points + last; 190 191 if ( n == last ) 192 next = outline->points + first; 193 194 first = last + 1; 195 } 196 197 product = FT_MulDiv( cur->x - prev->x, /* in.x */ 198 next->y - cur->y, /* out.y */ 199 0x40 ) 200 - 201 FT_MulDiv( cur->y - prev->y, /* in.y */ 202 next->x - cur->x, /* out.x */ 203 0x40 ); 204 205 retval = 0; 206 if ( product ) 207 retval = product > 0 ? 2 : 1; 208 209 return retval; 210 } 211 212 213 /* Compute the orientation of path filling. It differs between TrueType */ 214 /* and Type1 formats. We could use the `FT_OUTLINE_REVERSE_FILL' flag, */ 215 /* but it is better to re-compute it directly (it seems that this flag */ 216 /* isn't correctly set for some weird composite glyphs currently). */ 217 /* */ 218 /* We do this by computing bounding box points, and computing their */ 219 /* curvature. */ 220 /* */ 221 /* The function returns either 1 or -1. */ 222 /* */ 223 static FT_Int ah_get_orientation(FT_Outline * outline)224 ah_get_orientation( FT_Outline* outline ) 225 { 226 FT_BBox box; 227 FT_Int indices_xMin, indices_yMin, indices_xMax, indices_yMax; 228 FT_Int n, last; 229 230 231 indices_xMin = -1; 232 indices_yMin = -1; 233 indices_xMax = -1; 234 indices_yMax = -1; 235 236 box.xMin = box.yMin = 32767L; 237 box.xMax = box.yMax = -32768L; 238 239 /* is it empty? */ 240 if ( outline->n_contours < 1 ) 241 return 1; 242 243 last = outline->contours[outline->n_contours - 1]; 244 245 for ( n = 0; n <= last; n++ ) 246 { 247 FT_Pos x, y; 248 249 250 x = outline->points[n].x; 251 if ( x < box.xMin ) 252 { 253 box.xMin = x; 254 indices_xMin = n; 255 } 256 if ( x > box.xMax ) 257 { 258 box.xMax = x; 259 indices_xMax = n; 260 } 261 262 y = outline->points[n].y; 263 if ( y < box.yMin ) 264 { 265 box.yMin = y; 266 indices_yMin = n; 267 } 268 if ( y > box.yMax ) 269 { 270 box.yMax = y; 271 indices_yMax = n; 272 } 273 } 274 275 /* test orientation of the xmin */ 276 n = ah_test_extrema( outline, indices_xMin ); 277 if ( n ) 278 goto Exit; 279 280 n = ah_test_extrema( outline, indices_yMin ); 281 if ( n ) 282 goto Exit; 283 284 n = ah_test_extrema( outline, indices_xMax ); 285 if ( n ) 286 goto Exit; 287 288 n = ah_test_extrema( outline, indices_yMax ); 289 if ( !n ) 290 n = 1; 291 292 Exit: 293 return n; 294 } 295 296 297 /*************************************************************************/ 298 /* */ 299 /* <Function> */ 300 /* ah_outline_new */ 301 /* */ 302 /* <Description> */ 303 /* Creates a new and empty AH_OutlineRec object. */ 304 /* */ 305 FT_LOCAL_DEF( FT_Error ) ah_outline_new(FT_Memory memory,AH_Outline * aoutline)306 ah_outline_new( FT_Memory memory, 307 AH_Outline* aoutline ) 308 { 309 FT_Error error; 310 AH_Outline outline; 311 312 313 if ( !FT_NEW( outline ) ) 314 { 315 outline->memory = memory; 316 *aoutline = outline; 317 } 318 319 return error; 320 } 321 322 323 /*************************************************************************/ 324 /* */ 325 /* <Function> */ 326 /* ah_outline_done */ 327 /* */ 328 /* <Description> */ 329 /* Destroys a given AH_OutlineRec object. */ 330 /* */ 331 FT_LOCAL_DEF( void ) ah_outline_done(AH_Outline outline)332 ah_outline_done( AH_Outline outline ) 333 { 334 FT_Memory memory = outline->memory; 335 336 337 FT_FREE( outline->horz_edges ); 338 FT_FREE( outline->horz_segments ); 339 FT_FREE( outline->contours ); 340 FT_FREE( outline->points ); 341 342 FT_FREE( outline ); 343 } 344 345 346 /*************************************************************************/ 347 /* */ 348 /* <Function> */ 349 /* ah_outline_save */ 350 /* */ 351 /* <Description> */ 352 /* Saves the contents of a given AH_OutlineRec object into a face's */ 353 /* glyph slot. */ 354 /* */ 355 FT_LOCAL_DEF( void ) ah_outline_save(AH_Outline outline,AH_Loader gloader)356 ah_outline_save( AH_Outline outline, 357 AH_Loader gloader ) 358 { 359 AH_Point point = outline->points; 360 AH_Point point_limit = point + outline->num_points; 361 FT_Vector* vec = gloader->current.outline.points; 362 char* tag = gloader->current.outline.tags; 363 364 365 /* we assume that the glyph loader has already been checked for storage */ 366 for ( ; point < point_limit; point++, vec++, tag++ ) 367 { 368 vec->x = point->x; 369 vec->y = point->y; 370 371 if ( point->flags & AH_FLAG_CONIC ) 372 tag[0] = FT_CURVE_TAG_CONIC; 373 else if ( point->flags & AH_FLAG_CUBIC ) 374 tag[0] = FT_CURVE_TAG_CUBIC; 375 else 376 tag[0] = FT_CURVE_TAG_ON; 377 } 378 } 379 380 381 /*************************************************************************/ 382 /* */ 383 /* <Function> */ 384 /* ah_outline_load */ 385 /* */ 386 /* <Description> */ 387 /* Loads an unscaled outline from a glyph slot into an AH_OutlineRec */ 388 /* object. */ 389 /* */ 390 FT_LOCAL_DEF( FT_Error ) ah_outline_load(AH_Outline outline,FT_Face face)391 ah_outline_load( AH_Outline outline, 392 FT_Face face ) 393 { 394 FT_Memory memory = outline->memory; 395 FT_Error error = AH_Err_Ok; 396 FT_Outline* source = &face->glyph->outline; 397 FT_Int num_points = source->n_points; 398 FT_Int num_contours = source->n_contours; 399 AH_Point points; 400 401 402 /* check arguments */ 403 if ( !face || 404 !face->size || 405 face->glyph->format != FT_GLYPH_FORMAT_OUTLINE ) 406 return AH_Err_Invalid_Argument; 407 408 /* first of all, reallocate the contours array if necessary */ 409 if ( num_contours > outline->max_contours ) 410 { 411 FT_Int new_contours = ( num_contours + 3 ) & -4; 412 413 414 if ( FT_RENEW_ARRAY( outline->contours, 415 outline->max_contours, 416 new_contours ) ) 417 goto Exit; 418 419 outline->max_contours = new_contours; 420 } 421 422 /* then, reallocate the points, segments & edges arrays if needed -- */ 423 /* note that we reserved two additional point positions, used to */ 424 /* hint metrics appropriately */ 425 /* */ 426 if ( num_points + 2 > outline->max_points ) 427 { 428 FT_Int news = ( num_points + 2 + 7 ) & -8; 429 FT_Int max = outline->max_points; 430 431 432 if ( FT_RENEW_ARRAY( outline->points, max, news ) || 433 FT_RENEW_ARRAY( outline->horz_edges, max * 2, news * 2 ) || 434 FT_RENEW_ARRAY( outline->horz_segments, max * 2, news * 2 ) ) 435 goto Exit; 436 437 /* readjust some pointers */ 438 outline->vert_edges = outline->horz_edges + news; 439 outline->vert_segments = outline->horz_segments + news; 440 outline->max_points = news; 441 } 442 443 outline->num_points = num_points; 444 outline->num_contours = num_contours; 445 446 outline->num_hedges = 0; 447 outline->num_vedges = 0; 448 outline->num_hsegments = 0; 449 outline->num_vsegments = 0; 450 451 /* We can't rely on the value of `FT_Outline.flags' to know the fill */ 452 /* direction used for a glyph, given that some fonts are broken (e.g. */ 453 /* the Arphic ones). We thus recompute it each time we need to. */ 454 /* */ 455 outline->vert_major_dir = AH_DIR_UP; 456 outline->horz_major_dir = AH_DIR_LEFT; 457 458 if ( ah_get_orientation( source ) > 1 ) 459 { 460 outline->vert_major_dir = AH_DIR_DOWN; 461 outline->horz_major_dir = AH_DIR_RIGHT; 462 } 463 464 outline->x_scale = face->size->metrics.x_scale; 465 outline->y_scale = face->size->metrics.y_scale; 466 467 points = outline->points; 468 if ( outline->num_points == 0 ) 469 goto Exit; 470 471 { 472 /* do one thing at a time -- it is easier to understand, and */ 473 /* the code is clearer */ 474 AH_Point point; 475 AH_Point point_limit = points + outline->num_points; 476 477 478 /* compute coordinates */ 479 { 480 FT_Vector* vec = source->points; 481 FT_Fixed x_scale = outline->x_scale; 482 FT_Fixed y_scale = outline->y_scale; 483 484 485 for ( point = points; point < point_limit; vec++, point++ ) 486 { 487 point->fx = vec->x; 488 point->fy = vec->y; 489 point->ox = point->x = FT_MulFix( vec->x, x_scale ); 490 point->oy = point->y = FT_MulFix( vec->y, y_scale ); 491 492 point->flags = 0; 493 } 494 } 495 496 /* compute Bezier flags */ 497 { 498 char* tag = source->tags; 499 500 501 for ( point = points; point < point_limit; point++, tag++ ) 502 { 503 switch ( FT_CURVE_TAG( *tag ) ) 504 { 505 case FT_CURVE_TAG_CONIC: 506 point->flags = AH_FLAG_CONIC; break; 507 case FT_CURVE_TAG_CUBIC: 508 point->flags = AH_FLAG_CUBIC; break; 509 default: 510 ; 511 } 512 } 513 } 514 515 /* compute `next' and `prev' */ 516 { 517 FT_Int contour_index; 518 AH_Point prev; 519 AH_Point first; 520 AH_Point end; 521 522 523 contour_index = 0; 524 525 first = points; 526 end = points + source->contours[0]; 527 prev = end; 528 529 for ( point = points; point < point_limit; point++ ) 530 { 531 point->prev = prev; 532 if ( point < end ) 533 { 534 point->next = point + 1; 535 prev = point; 536 } 537 else 538 { 539 point->next = first; 540 contour_index++; 541 if ( point + 1 < point_limit ) 542 { 543 end = points + source->contours[contour_index]; 544 first = point + 1; 545 prev = end; 546 } 547 } 548 } 549 } 550 551 /* set-up the contours array */ 552 { 553 AH_Point* contour = outline->contours; 554 AH_Point* contour_limit = contour + outline->num_contours; 555 short* end = source->contours; 556 short idx = 0; 557 558 559 for ( ; contour < contour_limit; contour++, end++ ) 560 { 561 contour[0] = points + idx; 562 idx = (short)( end[0] + 1 ); 563 } 564 } 565 566 /* compute directions of in & out vectors */ 567 { 568 for ( point = points; point < point_limit; point++ ) 569 { 570 AH_Point prev; 571 AH_Point next; 572 FT_Vector ivec, ovec; 573 574 575 prev = point->prev; 576 ivec.x = point->fx - prev->fx; 577 ivec.y = point->fy - prev->fy; 578 579 point->in_dir = ah_compute_direction( ivec.x, ivec.y ); 580 581 next = point->next; 582 ovec.x = next->fx - point->fx; 583 ovec.y = next->fy - point->fy; 584 585 point->out_dir = ah_compute_direction( ovec.x, ovec.y ); 586 587 #ifndef AH_OPTION_NO_WEAK_INTERPOLATION 588 if ( point->flags & (AH_FLAG_CONIC | AH_FLAG_CUBIC) ) 589 { 590 Is_Weak_Point: 591 point->flags |= AH_FLAG_WEAK_INTERPOLATION; 592 } 593 else if ( point->out_dir == point->in_dir ) 594 { 595 AH_Angle angle_in, angle_out, delta; 596 597 598 if ( point->out_dir != AH_DIR_NONE ) 599 goto Is_Weak_Point; 600 601 angle_in = ah_angle( &ivec ); 602 angle_out = ah_angle( &ovec ); 603 delta = angle_in - angle_out; 604 605 if ( delta > AH_PI ) 606 delta = AH_2PI - delta; 607 608 if ( delta < 0 ) 609 delta = -delta; 610 611 if ( delta < 2 ) 612 goto Is_Weak_Point; 613 } 614 else if ( point->in_dir == -point->out_dir ) 615 goto Is_Weak_Point; 616 #endif 617 } 618 } 619 } 620 621 Exit: 622 return error; 623 } 624 625 626 FT_LOCAL_DEF( void ) ah_setup_uv(AH_Outline outline,AH_UV source)627 ah_setup_uv( AH_Outline outline, 628 AH_UV source ) 629 { 630 AH_Point point = outline->points; 631 AH_Point point_limit = point + outline->num_points; 632 633 634 for ( ; point < point_limit; point++ ) 635 { 636 FT_Pos u, v; 637 638 639 switch ( source ) 640 { 641 case AH_UV_FXY: 642 u = point->fx; 643 v = point->fy; 644 break; 645 case AH_UV_FYX: 646 u = point->fy; 647 v = point->fx; 648 break; 649 case AH_UV_OXY: 650 u = point->ox; 651 v = point->oy; 652 break; 653 case AH_UV_OYX: 654 u = point->oy; 655 v = point->ox; 656 break; 657 case AH_UV_YX: 658 u = point->y; 659 v = point->x; 660 break; 661 case AH_UV_OX: 662 u = point->x; 663 v = point->ox; 664 break; 665 case AH_UV_OY: 666 u = point->y; 667 v = point->oy; 668 break; 669 default: 670 u = point->x; 671 v = point->y; 672 break; 673 } 674 point->u = u; 675 point->v = v; 676 } 677 } 678 679 680 /* compute all inflex points in a given glyph */ 681 static void ah_outline_compute_inflections(AH_Outline outline)682 ah_outline_compute_inflections( AH_Outline outline ) 683 { 684 AH_Point* contour = outline->contours; 685 AH_Point* contour_limit = contour + outline->num_contours; 686 687 688 /* load original coordinates in (u,v) */ 689 ah_setup_uv( outline, AH_UV_FXY ); 690 691 /* do each contour separately */ 692 for ( ; contour < contour_limit; contour++ ) 693 { 694 FT_Vector vec; 695 AH_Point point = contour[0]; 696 AH_Point first = point; 697 AH_Point start = point; 698 AH_Point end = point; 699 AH_Point before; 700 AH_Point after; 701 AH_Angle angle_in, angle_seg, angle_out; 702 AH_Angle diff_in, diff_out; 703 FT_Int finished = 0; 704 705 706 /* compute first segment in contour */ 707 first = point; 708 709 start = end = first; 710 do 711 { 712 end = end->next; 713 if ( end == first ) 714 goto Skip; 715 716 } while ( end->u == first->u && end->v == first->v ); 717 718 vec.x = end->u - start->u; 719 vec.y = end->v - start->v; 720 angle_seg = ah_angle( &vec ); 721 722 /* extend the segment start whenever possible */ 723 before = start; 724 do 725 { 726 do 727 { 728 start = before; 729 before = before->prev; 730 if ( before == first ) 731 goto Skip; 732 733 } while ( before->u == start->u && before->v == start->v ); 734 735 vec.x = start->u - before->u; 736 vec.y = start->v - before->v; 737 angle_in = ah_angle( &vec ); 738 739 } while ( angle_in == angle_seg ); 740 741 first = start; 742 diff_in = ah_angle_diff( angle_in, angle_seg ); 743 744 /* now, process all segments in the contour */ 745 do 746 { 747 /* first, extend current segment's end whenever possible */ 748 after = end; 749 do 750 { 751 do 752 { 753 end = after; 754 after = after->next; 755 if ( after == first ) 756 finished = 1; 757 758 } while ( end->u == after->u && end->v == after->v ); 759 760 vec.x = after->u - end->u; 761 vec.y = after->v - end->v; 762 angle_out = ah_angle( &vec ); 763 764 } while ( angle_out == angle_seg ); 765 766 diff_out = ah_angle_diff( angle_seg, angle_out ); 767 768 if ( ( diff_in ^ diff_out ) < 0 ) 769 { 770 /* diff_in and diff_out have different signs, we have */ 771 /* inflection points here... */ 772 773 do 774 { 775 start->flags |= AH_FLAG_INFLECTION; 776 start = start->next; 777 778 } while ( start != end ); 779 780 start->flags |= AH_FLAG_INFLECTION; 781 } 782 783 start = end; 784 end = after; 785 angle_seg = angle_out; 786 diff_in = diff_out; 787 788 } while ( !finished ); 789 790 Skip: 791 ; 792 } 793 } 794 795 796 FT_LOCAL_DEF( void ) ah_outline_compute_segments(AH_Outline outline)797 ah_outline_compute_segments( AH_Outline outline ) 798 { 799 int dimension; 800 AH_Segment segments; 801 FT_Int* p_num_segments; 802 AH_Direction segment_dir; 803 AH_Direction major_dir; 804 805 806 segments = outline->horz_segments; 807 p_num_segments = &outline->num_hsegments; 808 major_dir = AH_DIR_RIGHT; /* This value must be positive! */ 809 segment_dir = major_dir; 810 811 /* set up (u,v) in each point */ 812 ah_setup_uv( outline, AH_UV_FYX ); 813 814 for ( dimension = 1; dimension >= 0; dimension-- ) 815 { 816 AH_Point* contour = outline->contours; 817 AH_Point* contour_limit = contour + outline->num_contours; 818 AH_Segment segment = segments; 819 FT_Int num_segments = 0; 820 821 #ifdef AH_HINT_METRICS 822 AH_Point min_point = 0; 823 AH_Point max_point = 0; 824 FT_Pos min_coord = 32000; 825 FT_Pos max_coord = -32000; 826 #endif 827 828 829 /* do each contour separately */ 830 for ( ; contour < contour_limit; contour++ ) 831 { 832 AH_Point point = contour[0]; 833 AH_Point last = point->prev; 834 int on_edge = 0; 835 FT_Pos min_pos = +32000; /* minimum segment pos != min_coord */ 836 FT_Pos max_pos = -32000; /* maximum segment pos != max_coord */ 837 FT_Bool passed; 838 839 840 #ifdef AH_HINT_METRICS 841 if ( point->u < min_coord ) 842 { 843 min_coord = point->u; 844 min_point = point; 845 } 846 if ( point->u > max_coord ) 847 { 848 max_coord = point->u; 849 max_point = point; 850 } 851 #endif 852 853 if ( point == last ) /* skip singletons -- just in case? */ 854 continue; 855 856 if ( ABS( last->out_dir ) == major_dir && 857 ABS( point->out_dir ) == major_dir ) 858 { 859 /* we are already on an edge, try to locate its start */ 860 last = point; 861 862 for (;;) 863 { 864 point = point->prev; 865 if ( ABS( point->out_dir ) != major_dir ) 866 { 867 point = point->next; 868 break; 869 } 870 if ( point == last ) 871 break; 872 } 873 } 874 875 last = point; 876 passed = 0; 877 878 for (;;) 879 { 880 FT_Pos u, v; 881 882 883 if ( on_edge ) 884 { 885 u = point->u; 886 if ( u < min_pos ) 887 min_pos = u; 888 if ( u > max_pos ) 889 max_pos = u; 890 891 if ( point->out_dir != segment_dir || point == last ) 892 { 893 /* we are just leaving an edge; record a new segment! */ 894 segment->last = point; 895 segment->pos = ( min_pos + max_pos ) >> 1; 896 897 /* a segment is round if either its first or last point */ 898 /* is a control point */ 899 if ( ( segment->first->flags | point->flags ) & 900 AH_FLAG_CONTROL ) 901 segment->flags |= AH_EDGE_ROUND; 902 903 /* compute segment size */ 904 min_pos = max_pos = point->v; 905 906 v = segment->first->v; 907 if ( v < min_pos ) 908 min_pos = v; 909 if ( v > max_pos ) 910 max_pos = v; 911 912 segment->min_coord = min_pos; 913 segment->max_coord = max_pos; 914 915 on_edge = 0; 916 num_segments++; 917 segment++; 918 /* fallthrough */ 919 } 920 } 921 922 /* now exit if we are at the start/end point */ 923 if ( point == last ) 924 { 925 if ( passed ) 926 break; 927 passed = 1; 928 } 929 930 if ( !on_edge && ABS( point->out_dir ) == major_dir ) 931 { 932 /* this is the start of a new segment! */ 933 segment_dir = point->out_dir; 934 935 /* clear all segment fields */ 936 FT_ZERO( segment ); 937 938 segment->dir = segment_dir; 939 segment->flags = AH_EDGE_NORMAL; 940 min_pos = max_pos = point->u; 941 segment->first = point; 942 segment->last = point; 943 segment->contour = contour; 944 on_edge = 1; 945 946 #ifdef AH_HINT_METRICS 947 if ( point == max_point ) 948 max_point = 0; 949 950 if ( point == min_point ) 951 min_point = 0; 952 #endif 953 } 954 955 point = point->next; 956 } 957 958 } /* contours */ 959 960 #ifdef AH_HINT_METRICS 961 /* we need to ensure that there are edges on the left-most and */ 962 /* right-most points of the glyph in order to hint the metrics; */ 963 /* we do this by inserting fake segments when needed */ 964 if ( dimension == 0 ) 965 { 966 AH_Point point = outline->points; 967 AH_Point point_limit = point + outline->num_points; 968 969 FT_Pos min_pos = 32000; 970 FT_Pos max_pos = -32000; 971 972 973 min_point = 0; 974 max_point = 0; 975 976 /* compute minimum and maximum points */ 977 for ( ; point < point_limit; point++ ) 978 { 979 FT_Pos x = point->fx; 980 981 982 if ( x < min_pos ) 983 { 984 min_pos = x; 985 min_point = point; 986 } 987 if ( x > max_pos ) 988 { 989 max_pos = x; 990 max_point = point; 991 } 992 } 993 994 /* insert minimum segment */ 995 if ( min_point ) 996 { 997 /* clear all segment fields */ 998 FT_ZERO( segment ); 999 1000 segment->dir = segment_dir; 1001 segment->flags = AH_EDGE_NORMAL; 1002 segment->first = min_point; 1003 segment->last = min_point; 1004 segment->pos = min_pos; 1005 1006 num_segments++; 1007 segment++; 1008 } 1009 1010 /* insert maximum segment */ 1011 if ( max_point ) 1012 { 1013 /* clear all segment fields */ 1014 FT_ZERO( segment ); 1015 1016 segment->dir = segment_dir; 1017 segment->flags = AH_EDGE_NORMAL; 1018 segment->first = max_point; 1019 segment->last = max_point; 1020 segment->pos = max_pos; 1021 1022 num_segments++; 1023 segment++; 1024 } 1025 } 1026 #endif /* AH_HINT_METRICS */ 1027 1028 *p_num_segments = num_segments; 1029 1030 segments = outline->vert_segments; 1031 major_dir = AH_DIR_UP; 1032 p_num_segments = &outline->num_vsegments; 1033 ah_setup_uv( outline, AH_UV_FXY ); 1034 } 1035 } 1036 1037 1038 FT_LOCAL_DEF( void ) ah_outline_link_segments(AH_Outline outline)1039 ah_outline_link_segments( AH_Outline outline ) 1040 { 1041 AH_Segment segments; 1042 AH_Segment segment_limit; 1043 int dimension; 1044 1045 1046 ah_setup_uv( outline, AH_UV_FYX ); 1047 1048 segments = outline->horz_segments; 1049 segment_limit = segments + outline->num_hsegments; 1050 1051 for ( dimension = 1; dimension >= 0; dimension-- ) 1052 { 1053 AH_Segment seg1; 1054 AH_Segment seg2; 1055 1056 1057 /* now compare each segment to the others */ 1058 for ( seg1 = segments; seg1 < segment_limit; seg1++ ) 1059 { 1060 FT_Pos best_score; 1061 AH_Segment best_segment; 1062 1063 1064 /* the fake segments are introduced to hint the metrics -- */ 1065 /* we must never link them to anything */ 1066 if ( seg1->first == seg1->last ) 1067 continue; 1068 1069 best_segment = seg1->link; 1070 if ( best_segment ) 1071 best_score = seg1->score; 1072 else 1073 best_score = 32000; 1074 1075 for ( seg2 = segments; seg2 < segment_limit; seg2++ ) 1076 if ( seg1 != seg2 && seg1->dir + seg2->dir == 0 ) 1077 { 1078 FT_Pos pos1 = seg1->pos; 1079 FT_Pos pos2 = seg2->pos; 1080 FT_Bool is_dir; 1081 FT_Bool is_pos; 1082 1083 1084 /* check that the segments are correctly oriented and */ 1085 /* positioned to form a black distance */ 1086 1087 is_dir = (FT_Bool)( seg1->dir == outline->horz_major_dir || 1088 seg1->dir == outline->vert_major_dir ); 1089 is_pos = (FT_Bool)( pos1 > pos2 ); 1090 1091 if ( pos1 == pos2 || !(is_dir ^ is_pos) ) 1092 continue; 1093 1094 { 1095 FT_Pos min = seg1->min_coord; 1096 FT_Pos max = seg1->max_coord; 1097 FT_Pos len, dist, score; 1098 1099 1100 if ( min < seg2->min_coord ) 1101 min = seg2->min_coord; 1102 1103 if ( max > seg2->max_coord ) 1104 max = seg2->max_coord; 1105 1106 len = max - min; 1107 if ( len >= 8 ) 1108 { 1109 dist = seg2->pos - seg1->pos; 1110 if ( dist < 0 ) 1111 dist = -dist; 1112 1113 score = dist + 3000 / len; 1114 1115 if ( score < best_score ) 1116 { 1117 best_score = score; 1118 best_segment = seg2; 1119 } 1120 } 1121 } 1122 } 1123 1124 if ( best_segment ) 1125 { 1126 seg1->link = best_segment; 1127 seg1->score = best_score; 1128 1129 best_segment->num_linked++; 1130 } 1131 1132 } /* edges 1 */ 1133 1134 /* now, compute the `serif' segments */ 1135 for ( seg1 = segments; seg1 < segment_limit; seg1++ ) 1136 { 1137 seg2 = seg1->link; 1138 1139 if ( seg2 && seg2->link != seg1 ) 1140 { 1141 seg1->link = 0; 1142 seg1->serif = seg2->link; 1143 } 1144 } 1145 1146 ah_setup_uv( outline, AH_UV_FXY ); 1147 1148 segments = outline->vert_segments; 1149 segment_limit = segments + outline->num_vsegments; 1150 } 1151 } 1152 1153 1154 static void ah_outline_compute_edges(AH_Outline outline)1155 ah_outline_compute_edges( AH_Outline outline ) 1156 { 1157 AH_Edge edges; 1158 AH_Segment segments; 1159 AH_Segment segment_limit; 1160 AH_Direction up_dir; 1161 FT_Int* p_num_edges; 1162 FT_Int dimension; 1163 FT_Fixed scale; 1164 FT_Pos edge_distance_threshold; 1165 1166 1167 edges = outline->horz_edges; 1168 segments = outline->horz_segments; 1169 segment_limit = segments + outline->num_hsegments; 1170 p_num_edges = &outline->num_hedges; 1171 up_dir = AH_DIR_RIGHT; 1172 scale = outline->y_scale; 1173 1174 for ( dimension = 1; dimension >= 0; dimension-- ) 1175 { 1176 AH_Edge edge; 1177 AH_Edge edge_limit; /* really == edge + num_edges */ 1178 AH_Segment seg; 1179 1180 1181 /*********************************************************************/ 1182 /* */ 1183 /* We will begin by generating a sorted table of edges for the */ 1184 /* current direction. To do so, we simply scan each segment and try */ 1185 /* to find an edge in our table that corresponds to its position. */ 1186 /* */ 1187 /* If no edge is found, we create and insert a new edge in the */ 1188 /* sorted table. Otherwise, we simply add the segment to the edge's */ 1189 /* list which will be processed in the second step to compute the */ 1190 /* edge's properties. */ 1191 /* */ 1192 /* Note that the edges table is sorted along the segment/edge */ 1193 /* position. */ 1194 /* */ 1195 /*********************************************************************/ 1196 1197 edge_distance_threshold = FT_MulFix( outline->edge_distance_threshold, 1198 scale ); 1199 if ( edge_distance_threshold > 64 / 4 ) 1200 edge_distance_threshold = 64 / 4; 1201 1202 edge_limit = edges; 1203 for ( seg = segments; seg < segment_limit; seg++ ) 1204 { 1205 AH_Edge found = 0; 1206 1207 1208 /* look for an edge corresponding to the segment */ 1209 for ( edge = edges; edge < edge_limit; edge++ ) 1210 { 1211 FT_Pos dist; 1212 1213 1214 dist = seg->pos - edge->fpos; 1215 if ( dist < 0 ) 1216 dist = -dist; 1217 1218 dist = FT_MulFix( dist, scale ); 1219 if ( dist < edge_distance_threshold ) 1220 { 1221 found = edge; 1222 break; 1223 } 1224 } 1225 1226 if ( !found ) 1227 { 1228 /* insert a new edge in the list and */ 1229 /* sort according to the position */ 1230 while ( edge > edges && edge[-1].fpos > seg->pos ) 1231 { 1232 edge[0] = edge[-1]; 1233 edge--; 1234 } 1235 edge_limit++; 1236 1237 /* clear all edge fields */ 1238 FT_MEM_ZERO( edge, sizeof ( *edge ) ); 1239 1240 /* add the segment to the new edge's list */ 1241 edge->first = seg; 1242 edge->last = seg; 1243 edge->fpos = seg->pos; 1244 edge->opos = edge->pos = FT_MulFix( seg->pos, scale ); 1245 seg->edge_next = seg; 1246 } 1247 else 1248 { 1249 /* if an edge was found, simply add the segment to the edge's */ 1250 /* list */ 1251 seg->edge_next = edge->first; 1252 edge->last->edge_next = seg; 1253 edge->last = seg; 1254 } 1255 } 1256 1257 *p_num_edges = (FT_Int)( edge_limit - edges ); 1258 1259 1260 /*********************************************************************/ 1261 /* */ 1262 /* Good, we will now compute each edge's properties according to */ 1263 /* segments found on its position. Basically, these are: */ 1264 /* */ 1265 /* - edge's main direction */ 1266 /* - stem edge, serif edge or both (which defaults to stem then) */ 1267 /* - rounded edge, straigth or both (which defaults to straight) */ 1268 /* - link for edge */ 1269 /* */ 1270 /*********************************************************************/ 1271 1272 /* first of all, set the `edge' field in each segment -- this is */ 1273 /* required in order to compute edge links */ 1274 for ( edge = edges; edge < edge_limit; edge++ ) 1275 { 1276 seg = edge->first; 1277 if ( seg ) 1278 do 1279 { 1280 seg->edge = edge; 1281 seg = seg->edge_next; 1282 } 1283 while ( seg != edge->first ); 1284 } 1285 1286 /* now, compute each edge properties */ 1287 for ( edge = edges; edge < edge_limit; edge++ ) 1288 { 1289 FT_Int is_round = 0; /* does it contain round segments? */ 1290 FT_Int is_straight = 0; /* does it contain straight segments? */ 1291 FT_Pos ups = 0; /* number of upwards segments */ 1292 FT_Pos downs = 0; /* number of downwards segments */ 1293 1294 1295 seg = edge->first; 1296 1297 do 1298 { 1299 FT_Bool is_serif; 1300 1301 1302 /* check for roundness of segment */ 1303 if ( seg->flags & AH_EDGE_ROUND ) 1304 is_round++; 1305 else 1306 is_straight++; 1307 1308 /* check for segment direction */ 1309 if ( seg->dir == up_dir ) 1310 ups += seg->max_coord-seg->min_coord; 1311 else 1312 downs += seg->max_coord-seg->min_coord; 1313 1314 /* check for links -- if seg->serif is set, then seg->link must */ 1315 /* be ignored */ 1316 is_serif = (FT_Bool)( seg->serif && seg->serif->edge != edge ); 1317 1318 if ( seg->link || is_serif ) 1319 { 1320 AH_Edge edge2; 1321 AH_Segment seg2; 1322 1323 1324 edge2 = edge->link; 1325 seg2 = seg->link; 1326 1327 if ( is_serif ) 1328 { 1329 seg2 = seg->serif; 1330 edge2 = edge->serif; 1331 } 1332 1333 if ( edge2 ) 1334 { 1335 FT_Pos edge_delta; 1336 FT_Pos seg_delta; 1337 1338 1339 edge_delta = edge->fpos - edge2->fpos; 1340 if ( edge_delta < 0 ) 1341 edge_delta = -edge_delta; 1342 1343 seg_delta = seg->pos - seg2->pos; 1344 if ( seg_delta < 0 ) 1345 seg_delta = -seg_delta; 1346 1347 if ( seg_delta < edge_delta ) 1348 edge2 = seg2->edge; 1349 } 1350 else 1351 edge2 = seg2->edge; 1352 1353 if ( is_serif ) 1354 edge->serif = edge2; 1355 else 1356 edge->link = edge2; 1357 } 1358 1359 seg = seg->edge_next; 1360 1361 } while ( seg != edge->first ); 1362 1363 /* set the round/straight flags */ 1364 edge->flags = AH_EDGE_NORMAL; 1365 1366 if ( is_round > 0 && is_round >= is_straight ) 1367 edge->flags |= AH_EDGE_ROUND; 1368 1369 /* set the edge's main direction */ 1370 edge->dir = AH_DIR_NONE; 1371 1372 if ( ups > downs ) 1373 edge->dir = up_dir; 1374 1375 else if ( ups < downs ) 1376 edge->dir = - up_dir; 1377 1378 else if ( ups == downs ) 1379 edge->dir = 0; /* both up and down !! */ 1380 1381 /* gets rid of serifs if link is set */ 1382 /* XXX: This gets rid of many unpleasant artefacts! */ 1383 /* Example: the `c' in cour.pfa at size 13 */ 1384 1385 if ( edge->serif && edge->link ) 1386 edge->serif = 0; 1387 } 1388 1389 edges = outline->vert_edges; 1390 segments = outline->vert_segments; 1391 segment_limit = segments + outline->num_vsegments; 1392 p_num_edges = &outline->num_vedges; 1393 up_dir = AH_DIR_UP; 1394 scale = outline->x_scale; 1395 } 1396 } 1397 1398 1399 /*************************************************************************/ 1400 /* */ 1401 /* <Function> */ 1402 /* ah_outline_detect_features */ 1403 /* */ 1404 /* <Description> */ 1405 /* Performs feature detection on a given AH_OutlineRec object. */ 1406 /* */ 1407 FT_LOCAL_DEF( void ) ah_outline_detect_features(AH_Outline outline)1408 ah_outline_detect_features( AH_Outline outline ) 1409 { 1410 ah_outline_compute_segments ( outline ); 1411 ah_outline_link_segments ( outline ); 1412 ah_outline_compute_edges ( outline ); 1413 ah_outline_compute_inflections( outline ); 1414 } 1415 1416 1417 /*************************************************************************/ 1418 /* */ 1419 /* <Function> */ 1420 /* ah_outline_compute_blue_edges */ 1421 /* */ 1422 /* <Description> */ 1423 /* Computes the `blue edges' in a given outline (i.e. those that must */ 1424 /* be snapped to a blue zone edge (top or bottom). */ 1425 /* */ 1426 FT_LOCAL_DEF( void ) ah_outline_compute_blue_edges(AH_Outline outline,AH_Face_Globals face_globals)1427 ah_outline_compute_blue_edges( AH_Outline outline, 1428 AH_Face_Globals face_globals ) 1429 { 1430 AH_Edge edge = outline->horz_edges; 1431 AH_Edge edge_limit = edge + outline->num_hedges; 1432 AH_Globals globals = &face_globals->design; 1433 FT_Fixed y_scale = outline->y_scale; 1434 1435 FT_Bool blue_active[AH_BLUE_MAX]; 1436 1437 1438 /* compute which blue zones are active, i.e. have their scaled */ 1439 /* size < 3/4 pixels */ 1440 { 1441 AH_Blue blue; 1442 FT_Bool check = 0; 1443 1444 1445 for ( blue = AH_BLUE_CAPITAL_TOP; blue < AH_BLUE_MAX; blue++ ) 1446 { 1447 FT_Pos ref, shoot, dist; 1448 1449 1450 ref = globals->blue_refs[blue]; 1451 shoot = globals->blue_shoots[blue]; 1452 dist = ref-shoot; 1453 if ( dist < 0 ) 1454 dist = -dist; 1455 1456 blue_active[blue] = 0; 1457 1458 if ( FT_MulFix( dist, y_scale ) < 48 ) 1459 { 1460 blue_active[blue] = 1; 1461 check = 1; 1462 } 1463 } 1464 1465 /* return immediately if no blue zone is active */ 1466 if ( !check ) 1467 return; 1468 } 1469 1470 /* compute for each horizontal edge, which blue zone is closer */ 1471 for ( ; edge < edge_limit; edge++ ) 1472 { 1473 AH_Blue blue; 1474 FT_Pos* best_blue = 0; 1475 FT_Pos best_dist; /* initial threshold */ 1476 1477 1478 /* compute the initial threshold as a fraction of the EM size */ 1479 best_dist = FT_MulFix( face_globals->face->units_per_EM / 40, y_scale ); 1480 if ( best_dist > 64 / 4 ) 1481 best_dist = 64 / 4; 1482 1483 for ( blue = AH_BLUE_CAPITAL_TOP; blue < AH_BLUE_MAX; blue++ ) 1484 { 1485 /* if it is a top zone, check for right edges -- if it is a bottom */ 1486 /* zone, check for left edges */ 1487 /* */ 1488 /* of course, that's for TrueType XXX */ 1489 FT_Bool is_top_blue = 1490 FT_BOOL( AH_IS_TOP_BLUE( blue ) ); 1491 FT_Bool is_major_dir = 1492 FT_BOOL( edge->dir == outline->horz_major_dir ); 1493 1494 if ( !blue_active[blue] ) 1495 continue; 1496 1497 /* if it is a top zone, the edge must be against the major */ 1498 /* direction; if it is a bottom zone, it must be in the major */ 1499 /* direction */ 1500 if ( is_top_blue ^ is_major_dir ) 1501 { 1502 FT_Pos dist; 1503 FT_Pos* blue_pos = globals->blue_refs + blue; 1504 1505 1506 /* first of all, compare it to the reference position */ 1507 dist = edge->fpos - *blue_pos; 1508 if ( dist < 0 ) 1509 dist = -dist; 1510 1511 dist = FT_MulFix( dist, y_scale ); 1512 if ( dist < best_dist ) 1513 { 1514 best_dist = dist; 1515 best_blue = blue_pos; 1516 } 1517 1518 /* now, compare it to the overshoot position if the edge is */ 1519 /* rounded, and if the edge is over the reference position of a */ 1520 /* top zone, or under the reference position of a bottom zone */ 1521 if ( edge->flags & AH_EDGE_ROUND && dist != 0 ) 1522 { 1523 FT_Bool is_under_ref = FT_BOOL( edge->fpos < *blue_pos ); 1524 1525 1526 if ( is_top_blue ^ is_under_ref ) 1527 { 1528 blue_pos = globals->blue_shoots + blue; 1529 dist = edge->fpos - *blue_pos; 1530 if ( dist < 0 ) 1531 dist = -dist; 1532 1533 dist = FT_MulFix( dist, y_scale ); 1534 if ( dist < best_dist ) 1535 { 1536 best_dist = dist; 1537 best_blue = blue_pos; 1538 } 1539 } 1540 } 1541 } 1542 } 1543 1544 if ( best_blue ) 1545 edge->blue_edge = best_blue; 1546 } 1547 } 1548 1549 1550 /*************************************************************************/ 1551 /* */ 1552 /* <Function> */ 1553 /* ah_outline_scale_blue_edges */ 1554 /* */ 1555 /* <Description> */ 1556 /* This functions must be called before hinting in order to re-adjust */ 1557 /* the contents of the detected edges (basically change the `blue */ 1558 /* edge' pointer from `design units' to `scaled ones'). */ 1559 /* */ 1560 FT_LOCAL_DEF( void ) ah_outline_scale_blue_edges(AH_Outline outline,AH_Face_Globals globals)1561 ah_outline_scale_blue_edges( AH_Outline outline, 1562 AH_Face_Globals globals ) 1563 { 1564 AH_Edge edge = outline->horz_edges; 1565 AH_Edge edge_limit = edge + outline->num_hedges; 1566 FT_Pos delta; 1567 1568 1569 delta = globals->scaled.blue_refs - globals->design.blue_refs; 1570 1571 for ( ; edge < edge_limit; edge++ ) 1572 { 1573 if ( edge->blue_edge ) 1574 edge->blue_edge += delta; 1575 } 1576 } 1577 1578 1579 /* END */ 1580