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