src/autofit/afhints.h

   1 /****************************************************************************
   2  *
   3  * afhints.h
   4  *
   5  *   Auto-fitter hinting routines (specification).
   6  *
   7  * Copyright (C) 2003-2020 by
   8  * David Turner, Robert Wilhelm, and Werner Lemberg.
   9  *
  10  * This file is part of the FreeType project, and may only be used,
  11  * modified, and distributed under the terms of the FreeType project
  12  * license, LICENSE.TXT.  By continuing to use, modify, or distribute
  13  * this file you indicate that you have read the license and
  14  * understand and accept it fully.
  15  *
  16  */
  17
  18
  19 #ifndef AFHINTS_H_
  20 #define AFHINTS_H_
  21
  22 #include "aftypes.h"
  23
  24 #define xxAF_SORT_SEGMENTS
  25
  26 FT_BEGIN_HEADER
  27
  28   /*
  29    * The definition of outline glyph hints.  These are shared by all
  30    * writing system analysis routines (until now).
  31    */
  32
  33   typedef enum  AF_Dimension_
  34   {
  35     AF_DIMENSION_HORZ = 0,  /* x coordinates,                    */
  36                             /* i.e., vertical segments & edges   */
  37     AF_DIMENSION_VERT = 1,  /* y coordinates,                    */
  38                             /* i.e., horizontal segments & edges */
  39
  40     AF_DIMENSION_MAX  /* do not remove */
  41
  42   } AF_Dimension;
  43
  44
  45   /* hint directions -- the values are computed so that two vectors are */
  46   /* in opposite directions iff `dir1 + dir2 == 0'                      */
  47   typedef enum  AF_Direction_
  48   {
  49     AF_DIR_NONE  =  4,
  50     AF_DIR_RIGHT =  1,
  51     AF_DIR_LEFT  = -1,
  52     AF_DIR_UP    =  2,
  53     AF_DIR_DOWN  = -2
  54
  55   } AF_Direction;
  56
  57
  58   /*
  59    * The following explanations are mostly taken from the article
  60    *
  61    *   Real-Time Grid Fitting of Typographic Outlines
  62    *
  63    * by David Turner and Werner Lemberg
  64    *
  65    *   https://www.tug.org/TUGboat/Articles/tb24-3/lemberg.pdf
  66    *
  67    * with appropriate updates.
  68    *
  69    *
  70    * Segments
  71    *
  72    *   `af_{cjk,latin,...}_hints_compute_segments' are the functions to
  73    *   find segments in an outline.
  74    *
  75    *   A segment is a series of at least two consecutive points that are
  76    *   approximately aligned along a coordinate axis.  The analysis to do
  77    *   so is specific to a writing system.
  78    *
  79    *
  80    * Edges
  81    *
  82    *   `af_{cjk,latin,...}_hints_compute_edges' are the functions to find
  83    *   edges.
  84    *
  85    *   As soon as segments are defined, the auto-hinter groups them into
  86    *   edges.  An edge corresponds to a single position on the main
  87    *   dimension that collects one or more segments (allowing for a small
  88    *   threshold).
  89    *
  90    *   As an example, the `latin' writing system first tries to grid-fit
  91    *   edges, then to align segments on the edges unless it detects that
  92    *   they form a serif.
  93    *
  94    *
  95    *                     A          H
  96    *                      |        |
  97    *                      |        |
  98    *                      |        |
  99    *                      |        |
 100    *        C             |        |             F
 101    *         +------<-----+        +-----<------+
 102    *         |             B      G             |
 103    *         |                                  |
 104    *         |                                  |
 105    *         +--------------->------------------+
 106    *        D                                    E
 107    *
 108    *
 109    * Stems
 110    *
 111    *   Stems are detected by `af_{cjk,latin,...}_hint_edges'.
 112    *
 113    *   Segments need to be `linked' to other ones in order to detect stems.
 114    *   A stem is made of two segments that face each other in opposite
 115    *   directions and that are sufficiently close to each other.  Using
 116    *   vocabulary from the TrueType specification, stem segments form a
 117    *   `black distance'.
 118    *
 119    *   In the above ASCII drawing, the horizontal segments are BC, DE, and
 120    *   FG; the vertical segments are AB, CD, EF, and GH.
 121    *
 122    *   Each segment has at most one `best' candidate to form a black
 123    *   distance, or no candidate at all.  Notice that two distinct segments
 124    *   can have the same candidate, which frequently means a serif.
 125    *
 126    *   A stem is recognized by the following condition:
 127    *
 128    *     best segment_1 = segment_2 && best segment_2 = segment_1
 129    *
 130    *   The best candidate is stored in field `link' in structure
 131    *   `AF_Segment'.
 132    *
 133    *   In the above ASCII drawing, the best candidate for both AB and CD is
 134    *   GH, while the best candidate for GH is AB.  Similarly, the best
 135    *   candidate for EF and GH is AB, while the best candidate for AB is
 136    *   GH.
 137    *
 138    *   The detection and handling of stems is dependent on the writing
 139    *   system.
 140    *
 141    *
 142    * Serifs
 143    *
 144    *   Serifs are detected by `af_{cjk,latin,...}_hint_edges'.
 145    *
 146    *   In comparison to a stem, a serif (as handled by the auto-hinter
 147    *   module that takes care of the `latin' writing system) has
 148    *
 149    *     best segment_1 = segment_2 && best segment_2 != segment_1
 150    *
 151    *   where segment_1 corresponds to the serif segment (CD and EF in the
 152    *   above ASCII drawing).
 153    *
 154    *   The best candidate is stored in field `serif' in structure
 155    *   `AF_Segment' (and `link' is set to NULL).
 156    *
 157    *
 158    * Touched points
 159    *
 160    *   A point is called `touched' if it has been processed somehow by the
 161    *   auto-hinter.  It basically means that it shouldn't be moved again
 162    *   (or moved only under certain constraints to preserve the already
 163    *   applied processing).
 164    *
 165    *
 166    * Flat and round segments
 167    *
 168    *   Segments are `round' or `flat', depending on the series of points
 169    *   that define them.  A segment is round if the next and previous point
 170    *   of an extremum (which can be either a single point or sequence of
 171    *   points) are both conic or cubic control points.  Otherwise, a
 172    *   segment with an extremum is flat.
 173    *
 174    *
 175    * Strong Points
 176    *
 177    *   Experience has shown that points not part of an edge need to be
 178    *   interpolated linearly between their two closest edges, even if these
 179    *   are not part of the contour of those particular points.  Typical
 180    *   candidates for this are
 181    *
 182    *   - angle points (i.e., points where the `in' and `out' direction
 183    *     differ greatly)
 184    *
 185    *   - inflection points (i.e., where the `in' and `out' angles are the
 186    *     same, but the curvature changes sign) [currently, such points
 187    *     aren't handled specially in the auto-hinter]
 188    *
 189    *   `af_glyph_hints_align_strong_points' is the function that takes
 190    *   care of such situations; it is equivalent to the TrueType `IP'
 191    *   hinting instruction.
 192    *
 193    *
 194    * Weak Points
 195    *
 196    *   Other points in the outline must be interpolated using the
 197    *   coordinates of their previous and next unfitted contour neighbours.
 198    *   These are called `weak points' and are touched by the function
 199    *   `af_glyph_hints_align_weak_points', equivalent to the TrueType `IUP'
 200    *   hinting instruction.  Typical candidates are control points and
 201    *   points on the contour without a major direction.
 202    *
 203    *   The major effect is to reduce possible distortion caused by
 204    *   alignment of edges and strong points, thus weak points are processed
 205    *   after strong points.
 206    */
 207
 208
 209   /* point hint flags */
 210 #define AF_FLAG_NONE  0
 211
 212   /* point type flags */
 213 #define AF_FLAG_CONIC    ( 1U << 0 )
 214 #define AF_FLAG_CUBIC    ( 1U << 1 )
 215 #define AF_FLAG_CONTROL  ( AF_FLAG_CONIC | AF_FLAG_CUBIC )
 216
 217   /* point touch flags */
 218 #define AF_FLAG_TOUCH_X  ( 1U << 2 )
 219 #define AF_FLAG_TOUCH_Y  ( 1U << 3 )
 220
 221   /* candidates for weak interpolation have this flag set */
 222 #define AF_FLAG_WEAK_INTERPOLATION  ( 1U << 4 )
 223
 224   /* the distance to the next point is very small */
 225 #define AF_FLAG_NEAR  ( 1U << 5 )
 226
 227
 228   /* edge hint flags */
 229 #define AF_EDGE_NORMAL  0
 230 #define AF_EDGE_ROUND    ( 1U << 0 )
 231 #define AF_EDGE_SERIF    ( 1U << 1 )
 232 #define AF_EDGE_DONE     ( 1U << 2 )
 233 #define AF_EDGE_NEUTRAL  ( 1U << 3 ) /* edge aligns to a neutral blue zone */
 234
 235
 236   typedef struct AF_PointRec_*    AF_Point;
 237   typedef struct AF_SegmentRec_*  AF_Segment;
 238   typedef struct AF_EdgeRec_*     AF_Edge;
 239
 240
 241   typedef struct  AF_PointRec_
 242   {
 243     FT_UShort  flags;    /* point flags used by hinter   */
 244     FT_Char    in_dir;   /* direction of inwards vector  */
 245     FT_Char    out_dir;  /* direction of outwards vector */
 246
 247     FT_Pos     ox, oy;   /* original, scaled position                   */
 248     FT_Short   fx, fy;   /* original, unscaled position (in font units) */
 249     FT_Pos     x, y;     /* current position                            */
 250     FT_Pos     u, v;     /* current (x,y) or (y,x) depending on context */
 251
 252     AF_Point   next;     /* next point in contour     */
 253     AF_Point   prev;     /* previous point in contour */
 254
 255 #ifdef FT_DEBUG_AUTOFIT
 256     /* track `before' and `after' edges for strong points */
 257     AF_Edge    before[2];
 258     AF_Edge    after[2];
 259 #endif
 260
 261   } AF_PointRec;
 262
 263
 264   typedef struct  AF_SegmentRec_
 265   {
 266     FT_Byte     flags;       /* edge/segment flags for this segment */
 267     FT_Char     dir;         /* segment direction                   */
 268     FT_Short    pos;         /* position of segment                 */
 269     FT_Short    delta;       /* deviation from segment position     */
 270     FT_Short    min_coord;   /* minimum coordinate of segment       */
 271     FT_Short    max_coord;   /* maximum coordinate of segment       */
 272     FT_Short    height;      /* the hinted segment height           */
 273
 274     AF_Edge     edge;        /* the segment's parent edge           */
 275     AF_Segment  edge_next;   /* link to next segment in parent edge */
 276
 277     AF_Segment  link;        /* (stem) link segment        */
 278     AF_Segment  serif;       /* primary segment for serifs */
 279     FT_Pos      score;       /* used during stem matching  */
 280     FT_Pos      len;         /* used during stem matching  */
 281
 282     AF_Point    first;       /* first point in edge segment */
 283     AF_Point    last;        /* last point in edge segment  */
 284
 285   } AF_SegmentRec;
 286
 287
 288   typedef struct  AF_EdgeRec_
 289   {
 290     FT_Short    fpos;       /* original, unscaled position (in font units) */
 291     FT_Pos      opos;       /* original, scaled position                   */
 292     FT_Pos      pos;        /* current position                            */
 293
 294     FT_Byte     flags;      /* edge flags                                   */
 295     FT_Char     dir;        /* edge direction                               */
 296     FT_Fixed    scale;      /* used to speed up interpolation between edges */
 297
 298     AF_Width    blue_edge;  /* non-NULL if this is a blue edge */
 299     AF_Edge     link;       /* link edge                       */
 300     AF_Edge     serif;      /* primary edge for serifs         */
 301     FT_Int      score;      /* used during stem matching       */
 302
 303     AF_Segment  first;      /* first segment in edge */
 304     AF_Segment  last;       /* last segment in edge  */
 305
 306   } AF_EdgeRec;
 307
 308 #define AF_SEGMENTS_EMBEDDED  18   /* number of embedded segments   */
 309 #define AF_EDGES_EMBEDDED     12   /* number of embedded edges      */
 310
 311   typedef struct  AF_AxisHintsRec_
 312   {
 313     FT_Int        num_segments; /* number of used segments      */
 314     FT_Int        max_segments; /* number of allocated segments */
 315     AF_Segment    segments;     /* segments array               */
 316 #ifdef AF_SORT_SEGMENTS
 317     FT_Int        mid_segments;
 318 #endif
 319
 320     FT_Int        num_edges;    /* number of used edges      */
 321     FT_Int        max_edges;    /* number of allocated edges */
 322     AF_Edge       edges;        /* edges array               */
 323
 324     AF_Direction  major_dir;    /* either vertical or horizontal */
 325
 326     /* two arrays to avoid allocation penalty */
 327     struct
 328     {
 329       AF_SegmentRec  segments[AF_SEGMENTS_EMBEDDED];
 330       AF_EdgeRec     edges[AF_EDGES_EMBEDDED];
 331     } embedded;
 332
 333
 334   } AF_AxisHintsRec, *AF_AxisHints;
 335
 336
 337 #define AF_POINTS_EMBEDDED     96   /* number of embedded points   */
 338 #define AF_CONTOURS_EMBEDDED    8   /* number of embedded contours */
 339
 340   typedef struct  AF_GlyphHintsRec_
 341   {
 342     FT_Memory        memory;
 343
 344     FT_Fixed         x_scale;
 345     FT_Pos           x_delta;
 346
 347     FT_Fixed         y_scale;
 348     FT_Pos           y_delta;
 349
 350     FT_Int           max_points;    /* number of allocated points */
 351     FT_Int           num_points;    /* number of used points      */
 352     AF_Point         points;        /* points array               */
 353
 354     FT_Int           max_contours;  /* number of allocated contours */
 355     FT_Int           num_contours;  /* number of used contours      */
 356     AF_Point*        contours;      /* contours array               */
 357
 358     AF_AxisHintsRec  axis[AF_DIMENSION_MAX];
 359
 360     FT_UInt32        scaler_flags;  /* copy of scaler flags    */
 361     FT_UInt32        other_flags;   /* free for style-specific */
 362                                     /* implementations         */
 363     AF_StyleMetrics  metrics;
 364
 365     FT_Pos           xmin_delta;    /* used for warping */
 366     FT_Pos           xmax_delta;
 367
 368     /* Two arrays to avoid allocation penalty.            */
 369     /* The `embedded' structure must be the last element! */
 370     struct
 371     {
 372       AF_Point       contours[AF_CONTOURS_EMBEDDED];
 373       AF_PointRec    points[AF_POINTS_EMBEDDED];
 374     } embedded;
 375
 376   } AF_GlyphHintsRec;
 377
 378
 379 #define AF_HINTS_TEST_SCALER( h, f )  ( (h)->scaler_flags & (f) )
 380 #define AF_HINTS_TEST_OTHER( h, f )   ( (h)->other_flags  & (f) )
 381
 382
 383 #ifdef FT_DEBUG_AUTOFIT
 384
 385 #define AF_HINTS_DO_HORIZONTAL( h )                                     \
 386           ( !_af_debug_disable_horz_hints                            && \
 387             !AF_HINTS_TEST_SCALER( h, AF_SCALER_FLAG_NO_HORIZONTAL ) )
 388
 389 #define AF_HINTS_DO_VERTICAL( h )                                     \
 390           ( !_af_debug_disable_vert_hints                          && \
 391             !AF_HINTS_TEST_SCALER( h, AF_SCALER_FLAG_NO_VERTICAL ) )
 392
 393 #define AF_HINTS_DO_BLUES( h )  ( !_af_debug_disable_blue_hints )
 394
 395 #else /* !FT_DEBUG_AUTOFIT */
 396
 397 #define AF_HINTS_DO_HORIZONTAL( h )                                \
 398           !AF_HINTS_TEST_SCALER( h, AF_SCALER_FLAG_NO_HORIZONTAL )
 399
 400 #define AF_HINTS_DO_VERTICAL( h )                                \
 401           !AF_HINTS_TEST_SCALER( h, AF_SCALER_FLAG_NO_VERTICAL )
 402
 403 #define AF_HINTS_DO_BLUES( h )  1
 404
 405 #endif /* !FT_DEBUG_AUTOFIT */
 406
 407
 408 #define AF_HINTS_DO_ADVANCE( h )                                \
 409           !AF_HINTS_TEST_SCALER( h, AF_SCALER_FLAG_NO_ADVANCE )
 410
 411 #define AF_HINTS_DO_WARP( h )                                  \
 412           !AF_HINTS_TEST_SCALER( h, AF_SCALER_FLAG_NO_WARPER )
 413
 414
 415
 416   FT_LOCAL( AF_Direction )
 417   af_direction_compute( FT_Pos  dx,
 418                         FT_Pos  dy );
 419
 420
 421   FT_LOCAL( FT_Error )
 422   af_axis_hints_new_segment( AF_AxisHints  axis,
 423                              FT_Memory     memory,
 424                              AF_Segment   *asegment );
 425
 426   FT_LOCAL( FT_Error)
 427   af_axis_hints_new_edge( AF_AxisHints  axis,
 428                           FT_Int        fpos,
 429                           AF_Direction  dir,
 430                           FT_Bool       top_to_bottom_hinting,
 431                           FT_Memory     memory,
 432                           AF_Edge      *edge );
 433
 434   FT_LOCAL( void )
 435   af_glyph_hints_init( AF_GlyphHints  hints,
 436                        FT_Memory      memory );
 437
 438   FT_LOCAL( void )
 439   af_glyph_hints_rescale( AF_GlyphHints    hints,
 440                           AF_StyleMetrics  metrics );
 441
 442   FT_LOCAL( FT_Error )
 443   af_glyph_hints_reload( AF_GlyphHints  hints,
 444                          FT_Outline*    outline );
 445
 446   FT_LOCAL( void )
 447   af_glyph_hints_save( AF_GlyphHints  hints,
 448                        FT_Outline*    outline );
 449
 450   FT_LOCAL( void )
 451   af_glyph_hints_align_edge_points( AF_GlyphHints  hints,
 452                                     AF_Dimension   dim );
 453
 454   FT_LOCAL( void )
 455   af_glyph_hints_align_strong_points( AF_GlyphHints  hints,
 456                                       AF_Dimension   dim );
 457
 458   FT_LOCAL( void )
 459   af_glyph_hints_align_weak_points( AF_GlyphHints  hints,
 460                                     AF_Dimension   dim );
 461
 462 #ifdef AF_CONFIG_OPTION_USE_WARPER
 463   FT_LOCAL( void )
 464   af_glyph_hints_scale_dim( AF_GlyphHints  hints,
 465                             AF_Dimension   dim,
 466                             FT_Fixed       scale,
 467                             FT_Pos         delta );
 468 #endif
 469
 470   FT_LOCAL( void )
 471   af_glyph_hints_done( AF_GlyphHints  hints );
 472
 473 /* */
 474
 475 #define AF_SEGMENT_LEN( seg )          ( (seg)->max_coord - (seg)->min_coord )
 476
 477 #define AF_SEGMENT_DIST( seg1, seg2 )  ( ( (seg1)->pos > (seg2)->pos )   \
 478                                            ? (seg1)->pos - (seg2)->pos   \
 479                                            : (seg2)->pos - (seg1)->pos )
 480
 481
 482 FT_END_HEADER
 483
 484 #endif /* AFHINTS_H_ */
 485
 486
 487 /* END */