1 /***************************************************************************/ 2 /* */ 3 /* pshalgo2.c */ 4 /* */ 5 /* PostScript hinting algorithm 2 (body). */ 6 /* */ 7 /* Copyright 2001, 2002 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 <ft2build.h> 20 #include FT_INTERNAL_OBJECTS_H 21 #include FT_INTERNAL_DEBUG_H 22 #include "pshalgo2.h" 23 24 #undef FT_COMPONENT 25 #define FT_COMPONENT trace_pshalgo2 26 27 #ifdef DEBUG_HINTER 28 PSH2_Hint_Table ps2_debug_hint_table = 0; 29 PSH2_HintFunc ps2_debug_hint_func = 0; 30 PSH2_Glyph ps2_debug_glyph = 0; 31 #endif 32 33 34 /*************************************************************************/ 35 /*************************************************************************/ 36 /***** *****/ 37 /***** BASIC HINTS RECORDINGS *****/ 38 /***** *****/ 39 /*************************************************************************/ 40 /*************************************************************************/ 41 42 /* return true iff two stem hints overlap */ 43 static FT_Int psh2_hint_overlap(PSH2_Hint hint1,PSH2_Hint hint2)44 psh2_hint_overlap( PSH2_Hint hint1, 45 PSH2_Hint hint2 ) 46 { 47 return ( hint1->org_pos + hint1->org_len >= hint2->org_pos && 48 hint2->org_pos + hint2->org_len >= hint1->org_pos ); 49 } 50 51 52 /* destroy hints table */ 53 static void psh2_hint_table_done(PSH2_Hint_Table table,FT_Memory memory)54 psh2_hint_table_done( PSH2_Hint_Table table, 55 FT_Memory memory ) 56 { 57 FT_FREE( table->zones ); 58 table->num_zones = 0; 59 table->zone = 0; 60 61 FT_FREE( table->sort ); 62 FT_FREE( table->hints ); 63 table->num_hints = 0; 64 table->max_hints = 0; 65 table->sort_global = 0; 66 } 67 68 69 /* deactivate all hints in a table */ 70 static void psh2_hint_table_deactivate(PSH2_Hint_Table table)71 psh2_hint_table_deactivate( PSH2_Hint_Table table ) 72 { 73 FT_UInt count = table->max_hints; 74 PSH2_Hint hint = table->hints; 75 76 77 for ( ; count > 0; count--, hint++ ) 78 { 79 psh2_hint_deactivate( hint ); 80 hint->order = -1; 81 } 82 } 83 84 85 /* internal function used to record a new hint */ 86 static void psh2_hint_table_record(PSH2_Hint_Table table,FT_UInt idx)87 psh2_hint_table_record( PSH2_Hint_Table table, 88 FT_UInt idx ) 89 { 90 PSH2_Hint hint = table->hints + idx; 91 92 93 if ( idx >= table->max_hints ) 94 { 95 FT_ERROR(( "%s.activate: invalid hint index %d\n", idx )); 96 return; 97 } 98 99 /* ignore active hints */ 100 if ( psh2_hint_is_active( hint ) ) 101 return; 102 103 psh2_hint_activate( hint ); 104 105 /* now scan the current active hint set in order to determine */ 106 /* if we are overlapping with another segment */ 107 { 108 PSH2_Hint* sorted = table->sort_global; 109 FT_UInt count = table->num_hints; 110 PSH2_Hint hint2; 111 112 113 hint->parent = 0; 114 for ( ; count > 0; count--, sorted++ ) 115 { 116 hint2 = sorted[0]; 117 118 if ( psh2_hint_overlap( hint, hint2 ) ) 119 { 120 hint->parent = hint2; 121 break; 122 } 123 } 124 } 125 126 if ( table->num_hints < table->max_hints ) 127 table->sort_global[table->num_hints++] = hint; 128 else 129 FT_ERROR(( "%s.activate: too many sorted hints! BUG!\n", 130 "ps.fitter" )); 131 } 132 133 134 static void psh2_hint_table_record_mask(PSH2_Hint_Table table,PS_Mask hint_mask)135 psh2_hint_table_record_mask( PSH2_Hint_Table table, 136 PS_Mask hint_mask ) 137 { 138 FT_Int mask = 0, val = 0; 139 FT_Byte* cursor = hint_mask->bytes; 140 FT_UInt idx, limit; 141 142 143 limit = hint_mask->num_bits; 144 145 for ( idx = 0; idx < limit; idx++ ) 146 { 147 if ( mask == 0 ) 148 { 149 val = *cursor++; 150 mask = 0x80; 151 } 152 153 if ( val & mask ) 154 psh2_hint_table_record( table, idx ); 155 156 mask >>= 1; 157 } 158 } 159 160 161 /* create hints table */ 162 static FT_Error psh2_hint_table_init(PSH2_Hint_Table table,PS_Hint_Table hints,PS_Mask_Table hint_masks,PS_Mask_Table counter_masks,FT_Memory memory)163 psh2_hint_table_init( PSH2_Hint_Table table, 164 PS_Hint_Table hints, 165 PS_Mask_Table hint_masks, 166 PS_Mask_Table counter_masks, 167 FT_Memory memory ) 168 { 169 FT_UInt count = hints->num_hints; 170 FT_Error error; 171 172 FT_UNUSED( counter_masks ); 173 174 175 /* allocate our tables */ 176 if ( FT_NEW_ARRAY( table->sort, 2 * count ) || 177 FT_NEW_ARRAY( table->hints, count ) || 178 FT_NEW_ARRAY( table->zones, 2 * count + 1 ) ) 179 goto Exit; 180 181 table->max_hints = count; 182 table->sort_global = table->sort + count; 183 table->num_hints = 0; 184 table->num_zones = 0; 185 table->zone = 0; 186 187 /* now, initialize the "hints" array */ 188 { 189 PSH2_Hint write = table->hints; 190 PS_Hint read = hints->hints; 191 192 193 for ( ; count > 0; count--, write++, read++ ) 194 { 195 write->org_pos = read->pos; 196 write->org_len = read->len; 197 write->flags = read->flags; 198 } 199 } 200 201 /* we now need to determine the initial "parent" stems; first */ 202 /* activate the hints that are given by the initial hint masks */ 203 if ( hint_masks ) 204 { 205 FT_UInt Count = hint_masks->num_masks; 206 PS_Mask Mask = hint_masks->masks; 207 208 209 table->hint_masks = hint_masks; 210 211 for ( ; Count > 0; Count--, Mask++ ) 212 psh2_hint_table_record_mask( table, Mask ); 213 } 214 215 /* now, do a linear parse in case some hints were left alone */ 216 if ( table->num_hints != table->max_hints ) 217 { 218 FT_UInt Index, Count; 219 220 221 FT_ERROR(( "%s.init: missing/incorrect hint masks!\n" )); 222 Count = table->max_hints; 223 for ( Index = 0; Index < Count; Index++ ) 224 psh2_hint_table_record( table, Index ); 225 } 226 227 Exit: 228 return error; 229 } 230 231 232 static void psh2_hint_table_activate_mask(PSH2_Hint_Table table,PS_Mask hint_mask)233 psh2_hint_table_activate_mask( PSH2_Hint_Table table, 234 PS_Mask hint_mask ) 235 { 236 FT_Int mask = 0, val = 0; 237 FT_Byte* cursor = hint_mask->bytes; 238 FT_UInt idx, limit, count; 239 240 241 limit = hint_mask->num_bits; 242 count = 0; 243 244 psh2_hint_table_deactivate( table ); 245 246 for ( idx = 0; idx < limit; idx++ ) 247 { 248 if ( mask == 0 ) 249 { 250 val = *cursor++; 251 mask = 0x80; 252 } 253 254 if ( val & mask ) 255 { 256 PSH2_Hint hint = &table->hints[idx]; 257 258 259 if ( !psh2_hint_is_active( hint ) ) 260 { 261 FT_UInt count2; 262 263 #if 0 264 PSH2_Hint* sort = table->sort; 265 PSH2_Hint hint2; 266 267 for ( count2 = count; count2 > 0; count2--, sort++ ) 268 { 269 hint2 = sort[0]; 270 if ( psh2_hint_overlap( hint, hint2 ) ) 271 FT_ERROR(( "%s.activate_mask: found overlapping hints\n", 272 "psf.hint" )); 273 } 274 #else 275 count2 = 0; 276 #endif 277 278 if ( count2 == 0 ) 279 { 280 psh2_hint_activate( hint ); 281 if ( count < table->max_hints ) 282 table->sort[count++] = hint; 283 else 284 FT_ERROR(( "%s.activate_mask: too many active hints\n", 285 "psf.hint" )); 286 } 287 } 288 } 289 290 mask >>= 1; 291 } 292 table->num_hints = count; 293 294 /* now, sort the hints; they are guaranteed to not overlap */ 295 /* so we can compare their "org_pos" field directly */ 296 { 297 FT_Int i1, i2; 298 PSH2_Hint hint1, hint2; 299 PSH2_Hint* sort = table->sort; 300 301 302 /* a simple bubble sort will do, since in 99% of cases, the hints */ 303 /* will be already sorted -- and the sort will be linear */ 304 for ( i1 = 1; i1 < (FT_Int)count; i1++ ) 305 { 306 hint1 = sort[i1]; 307 for ( i2 = i1 - 1; i2 >= 0; i2-- ) 308 { 309 hint2 = sort[i2]; 310 311 if ( hint2->org_pos < hint1->org_pos ) 312 break; 313 314 sort[i2 + 1] = hint2; 315 sort[i2] = hint1; 316 } 317 } 318 } 319 } 320 321 322 /*************************************************************************/ 323 /*************************************************************************/ 324 /***** *****/ 325 /***** HINTS GRID-FITTING AND OPTIMIZATION *****/ 326 /***** *****/ 327 /*************************************************************************/ 328 /*************************************************************************/ 329 330 #ifdef DEBUG_HINTER 331 static void ps2_simple_scale(PSH2_Hint_Table table,FT_Fixed scale,FT_Fixed delta,FT_Int dimension)332 ps2_simple_scale( PSH2_Hint_Table table, 333 FT_Fixed scale, 334 FT_Fixed delta, 335 FT_Int dimension ) 336 { 337 PSH2_Hint hint; 338 FT_UInt count; 339 340 341 for ( count = 0; count < table->max_hints; count++ ) 342 { 343 hint = table->hints + count; 344 345 hint->cur_pos = FT_MulFix( hint->org_pos, scale ) + delta; 346 hint->cur_len = FT_MulFix( hint->org_len, scale ); 347 348 if ( ps2_debug_hint_func ) 349 ps2_debug_hint_func( hint, dimension ); 350 } 351 } 352 #endif 353 354 355 static void psh2_hint_align(PSH2_Hint hint,PSH_Globals globals,FT_Int dimension)356 psh2_hint_align( PSH2_Hint hint, 357 PSH_Globals globals, 358 FT_Int dimension ) 359 { 360 PSH_Dimension dim = &globals->dimension[dimension]; 361 FT_Fixed scale = dim->scale_mult; 362 FT_Fixed delta = dim->scale_delta; 363 364 365 if ( !psh2_hint_is_fitted(hint) ) 366 { 367 FT_Pos pos = FT_MulFix( hint->org_pos, scale ) + delta; 368 FT_Pos len = FT_MulFix( hint->org_len, scale ); 369 370 FT_Pos fit_center; 371 FT_Pos fit_len; 372 373 PSH_AlignmentRec align; 374 375 376 /* compute fitted width/height */ 377 fit_len = 0; 378 if ( hint->org_len ) 379 { 380 fit_len = psh_dimension_snap_width( dim, hint->org_len ); 381 if ( fit_len < 64 ) 382 fit_len = 64; 383 else 384 fit_len = ( fit_len + 32 ) & -64; 385 } 386 387 hint->cur_len = fit_len; 388 389 /* check blue zones for horizontal stems */ 390 align.align = PSH_BLUE_ALIGN_NONE; 391 align.align_bot = align.align_top = 0; 392 393 if ( dimension == 1 ) 394 psh_blues_snap_stem( &globals->blues, 395 hint->org_pos + hint->org_len, 396 hint->org_pos, 397 &align ); 398 399 switch ( align.align ) 400 { 401 case PSH_BLUE_ALIGN_TOP: 402 /* the top of the stem is aligned against a blue zone */ 403 hint->cur_pos = align.align_top - fit_len; 404 break; 405 406 case PSH_BLUE_ALIGN_BOT: 407 /* the bottom of the stem is aligned against a blue zone */ 408 hint->cur_pos = align.align_bot; 409 break; 410 411 case PSH_BLUE_ALIGN_TOP | PSH_BLUE_ALIGN_BOT: 412 /* both edges of the stem are aligned against blue zones */ 413 hint->cur_pos = align.align_bot; 414 hint->cur_len = align.align_top - align.align_bot; 415 break; 416 417 default: 418 { 419 PSH2_Hint parent = hint->parent; 420 421 422 if ( parent ) 423 { 424 FT_Pos par_org_center, par_cur_center; 425 FT_Pos cur_org_center, cur_delta; 426 427 428 /* ensure that parent is already fitted */ 429 if ( !psh2_hint_is_fitted( parent ) ) 430 psh2_hint_align( parent, globals, dimension ); 431 432 par_org_center = parent->org_pos + ( parent->org_len / 2); 433 par_cur_center = parent->cur_pos + ( parent->cur_len / 2); 434 cur_org_center = hint->org_pos + ( hint->org_len / 2); 435 436 cur_delta = FT_MulFix( cur_org_center - par_org_center, scale ); 437 #if 0 438 if ( cur_delta >= 0 ) 439 cur_delta = ( cur_delta + 16 ) & -64; 440 else 441 cur_delta = -( (-cur_delta + 16 ) & -64 ); 442 #endif 443 pos = par_cur_center + cur_delta - ( len >> 1 ); 444 } 445 446 /* normal processing */ 447 if ( ( fit_len / 64 ) & 1 ) 448 { 449 /* odd number of pixels */ 450 fit_center = ( ( pos + ( len >> 1 ) ) & -64 ) + 32; 451 } 452 else 453 { 454 /* even number of pixels */ 455 fit_center = ( pos + ( len >> 1 ) + 32 ) & -64; 456 } 457 458 hint->cur_pos = fit_center - ( fit_len >> 1 ); 459 } 460 } 461 462 psh2_hint_set_fitted( hint ); 463 464 #ifdef DEBUG_HINTER 465 if ( ps2_debug_hint_func ) 466 ps2_debug_hint_func( hint, dimension ); 467 #endif 468 } 469 } 470 471 472 static void psh2_hint_table_align_hints(PSH2_Hint_Table table,PSH_Globals globals,FT_Int dimension)473 psh2_hint_table_align_hints( PSH2_Hint_Table table, 474 PSH_Globals globals, 475 FT_Int dimension ) 476 { 477 PSH2_Hint hint; 478 FT_UInt count; 479 480 #ifdef DEBUG_HINTER 481 PSH_Dimension dim = &globals->dimension[dimension]; 482 FT_Fixed scale = dim->scale_mult; 483 FT_Fixed delta = dim->scale_delta; 484 485 486 if ( ps_debug_no_vert_hints && dimension == 0 ) 487 { 488 ps2_simple_scale( table, scale, delta, dimension ); 489 return; 490 } 491 492 if ( ps_debug_no_horz_hints && dimension == 1 ) 493 { 494 ps2_simple_scale( table, scale, delta, dimension ); 495 return; 496 } 497 #endif 498 499 hint = table->hints; 500 count = table->max_hints; 501 502 for ( ; count > 0; count--, hint++ ) 503 psh2_hint_align( hint, globals, dimension ); 504 } 505 506 507 /*************************************************************************/ 508 /*************************************************************************/ 509 /***** *****/ 510 /***** POINTS INTERPOLATION ROUTINES *****/ 511 /***** *****/ 512 /*************************************************************************/ 513 /*************************************************************************/ 514 515 #define PSH2_ZONE_MIN -3200000 516 #define PSH2_ZONE_MAX +3200000 517 518 #define xxDEBUG_ZONES 519 520 521 #ifdef DEBUG_ZONES 522 523 #include <stdio.h> 524 525 static void psh2_print_zone(PSH2_Zone zone)526 psh2_print_zone( PSH2_Zone zone ) 527 { 528 printf( "zone [scale,delta,min,max] = [%.3f,%.3f,%d,%d]\n", 529 zone->scale/65536.0, 530 zone->delta/64.0, 531 zone->min, 532 zone->max ); 533 } 534 535 #else 536 537 #define psh2_print_zone( x ) do { } while ( 0 ) 538 539 #endif 540 541 #if 0 542 /* setup interpolation zones once the hints have been grid-fitted */ 543 /* by the optimizer */ 544 static void 545 psh2_hint_table_setup_zones( PSH2_Hint_Table table, 546 FT_Fixed scale, 547 FT_Fixed delta ) 548 { 549 FT_UInt count; 550 PSH2_Zone zone; 551 PSH2_Hint *sort, hint, hint2; 552 553 554 zone = table->zones; 555 556 /* special case, no hints defined */ 557 if ( table->num_hints == 0 ) 558 { 559 zone->scale = scale; 560 zone->delta = delta; 561 zone->min = PSH2_ZONE_MIN; 562 zone->max = PSH2_ZONE_MAX; 563 564 table->num_zones = 1; 565 table->zone = zone; 566 return; 567 } 568 569 /* the first zone is before the first hint */ 570 /* x' = (x-x0)*s + x0' = x*s + ( x0' - x0*s ) */ 571 sort = table->sort; 572 hint = sort[0]; 573 574 zone->scale = scale; 575 zone->delta = hint->cur_pos - FT_MulFix( hint->org_pos, scale ); 576 zone->min = PSH2_ZONE_MIN; 577 zone->max = hint->org_pos; 578 579 psh2_print_zone( zone ); 580 581 zone++; 582 583 for ( count = table->num_hints; count > 0; count-- ) 584 { 585 FT_Fixed scale2; 586 587 588 if ( hint->org_len > 0 ) 589 { 590 /* setup a zone for inner-stem interpolation */ 591 /* (x' - x0') = (x - x0)*(x1'-x0')/(x1-x0) */ 592 /* x' = x*s2 + x0' - x0*s2 */ 593 594 scale2 = FT_DivFix( hint->cur_len, hint->org_len ); 595 zone->scale = scale2; 596 zone->min = hint->org_pos; 597 zone->max = hint->org_pos + hint->org_len; 598 zone->delta = hint->cur_pos - FT_MulFix( zone->min, scale2 ); 599 600 psh2_print_zone( zone ); 601 602 zone++; 603 } 604 605 if ( count == 1 ) 606 break; 607 608 sort++; 609 hint2 = sort[0]; 610 611 /* setup zone for inter-stem interpolation */ 612 /* (x'-x1') = (x-x1)*(x2'-x1')/(x2-x1) */ 613 /* x' = x*s3 + x1' - x1*s3 */ 614 615 scale2 = FT_DivFix( hint2->cur_pos - (hint->cur_pos + hint->cur_len), 616 hint2->org_pos - (hint->org_pos + hint->org_len) ); 617 zone->scale = scale2; 618 zone->min = hint->org_pos + hint->org_len; 619 zone->max = hint2->org_pos; 620 zone->delta = hint->cur_pos + hint->cur_len - 621 FT_MulFix( zone->min, scale2 ); 622 623 psh2_print_zone( zone ); 624 625 zone++; 626 627 hint = hint2; 628 } 629 630 /* the last zone */ 631 zone->scale = scale; 632 zone->min = hint->org_pos + hint->org_len; 633 zone->max = PSH2_ZONE_MAX; 634 zone->delta = hint->cur_pos + hint->cur_len - 635 FT_MulFix( zone->min, scale ); 636 637 psh2_print_zone( zone ); 638 639 zone++; 640 641 table->num_zones = zone - table->zones; 642 table->zone = table->zones; 643 } 644 #endif 645 646 #if 0 647 /* tune a single coordinate with the current interpolation zones */ 648 static FT_Pos 649 psh2_hint_table_tune_coord( PSH2_Hint_Table table, 650 FT_Int coord ) 651 { 652 PSH2_Zone zone; 653 654 655 zone = table->zone; 656 657 if ( coord < zone->min ) 658 { 659 do 660 { 661 if ( zone == table->zones ) 662 break; 663 664 zone--; 665 666 } while ( coord < zone->min ); 667 table->zone = zone; 668 } 669 else if ( coord > zone->max ) 670 { 671 do 672 { 673 if ( zone == table->zones + table->num_zones - 1 ) 674 break; 675 676 zone++; 677 678 } while ( coord > zone->max ); 679 table->zone = zone; 680 } 681 682 return FT_MulFix( coord, zone->scale ) + zone->delta; 683 } 684 #endif 685 686 #if 0 687 /* tune a given outline with current interpolation zones */ 688 /* the function only works in a single dimension.. */ 689 static void 690 psh2_hint_table_tune_outline( PSH2_Hint_Table table, 691 FT_Outline* outline, 692 PSH_Globals globals, 693 FT_Int dimension ) 694 695 { 696 FT_UInt count, first, last; 697 PS_Mask_Table hint_masks = table->hint_masks; 698 PS_Mask mask; 699 PSH_Dimension dim = &globals->dimension[dimension]; 700 FT_Fixed scale = dim->scale_mult; 701 FT_Fixed delta = dim->scale_delta; 702 703 704 if ( hint_masks && hint_masks->num_masks > 0 ) 705 { 706 first = 0; 707 mask = hint_masks->masks; 708 count = hint_masks->num_masks; 709 710 for ( ; count > 0; count--, mask++ ) 711 { 712 last = mask->end_point; 713 714 if ( last > first ) 715 { 716 FT_Vector* vec; 717 FT_Int count2; 718 719 720 psh2_hint_table_activate_mask( table, mask ); 721 psh2_hint_table_optimize( table, globals, outline, dimension ); 722 psh2_hint_table_setup_zones( table, scale, delta ); 723 last = mask->end_point; 724 725 vec = outline->points + first; 726 count2 = last - first; 727 728 for ( ; count2 > 0; count2--, vec++ ) 729 { 730 FT_Pos x, *px; 731 732 733 px = dimension ? &vec->y : &vec->x; 734 x = *px; 735 736 *px = psh2_hint_table_tune_coord( table, (FT_Int)x ); 737 } 738 } 739 740 first = last; 741 } 742 } 743 else /* no hints in this glyph, simply scale the outline */ 744 { 745 FT_Vector* vec; 746 747 748 vec = outline->points; 749 count = outline->n_points; 750 751 if ( dimension == 0 ) 752 { 753 for ( ; count > 0; count--, vec++ ) 754 vec->x = FT_MulFix( vec->x, scale ) + delta; 755 } 756 else 757 { 758 for ( ; count > 0; count--, vec++ ) 759 vec->y = FT_MulFix( vec->y, scale ) + delta; 760 } 761 } 762 } 763 #endif 764 765 766 /*************************************************************************/ 767 /*************************************************************************/ 768 /***** *****/ 769 /***** HINTER GLYPH MANAGEMENT *****/ 770 /***** *****/ 771 /*************************************************************************/ 772 /*************************************************************************/ 773 774 static int psh2_point_is_extremum(PSH2_Point point)775 psh2_point_is_extremum( PSH2_Point point ) 776 { 777 PSH2_Point before = point; 778 PSH2_Point after = point; 779 FT_Pos d_before; 780 FT_Pos d_after; 781 782 783 do 784 { 785 before = before->prev; 786 if ( before == point ) 787 return 0; 788 789 d_before = before->org_u - point->org_u; 790 791 } while ( d_before == 0 ); 792 793 do 794 { 795 after = after->next; 796 if ( after == point ) 797 return 0; 798 799 d_after = after->org_u - point->org_u; 800 801 } while ( d_after == 0 ); 802 803 return ( ( d_before > 0 && d_after > 0 ) || 804 ( d_before < 0 && d_after < 0 ) ); 805 } 806 807 808 static void psh2_glyph_done(PSH2_Glyph glyph)809 psh2_glyph_done( PSH2_Glyph glyph ) 810 { 811 FT_Memory memory = glyph->memory; 812 813 814 psh2_hint_table_done( &glyph->hint_tables[1], memory ); 815 psh2_hint_table_done( &glyph->hint_tables[0], memory ); 816 817 FT_FREE( glyph->points ); 818 FT_FREE( glyph->contours ); 819 820 glyph->num_points = 0; 821 glyph->num_contours = 0; 822 823 glyph->memory = 0; 824 } 825 826 827 static int psh2_compute_dir(FT_Pos dx,FT_Pos dy)828 psh2_compute_dir( FT_Pos dx, 829 FT_Pos dy ) 830 { 831 FT_Pos ax, ay; 832 int result = PSH2_DIR_NONE; 833 834 835 ax = ( dx >= 0 ) ? dx : -dx; 836 ay = ( dy >= 0 ) ? dy : -dy; 837 838 if ( ay * 12 < ax ) 839 { 840 /* |dy| <<< |dx| means a near-horizontal segment */ 841 result = ( dx >= 0 ) ? PSH2_DIR_RIGHT : PSH2_DIR_LEFT; 842 } 843 else if ( ax * 12 < ay ) 844 { 845 /* |dx| <<< |dy| means a near-vertical segment */ 846 result = ( dy >= 0 ) ? PSH2_DIR_UP : PSH2_DIR_DOWN; 847 } 848 849 return result; 850 } 851 852 853 static FT_Error psh2_glyph_init(PSH2_Glyph glyph,FT_Outline * outline,PS_Hints ps_hints,PSH_Globals globals)854 psh2_glyph_init( PSH2_Glyph glyph, 855 FT_Outline* outline, 856 PS_Hints ps_hints, 857 PSH_Globals globals ) 858 { 859 FT_Error error; 860 FT_Memory memory; 861 862 863 /* clear all fields */ 864 FT_MEM_ZERO( glyph, sizeof ( *glyph ) ); 865 866 memory = globals->memory; 867 868 /* allocate and setup points + contours arrays */ 869 if ( FT_NEW_ARRAY( glyph->points, outline->n_points ) || 870 FT_NEW_ARRAY( glyph->contours, outline->n_contours ) ) 871 goto Exit; 872 873 glyph->num_points = outline->n_points; 874 glyph->num_contours = outline->n_contours; 875 876 { 877 FT_UInt first = 0, next, n; 878 PSH2_Point points = glyph->points; 879 PSH2_Contour contour = glyph->contours; 880 881 882 for ( n = 0; n < glyph->num_contours; n++ ) 883 { 884 FT_Int count; 885 PSH2_Point point; 886 887 888 next = outline->contours[n] + 1; 889 count = next - first; 890 891 contour->start = points + first; 892 contour->count = (FT_UInt)count; 893 894 if ( count > 0 ) 895 { 896 point = points + first; 897 898 point->prev = points + next - 1; 899 point->contour = contour; 900 901 for ( ; count > 1; count-- ) 902 { 903 point[0].next = point + 1; 904 point[1].prev = point; 905 point++; 906 point->contour = contour; 907 } 908 point->next = points + first; 909 } 910 911 contour++; 912 first = next; 913 } 914 } 915 916 { 917 PSH2_Point points = glyph->points; 918 PSH2_Point point = points; 919 FT_Vector* vec = outline->points; 920 FT_UInt n; 921 922 923 for ( n = 0; n < glyph->num_points; n++, point++ ) 924 { 925 FT_Int n_prev = point->prev - points; 926 FT_Int n_next = point->next - points; 927 FT_Pos dxi, dyi, dxo, dyo; 928 929 930 if ( !( outline->tags[n] & FT_CURVE_TAG_ON ) ) 931 point->flags = PSH2_POINT_OFF; 932 933 dxi = vec[n].x - vec[n_prev].x; 934 dyi = vec[n].y - vec[n_prev].y; 935 936 point->dir_in = (FT_Char)psh2_compute_dir( dxi, dyi ); 937 938 dxo = vec[n_next].x - vec[n].x; 939 dyo = vec[n_next].y - vec[n].y; 940 941 point->dir_out = (FT_Char)psh2_compute_dir( dxo, dyo ); 942 943 /* detect smooth points */ 944 if ( point->flags & PSH2_POINT_OFF ) 945 point->flags |= PSH2_POINT_SMOOTH; 946 else if ( point->dir_in != PSH2_DIR_NONE || 947 point->dir_out != PSH2_DIR_NONE ) 948 { 949 if ( point->dir_in == point->dir_out ) 950 point->flags |= PSH2_POINT_SMOOTH; 951 } 952 else 953 { 954 FT_Angle angle_in, angle_out, diff; 955 956 957 angle_in = FT_Atan2( dxi, dyi ); 958 angle_out = FT_Atan2( dxo, dyo ); 959 960 diff = angle_in - angle_out; 961 if ( diff < 0 ) 962 diff = -diff; 963 964 if ( diff > FT_ANGLE_PI ) 965 diff = FT_ANGLE_2PI - diff; 966 967 if ( diff < FT_ANGLE_PI / 16 ) 968 point->flags |= PSH2_POINT_SMOOTH; 969 } 970 } 971 } 972 973 glyph->memory = memory; 974 glyph->outline = outline; 975 glyph->globals = globals; 976 977 /* now deal with hints tables */ 978 error = psh2_hint_table_init( &glyph->hint_tables [0], 979 &ps_hints->dimension[0].hints, 980 &ps_hints->dimension[0].masks, 981 &ps_hints->dimension[0].counters, 982 memory ); 983 if ( error ) 984 goto Exit; 985 986 error = psh2_hint_table_init( &glyph->hint_tables [1], 987 &ps_hints->dimension[1].hints, 988 &ps_hints->dimension[1].masks, 989 &ps_hints->dimension[1].counters, 990 memory ); 991 if ( error ) 992 goto Exit; 993 994 Exit: 995 return error; 996 } 997 998 999 /* load outline point coordinates into hinter glyph */ 1000 static void psh2_glyph_load_points(PSH2_Glyph glyph,FT_Int dimension)1001 psh2_glyph_load_points( PSH2_Glyph glyph, 1002 FT_Int dimension ) 1003 { 1004 FT_Vector* vec = glyph->outline->points; 1005 PSH2_Point point = glyph->points; 1006 FT_UInt count = glyph->num_points; 1007 1008 1009 for ( ; count > 0; count--, point++, vec++ ) 1010 { 1011 point->flags &= PSH2_POINT_OFF | PSH2_POINT_SMOOTH; 1012 point->hint = 0; 1013 if ( dimension == 0 ) 1014 point->org_u = vec->x; 1015 else 1016 point->org_u = vec->y; 1017 1018 #ifdef DEBUG_HINTER 1019 point->org_x = vec->x; 1020 point->org_y = vec->y; 1021 #endif 1022 } 1023 } 1024 1025 1026 /* save hinted point coordinates back to outline */ 1027 static void psh2_glyph_save_points(PSH2_Glyph glyph,FT_Int dimension)1028 psh2_glyph_save_points( PSH2_Glyph glyph, 1029 FT_Int dimension ) 1030 { 1031 FT_UInt n; 1032 PSH2_Point point = glyph->points; 1033 FT_Vector* vec = glyph->outline->points; 1034 char* tags = glyph->outline->tags; 1035 1036 1037 for ( n = 0; n < glyph->num_points; n++ ) 1038 { 1039 if ( dimension == 0 ) 1040 vec[n].x = point->cur_u; 1041 else 1042 vec[n].y = point->cur_u; 1043 1044 if ( psh2_point_is_strong( point ) ) 1045 tags[n] |= (char)( ( dimension == 0 ) ? 32 : 64 ); 1046 1047 #ifdef DEBUG_HINTER 1048 if ( dimension == 0 ) 1049 { 1050 point->cur_x = point->cur_u; 1051 point->flags_x = point->flags; 1052 } 1053 else 1054 { 1055 point->cur_y = point->cur_u; 1056 point->flags_y = point->flags; 1057 } 1058 #endif 1059 point++; 1060 } 1061 } 1062 1063 1064 #define PSH2_STRONG_THRESHOLD 10 1065 1066 1067 static void psh2_hint_table_find_strong_point(PSH2_Hint_Table table,PSH2_Point point,FT_Int major_dir)1068 psh2_hint_table_find_strong_point( PSH2_Hint_Table table, 1069 PSH2_Point point, 1070 FT_Int major_dir ) 1071 { 1072 PSH2_Hint* sort = table->sort; 1073 FT_UInt num_hints = table->num_hints; 1074 1075 1076 for ( ; num_hints > 0; num_hints--, sort++ ) 1077 { 1078 PSH2_Hint hint = sort[0]; 1079 1080 1081 if ( ABS( point->dir_in ) == major_dir || 1082 ABS( point->dir_out ) == major_dir ) 1083 { 1084 FT_Pos d; 1085 1086 1087 d = point->org_u - hint->org_pos; 1088 if ( ABS( d ) < PSH2_STRONG_THRESHOLD ) 1089 { 1090 Is_Strong: 1091 psh2_point_set_strong( point ); 1092 point->hint = hint; 1093 break; 1094 } 1095 1096 d -= hint->org_len; 1097 if ( ABS( d ) < PSH2_STRONG_THRESHOLD ) 1098 goto Is_Strong; 1099 } 1100 1101 #if 1 1102 if ( point->org_u >= hint->org_pos && 1103 point->org_u <= hint->org_pos + hint->org_len && 1104 psh2_point_is_extremum( point ) ) 1105 { 1106 /* attach to hint, but don't mark as strong */ 1107 point->hint = hint; 1108 break; 1109 } 1110 #endif 1111 } 1112 } 1113 1114 1115 /* find strong points in a glyph */ 1116 static void psh2_glyph_find_strong_points(PSH2_Glyph glyph,FT_Int dimension)1117 psh2_glyph_find_strong_points( PSH2_Glyph glyph, 1118 FT_Int dimension ) 1119 { 1120 /* a point is strong if it is located on a stem */ 1121 /* edge and has an "in" or "out" tangent to the hint's direction */ 1122 { 1123 PSH2_Hint_Table table = &glyph->hint_tables[dimension]; 1124 PS_Mask mask = table->hint_masks->masks; 1125 FT_UInt num_masks = table->hint_masks->num_masks; 1126 FT_UInt first = 0; 1127 FT_Int major_dir = dimension == 0 ? PSH2_DIR_UP : PSH2_DIR_RIGHT; 1128 1129 1130 /* process secondary hints to "selected" points */ 1131 if ( num_masks > 1 && glyph->num_points > 0 ) 1132 { 1133 first = mask->end_point; 1134 mask++; 1135 for ( ; num_masks > 1; num_masks--, mask++ ) 1136 { 1137 FT_UInt next; 1138 FT_Int count; 1139 1140 1141 next = mask->end_point; 1142 count = next - first; 1143 if ( count > 0 ) 1144 { 1145 PSH2_Point point = glyph->points + first; 1146 1147 1148 psh2_hint_table_activate_mask( table, mask ); 1149 1150 for ( ; count > 0; count--, point++ ) 1151 psh2_hint_table_find_strong_point( table, point, major_dir ); 1152 } 1153 first = next; 1154 } 1155 } 1156 1157 /* process primary hints for all points */ 1158 if ( num_masks == 1 ) 1159 { 1160 FT_UInt count = glyph->num_points; 1161 PSH2_Point point = glyph->points; 1162 1163 1164 psh2_hint_table_activate_mask( table, table->hint_masks->masks ); 1165 for ( ; count > 0; count--, point++ ) 1166 { 1167 if ( !psh2_point_is_strong( point ) ) 1168 psh2_hint_table_find_strong_point( table, point, major_dir ); 1169 } 1170 } 1171 1172 /* now, certain points may have been attached to hint and */ 1173 /* not marked as strong; update their flags then */ 1174 { 1175 FT_UInt count = glyph->num_points; 1176 PSH2_Point point = glyph->points; 1177 1178 1179 for ( ; count > 0; count--, point++ ) 1180 if ( point->hint && !psh2_point_is_strong( point ) ) 1181 psh2_point_set_strong( point ); 1182 } 1183 } 1184 } 1185 1186 1187 /* interpolate strong points with the help of hinted coordinates */ 1188 static void psh2_glyph_interpolate_strong_points(PSH2_Glyph glyph,FT_Int dimension)1189 psh2_glyph_interpolate_strong_points( PSH2_Glyph glyph, 1190 FT_Int dimension ) 1191 { 1192 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1193 FT_Fixed scale = dim->scale_mult; 1194 1195 1196 { 1197 FT_UInt count = glyph->num_points; 1198 PSH2_Point point = glyph->points; 1199 1200 1201 for ( ; count > 0; count--, point++ ) 1202 { 1203 PSH2_Hint hint = point->hint; 1204 1205 1206 if ( hint ) 1207 { 1208 FT_Pos delta; 1209 1210 1211 delta = point->org_u - hint->org_pos; 1212 1213 if ( delta <= 0 ) 1214 point->cur_u = hint->cur_pos + FT_MulFix( delta, scale ); 1215 1216 else if ( delta >= hint->org_len ) 1217 point->cur_u = hint->cur_pos + hint->cur_len + 1218 FT_MulFix( delta - hint->org_len, scale ); 1219 1220 else if ( hint->org_len > 0 ) 1221 point->cur_u = hint->cur_pos + 1222 FT_MulDiv( delta, hint->cur_len, hint->org_len ); 1223 else 1224 point->cur_u = hint->cur_pos; 1225 1226 psh2_point_set_fitted( point ); 1227 } 1228 } 1229 } 1230 } 1231 1232 1233 static void psh2_glyph_interpolate_normal_points(PSH2_Glyph glyph,FT_Int dimension)1234 psh2_glyph_interpolate_normal_points( PSH2_Glyph glyph, 1235 FT_Int dimension ) 1236 { 1237 #if 1 1238 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1239 FT_Fixed scale = dim->scale_mult; 1240 1241 1242 /* first technique: a point is strong if it is a local extrema */ 1243 { 1244 FT_UInt count = glyph->num_points; 1245 PSH2_Point point = glyph->points; 1246 1247 1248 for ( ; count > 0; count--, point++ ) 1249 { 1250 if ( psh2_point_is_strong( point ) ) 1251 continue; 1252 1253 /* sometimes, some local extremas are smooth points */ 1254 if ( psh2_point_is_smooth( point ) ) 1255 { 1256 if ( point->dir_in == PSH2_DIR_NONE || 1257 point->dir_in != point->dir_out ) 1258 continue; 1259 1260 if ( !psh2_point_is_extremum( point ) ) 1261 continue; 1262 1263 point->flags &= ~PSH2_POINT_SMOOTH; 1264 } 1265 1266 /* find best enclosing point coordinates */ 1267 { 1268 PSH2_Point before = 0; 1269 PSH2_Point after = 0; 1270 1271 FT_Pos diff_before = -32000; 1272 FT_Pos diff_after = 32000; 1273 FT_Pos u = point->org_u; 1274 1275 FT_Int count2 = glyph->num_points; 1276 PSH2_Point cur = glyph->points; 1277 1278 1279 for ( ; count2 > 0; count2--, cur++ ) 1280 { 1281 if ( psh2_point_is_strong( cur ) ) 1282 { 1283 FT_Pos diff = cur->org_u - u;; 1284 1285 1286 if ( diff <= 0 ) 1287 { 1288 if ( diff > diff_before ) 1289 { 1290 diff_before = diff; 1291 before = cur; 1292 } 1293 } 1294 else if ( diff >= 0 ) 1295 { 1296 if ( diff < diff_after ) 1297 { 1298 diff_after = diff; 1299 after = cur; 1300 } 1301 } 1302 } 1303 } 1304 1305 if ( !before ) 1306 { 1307 if ( !after ) 1308 continue; 1309 1310 /* we are before the first strong point coordinate; */ 1311 /* simply translate the point */ 1312 point->cur_u = after->cur_u + 1313 FT_MulFix( point->org_u - after->org_u, scale ); 1314 } 1315 else if ( !after ) 1316 { 1317 /* we are after the last strong point coordinate; */ 1318 /* simply translate the point */ 1319 point->cur_u = before->cur_u + 1320 FT_MulFix( point->org_u - before->org_u, scale ); 1321 } 1322 else 1323 { 1324 if ( diff_before == 0 ) 1325 point->cur_u = before->cur_u; 1326 1327 else if ( diff_after == 0 ) 1328 point->cur_u = after->cur_u; 1329 1330 else 1331 point->cur_u = before->cur_u + 1332 FT_MulDiv( u - before->org_u, 1333 after->cur_u - before->cur_u, 1334 after->org_u - before->org_u ); 1335 } 1336 1337 psh2_point_set_fitted( point ); 1338 } 1339 } 1340 } 1341 #endif 1342 } 1343 1344 1345 /* interpolate other points */ 1346 static void psh2_glyph_interpolate_other_points(PSH2_Glyph glyph,FT_Int dimension)1347 psh2_glyph_interpolate_other_points( PSH2_Glyph glyph, 1348 FT_Int dimension ) 1349 { 1350 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1351 FT_Fixed scale = dim->scale_mult; 1352 FT_Fixed delta = dim->scale_delta; 1353 PSH2_Contour contour = glyph->contours; 1354 FT_UInt num_contours = glyph->num_contours; 1355 1356 1357 for ( ; num_contours > 0; num_contours--, contour++ ) 1358 { 1359 PSH2_Point start = contour->start; 1360 PSH2_Point first, next, point; 1361 FT_UInt fit_count; 1362 1363 1364 /* count the number of strong points in this contour */ 1365 next = start + contour->count; 1366 fit_count = 0; 1367 first = 0; 1368 1369 for ( point = start; point < next; point++ ) 1370 if ( psh2_point_is_fitted( point ) ) 1371 { 1372 if ( !first ) 1373 first = point; 1374 1375 fit_count++; 1376 } 1377 1378 /* if there are less than 2 fitted points in the contour, we */ 1379 /* simply scale and eventually translate the contour points */ 1380 if ( fit_count < 2 ) 1381 { 1382 if ( fit_count == 1 ) 1383 delta = first->cur_u - FT_MulFix( first->org_u, scale ); 1384 1385 for ( point = start; point < next; point++ ) 1386 if ( point != first ) 1387 point->cur_u = FT_MulFix( point->org_u, scale ) + delta; 1388 1389 goto Next_Contour; 1390 } 1391 1392 /* there are more than 2 strong points in this contour; we */ 1393 /* need to interpolate weak points between them */ 1394 start = first; 1395 do 1396 { 1397 point = first; 1398 1399 /* skip consecutive fitted points */ 1400 for (;;) 1401 { 1402 next = first->next; 1403 if ( next == start ) 1404 goto Next_Contour; 1405 1406 if ( !psh2_point_is_fitted( next ) ) 1407 break; 1408 1409 first = next; 1410 } 1411 1412 /* find next fitted point after unfitted one */ 1413 for (;;) 1414 { 1415 next = next->next; 1416 if ( psh2_point_is_fitted( next ) ) 1417 break; 1418 } 1419 1420 /* now interpolate between them */ 1421 { 1422 FT_Pos org_a, org_ab, cur_a, cur_ab; 1423 FT_Pos org_c, org_ac, cur_c; 1424 FT_Fixed scale_ab; 1425 1426 1427 if ( first->org_u <= next->org_u ) 1428 { 1429 org_a = first->org_u; 1430 cur_a = first->cur_u; 1431 org_ab = next->org_u - org_a; 1432 cur_ab = next->cur_u - cur_a; 1433 } 1434 else 1435 { 1436 org_a = next->org_u; 1437 cur_a = next->cur_u; 1438 org_ab = first->org_u - org_a; 1439 cur_ab = first->cur_u - cur_a; 1440 } 1441 1442 scale_ab = 0x10000L; 1443 if ( org_ab > 0 ) 1444 scale_ab = FT_DivFix( cur_ab, org_ab ); 1445 1446 point = first->next; 1447 do 1448 { 1449 org_c = point->org_u; 1450 org_ac = org_c - org_a; 1451 1452 if ( org_ac <= 0 ) 1453 { 1454 /* on the left of the interpolation zone */ 1455 cur_c = cur_a + FT_MulFix( org_ac, scale ); 1456 } 1457 else if ( org_ac >= org_ab ) 1458 { 1459 /* on the right on the interpolation zone */ 1460 cur_c = cur_a + cur_ab + FT_MulFix( org_ac - org_ab, scale ); 1461 } 1462 else 1463 { 1464 /* within the interpolation zone */ 1465 cur_c = cur_a + FT_MulFix( org_ac, scale_ab ); 1466 } 1467 1468 point->cur_u = cur_c; 1469 1470 point = point->next; 1471 1472 } while ( point != next ); 1473 } 1474 1475 /* keep going until all points in the contours have been processed */ 1476 first = next; 1477 1478 } while ( first != start ); 1479 1480 Next_Contour: 1481 ; 1482 } 1483 } 1484 1485 1486 /*************************************************************************/ 1487 /*************************************************************************/ 1488 /***** *****/ 1489 /***** HIGH-LEVEL INTERFACE *****/ 1490 /***** *****/ 1491 /*************************************************************************/ 1492 /*************************************************************************/ 1493 1494 FT_Error ps2_hints_apply(PS_Hints ps_hints,FT_Outline * outline,PSH_Globals globals,FT_Render_Mode hint_mode)1495 ps2_hints_apply( PS_Hints ps_hints, 1496 FT_Outline* outline, 1497 PSH_Globals globals, 1498 FT_Render_Mode hint_mode ) 1499 { 1500 PSH2_GlyphRec glyphrec; 1501 PSH2_Glyph glyph = &glyphrec; 1502 FT_Error error; 1503 #ifdef DEBUG_HINTER 1504 FT_Memory memory; 1505 #endif 1506 FT_Int dimension; 1507 1508 FT_UNUSED( hint_mode ); 1509 1510 #ifdef DEBUG_HINTER 1511 memory = globals->memory; 1512 1513 if ( ps2_debug_glyph ) 1514 { 1515 psh2_glyph_done( ps2_debug_glyph ); 1516 FT_FREE( ps2_debug_glyph ); 1517 } 1518 1519 if ( FT_NEW( glyph ) ) 1520 return error; 1521 1522 ps2_debug_glyph = glyph; 1523 #endif 1524 1525 error = psh2_glyph_init( glyph, outline, ps_hints, globals ); 1526 if ( error ) 1527 goto Exit; 1528 1529 for ( dimension = 0; dimension < 2; dimension++ ) 1530 { 1531 /* load outline coordinates into glyph */ 1532 psh2_glyph_load_points( glyph, dimension ); 1533 1534 /* compute aligned stem/hints positions */ 1535 psh2_hint_table_align_hints( &glyph->hint_tables[dimension], 1536 glyph->globals, 1537 dimension ); 1538 1539 /* find strong points, align them, then interpolate others */ 1540 psh2_glyph_find_strong_points( glyph, dimension ); 1541 psh2_glyph_interpolate_strong_points( glyph, dimension ); 1542 psh2_glyph_interpolate_normal_points( glyph, dimension ); 1543 psh2_glyph_interpolate_other_points( glyph, dimension ); 1544 1545 /* save hinted coordinates back to outline */ 1546 psh2_glyph_save_points( glyph, dimension ); 1547 } 1548 1549 Exit: 1550 #ifndef DEBUG_HINTER 1551 psh2_glyph_done( glyph ); 1552 #endif 1553 return error; 1554 } 1555 1556 1557 /* END */ 1558