libraries/freetype-2.0.5/ahglyph.c

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