lib/tahints.c

   1 /* tahints.c */
   2
   3 /*
   4  * Copyright (C) 2011-2014 by Werner Lemberg.
   5  *
   6  * This file is part of the ttfautohint library, and may only be used,
   7  * modified, and distributed under the terms given in `COPYING'.  By
   8  * continuing to use, modify, or distribute this file you indicate that you
   9  * have read `COPYING' and understand and accept it fully.
  10  *
  11  * The file `COPYING' mentioned in the previous paragraph is distributed
  12  * with the ttfautohint library.
  13  */
  14
  15
  16 /* originally file `afhints.c' (2011-Mar-28) from FreeType */
  17
  18 /* heavily modified 2011 by Werner Lemberg <wl@gnu.org> */
  19
  20 #include "ta.h"
  21
  22 #include <string.h>
  23 #include <stdlib.h>
  24 #include "tahints.h"
  25
  26
  27 /* get new segment for given axis */
  28
  29 FT_Error
  30 ta_axis_hints_new_segment(TA_AxisHints axis,
  31                           TA_Segment* asegment)
  32 {
  33   FT_Error error = FT_Err_Ok;
  34   TA_Segment segment = NULL;
  35
  36
  37   if (axis->num_segments >= axis->max_segments)
  38   {
  39     TA_Segment segments_new;
  40
  41     FT_Int old_max = axis->max_segments;
  42     FT_Int new_max = old_max;
  43     FT_Int big_max = (FT_Int)(FT_INT_MAX / sizeof (*segment));
  44
  45
  46     if (old_max >= big_max)
  47     {
  48       error = FT_Err_Out_Of_Memory;
  49       goto Exit;
  50     }
  51
  52     new_max += (new_max >> 2) + 4;
  53     if (new_max < old_max
  54         || new_max > big_max)
  55       new_max = big_max;
  56
  57     segments_new = (TA_Segment)realloc(axis->segments,
  58                                        new_max * sizeof (TA_SegmentRec));
  59     if (!segments_new)
  60       return FT_Err_Out_Of_Memory;
  61
  62     axis->segments = segments_new;
  63     axis->max_segments = new_max;
  64   }
  65
  66   segment = axis->segments + axis->num_segments++;
  67
  68 Exit:
  69   *asegment = segment;
  70   return error;
  71 }
  72
  73
  74 /* get new edge for given axis, direction, and position, */
  75 /* without initializing the edge itself */
  76
  77 FT_Error
  78 ta_axis_hints_new_edge(TA_AxisHints axis,
  79                        FT_Int fpos,
  80                        TA_Direction dir,
  81                        TA_Edge* anedge)
  82 {
  83   FT_Error error = FT_Err_Ok;
  84   TA_Edge edge = NULL;
  85   TA_Edge edges;
  86
  87
  88   if (axis->num_edges >= axis->max_edges)
  89   {
  90     TA_Edge edges_new;
  91
  92     FT_Int old_max = axis->max_edges;
  93     FT_Int new_max = old_max;
  94     FT_Int big_max = (FT_Int)(FT_INT_MAX / sizeof (*edge));
  95
  96
  97     if (old_max >= big_max)
  98     {
  99       error = FT_Err_Out_Of_Memory;
 100       goto Exit;
 101     }
 102
 103     new_max += (new_max >> 2) + 4;
 104     if (new_max < old_max
 105         || new_max > big_max)
 106       new_max = big_max;
 107
 108     edges_new = (TA_Edge)realloc(axis->edges,
 109                                  new_max * sizeof (TA_EdgeRec));
 110     if (!edges_new)
 111       return FT_Err_Out_Of_Memory;
 112
 113     axis->edges = edges_new;
 114     axis->max_edges = new_max;
 115   }
 116
 117   edges = axis->edges;
 118   edge = edges + axis->num_edges;
 119
 120   while (edge > edges)
 121   {
 122     if (edge[-1].fpos < fpos)
 123       break;
 124
 125     /* we want the edge with same position and minor direction */
 126     /* to appear before those in the major one in the list */
 127     if (edge[-1].fpos == fpos
 128         && dir == axis->major_dir)
 129       break;
 130
 131     edge[0] = edge[-1];
 132     edge--;
 133   }
 134
 135   axis->num_edges++;
 136
 137 Exit:
 138   *anedge = edge;
 139   return error;
 140 }
 141
 142
 143 #ifdef TA_DEBUG
 144
 145 #include <stdio.h>
 146 #include <stdarg.h>
 147 #include <string.h>
 148
 149
 150 void
 151 _ta_message(const char* format,
 152             ...)
 153 {
 154   va_list ap;
 155
 156
 157   va_start(ap, format);
 158   vfprintf(stderr, format, ap);
 159   va_end(ap);
 160 }
 161
 162
 163 static const char*
 164 ta_dir_str(TA_Direction dir)
 165 {
 166   const char* result;
 167
 168
 169   switch (dir)
 170   {
 171   case TA_DIR_UP:
 172     result = "up";
 173     break;
 174   case TA_DIR_DOWN:
 175     result = "down";
 176     break;
 177   case TA_DIR_LEFT:
 178     result = "left";
 179     break;
 180   case TA_DIR_RIGHT:
 181     result = "right";
 182     break;
 183   default:
 184     result = "none";
 185   }
 186
 187   return result;
 188 }
 189
 190
 191 #define TA_INDEX_NUM(ptr, base) \
 192           ((ptr) ? ((ptr) - (base)) \
 193                  : -1)
 194
 195
 196 void
 197 ta_glyph_hints_dump_points(TA_GlyphHints hints)
 198 {
 199   TA_Point points = hints->points;
 200   TA_Point limit = points + hints->num_points;
 201   TA_Point point;
 202
 203
 204   TA_LOG(("Table of points:\n"
 205           "  [ index |  xorg |  yorg | xscale | yscale"
 206           " |  xfit |  yfit | flags ]\n"));
 207
 208   for (point = points; point < limit; point++)
 209     TA_LOG(("  [ %5d | %5d | %5d | %6.2f | %6.2f"
 210             " | %5.2f | %5.2f |   %c   ]\n",
 211             point - points,
 212             point->fx,
 213             point->fy,
 214             point->ox / 64.0,
 215             point->oy / 64.0,
 216             point->x / 64.0,
 217             point->y / 64.0,
 218             (point->flags & TA_FLAG_WEAK_INTERPOLATION) ? 'w' : ' '));
 219   TA_LOG(("\n"));
 220 }
 221
 222
 223 static const char*
 224 ta_edge_flags_to_string(FT_Byte flags)
 225 {
 226   static char temp[32];
 227   int pos = 0;
 228
 229
 230   if (flags & TA_EDGE_ROUND)
 231   {
 232     memcpy(temp + pos, "round", 5);
 233     pos += 5;
 234   }
 235   if (flags & TA_EDGE_SERIF)
 236   {
 237     if (pos > 0)
 238       temp[pos++] = ' ';
 239     memcpy(temp + pos, "serif", 5);
 240     pos += 5;
 241   }
 242   if (pos == 0)
 243     return "normal";
 244
 245   temp[pos] = '\0';
 246
 247   return temp;
 248 }
 249
 250
 251 /* dump the array of linked segments */
 252
 253 void
 254 ta_glyph_hints_dump_segments(TA_GlyphHints hints)
 255 {
 256   FT_Int dimension;
 257
 258
 259   for (dimension = TA_DEBUG_STARTDIM;
 260        dimension >= TA_DEBUG_ENDDIM;
 261        dimension--)
 262   {
 263     TA_AxisHints axis = &hints->axis[dimension];
 264     TA_Point points = hints->points;
 265     TA_Edge edges = axis->edges;
 266     TA_Segment segments = axis->segments;
 267     TA_Segment limit = segments + axis->num_segments;
 268     TA_Segment seg;
 269
 270
 271     TA_LOG(("Table of %s segments:\n",
 272             dimension == TA_DIMENSION_HORZ ? "vertical"
 273                                            : "horizontal"));
 274     if (axis->num_segments)
 275       TA_LOG(("  [ index |  pos  |  dir  | from"
 276               " |  to  | link | serif | edge"
 277               " | height | extra |    flags    ]\n"));
 278     else
 279       TA_LOG(("  (none)\n"));
 280
 281     for (seg = segments; seg < limit; seg++)
 282       TA_LOG(("  [ %5d | %5.2g | %5s | %4d"
 283               " | %4d | %4d | %5d | %4d"
 284               " | %6d | %5d | %11s ]\n",
 285               seg - segments,
 286               dimension == TA_DIMENSION_HORZ ? (int)seg->first->ox / 64.0
 287                                              : (int)seg->first->oy / 64.0,
 288               ta_dir_str((TA_Direction)seg->dir),
 289               TA_INDEX_NUM(seg->first, points),
 290               TA_INDEX_NUM(seg->last, points),
 291               TA_INDEX_NUM(seg->link, segments),
 292               TA_INDEX_NUM(seg->serif, segments),
 293               TA_INDEX_NUM(seg->edge, edges),
 294               seg->height,
 295               seg->height - (seg->max_coord - seg->min_coord),
 296               ta_edge_flags_to_string(seg->flags)));
 297     TA_LOG(("\n"));
 298   }
 299 }
 300
 301
 302 /* dump the array of linked edges */
 303
 304 void
 305 ta_glyph_hints_dump_edges(TA_GlyphHints hints)
 306 {
 307   FT_Int dimension;
 308
 309
 310   for (dimension = TA_DEBUG_STARTDIM;
 311        dimension >= TA_DEBUG_ENDDIM;
 312        dimension--)
 313   {
 314     TA_AxisHints axis = &hints->axis[dimension];
 315     TA_Edge edges = axis->edges;
 316     TA_Edge limit = edges + axis->num_edges;
 317     TA_Edge edge;
 318
 319
 320     /* note that TA_DIMENSION_HORZ corresponds to _vertical_ edges */
 321     /* since they have a constant X coordinate */
 322     TA_LOG(("Table of %s edges:\n",
 323             dimension == TA_DIMENSION_HORZ ? "vertical"
 324                                            : "horizontal"));
 325     if (axis->num_edges)
 326       TA_LOG(("  [ index |  pos  |  dir  | link"
 327               " | serif | blue | opos  |  pos  |    flags    ]\n"));
 328     else
 329       TA_LOG(("  (none)\n"));
 330
 331     for (edge = edges; edge < limit; edge++)
 332       TA_LOG(("  [ %5d | %5.2g | %5s | %4d"
 333               " | %5d |   %c  | %5.2f | %5.2f | %11s ]\n",
 334               edge - edges,
 335               (int)edge->opos / 64.0,
 336               ta_dir_str((TA_Direction)edge->dir),
 337               TA_INDEX_NUM(edge->link, edges),
 338               TA_INDEX_NUM(edge->serif, edges),
 339               edge->blue_edge ? 'y' : 'n',
 340               edge->opos / 64.0,
 341               edge->pos / 64.0,
 342               ta_edge_flags_to_string(edge->flags)));
 343     TA_LOG(("\n"));
 344   }
 345 }
 346
 347 #endif /* TA_DEBUG */
 348
 349
 350 /* compute the direction value of a given vector */
 351
 352 TA_Direction
 353 ta_direction_compute(FT_Pos dx,
 354                      FT_Pos dy)
 355 {
 356   FT_Pos ll, ss; /* long and short arm lengths */
 357   TA_Direction dir; /* candidate direction */
 358
 359
 360   if (dy >= dx)
 361   {
 362     if (dy >= -dx)
 363     {
 364       dir = TA_DIR_UP;
 365       ll = dy;
 366       ss = dx;
 367     }
 368     else
 369     {
 370       dir = TA_DIR_LEFT;
 371       ll = -dx;
 372       ss = dy;
 373     }
 374   }
 375   else /* dy < dx */
 376   {
 377     if (dy >= -dx)
 378     {
 379       dir = TA_DIR_RIGHT;
 380       ll = dx;
 381       ss = dy;
 382     }
 383     else
 384     {
 385       dir = TA_DIR_DOWN;
 386       ll = dy;
 387       ss = dx;
 388     }
 389   }
 390
 391   /* return no direction if arm lengths differ too much */
 392   /* (value 14 is heuristic, corresponding to approx. 4.1 degrees) */
 393   ss *= 14;
 394   if (TA_ABS(ll) <= TA_ABS(ss))
 395     dir = TA_DIR_NONE;
 396
 397   return dir;
 398 }
 399
 400
 401 void
 402 ta_glyph_hints_init(TA_GlyphHints hints)
 403 {
 404   memset(hints, 0, sizeof (TA_GlyphHintsRec));
 405 }
 406
 407
 408 void
 409 ta_glyph_hints_done(TA_GlyphHints hints)
 410 {
 411   int dim;
 412
 413
 414   if (!hints)
 415     return;
 416
 417   /* we don't need to free the segment and edge buffers */
 418   /* since they are really within the hints->points array */
 419   for (dim = 0; dim < TA_DIMENSION_MAX; dim++)
 420   {
 421     TA_AxisHints axis = &hints->axis[dim];
 422
 423
 424     axis->num_segments = 0;
 425     axis->max_segments = 0;
 426     free(axis->segments);
 427     axis->segments = NULL;
 428
 429     axis->num_edges = 0;
 430     axis->max_edges = 0;
 431     free(axis->edges);
 432     axis->edges = NULL;
 433   }
 434
 435   free(hints->contours);
 436   hints->contours = NULL;
 437   hints->max_contours = 0;
 438   hints->num_contours = 0;
 439
 440   free(hints->points);
 441   hints->points = NULL;
 442   hints->num_points = 0;
 443   hints->max_points = 0;
 444 }
 445
 446
 447 /* reset metrics */
 448
 449 void
 450 ta_glyph_hints_rescale(TA_GlyphHints hints,
 451                        TA_StyleMetrics metrics)
 452 {
 453   hints->metrics = metrics;
 454   hints->scaler_flags = metrics->scaler.flags;
 455 }
 456
 457
 458 /* from FreeType's ftcalc.c */
 459
 460 static FT_Int
 461 ta_corner_is_flat(FT_Pos in_x,
 462                   FT_Pos in_y,
 463                   FT_Pos out_x,
 464                   FT_Pos out_y)
 465 {
 466   FT_Pos ax = in_x;
 467   FT_Pos ay = in_y;
 468
 469   FT_Pos d_in, d_out, d_corner;
 470
 471
 472   if (ax < 0)
 473     ax = -ax;
 474   if (ay < 0)
 475     ay = -ay;
 476   d_in = ax + ay;
 477
 478   ax = out_x;
 479   if (ax < 0)
 480     ax = -ax;
 481   ay = out_y;
 482   if (ay < 0)
 483     ay = -ay;
 484   d_out = ax + ay;
 485
 486   ax = out_x + in_x;
 487   if (ax < 0)
 488     ax = -ax;
 489   ay = out_y + in_y;
 490   if (ay < 0)
 491     ay = -ay;
 492   d_corner = ax + ay;
 493
 494   return (d_in + d_out - d_corner) < (d_corner >> 4);
 495 }
 496
 497
 498 /* recompute all TA_Point in TA_GlyphHints */
 499 /* from the definitions in a source outline */
 500
 501 FT_Error
 502 ta_glyph_hints_reload(TA_GlyphHints hints,
 503                       FT_Outline* outline)
 504 {
 505   FT_Error error = FT_Err_Ok;
 506   TA_Point points;
 507   FT_UInt old_max, new_max;
 508
 509   FT_Fixed x_scale = hints->x_scale;
 510   FT_Fixed y_scale = hints->y_scale;
 511   FT_Pos x_delta = hints->x_delta;
 512   FT_Pos y_delta = hints->y_delta;
 513
 514
 515   hints->num_points = 0;
 516   hints->num_contours = 0;
 517
 518   hints->axis[0].num_segments = 0;
 519   hints->axis[0].num_edges = 0;
 520   hints->axis[1].num_segments = 0;
 521   hints->axis[1].num_edges = 0;
 522
 523   /* first of all, reallocate the contours array if necessary */
 524   new_max = (FT_UInt)outline->n_contours;
 525   old_max = hints->max_contours;
 526   if (new_max > old_max)
 527   {
 528     TA_Point* contours_new;
 529
 530
 531     new_max = (new_max + 3) & ~3; /* round up to a multiple of 4 */
 532
 533     contours_new = (TA_Point*)realloc(hints->contours,
 534                                       new_max * sizeof (TA_Point));
 535     if (!contours_new)
 536       return FT_Err_Out_Of_Memory;
 537
 538     hints->contours = contours_new;
 539     hints->max_contours = new_max;
 540   }
 541
 542   /* reallocate the points arrays if necessary -- we reserve */
 543   /* two additional point positions, used to hint metrics appropriately */
 544   new_max = (FT_UInt)(outline->n_points + 2);
 545   old_max = hints->max_points;
 546   if (new_max > old_max)
 547   {
 548     TA_Point points_new;
 549
 550
 551     new_max = (new_max + 2 + 7) & ~7; /* round up to a multiple of 8 */
 552
 553     points_new = (TA_Point)realloc(hints->points,
 554                                    new_max * sizeof (TA_PointRec));
 555     if (!points_new)
 556       return FT_Err_Out_Of_Memory;
 557
 558     hints->points = points_new;
 559     hints->max_points = new_max;
 560   }
 561
 562   hints->num_points = outline->n_points;
 563   hints->num_contours = outline->n_contours;
 564
 565   /* we can't rely on the value of `FT_Outline.flags' to know the fill */
 566   /* direction used for a glyph, given that some fonts are broken */
 567   /* (e.g. the Arphic ones); we thus recompute it each time we need to */
 568
 569   hints->axis[TA_DIMENSION_HORZ].major_dir = TA_DIR_UP;
 570   hints->axis[TA_DIMENSION_VERT].major_dir = TA_DIR_LEFT;
 571
 572   if (FT_Outline_Get_Orientation(outline) == FT_ORIENTATION_POSTSCRIPT)
 573   {
 574     hints->axis[TA_DIMENSION_HORZ].major_dir = TA_DIR_DOWN;
 575     hints->axis[TA_DIMENSION_VERT].major_dir = TA_DIR_RIGHT;
 576   }
 577
 578   hints->x_scale = x_scale;
 579   hints->y_scale = y_scale;
 580   hints->x_delta = x_delta;
 581   hints->y_delta = y_delta;
 582
 583   hints->xmin_delta = 0;
 584   hints->xmax_delta = 0;
 585
 586   points = hints->points;
 587   if (hints->num_points == 0)
 588     goto Exit;
 589
 590   {
 591     TA_Point point;
 592     TA_Point point_limit = points + hints->num_points;
 593
 594
 595     /* compute coordinates & Bezier flags, next and prev */
 596     {
 597       FT_Vector* vec = outline->points;
 598       char* tag = outline->tags;
 599
 600       TA_Point end = points + outline->contours[0];
 601       TA_Point prev = end;
 602
 603       FT_Int contour_index = 0;
 604
 605
 606       for (point = points; point < point_limit; point++, vec++, tag++)
 607       {
 608         point->in_dir = (FT_Char)TA_DIR_NONE;
 609         point->out_dir = (FT_Char)TA_DIR_NONE;
 610
 611         point->fx = (FT_Short)vec->x;
 612         point->fy = (FT_Short)vec->y;
 613         point->ox = point->x = FT_MulFix(vec->x, x_scale) + x_delta;
 614         point->oy = point->y = FT_MulFix(vec->y, y_scale) + y_delta;
 615
 616         switch (FT_CURVE_TAG(*tag))
 617         {
 618         case FT_CURVE_TAG_CONIC:
 619           point->flags = TA_FLAG_CONIC;
 620           break;
 621         case FT_CURVE_TAG_CUBIC:
 622           point->flags = TA_FLAG_CUBIC;
 623           break;
 624         default:
 625           point->flags = TA_FLAG_NONE;
 626         }
 627
 628         point->prev = prev;
 629         prev->next = point;
 630         prev = point;
 631
 632         if (point == end)
 633         {
 634           if (++contour_index < outline->n_contours)
 635           {
 636             end = points + outline->contours[contour_index];
 637             prev = end;
 638           }
 639         }
 640       }
 641     }
 642
 643     /* set up the contours array */
 644     {
 645       TA_Point* contour = hints->contours;
 646       TA_Point* contour_limit = contour + hints->num_contours;
 647
 648       short* end = outline->contours;
 649       short idx = 0;
 650
 651
 652       for (; contour < contour_limit; contour++, end++)
 653       {
 654         contour[0] = points + idx;
 655         idx = (short)(end[0] + 1);
 656       }
 657     }
 658
 659     {
 660       /*
 661        *  Compute directions of `in' and `out' vectors.
 662        *
 663        *  Note that distances between points that are very near to each
 664        *  other are accumulated.  In other words, the auto-hinter
 665        *  prepends the small vectors between near points to the first
 666        *  non-near vector.  All intermediate points are tagged as
 667        *  weak; the directions are adjusted also to be equal to the
 668        *  accumulated one.
 669        */
 670
 671       /* value 20 in `near_limit' is heuristic */
 672       FT_UInt units_per_em = hints->metrics->scaler.face->units_per_EM;
 673       FT_Int near_limit = 20 * units_per_em / 2048;
 674       FT_Int near_limit2 = 2 * near_limit - 1;
 675
 676       TA_Point* contour;
 677       TA_Point* contour_limit = hints->contours + hints->num_contours;
 678
 679
 680       for (contour = hints->contours; contour < contour_limit; contour++)
 681       {
 682         TA_Point first = *contour;
 683         TA_Point next, prev, curr;
 684
 685         FT_Pos out_x, out_y;
 686
 687         FT_Bool is_first;
 688
 689
 690         /* since the first point of a contour could be part of a */
 691         /* series of near points, go backwards to find the first */
 692         /* non-near point and adjust `first' */
 693
 694         point = first;
 695         prev = first->prev;
 696
 697         while (prev != first)
 698         {
 699           out_x = point->fx - prev->fx;
 700           out_y = point->fy - prev->fy;
 701
 702           /*
 703            *  We use Taxicab metrics to measure the vector length.
 704            *
 705            *  Note that the accumulated distances so far could have the
 706            *  opposite direction of the distance measured here.  For this
 707            *  reason we use `near_limit2' for the comparison to get a
 708            *  non-near point even in the worst case.
 709            */
 710           if (TA_ABS(out_x) + TA_ABS(out_y) >= near_limit2)
 711             break;
 712
 713           point = prev;
 714           prev = prev->prev;
 715         }
 716
 717         /* adjust first point */
 718         first = point;
 719
 720         /* now loop over all points of the contour to get */
 721         /* `in' and `out' vector directions */
 722
 723         curr = first;
 724
 725         /*
 726          *  We abuse the `u' and `v' fields to store index deltas to the
 727          *  next and previous non-near point, respectively.
 728          *
 729          *  To avoid problems with not having non-near points, we point to
 730          *  `first' by default as the next non-near point.
 731          */
 732         curr->u = (FT_Pos)(first - curr);
 733         first->v = -curr->u;
 734
 735         out_x = 0;
 736         out_y = 0;
 737
 738         is_first = 1;
 739
 740         for (point = first;
 741              point != first || is_first;
 742              point = point->next)
 743         {
 744           TA_Direction out_dir;
 745
 746
 747           is_first = 0;
 748
 749           next = point->next;
 750
 751           out_x += next->fx - point->fx;
 752           out_y += next->fy - point->fy;
 753
 754           if (TA_ABS(out_x) + TA_ABS(out_y) < near_limit)
 755           {
 756             next->flags |= TA_FLAG_WEAK_INTERPOLATION;
 757             continue;
 758           }
 759
 760           curr->u = (FT_Pos)(next - curr);
 761           next->v = -curr->u;
 762
 763           out_dir = ta_direction_compute(out_x, out_y);
 764
 765           /* adjust directions for all points inbetween; */
 766           /* the loop also updates position of `curr' */
 767           curr->out_dir = (FT_Char)out_dir;
 768           for (curr = curr->next; curr != next; curr = curr->next)
 769           {
 770             curr->in_dir = (FT_Char)out_dir;
 771             curr->out_dir = (FT_Char)out_dir;
 772           }
 773           next->in_dir = (FT_Char)out_dir;
 774
 775           curr->u = (FT_Pos)(first - curr);
 776           first->v = -curr->u;
 777
 778           out_x = 0;
 779           out_y = 0;
 780         }
 781       }
 782
 783       /*
 784        *  The next step is to `simplify' an outline's topology so that we
 785        *  can identify local extrema more reliably: A series of
 786        *  non-horizontal or non-vertical vectors pointing into the same
 787        *  quadrant are handled as a single, long vector.  From a
 788        *  topological point of the view, the intermediate points are of no
 789        *  interest and thus tagged as weak.
 790        */
 791
 792       for (point = points; point < point_limit; point++)
 793       {
 794         if (point->flags & TA_FLAG_WEAK_INTERPOLATION)
 795           continue;
 796
 797         if (point->in_dir == TA_DIR_NONE
 798             && point->out_dir == TA_DIR_NONE)
 799         {
 800           /* check whether both vectors point into the same quadrant */
 801
 802           FT_Pos in_x, in_y;
 803           FT_Pos out_x, out_y;
 804
 805           TA_Point next_u = point + point->u;
 806           TA_Point prev_v = point + point->v;
 807
 808
 809           in_x = point->fx - prev_v->fx;
 810           in_y = point->fy - prev_v->fy;
 811
 812           out_x = next_u->fx - point->fx;
 813           out_y = next_u->fy - point->fy;
 814
 815           if ((in_x ^ out_x) >= 0 && (in_y ^ out_y) >= 0)
 816           {
 817             /* yes, so tag current point as weak */
 818             /* and update index deltas */
 819
 820             point->flags |= TA_FLAG_WEAK_INTERPOLATION;
 821
 822             prev_v->u = (FT_Pos)(next_u - prev_v);
 823             next_u->v = -prev_v->u;
 824           }
 825         }
 826       }
 827
 828       /*
 829        *  Finally, check for remaining weak points.  Everything else not
 830        *  collected in edges so far is then implicitly classified as strong
 831        *  points.
 832        */
 833
 834       for (point = points; point < point_limit; point++)
 835       {
 836         if (point->flags & TA_FLAG_WEAK_INTERPOLATION)
 837           continue;
 838
 839         if (point->flags & TA_FLAG_CONTROL)
 840         {
 841           /* control points are always weak */
 842         Is_Weak_Point:
 843           point->flags |= TA_FLAG_WEAK_INTERPOLATION;
 844         }
 845         else if (point->out_dir == point->in_dir)
 846         {
 847           if (point->out_dir != TA_DIR_NONE)
 848           {
 849             /* current point lies on a horizontal or */
 850             /* vertical segment (but doesn't start or end it) */
 851             goto Is_Weak_Point;
 852           }
 853
 854           {
 855             TA_Point next_u = point + point->u;
 856             TA_Point prev_v = point + point->v;
 857
 858
 859             if (ta_corner_is_flat(point->fx - prev_v->fx,
 860                                   point->fy - prev_v->fy,
 861                                   next_u->fx - point->fx,
 862                                   next_u->fy - point->fy))
 863             {
 864               /* either the `in' or the `out' vector is much more */
 865               /* dominant than the other one, so tag current point */
 866               /* as weak and update index deltas */
 867
 868               prev_v->u = (FT_Pos)(next_u - prev_v);
 869               next_u->v = -prev_v->u;
 870
 871               goto Is_Weak_Point;
 872             }
 873           }
 874         }
 875         else if (point->in_dir == -point->out_dir)
 876         {
 877           /* current point forms a spike */
 878           goto Is_Weak_Point;
 879         }
 880       }
 881     }
 882   }
 883
 884   /* change some directions at the user's request */
 885   /* to make ttfautohint insert one-point segments */
 886   /* or remove points from segments */
 887   {
 888     FONT* font;
 889     FT_Int idx;
 890     TA_Direction dir;
 891
 892
 893     /* `globals' is not set up while initializing metrics, */
 894     /* so exit early in this case */
 895     if (!hints->metrics->globals)
 896       goto Exit;
 897
 898     font = hints->metrics->globals->font;
 899
 900     /* start conditions are set with `TA_control_point_dir_collect' */
 901     while (TA_control_point_dir_get_next(font, &idx, &dir))
 902     {
 903       TA_Point point = &points[idx];
 904
 905
 906       point->out_dir = dir;
 907       if (dir == TA_DIR_NONE)
 908         point->flags |= TA_FLAG_WEAK_INTERPOLATION;
 909       else
 910         point->flags &= ~TA_FLAG_WEAK_INTERPOLATION;
 911     }
 912   }
 913
 914 Exit:
 915   return error;
 916 }
 917
 918
 919 /* store the hinted outline in an FT_Outline structure */
 920
 921 void
 922 ta_glyph_hints_save(TA_GlyphHints hints,
 923                     FT_Outline* outline)
 924 {
 925   TA_Point point = hints->points;
 926   TA_Point limit = point + hints->num_points;
 927
 928   FT_Vector* vec = outline->points;
 929   char* tag = outline->tags;
 930
 931
 932   for (; point < limit; point++, vec++, tag++)
 933   {
 934     vec->x = point->x;
 935     vec->y = point->y;
 936
 937     if (point->flags & TA_FLAG_CONIC)
 938       tag[0] = FT_CURVE_TAG_CONIC;
 939     else if (point->flags & TA_FLAG_CUBIC)
 940       tag[0] = FT_CURVE_TAG_CUBIC;
 941     else
 942       tag[0] = FT_CURVE_TAG_ON;
 943   }
 944 }
 945
 946
 947 /****************************************************************
 948  *
 949  *                     EDGE POINT GRID-FITTING
 950  *
 951  ****************************************************************/
 952
 953
 954 /* align all points of an edge to the same coordinate value, */
 955 /* either horizontally or vertically */
 956
 957 void
 958 ta_glyph_hints_align_edge_points(TA_GlyphHints hints,
 959                                  TA_Dimension dim)
 960 {
 961   TA_AxisHints axis = &hints->axis[dim];
 962   TA_Segment segments = axis->segments;
 963   TA_Segment segment_limit = segments + axis->num_segments;
 964   TA_Segment seg;
 965
 966
 967   if (dim == TA_DIMENSION_HORZ)
 968   {
 969     for (seg = segments; seg < segment_limit; seg++)
 970     {
 971       TA_Edge edge = seg->edge;
 972       TA_Point point, first, last;
 973
 974
 975       if (edge == NULL)
 976         continue;
 977
 978       first = seg->first;
 979       last = seg->last;
 980       point = first;
 981       for (;;)
 982       {
 983         point->x = edge->pos;
 984         point->flags |= TA_FLAG_TOUCH_X;
 985
 986         if (point == last)
 987           break;
 988
 989         point = point->next;
 990       }
 991     }
 992   }
 993   else
 994   {
 995     for (seg = segments; seg < segment_limit; seg++)
 996     {
 997       TA_Edge edge = seg->edge;
 998       TA_Point point, first, last;
 999
1000
1001       if (edge == NULL)
1002         continue;
1003
1004       first = seg->first;
1005       last = seg->last;
1006       point = first;
1007       for (;;)
1008       {
1009         point->y = edge->pos;
1010         point->flags |= TA_FLAG_TOUCH_Y;
1011
1012         if (point == last)
1013           break;
1014
1015         point = point->next;
1016       }
1017     }
1018   }
1019 }
1020
1021
1022 /****************************************************************
1023  *
1024  *                    STRONG POINT INTERPOLATION
1025  *
1026  ****************************************************************/
1027
1028
1029 /* hint the strong points -- */
1030 /* this is equivalent to the TrueType `IP' hinting instruction */
1031
1032 void
1033 ta_glyph_hints_align_strong_points(TA_GlyphHints hints,
1034                                    TA_Dimension dim)
1035 {
1036   TA_Point points = hints->points;
1037   TA_Point point_limit = points + hints->num_points;
1038
1039   TA_AxisHints axis = &hints->axis[dim];
1040
1041   TA_Edge edges = axis->edges;
1042   TA_Edge edge_limit = edges + axis->num_edges;
1043
1044   FT_UShort touch_flag;
1045
1046
1047   if (dim == TA_DIMENSION_HORZ)
1048     touch_flag = TA_FLAG_TOUCH_X;
1049   else
1050     touch_flag = TA_FLAG_TOUCH_Y;
1051
1052   if (edges < edge_limit)
1053   {
1054     TA_Point point;
1055     TA_Edge edge;
1056
1057
1058     for (point = points; point < point_limit; point++)
1059     {
1060       FT_Pos u, ou, fu; /* point position */
1061       FT_Pos delta;
1062
1063
1064       if (point->flags & touch_flag)
1065         continue;
1066
1067       /* if this point is candidate to weak interpolation, we */
1068       /* interpolate it after all strong points have been processed */
1069
1070       if ((point->flags & TA_FLAG_WEAK_INTERPOLATION))
1071         continue;
1072
1073       if (dim == TA_DIMENSION_VERT)
1074       {
1075         u = point->fy;
1076         ou = point->oy;
1077       }
1078       else
1079       {
1080         u = point->fx;
1081         ou = point->ox;
1082       }
1083
1084       fu = u;
1085
1086       /* is the point before the first edge? */
1087       edge = edges;
1088       delta = edge->fpos - u;
1089       if (delta >= 0)
1090       {
1091         u = edge->pos - (edge->opos - ou);
1092
1093         if (hints->recorder)
1094           hints->recorder(ta_ip_before, hints, dim,
1095                           point, NULL, NULL, NULL, NULL);
1096
1097         goto Store_Point;
1098       }
1099
1100       /* is the point after the last edge? */
1101       edge = edge_limit - 1;
1102       delta = u - edge->fpos;
1103       if (delta >= 0)
1104       {
1105         u = edge->pos + (ou - edge->opos);
1106
1107         if (hints->recorder)
1108           hints->recorder(ta_ip_after, hints, dim,
1109                           point, NULL, NULL, NULL, NULL);
1110
1111         goto Store_Point;
1112       }
1113
1114       {
1115         FT_PtrDist min, max, mid;
1116         FT_Pos fpos;
1117
1118
1119         /* find enclosing edges */
1120         min = 0;
1121         max = edge_limit - edges;
1122
1123         /* for a small number of edges, a linear search is better */
1124         if (max <= 8)
1125         {
1126           FT_PtrDist nn;
1127
1128
1129           for (nn = 0; nn < max; nn++)
1130             if (edges[nn].fpos >= u)
1131               break;
1132
1133           if (edges[nn].fpos == u)
1134           {
1135             u = edges[nn].pos;
1136
1137             if (hints->recorder)
1138               hints->recorder(ta_ip_on, hints, dim,
1139                               point, &edges[nn], NULL, NULL, NULL);
1140
1141             goto Store_Point;
1142           }
1143           min = nn;
1144         }
1145         else
1146           while (min < max)
1147           {
1148             mid = (max + min) >> 1;
1149             edge = edges + mid;
1150             fpos = edge->fpos;
1151
1152             if (u < fpos)
1153               max = mid;
1154             else if (u > fpos)
1155               min = mid + 1;
1156             else
1157             {
1158               /* we are on the edge */
1159               u = edge->pos;
1160
1161               if (hints->recorder)
1162                 hints->recorder(ta_ip_on, hints, dim,
1163                                 point, edge, NULL, NULL, NULL);
1164
1165               goto Store_Point;
1166             }
1167           }
1168
1169         /* point is not on an edge */
1170         {
1171           TA_Edge before = edges + min - 1;
1172           TA_Edge after = edges + min + 0;
1173
1174
1175           /* assert(before && after && before != after) */
1176           if (before->scale == 0)
1177             before->scale = FT_DivFix(after->pos - before->pos,
1178                                       after->fpos - before->fpos);
1179
1180           u = before->pos + FT_MulFix(fu - before->fpos,
1181                                       before->scale);
1182
1183           if (hints->recorder)
1184             hints->recorder(ta_ip_between, hints, dim,
1185                             point, before, after, NULL, NULL);
1186         }
1187       }
1188
1189     Store_Point:
1190       /* save the point position */
1191       if (dim == TA_DIMENSION_HORZ)
1192         point->x = u;
1193       else
1194         point->y = u;
1195
1196       point->flags |= touch_flag;
1197     }
1198   }
1199 }
1200
1201
1202 /****************************************************************
1203  *
1204  *                    WEAK POINT INTERPOLATION
1205  *
1206  ****************************************************************/
1207
1208
1209 /* shift the original coordinates of all points between `p1' and */
1210 /* `p2' to get hinted coordinates, using the same difference as */
1211 /* given by `ref' */
1212
1213 static void
1214 ta_iup_shift(TA_Point p1,
1215              TA_Point p2,
1216              TA_Point ref)
1217 {
1218   TA_Point p;
1219   FT_Pos delta = ref->u - ref->v;
1220
1221
1222   if (delta == 0)
1223     return;
1224
1225   for (p = p1; p < ref; p++)
1226     p->u = p->v + delta;
1227
1228   for (p = ref + 1; p <= p2; p++)
1229     p->u = p->v + delta;
1230 }
1231
1232
1233 /* interpolate the original coordinates of all points between `p1' and */
1234 /* `p2' to get hinted coordinates, using `ref1' and `ref2' as the */
1235 /* reference points; the `u' and `v' members are the current and */
1236 /* original coordinate values, respectively. */
1237
1238 /* details can be found in the TrueType bytecode specification */
1239
1240 static void
1241 ta_iup_interp(TA_Point p1,
1242               TA_Point p2,
1243               TA_Point ref1,
1244               TA_Point ref2)
1245 {
1246   TA_Point p;
1247   FT_Pos u;
1248   FT_Pos v1 = ref1->v;
1249   FT_Pos v2 = ref2->v;
1250   FT_Pos d1 = ref1->u - v1;
1251   FT_Pos d2 = ref2->u - v2;
1252
1253
1254   if (p1 > p2)
1255     return;
1256
1257   if (v1 == v2)
1258   {
1259     for (p = p1; p <= p2; p++)
1260     {
1261       u = p->v;
1262
1263       if (u <= v1)
1264         u += d1;
1265       else
1266         u += d2;
1267
1268       p->u = u;
1269     }
1270     return;
1271   }
1272
1273   if (v1 < v2)
1274   {
1275     for (p = p1; p <= p2; p++)
1276     {
1277       u = p->v;
1278
1279       if (u <= v1)
1280         u += d1;
1281       else if (u >= v2)
1282         u += d2;
1283       else
1284         u = ref1->u + FT_MulDiv(u - v1, ref2->u - ref1->u, v2 - v1);
1285
1286       p->u = u;
1287     }
1288   }
1289   else
1290   {
1291     for (p = p1; p <= p2; p++)
1292     {
1293       u = p->v;
1294
1295       if (u <= v2)
1296         u += d2;
1297       else if (u >= v1)
1298         u += d1;
1299       else
1300         u = ref1->u + FT_MulDiv(u - v1, ref2->u - ref1->u, v2 - v1);
1301
1302       p->u = u;
1303     }
1304   }
1305 }
1306
1307
1308 /* hint the weak points -- */
1309 /* this is equivalent to the TrueType `IUP' hinting instruction */
1310
1311 void
1312 ta_glyph_hints_align_weak_points(TA_GlyphHints hints,
1313                                  TA_Dimension dim)
1314 {
1315   TA_Point points = hints->points;
1316   TA_Point point_limit = points + hints->num_points;
1317
1318   TA_Point* contour = hints->contours;
1319   TA_Point* contour_limit = contour + hints->num_contours;
1320
1321   FT_UShort touch_flag;
1322   TA_Point point;
1323   TA_Point end_point;
1324   TA_Point first_point;
1325
1326
1327   /* pass 1: move segment points to edge positions */
1328
1329   if (dim == TA_DIMENSION_HORZ)
1330   {
1331     touch_flag = TA_FLAG_TOUCH_X;
1332
1333     for (point = points; point < point_limit; point++)
1334     {
1335       point->u = point->x;
1336       point->v = point->ox;
1337     }
1338   }
1339   else
1340   {
1341     touch_flag = TA_FLAG_TOUCH_Y;
1342
1343     for (point = points; point < point_limit; point++)
1344     {
1345       point->u = point->y;
1346       point->v = point->oy;
1347     }
1348   }
1349
1350   for (; contour < contour_limit; contour++)
1351   {
1352     TA_Point first_touched, last_touched;
1353
1354
1355     point = *contour;
1356     end_point = point->prev;
1357     first_point = point;
1358
1359     /* find first touched point */
1360     for (;;)
1361     {
1362       if (point > end_point) /* no touched point in contour */
1363         goto NextContour;
1364
1365       if (point->flags & touch_flag)
1366         break;
1367
1368       point++;
1369     }
1370
1371     first_touched = point;
1372
1373     for (;;)
1374     {
1375       /* skip any touched neighbours */
1376       while (point < end_point
1377              && (point[1].flags & touch_flag) != 0)
1378         point++;
1379
1380       last_touched = point;
1381
1382       /* find the next touched point, if any */
1383       point++;
1384       for (;;)
1385       {
1386         if (point > end_point)
1387           goto EndContour;
1388
1389         if ((point->flags & touch_flag) != 0)
1390           break;
1391
1392         point++;
1393       }
1394
1395       /* interpolate between last_touched and point */
1396       ta_iup_interp(last_touched + 1, point - 1,
1397                     last_touched, point);
1398     }
1399
1400   EndContour:
1401     /* special case: only one point was touched */
1402     if (last_touched == first_touched)
1403       ta_iup_shift(first_point, end_point, first_touched);
1404
1405     else /* interpolate the last part */
1406     {
1407       if (last_touched < end_point)
1408         ta_iup_interp(last_touched + 1, end_point,
1409                       last_touched, first_touched);
1410
1411       if (first_touched > points)
1412         ta_iup_interp(first_point, first_touched - 1,
1413                       last_touched, first_touched);
1414     }
1415
1416   NextContour:
1417     ;
1418   }
1419
1420   /* now save the interpolated values back to x/y */
1421   if (dim == TA_DIMENSION_HORZ)
1422   {
1423     for (point = points; point < point_limit; point++)
1424       point->x = point->u;
1425   }
1426   else
1427   {
1428     for (point = points; point < point_limit; point++)
1429       point->y = point->u;
1430   }
1431 }
1432
1433
1434 #ifdef TA_CONFIG_OPTION_USE_WARPER
1435
1436 /* apply (small) warp scale and warp delta for given dimension */
1437
1438 static void
1439 ta_glyph_hints_scale_dim(TA_GlyphHints hints,
1440                          TA_Dimension dim,
1441                          FT_Fixed scale,
1442                          FT_Pos delta)
1443 {
1444   TA_Point points = hints->points;
1445   TA_Point points_limit = points + hints->num_points;
1446   TA_Point point;
1447
1448
1449   if (dim == TA_DIMENSION_HORZ)
1450   {
1451     for (point = points; point < points_limit; point++)
1452       point->x = FT_MulFix(point->fx, scale) + delta;
1453   }
1454   else
1455   {
1456     for (point = points; point < points_limit; point++)
1457       point->y = FT_MulFix(point->fy, scale) + delta;
1458   }
1459 }
1460
1461 #endif /* TA_CONFIG_OPTION_USE_WARPER */
1462
1463 /* end of tahints.c */