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