Home | History | Annotate | Download | only in autofit
      1 /****************************************************************************
      2  *
      3  * afhints.h
      4  *
      5  *   Auto-fitter hinting routines (specification).
      6  *
      7  * Copyright 2003-2018 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   } AF_PointRec;
    256 
    257 
    258   typedef struct  AF_SegmentRec_
    259   {
    260     FT_Byte     flags;       /* edge/segment flags for this segment */
    261     FT_Char     dir;         /* segment direction                   */
    262     FT_Short    pos;         /* position of segment                 */
    263     FT_Short    delta;       /* deviation from segment position     */
    264     FT_Short    min_coord;   /* minimum coordinate of segment       */
    265     FT_Short    max_coord;   /* maximum coordinate of segment       */
    266     FT_Short    height;      /* the hinted segment height           */
    267 
    268     AF_Edge     edge;        /* the segment's parent edge           */
    269     AF_Segment  edge_next;   /* link to next segment in parent edge */
    270 
    271     AF_Segment  link;        /* (stem) link segment        */
    272     AF_Segment  serif;       /* primary segment for serifs */
    273     FT_Pos      score;       /* used during stem matching  */
    274     FT_Pos      len;         /* used during stem matching  */
    275 
    276     AF_Point    first;       /* first point in edge segment */
    277     AF_Point    last;        /* last point in edge segment  */
    278 
    279   } AF_SegmentRec;
    280 
    281 
    282   typedef struct  AF_EdgeRec_
    283   {
    284     FT_Short    fpos;       /* original, unscaled position (in font units) */
    285     FT_Pos      opos;       /* original, scaled position                   */
    286     FT_Pos      pos;        /* current position                            */
    287 
    288     FT_Byte     flags;      /* edge flags                                   */
    289     FT_Char     dir;        /* edge direction                               */
    290     FT_Fixed    scale;      /* used to speed up interpolation between edges */
    291 
    292     AF_Width    blue_edge;  /* non-NULL if this is a blue edge */
    293     AF_Edge     link;       /* link edge                       */
    294     AF_Edge     serif;      /* primary edge for serifs         */
    295     FT_Int      score;      /* used during stem matching       */
    296 
    297     AF_Segment  first;      /* first segment in edge */
    298     AF_Segment  last;       /* last segment in edge  */
    299 
    300   } AF_EdgeRec;
    301 
    302 #define AF_SEGMENTS_EMBEDDED  18   /* number of embedded segments   */
    303 #define AF_EDGES_EMBEDDED     12   /* number of embedded edges      */
    304 
    305   typedef struct  AF_AxisHintsRec_
    306   {
    307     FT_Int        num_segments; /* number of used segments      */
    308     FT_Int        max_segments; /* number of allocated segments */
    309     AF_Segment    segments;     /* segments array               */
    310 #ifdef AF_SORT_SEGMENTS
    311     FT_Int        mid_segments;
    312 #endif
    313 
    314     FT_Int        num_edges;    /* number of used edges      */
    315     FT_Int        max_edges;    /* number of allocated edges */
    316     AF_Edge       edges;        /* edges array               */
    317 
    318     AF_Direction  major_dir;    /* either vertical or horizontal */
    319 
    320     /* two arrays to avoid allocation penalty */
    321     struct
    322     {
    323       AF_SegmentRec  segments[AF_SEGMENTS_EMBEDDED];
    324       AF_EdgeRec     edges[AF_EDGES_EMBEDDED];
    325     } embedded;
    326 
    327 
    328   } AF_AxisHintsRec, *AF_AxisHints;
    329 
    330 
    331 #define AF_POINTS_EMBEDDED     96   /* number of embedded points   */
    332 #define AF_CONTOURS_EMBEDDED    8   /* number of embedded contours */
    333 
    334   typedef struct  AF_GlyphHintsRec_
    335   {
    336     FT_Memory        memory;
    337 
    338     FT_Fixed         x_scale;
    339     FT_Pos           x_delta;
    340 
    341     FT_Fixed         y_scale;
    342     FT_Pos           y_delta;
    343 
    344     FT_Int           max_points;    /* number of allocated points */
    345     FT_Int           num_points;    /* number of used points      */
    346     AF_Point         points;        /* points array               */
    347 
    348     FT_Int           max_contours;  /* number of allocated contours */
    349     FT_Int           num_contours;  /* number of used contours      */
    350     AF_Point*        contours;      /* contours array               */
    351 
    352     AF_AxisHintsRec  axis[AF_DIMENSION_MAX];
    353 
    354     FT_UInt32        scaler_flags;  /* copy of scaler flags    */
    355     FT_UInt32        other_flags;   /* free for style-specific */
    356                                     /* implementations         */
    357     AF_StyleMetrics  metrics;
    358 
    359     FT_Pos           xmin_delta;    /* used for warping */
    360     FT_Pos           xmax_delta;
    361 
    362     /* Two arrays to avoid allocation penalty.            */
    363     /* The `embedded' structure must be the last element! */
    364     struct
    365     {
    366       AF_Point       contours[AF_CONTOURS_EMBEDDED];
    367       AF_PointRec    points[AF_POINTS_EMBEDDED];
    368     } embedded;
    369 
    370   } AF_GlyphHintsRec;
    371 
    372 
    373 #define AF_HINTS_TEST_SCALER( h, f )  ( (h)->scaler_flags & (f) )
    374 #define AF_HINTS_TEST_OTHER( h, f )   ( (h)->other_flags  & (f) )
    375 
    376 
    377 #ifdef FT_DEBUG_AUTOFIT
    378 
    379 #define AF_HINTS_DO_HORIZONTAL( h )                                     \
    380           ( !_af_debug_disable_horz_hints                            && \
    381             !AF_HINTS_TEST_SCALER( h, AF_SCALER_FLAG_NO_HORIZONTAL ) )
    382 
    383 #define AF_HINTS_DO_VERTICAL( h )                                     \
    384           ( !_af_debug_disable_vert_hints                          && \
    385             !AF_HINTS_TEST_SCALER( h, AF_SCALER_FLAG_NO_VERTICAL ) )
    386 
    387 #define AF_HINTS_DO_BLUES( h )  ( !_af_debug_disable_blue_hints )
    388 
    389 #else /* !FT_DEBUG_AUTOFIT */
    390 
    391 #define AF_HINTS_DO_HORIZONTAL( h )                                \
    392           !AF_HINTS_TEST_SCALER( h, AF_SCALER_FLAG_NO_HORIZONTAL )
    393 
    394 #define AF_HINTS_DO_VERTICAL( h )                                \
    395           !AF_HINTS_TEST_SCALER( h, AF_SCALER_FLAG_NO_VERTICAL )
    396 
    397 #define AF_HINTS_DO_BLUES( h )  1
    398 
    399 #endif /* !FT_DEBUG_AUTOFIT */
    400 
    401 
    402 #define AF_HINTS_DO_ADVANCE( h )                                \
    403           !AF_HINTS_TEST_SCALER( h, AF_SCALER_FLAG_NO_ADVANCE )
    404 
    405 #define AF_HINTS_DO_WARP( h )                                  \
    406           !AF_HINTS_TEST_SCALER( h, AF_SCALER_FLAG_NO_WARPER )
    407 
    408 
    409 
    410   FT_LOCAL( AF_Direction )
    411   af_direction_compute( FT_Pos  dx,
    412                         FT_Pos  dy );
    413 
    414 
    415   FT_LOCAL( FT_Error )
    416   af_axis_hints_new_segment( AF_AxisHints  axis,
    417                              FT_Memory     memory,
    418                              AF_Segment   *asegment );
    419 
    420   FT_LOCAL( FT_Error)
    421   af_axis_hints_new_edge( AF_AxisHints  axis,
    422                           FT_Int        fpos,
    423                           AF_Direction  dir,
    424                           FT_Bool       top_to_bottom_hinting,
    425                           FT_Memory     memory,
    426                           AF_Edge      *edge );
    427 
    428   FT_LOCAL( void )
    429   af_glyph_hints_init( AF_GlyphHints  hints,
    430                        FT_Memory      memory );
    431 
    432   FT_LOCAL( void )
    433   af_glyph_hints_rescale( AF_GlyphHints    hints,
    434                           AF_StyleMetrics  metrics );
    435 
    436   FT_LOCAL( FT_Error )
    437   af_glyph_hints_reload( AF_GlyphHints  hints,
    438                          FT_Outline*    outline );
    439 
    440   FT_LOCAL( void )
    441   af_glyph_hints_save( AF_GlyphHints  hints,
    442                        FT_Outline*    outline );
    443 
    444   FT_LOCAL( void )
    445   af_glyph_hints_align_edge_points( AF_GlyphHints  hints,
    446                                     AF_Dimension   dim );
    447 
    448   FT_LOCAL( void )
    449   af_glyph_hints_align_strong_points( AF_GlyphHints  hints,
    450                                       AF_Dimension   dim );
    451 
    452   FT_LOCAL( void )
    453   af_glyph_hints_align_weak_points( AF_GlyphHints  hints,
    454                                     AF_Dimension   dim );
    455 
    456 #ifdef AF_CONFIG_OPTION_USE_WARPER
    457   FT_LOCAL( void )
    458   af_glyph_hints_scale_dim( AF_GlyphHints  hints,
    459                             AF_Dimension   dim,
    460                             FT_Fixed       scale,
    461                             FT_Pos         delta );
    462 #endif
    463 
    464   FT_LOCAL( void )
    465   af_glyph_hints_done( AF_GlyphHints  hints );
    466 
    467 /* */
    468 
    469 #define AF_SEGMENT_LEN( seg )          ( (seg)->max_coord - (seg)->min_coord )
    470 
    471 #define AF_SEGMENT_DIST( seg1, seg2 )  ( ( (seg1)->pos > (seg2)->pos )   \
    472                                            ? (seg1)->pos - (seg2)->pos   \
    473                                            : (seg2)->pos - (seg1)->pos )
    474 
    475 
    476 FT_END_HEADER
    477 
    478 #endif /* AFHINTS_H_ */
    479 
    480 
    481 /* END */
    482