lib/tahints.c

   1 /* tahints.c */
   2
   3 /*
   4  * Copyright (C) 2011-2012 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   fprintf(stderr, "Table of points:\n");
 206   fprintf(stderr, "  [ index |  xorg |  yorg | xscale | yscale"
 207                   " |  xfit |  yfit |  flags ]\n");
 208
 209   for (point = points; point < limit; point++)
 210   {
 211     fprintf(stderr, "  [ %5d | %5d | %5d | %6.2f | %6.2f"
 212                     " | %5.2f | %5.2f | %c%c%c%c%c%c ]\n",
 213             point - points,
 214             point->fx,
 215             point->fy,
 216             point->ox / 64.0,
 217             point->oy / 64.0,
 218             point->x / 64.0,
 219             point->y / 64.0,
 220             (point->flags & TA_FLAG_WEAK_INTERPOLATION) ? 'w' : ' ',
 221             (point->flags & TA_FLAG_INFLECTION) ? 'i' : ' ',
 222             (point->flags & TA_FLAG_EXTREMA_X) ? '<' : ' ',
 223             (point->flags & TA_FLAG_EXTREMA_Y) ? 'v' : ' ',
 224             (point->flags & TA_FLAG_ROUND_X) ? '(' : ' ',
 225             (point->flags & TA_FLAG_ROUND_Y) ? 'u' : ' ');
 226   }
 227   fprintf(stderr, "\n");
 228 }
 229
 230
 231 static const char*
 232 ta_edge_flags_to_string(FT_Byte flags)
 233 {
 234   static char temp[32];
 235   int pos = 0;
 236
 237
 238   if (flags & TA_EDGE_ROUND)
 239   {
 240     memcpy(temp + pos, "round", 5);
 241     pos += 5;
 242   }
 243   if (flags & TA_EDGE_SERIF)
 244   {
 245     if (pos > 0)
 246       temp[pos++] = ' ';
 247     memcpy(temp + pos, "serif", 5);
 248     pos += 5;
 249   }
 250   if (pos == 0)
 251     return "normal";
 252
 253   temp[pos] = '\0';
 254
 255   return temp;
 256 }
 257
 258
 259 /* dump the array of linked segments */
 260
 261 void
 262 ta_glyph_hints_dump_segments(TA_GlyphHints hints)
 263 {
 264   FT_Int dimension;
 265
 266
 267   for (dimension = TA_DEBUG_STARTDIM;
 268        dimension >= TA_DEBUG_ENDDIM;
 269        dimension--)
 270   {
 271     TA_AxisHints axis = &hints->axis[dimension];
 272     TA_Point points = hints->points;
 273     TA_Edge edges = axis->edges;
 274     TA_Segment segments = axis->segments;
 275     TA_Segment limit = segments + axis->num_segments;
 276     TA_Segment seg;
 277
 278
 279     fprintf(stderr, "Table of %s segments:\n",
 280             dimension == TA_DIMENSION_HORZ ? "vertical"
 281                                            : "horizontal");
 282     fprintf(stderr, "  [ index |  pos  |  dir  | from |  to  | link | serif | edge |"
 283                     " height | extra |    flags    ]\n");
 284
 285     for (seg = segments; seg < limit; seg++)
 286     {
 287       fprintf(stderr, "  [ %5d | %5.2g | %5s | %4d | %4d | %4d | %5d | %4d |"
 288                       " %6d | %5d | %11s ]\n",
 289               seg - segments,
 290               dimension == TA_DIMENSION_HORZ ? (int)seg->first->ox / 64.0
 291                                              : (int)seg->first->oy / 64.0,
 292               ta_dir_str((TA_Direction)seg->dir),
 293               TA_INDEX_NUM(seg->first, points),
 294               TA_INDEX_NUM(seg->last, points),
 295               TA_INDEX_NUM(seg->link, segments),
 296               TA_INDEX_NUM(seg->serif, segments),
 297               TA_INDEX_NUM(seg->edge, edges),
 298               seg->height,
 299               seg->height - (seg->max_coord - seg->min_coord),
 300               ta_edge_flags_to_string(seg->flags));
 301     }
 302     fprintf(stderr, "\n");
 303   }
 304 }
 305
 306
 307 /* dump the array of linked edges */
 308
 309 void
 310 ta_glyph_hints_dump_edges(TA_GlyphHints hints)
 311 {
 312   FT_Int dimension;
 313
 314
 315   for (dimension = TA_DEBUG_STARTDIM;
 316        dimension >= TA_DEBUG_ENDDIM;
 317        dimension--)
 318   {
 319     TA_AxisHints axis = &hints->axis[dimension];
 320     TA_Edge edges = axis->edges;
 321     TA_Edge limit = edges + axis->num_edges;
 322     TA_Edge edge;
 323
 324
 325     /* note that TA_DIMENSION_HORZ corresponds to _vertical_ edges */
 326     /* since they have a constant X coordinate */
 327     fprintf(stderr, "Table of %s edges:\n",
 328             dimension == TA_DIMENSION_HORZ ? "vertical"
 329                                            : "horizontal");
 330     fprintf(stderr, "  [ index |  pos  |  dir  | link |"
 331                     " serif | blue | opos  |  pos  |    flags    ]\n");
 332
 333     for (edge = edges; edge < limit; edge++)
 334     {
 335       fprintf(stderr, "  [ %5d | %5.2g | %5s | %4d |"
 336                       " %5d |   %c  | %5.2f | %5.2f | %11s ]\n",
 337               edge - edges,
 338               (int)edge->opos / 64.0,
 339               ta_dir_str((TA_Direction)edge->dir),
 340               TA_INDEX_NUM(edge->link, edges),
 341               TA_INDEX_NUM(edge->serif, edges),
 342               edge->blue_edge ? 'y' : 'n',
 343               edge->opos / 64.0,
 344               edge->pos / 64.0,
 345               ta_edge_flags_to_string(edge->flags));
 346     }
 347     fprintf(stderr, "\n");
 348   }
 349 }
 350
 351
 352 void
 353 ta_glyph_hints_dump_edge_links(TA_GlyphHints hints)
 354 {
 355   FT_Int dimension;
 356
 357
 358   for (dimension = TA_DEBUG_STARTDIM;
 359        dimension >= TA_DEBUG_ENDDIM;
 360        dimension--)
 361   {
 362     TA_AxisHints axis = &hints->axis[dimension];
 363     TA_Segment segments = axis->segments;
 364     TA_Edge edges = axis->edges;
 365     TA_Edge limit = edges + axis->num_edges;
 366
 367     TA_Edge edge;
 368     TA_Segment seg;
 369
 370
 371     fprintf(stderr, "%s edges consist of the following segments:\n",
 372             dimension == TA_DIMENSION_HORZ ? "Vertical"
 373                                            : "Horizontal");
 374     for (edge = edges; edge < limit; edge++)
 375     {
 376       fprintf(stderr, "  %2d:", edge - edges);
 377
 378       seg = edge->first;
 379       do
 380       {
 381         fprintf(stderr, " %d", seg - segments);
 382         seg = seg->edge_next;
 383       } while (seg != edge->first);
 384
 385       fprintf(stderr, "\n");
 386     }
 387     fprintf(stderr, "\n");
 388   }
 389 }
 390
 391 #endif /* TA_DEBUG */
 392
 393
 394 /* compute the direction value of a given vector */
 395
 396 TA_Direction
 397 ta_direction_compute(FT_Pos dx,
 398                      FT_Pos dy)
 399 {
 400   FT_Pos ll, ss;  /* long and short arm lengths */
 401   TA_Direction dir; /* candidate direction */
 402
 403
 404   if (dy >= dx)
 405   {
 406     if (dy >= -dx)
 407     {
 408       dir = TA_DIR_UP;
 409       ll = dy;
 410       ss = dx;
 411     }
 412     else
 413     {
 414       dir = TA_DIR_LEFT;
 415       ll = -dx;
 416       ss = dy;
 417     }
 418     }
 419   else /* dy < dx */
 420   {
 421     if (dy >= -dx)
 422     {
 423       dir = TA_DIR_RIGHT;
 424       ll = dx;
 425       ss = dy;
 426     }
 427     else
 428     {
 429       dir = TA_DIR_DOWN;
 430       ll = dy;
 431       ss = dx;
 432     }
 433   }
 434
 435   /* return no direction if arm lengths differ too much */
 436   /* (value 14 is heuristic)                            */
 437   ss *= 14;
 438   if (TA_ABS(ll) <= TA_ABS(ss))
 439     dir = TA_DIR_NONE;
 440
 441   return dir;
 442 }
 443
 444
 445 void
 446 ta_glyph_hints_init(TA_GlyphHints hints)
 447 {
 448   memset(hints, 0, sizeof (TA_GlyphHintsRec));
 449 }
 450
 451
 452 void
 453 ta_glyph_hints_done(TA_GlyphHints hints)
 454 {
 455   int dim;
 456
 457
 458   if (!hints)
 459     return;
 460
 461   /* we don't need to free the segment and edge buffers */
 462   /* since they are really within the hints->points array */
 463   for (dim = 0; dim < TA_DIMENSION_MAX; dim++)
 464   {
 465     TA_AxisHints axis = &hints->axis[dim];
 466
 467
 468     axis->num_segments = 0;
 469     axis->max_segments = 0;
 470     free(axis->segments);
 471     axis->segments = NULL;
 472
 473     axis->num_edges = 0;
 474     axis->max_edges = 0;
 475     free(axis->edges);
 476     axis->edges = NULL;
 477   }
 478
 479   free(hints->contours);
 480   hints->contours = NULL;
 481   hints->max_contours = 0;
 482   hints->num_contours = 0;
 483
 484   free(hints->points);
 485   hints->points = NULL;
 486   hints->num_points = 0;
 487   hints->max_points = 0;
 488 }
 489
 490
 491 /* reset metrics */
 492
 493 void
 494 ta_glyph_hints_rescale(TA_GlyphHints hints,
 495                        TA_ScriptMetrics metrics)
 496 {
 497   hints->metrics = metrics;
 498   hints->scaler_flags = metrics->scaler.flags;
 499 }
 500
 501
 502 /* from FreeType's ftcalc.c */
 503
 504 static FT_Int
 505 ta_corner_is_flat(FT_Pos in_x,
 506                   FT_Pos in_y,
 507                   FT_Pos out_x,
 508                   FT_Pos out_y)
 509 {
 510   FT_Pos ax = in_x;
 511   FT_Pos ay = in_y;
 512
 513   FT_Pos d_in, d_out, d_corner;
 514
 515
 516   if (ax < 0)
 517     ax = -ax;
 518   if (ay < 0)
 519     ay = -ay;
 520   d_in = ax + ay;
 521
 522   ax = out_x;
 523   if (ax < 0)
 524     ax = -ax;
 525   ay = out_y;
 526   if (ay < 0)
 527     ay = -ay;
 528   d_out = ax + ay;
 529
 530   ax = out_x + in_x;
 531   if (ax < 0)
 532     ax = -ax;
 533   ay = out_y + in_y;
 534   if (ay < 0)
 535     ay = -ay;
 536   d_corner = ax + ay;
 537
 538   return (d_in + d_out - d_corner) < (d_corner >> 4);
 539 }
 540
 541
 542 /* recompute all TA_Point in TA_GlyphHints */
 543 /* from the definitions in a source outline */
 544
 545 FT_Error
 546 ta_glyph_hints_reload(TA_GlyphHints hints,
 547                       FT_Outline* outline)
 548 {
 549   FT_Error error = FT_Err_Ok;
 550   TA_Point points;
 551   FT_UInt old_max, new_max;
 552
 553   FT_Fixed x_scale = hints->x_scale;
 554   FT_Fixed y_scale = hints->y_scale;
 555   FT_Pos x_delta = hints->x_delta;
 556   FT_Pos y_delta = hints->y_delta;
 557
 558
 559   hints->num_points = 0;
 560   hints->num_contours = 0;
 561
 562   hints->axis[0].num_segments = 0;
 563   hints->axis[0].num_edges = 0;
 564   hints->axis[1].num_segments = 0;
 565   hints->axis[1].num_edges = 0;
 566
 567   /* first of all, reallocate the contours array if necessary */
 568   new_max = (FT_UInt)outline->n_contours;
 569   old_max = hints->max_contours;
 570   if (new_max > old_max)
 571   {
 572     TA_Point* contours_new;
 573
 574
 575     new_max = (new_max + 3) & ~3; /* round up to a multiple of 4 */
 576
 577     contours_new = (TA_Point*)realloc(hints->contours,
 578                                       new_max * sizeof (TA_Point));
 579     if (!contours_new)
 580       return FT_Err_Out_Of_Memory;
 581
 582     hints->contours = contours_new;
 583     hints->max_contours = new_max;
 584   }
 585
 586   /* reallocate the points arrays if necessary -- we reserve */
 587   /* two additional point positions, used to hint metrics appropriately */
 588   new_max = (FT_UInt)(outline->n_points + 2);
 589   old_max = hints->max_points;
 590   if (new_max > old_max)
 591   {
 592     TA_Point  points_new;
 593
 594
 595     new_max = (new_max + 2 + 7) & ~7; /* round up to a multiple of 8 */
 596
 597     points_new = (TA_Point)realloc(hints->points,
 598                                    new_max * sizeof (TA_PointRec));
 599     if (!points_new)
 600       return FT_Err_Out_Of_Memory;
 601
 602     hints->points = points_new;
 603     hints->max_points = new_max;
 604   }
 605
 606   hints->num_points = outline->n_points;
 607   hints->num_contours = outline->n_contours;
 608
 609   /* we can't rely on the value of `FT_Outline.flags' to know the fill */
 610   /* direction used for a glyph, given that some fonts are broken */
 611   /* (e.g. the Arphic ones); we thus recompute it each time we need to */
 612
 613   hints->axis[TA_DIMENSION_HORZ].major_dir = TA_DIR_UP;
 614   hints->axis[TA_DIMENSION_VERT].major_dir = TA_DIR_LEFT;
 615
 616   if (FT_Outline_Get_Orientation(outline) == FT_ORIENTATION_POSTSCRIPT)
 617   {
 618     hints->axis[TA_DIMENSION_HORZ].major_dir = TA_DIR_DOWN;
 619     hints->axis[TA_DIMENSION_VERT].major_dir = TA_DIR_RIGHT;
 620   }
 621
 622   hints->x_scale = x_scale;
 623   hints->y_scale = y_scale;
 624   hints->x_delta = x_delta;
 625   hints->y_delta = y_delta;
 626
 627   hints->xmin_delta = 0;
 628   hints->xmax_delta = 0;
 629
 630   points = hints->points;
 631   if (hints->num_points == 0)
 632     goto Exit;
 633
 634   {
 635     TA_Point point;
 636     TA_Point point_limit = points + hints->num_points;
 637
 638
 639     /* compute coordinates & Bezier flags, next and prev */
 640     {
 641       FT_Vector* vec = outline->points;
 642       char* tag = outline->tags;
 643
 644       TA_Point end = points + outline->contours[0];
 645       TA_Point prev = end;
 646
 647       FT_Int contour_index = 0;
 648
 649
 650       for (point = points; point < point_limit; point++, vec++, tag++)
 651       {
 652         point->fx = (FT_Short)vec->x;
 653         point->fy = (FT_Short)vec->y;
 654         point->ox = point->x = FT_MulFix(vec->x, x_scale) + x_delta;
 655         point->oy = point->y = FT_MulFix(vec->y, y_scale) + y_delta;
 656
 657         switch (FT_CURVE_TAG(*tag))
 658         {
 659         case FT_CURVE_TAG_CONIC:
 660           point->flags = TA_FLAG_CONIC;
 661           break;
 662         case FT_CURVE_TAG_CUBIC:
 663           point->flags = TA_FLAG_CUBIC;
 664           break;
 665         default:
 666           point->flags = TA_FLAG_NONE;
 667         }
 668
 669         point->prev = prev;
 670         prev->next = point;
 671         prev = point;
 672
 673         if (point == end)
 674         {
 675           if (++contour_index < outline->n_contours)
 676           {
 677             end = points + outline->contours[contour_index];
 678             prev = end;
 679           }
 680         }
 681       }
 682     }
 683
 684     /* set up the contours array */
 685     {
 686       TA_Point* contour = hints->contours;
 687       TA_Point* contour_limit = contour + hints->num_contours;
 688
 689       short* end = outline->contours;
 690       short idx = 0;
 691
 692
 693       for (; contour < contour_limit; contour++, end++)
 694       {
 695         contour[0] = points + idx;
 696         idx = (short)(end[0] + 1);
 697       }
 698     }
 699
 700     /* compute directions of in & out vectors */
 701     {
 702       TA_Point first = points;
 703       TA_Point prev = NULL;
 704
 705       FT_Pos in_x = 0;
 706       FT_Pos in_y = 0;
 707
 708       TA_Direction in_dir = TA_DIR_NONE;
 709
 710
 711       for (point = points; point < point_limit; point++)
 712       {
 713         TA_Point next;
 714         FT_Pos out_x, out_y;
 715
 716
 717         if (point == first)
 718         {
 719           prev = first->prev;
 720           in_x = first->fx - prev->fx;
 721           in_y = first->fy - prev->fy;
 722           in_dir = ta_direction_compute(in_x, in_y);
 723           first = prev + 1;
 724         }
 725
 726         point->in_dir = (FT_Char)in_dir;
 727
 728         next = point->next;
 729         out_x = next->fx - point->fx;
 730         out_y = next->fy - point->fy;
 731
 732         in_dir = ta_direction_compute(out_x, out_y);
 733         point->out_dir = (FT_Char)in_dir;
 734
 735         /* check for weak points */
 736
 737         if (point->flags & TA_FLAG_CONTROL)
 738         {
 739         Is_Weak_Point:
 740           point->flags |= TA_FLAG_WEAK_INTERPOLATION;
 741         }
 742         else if (point->out_dir == point->in_dir)
 743         {
 744           if (point->out_dir != TA_DIR_NONE)
 745             goto Is_Weak_Point;
 746
 747           if (ta_corner_is_flat(in_x, in_y, out_x, out_y))
 748             goto Is_Weak_Point;
 749         }
 750         else if (point->in_dir == -point->out_dir)
 751           goto Is_Weak_Point;
 752
 753         in_x = out_x;
 754         in_y = out_y;
 755         prev = point;
 756       }
 757     }
 758   }
 759
 760 Exit:
 761   return error;
 762 }
 763
 764
 765 /* store the hinted outline in an FT_Outline structure */
 766
 767 void
 768 ta_glyph_hints_save(TA_GlyphHints hints,
 769                     FT_Outline* outline)
 770 {
 771   TA_Point point = hints->points;
 772   TA_Point limit = point + hints->num_points;
 773
 774   FT_Vector* vec = outline->points;
 775   char* tag = outline->tags;
 776
 777
 778   for (; point < limit; point++, vec++, tag++)
 779   {
 780     vec->x = point->x;
 781     vec->y = point->y;
 782
 783     if (point->flags & TA_FLAG_CONIC)
 784       tag[0] = FT_CURVE_TAG_CONIC;
 785     else if (point->flags & TA_FLAG_CUBIC)
 786       tag[0] = FT_CURVE_TAG_CUBIC;
 787     else
 788       tag[0] = FT_CURVE_TAG_ON;
 789   }
 790 }
 791
 792
 793 /****************************************************************
 794  *
 795  *                     EDGE POINT GRID-FITTING
 796  *
 797  ****************************************************************/
 798
 799
 800 /* align all points of an edge to the same coordinate value, */
 801 /* either horizontally or vertically */
 802
 803 void
 804 ta_glyph_hints_align_edge_points(TA_GlyphHints hints,
 805                                  TA_Dimension dim)
 806 {
 807   TA_AxisHints axis = &hints->axis[dim];
 808   TA_Segment segments = axis->segments;
 809   TA_Segment segment_limit = segments + axis->num_segments;
 810   TA_Segment seg;
 811
 812
 813   if (dim == TA_DIMENSION_HORZ)
 814   {
 815     for (seg = segments; seg < segment_limit; seg++)
 816     {
 817       TA_Edge edge = seg->edge;
 818       TA_Point point, first, last;
 819
 820
 821       if (edge == NULL)
 822         continue;
 823
 824       first = seg->first;
 825       last = seg->last;
 826       point = first;
 827       for (;;)
 828       {
 829         point->x = edge->pos;
 830         point->flags |= TA_FLAG_TOUCH_X;
 831
 832         if (point == last)
 833           break;
 834
 835         point = point->next;
 836       }
 837     }
 838   }
 839   else
 840   {
 841     for (seg = segments; seg < segment_limit; seg++)
 842     {
 843       TA_Edge edge = seg->edge;
 844       TA_Point point, first, last;
 845
 846
 847       if (edge == NULL)
 848         continue;
 849
 850       first = seg->first;
 851       last = seg->last;
 852       point = first;
 853       for (;;)
 854       {
 855         point->y = edge->pos;
 856         point->flags |= TA_FLAG_TOUCH_Y;
 857
 858         if (point == last)
 859           break;
 860
 861         point = point->next;
 862       }
 863     }
 864   }
 865 }
 866
 867
 868 /****************************************************************
 869  *
 870  *                    STRONG POINT INTERPOLATION
 871  *
 872  ****************************************************************/
 873
 874
 875 /* hint the strong points -- */
 876 /* this is equivalent to the TrueType `IP' hinting instruction */
 877
 878 void
 879 ta_glyph_hints_align_strong_points(TA_GlyphHints hints,
 880                                    TA_Dimension dim)
 881 {
 882   TA_Point points = hints->points;
 883   TA_Point point_limit = points + hints->num_points;
 884
 885   TA_AxisHints axis = &hints->axis[dim];
 886
 887   TA_Edge edges = axis->edges;
 888   TA_Edge edge_limit = edges + axis->num_edges;
 889
 890   FT_UShort touch_flag;
 891
 892
 893   if (dim == TA_DIMENSION_HORZ)
 894     touch_flag = TA_FLAG_TOUCH_X;
 895   else
 896     touch_flag = TA_FLAG_TOUCH_Y;
 897
 898   if (edges < edge_limit)
 899   {
 900     TA_Point point;
 901     TA_Edge edge;
 902
 903
 904     for (point = points; point < point_limit; point++)
 905     {
 906       FT_Pos u, ou, fu;  /* point position */
 907       FT_Pos delta;
 908
 909
 910       if (point->flags & touch_flag)
 911         continue;
 912
 913       /* if this point is candidate to weak interpolation, we */
 914       /* interpolate it after all strong points have been processed */
 915
 916       if ((point->flags & TA_FLAG_WEAK_INTERPOLATION)
 917           && !(point->flags & TA_FLAG_INFLECTION))
 918         continue;
 919
 920       if (dim == TA_DIMENSION_VERT)
 921       {
 922         u = point->fy;
 923         ou = point->oy;
 924       }
 925       else
 926       {
 927         u = point->fx;
 928         ou = point->ox;
 929       }
 930
 931       fu = u;
 932
 933       /* is the point before the first edge? */
 934       edge = edges;
 935       delta = edge->fpos - u;
 936       if (delta >= 0)
 937       {
 938         u = edge->pos - (edge->opos - ou);
 939
 940         if (hints->recorder)
 941           hints->recorder(ta_ip_before, hints, dim,
 942                           point, NULL, NULL, NULL, NULL);
 943
 944         goto Store_Point;
 945       }
 946
 947       /* is the point after the last edge? */
 948       edge = edge_limit - 1;
 949       delta = u - edge->fpos;
 950       if (delta >= 0)
 951       {
 952         u = edge->pos + (ou - edge->opos);
 953
 954         if (hints->recorder)
 955           hints->recorder(ta_ip_after, hints, dim,
 956                           point, NULL, NULL, NULL, NULL);
 957
 958         goto Store_Point;
 959       }
 960
 961       {
 962         FT_PtrDist min, max, mid;
 963         FT_Pos fpos;
 964
 965
 966         /* find enclosing edges */
 967         min = 0;
 968         max = edge_limit - edges;
 969
 970         /* for a small number of edges, a linear search is better */
 971         if (max <= 8)
 972         {
 973           FT_PtrDist nn;
 974
 975
 976           for (nn = 0; nn < max; nn++)
 977             if (edges[nn].fpos >= u)
 978               break;
 979
 980           if (edges[nn].fpos == u)
 981           {
 982             u = edges[nn].pos;
 983
 984             if (hints->recorder)
 985               hints->recorder(ta_ip_on, hints, dim,
 986                               point, &edges[nn], NULL, NULL, NULL);
 987
 988             goto Store_Point;
 989           }
 990           min = nn;
 991         }
 992         else
 993           while (min < max)
 994           {
 995             mid = (max + min) >> 1;
 996             edge = edges + mid;
 997             fpos = edge->fpos;
 998
 999             if (u < fpos)
1000               max = mid;
1001             else if (u > fpos)
1002               min = mid + 1;
1003             else
1004             {
1005               /* we are on the edge */
1006               u = edge->pos;
1007
1008               if (hints->recorder)
1009                 hints->recorder(ta_ip_on, hints, dim,
1010                                 point, edge, NULL, NULL, NULL);
1011
1012               goto Store_Point;
1013             }
1014           }
1015
1016         /* point is not on an edge */
1017         {
1018           TA_Edge before = edges + min - 1;
1019           TA_Edge after = edges + min + 0;
1020
1021
1022           /* assert(before && after && before != after) */
1023           if (before->scale == 0)
1024             before->scale = FT_DivFix(after->pos - before->pos,
1025                                       after->fpos - before->fpos);
1026
1027           u = before->pos + FT_MulFix(fu - before->fpos,
1028                                       before->scale);
1029
1030           if (hints->recorder)
1031             hints->recorder(ta_ip_between, hints, dim,
1032                             point, before, after, NULL, NULL);
1033         }
1034       }
1035
1036     Store_Point:
1037       /* save the point position */
1038       if (dim == TA_DIMENSION_HORZ)
1039         point->x = u;
1040       else
1041         point->y = u;
1042
1043       point->flags |= touch_flag;
1044     }
1045   }
1046 }
1047
1048
1049 /****************************************************************
1050  *
1051  *                    WEAK POINT INTERPOLATION
1052  *
1053  ****************************************************************/
1054
1055
1056 /* shift the original coordinates of all points between `p1' and */
1057 /* `p2' to get hinted coordinates, using the same difference as */
1058 /* given by `ref' */
1059
1060 static void
1061 ta_iup_shift(TA_Point p1,
1062              TA_Point p2,
1063              TA_Point ref)
1064 {
1065   TA_Point p;
1066   FT_Pos delta = ref->u - ref->v;
1067
1068
1069   if (delta == 0)
1070     return;
1071
1072   for (p = p1; p < ref; p++)
1073     p->u = p->v + delta;
1074
1075   for (p = ref + 1; p <= p2; p++)
1076     p->u = p->v + delta;
1077 }
1078
1079
1080 /* interpolate the original coordinates of all points between `p1' and */
1081 /* `p2' to get hinted coordinates, using `ref1' and `ref2' as the */
1082 /* reference points;  the `u' and `v' members are the current and */
1083 /* original coordinate values, respectively. */
1084
1085 /* details can be found in the TrueType bytecode specification */
1086
1087 static void
1088 ta_iup_interp(TA_Point p1,
1089               TA_Point p2,
1090               TA_Point ref1,
1091               TA_Point ref2)
1092 {
1093   TA_Point p;
1094   FT_Pos u;
1095   FT_Pos v1 = ref1->v;
1096   FT_Pos v2 = ref2->v;
1097   FT_Pos d1 = ref1->u - v1;
1098   FT_Pos d2 = ref2->u - v2;
1099
1100
1101   if (p1 > p2)
1102     return;
1103
1104   if (v1 == v2)
1105   {
1106     for (p = p1; p <= p2; p++)
1107     {
1108       u = p->v;
1109
1110       if (u <= v1)
1111         u += d1;
1112       else
1113         u += d2;
1114
1115       p->u = u;
1116     }
1117     return;
1118   }
1119
1120   if (v1 < v2)
1121   {
1122     for (p = p1; p <= p2; p++)
1123     {
1124       u = p->v;
1125
1126       if (u <= v1)
1127         u += d1;
1128       else if (u >= v2)
1129         u += d2;
1130       else
1131         u = ref1->u + FT_MulDiv(u - v1, ref2->u - ref1->u, v2 - v1);
1132
1133       p->u = u;
1134     }
1135   }
1136   else
1137   {
1138     for (p = p1; p <= p2; p++)
1139     {
1140       u = p->v;
1141
1142       if (u <= v2)
1143         u += d2;
1144       else if (u >= v1)
1145         u += d1;
1146       else
1147         u = ref1->u + FT_MulDiv(u - v1, ref2->u - ref1->u, v2 - v1);
1148
1149       p->u = u;
1150     }
1151   }
1152 }
1153
1154
1155 /* hint the weak points -- */
1156 /* this is equivalent to the TrueType `IUP' hinting instruction */
1157
1158 void
1159 ta_glyph_hints_align_weak_points(TA_GlyphHints hints,
1160                                  TA_Dimension dim)
1161 {
1162   TA_Point points = hints->points;
1163   TA_Point point_limit = points + hints->num_points;
1164
1165   TA_Point* contour = hints->contours;
1166   TA_Point* contour_limit = contour + hints->num_contours;
1167
1168   FT_UShort touch_flag;
1169   TA_Point point;
1170   TA_Point end_point;
1171   TA_Point first_point;
1172
1173
1174   /* pass 1: move segment points to edge positions */
1175
1176   if (dim == TA_DIMENSION_HORZ)
1177   {
1178     touch_flag = TA_FLAG_TOUCH_X;
1179
1180     for (point = points; point < point_limit; point++)
1181     {
1182       point->u = point->x;
1183       point->v = point->ox;
1184     }
1185   }
1186   else
1187   {
1188     touch_flag = TA_FLAG_TOUCH_Y;
1189
1190     for (point = points; point < point_limit; point++)
1191     {
1192       point->u = point->y;
1193       point->v = point->oy;
1194     }
1195   }
1196
1197   point = points;
1198
1199   for (; contour < contour_limit; contour++)
1200   {
1201     TA_Point first_touched, last_touched;
1202
1203
1204     point = *contour;
1205     end_point = point->prev;
1206     first_point = point;
1207
1208     /* find first touched point */
1209     for (;;)
1210     {
1211       if (point > end_point) /* no touched point in contour */
1212         goto NextContour;
1213
1214       if (point->flags & touch_flag)
1215         break;
1216
1217       point++;
1218     }
1219
1220     first_touched = point;
1221     last_touched = point;
1222
1223     for (;;)
1224     {
1225       /* skip any touched neighbours */
1226       while (point < end_point
1227              && (point[1].flags & touch_flag) != 0)
1228         point++;
1229
1230       last_touched = point;
1231
1232       /* find the next touched point, if any */
1233       point++;
1234       for (;;)
1235       {
1236         if (point > end_point)
1237           goto EndContour;
1238
1239         if ((point->flags & touch_flag) != 0)
1240           break;
1241
1242         point++;
1243       }
1244
1245       /* interpolate between last_touched and point */
1246       ta_iup_interp(last_touched + 1, point - 1,
1247                     last_touched, point);
1248     }
1249
1250   EndContour:
1251     /* special case: only one point was touched */
1252     if (last_touched == first_touched)
1253       ta_iup_shift(first_point, end_point, first_touched);
1254
1255     else /* interpolate the last part */
1256     {
1257       if (last_touched < end_point)
1258         ta_iup_interp(last_touched + 1, end_point,
1259                       last_touched, first_touched);
1260
1261       if (first_touched > points)
1262         ta_iup_interp(first_point, first_touched - 1,
1263                       last_touched, first_touched);
1264     }
1265
1266   NextContour:
1267     ;
1268   }
1269
1270   /* now save the interpolated values back to x/y */
1271   if (dim == TA_DIMENSION_HORZ)
1272   {
1273     for (point = points; point < point_limit; point++)
1274       point->x = point->u;
1275   }
1276   else
1277   {
1278     for (point = points; point < point_limit; point++)
1279       point->y = point->u;
1280   }
1281 }
1282
1283
1284 #ifdef TA_CONFIG_OPTION_USE_WARPER
1285
1286 /* apply (small) warp scale and warp delta for given dimension */
1287
1288 static void
1289 ta_glyph_hints_scale_dim(TA_GlyphHints hints,
1290                          TA_Dimension dim,
1291                          FT_Fixed scale,
1292                          FT_Pos delta)
1293 {
1294   TA_Point points = hints->points;
1295   TA_Point points_limit = points + hints->num_points;
1296   TA_Point point;
1297
1298
1299   if (dim == TA_DIMENSION_HORZ)
1300   {
1301     for (point = points; point < points_limit; point++)
1302       point->x = FT_MulFix(point->fx, scale) + delta;
1303   }
1304   else
1305   {
1306     for (point = points; point < points_limit; point++)
1307       point->y = FT_MulFix(point->fy, scale) + delta;
1308   }
1309 }
1310
1311 #endif /* TA_CONFIG_OPTION_USE_WARPER */
1312
1313 /* end of tahints.c */