1 /***************************************************************************/
5 /* Auto-fitter hinting routines (body). */
7 /* Copyright 2003-2007, 2009-2011 by */
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */
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. */
16 /***************************************************************************/
21 #include FT_INTERNAL_CALC_H
24 /* Get new segment for given axis. */
26 FT_LOCAL_DEF( FT_Error )
27 af_axis_hints_new_segment( AF_AxisHints axis,
29 AF_Segment *asegment )
31 FT_Error error = AF_Err_Ok;
32 AF_Segment segment = NULL;
35 if ( axis->num_segments >= axis->max_segments )
37 FT_Int old_max = axis->max_segments;
38 FT_Int new_max = old_max;
39 FT_Int big_max = (FT_Int)( FT_INT_MAX / sizeof ( *segment ) );
42 if ( old_max >= big_max )
44 error = AF_Err_Out_Of_Memory;
48 new_max += ( new_max >> 2 ) + 4;
49 if ( new_max < old_max || new_max > big_max )
52 if ( FT_RENEW_ARRAY( axis->segments, old_max, new_max ) )
55 axis->max_segments = new_max;
58 segment = axis->segments + axis->num_segments++;
66 /* Get new edge for given axis, direction, and position. */
69 af_axis_hints_new_edge( AF_AxisHints axis,
75 FT_Error error = AF_Err_Ok;
80 if ( axis->num_edges >= axis->max_edges )
82 FT_Int old_max = axis->max_edges;
83 FT_Int new_max = old_max;
84 FT_Int big_max = (FT_Int)( FT_INT_MAX / sizeof ( *edge ) );
87 if ( old_max >= big_max )
89 error = AF_Err_Out_Of_Memory;
93 new_max += ( new_max >> 2 ) + 4;
94 if ( new_max < old_max || new_max > big_max )
97 if ( FT_RENEW_ARRAY( axis->edges, old_max, new_max ) )
100 axis->max_edges = new_max;
104 edge = edges + axis->num_edges;
106 while ( edge > edges )
108 if ( edge[-1].fpos < fpos )
111 /* we want the edge with same position and minor direction */
112 /* to appear before those in the major one in the list */
113 if ( edge[-1].fpos == fpos && dir == axis->major_dir )
123 edge->fpos = (FT_Short)fpos;
124 edge->dir = (FT_Char)dir;
132 #ifdef FT_DEBUG_AUTOFIT
134 #include FT_CONFIG_STANDARD_LIBRARY_H
137 af_dir_str( AF_Direction dir )
164 #define AF_INDEX_NUM( ptr, base ) ( (ptr) ? ( (ptr) - (base) ) : -1 )
171 af_glyph_hints_dump_points( AF_GlyphHints hints )
173 AF_Point points = hints->points;
174 AF_Point limit = points + hints->num_points;
178 printf( "Table of points:\n" );
179 printf( " [ index | xorg | yorg | xscale | yscale"
180 " | xfit | yfit | flags ]\n" );
182 for ( point = points; point < limit; point++ )
184 printf( " [ %5d | %5d | %5d | %6.2f | %6.2f"
185 " | %5.2f | %5.2f | %c%c%c%c%c%c ]\n",
193 ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) ? 'w' : ' ',
194 ( point->flags & AF_FLAG_INFLECTION ) ? 'i' : ' ',
195 ( point->flags & AF_FLAG_EXTREMA_X ) ? '<' : ' ',
196 ( point->flags & AF_FLAG_EXTREMA_Y ) ? 'v' : ' ',
197 ( point->flags & AF_FLAG_ROUND_X ) ? '(' : ' ',
198 ( point->flags & AF_FLAG_ROUND_Y ) ? 'u' : ' ');
208 af_edge_flags_to_string( AF_Edge_Flags flags )
210 static char temp[32];
214 if ( flags & AF_EDGE_ROUND )
216 ft_memcpy( temp + pos, "round", 5 );
219 if ( flags & AF_EDGE_SERIF )
223 ft_memcpy( temp + pos, "serif", 5 );
235 /* Dump the array of linked segments. */
241 af_glyph_hints_dump_segments( AF_GlyphHints hints )
246 for ( dimension = 1; dimension >= 0; dimension-- )
248 AF_AxisHints axis = &hints->axis[dimension];
249 AF_Segment segments = axis->segments;
250 AF_Segment limit = segments + axis->num_segments;
254 printf ( "Table of %s segments:\n",
255 dimension == AF_DIMENSION_HORZ ? "vertical" : "horizontal" );
256 printf ( " [ index | pos | dir | link | serif |"
257 " height | extra | flags ]\n" );
259 for ( seg = segments; seg < limit; seg++ )
261 printf ( " [ %5d | %5.2g | %5s | %4d | %5d | %6d | %5d | %11s ]\n",
263 dimension == AF_DIMENSION_HORZ ? (int)seg->first->ox / 64.0
264 : (int)seg->first->oy / 64.0,
265 af_dir_str( (AF_Direction)seg->dir ),
266 AF_INDEX_NUM( seg->link, segments ),
267 AF_INDEX_NUM( seg->serif, segments ),
269 seg->height - ( seg->max_coord - seg->min_coord ),
270 af_edge_flags_to_string( (AF_Edge_Flags)seg->flags ) );
280 /* Fetch number of segments. */
286 af_glyph_hints_get_num_segments( AF_GlyphHints hints,
288 FT_Int* num_segments )
294 dim = ( dimension == 0 ) ? AF_DIMENSION_HORZ : AF_DIMENSION_VERT;
296 axis = &hints->axis[dim];
297 *num_segments = axis->num_segments;
306 /* Fetch offset of segments into user supplied offset array. */
312 af_glyph_hints_get_segment_offset( AF_GlyphHints hints,
323 return AF_Err_Invalid_Argument;
325 dim = ( dimension == 0 ) ? AF_DIMENSION_HORZ : AF_DIMENSION_VERT;
327 axis = &hints->axis[dim];
329 if ( idx < 0 || idx >= axis->num_segments )
330 return AF_Err_Invalid_Argument;
332 seg = &axis->segments[idx];
333 *offset = (dim == AF_DIMENSION_HORZ) ? seg->first->ox
343 /* Dump the array of linked edges. */
349 af_glyph_hints_dump_edges( AF_GlyphHints hints )
354 for ( dimension = 1; dimension >= 0; dimension-- )
356 AF_AxisHints axis = &hints->axis[dimension];
357 AF_Edge edges = axis->edges;
358 AF_Edge limit = edges + axis->num_edges;
363 * note: AF_DIMENSION_HORZ corresponds to _vertical_ edges
364 * since they have a constant X coordinate.
366 printf ( "Table of %s edges:\n",
367 dimension == AF_DIMENSION_HORZ ? "vertical" : "horizontal" );
368 printf ( " [ index | pos | dir | link |"
369 " serif | blue | opos | pos | flags ]\n" );
371 for ( edge = edges; edge < limit; edge++ )
373 printf ( " [ %5d | %5.2g | %5s | %4d |"
374 " %5d | %c | %5.2f | %5.2f | %11s ]\n",
376 (int)edge->opos / 64.0,
377 af_dir_str( (AF_Direction)edge->dir ),
378 AF_INDEX_NUM( edge->link, edges ),
379 AF_INDEX_NUM( edge->serif, edges ),
380 edge->blue_edge ? 'y' : 'n',
383 af_edge_flags_to_string( (AF_Edge_Flags)edge->flags ) );
392 #else /* !FT_DEBUG_AUTOFIT */
394 /* these empty stubs are only used to link the `ftgrid' test program */
395 /* if debugging is disabled */
402 af_glyph_hints_dump_points( AF_GlyphHints hints )
409 af_glyph_hints_dump_segments( AF_GlyphHints hints )
416 af_glyph_hints_get_num_segments( AF_GlyphHints hints,
418 FT_Int* num_segments )
421 FT_UNUSED( dimension );
422 FT_UNUSED( num_segments );
429 af_glyph_hints_get_segment_offset( AF_GlyphHints hints,
435 FT_UNUSED( dimension );
444 af_glyph_hints_dump_edges( AF_GlyphHints hints )
453 #endif /* !FT_DEBUG_AUTOFIT */
456 /* Compute the direction value of a given vector. */
458 FT_LOCAL_DEF( AF_Direction )
459 af_direction_compute( FT_Pos dx,
462 FT_Pos ll, ss; /* long and short arm lengths */
463 AF_Direction dir; /* candidate direction */
497 /* return no direction if arm lengths differ too much */
498 /* (value 14 is heuristic) */
500 if ( FT_ABS( ll ) <= FT_ABS( ss ) )
508 af_glyph_hints_init( AF_GlyphHints hints,
512 hints->memory = memory;
517 af_glyph_hints_done( AF_GlyphHints hints )
519 if ( hints && hints->memory )
521 FT_Memory memory = hints->memory;
526 * note that we don't need to free the segment and edge
527 * buffers since they are really within the hints->points array
529 for ( dim = 0; dim < AF_DIMENSION_MAX; dim++ )
531 AF_AxisHints axis = &hints->axis[dim];
534 axis->num_segments = 0;
535 axis->max_segments = 0;
536 FT_FREE( axis->segments );
540 FT_FREE( axis->edges );
543 FT_FREE( hints->contours );
544 hints->max_contours = 0;
545 hints->num_contours = 0;
547 FT_FREE( hints->points );
548 hints->num_points = 0;
549 hints->max_points = 0;
551 hints->memory = NULL;
559 af_glyph_hints_rescale( AF_GlyphHints hints,
560 AF_ScriptMetrics metrics )
562 hints->metrics = metrics;
563 hints->scaler_flags = metrics->scaler.flags;
567 /* Recompute all AF_Point in AF_GlyphHints from the definitions */
568 /* in a source outline. */
570 FT_LOCAL_DEF( FT_Error )
571 af_glyph_hints_reload( AF_GlyphHints hints,
572 FT_Outline* outline )
574 FT_Error error = AF_Err_Ok;
576 FT_UInt old_max, new_max;
577 FT_Fixed x_scale = hints->x_scale;
578 FT_Fixed y_scale = hints->y_scale;
579 FT_Pos x_delta = hints->x_delta;
580 FT_Pos y_delta = hints->y_delta;
581 FT_Memory memory = hints->memory;
584 hints->num_points = 0;
585 hints->num_contours = 0;
587 hints->axis[0].num_segments = 0;
588 hints->axis[0].num_edges = 0;
589 hints->axis[1].num_segments = 0;
590 hints->axis[1].num_edges = 0;
592 /* first of all, reallocate the contours array if necessary */
593 new_max = (FT_UInt)outline->n_contours;
594 old_max = hints->max_contours;
595 if ( new_max > old_max )
597 new_max = ( new_max + 3 ) & ~3; /* round up to a multiple of 4 */
599 if ( FT_RENEW_ARRAY( hints->contours, old_max, new_max ) )
602 hints->max_contours = new_max;
606 * then reallocate the points arrays if necessary --
607 * note that we reserve two additional point positions, used to
608 * hint metrics appropriately
610 new_max = (FT_UInt)( outline->n_points + 2 );
611 old_max = hints->max_points;
612 if ( new_max > old_max )
614 new_max = ( new_max + 2 + 7 ) & ~7; /* round up to a multiple of 8 */
616 if ( FT_RENEW_ARRAY( hints->points, old_max, new_max ) )
619 hints->max_points = new_max;
622 hints->num_points = outline->n_points;
623 hints->num_contours = outline->n_contours;
625 /* We can't rely on the value of `FT_Outline.flags' to know the fill */
626 /* direction used for a glyph, given that some fonts are broken (e.g., */
627 /* the Arphic ones). We thus recompute it each time we need to. */
629 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_UP;
630 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_LEFT;
632 if ( FT_Outline_Get_Orientation( outline ) == FT_ORIENTATION_POSTSCRIPT )
634 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_DOWN;
635 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_RIGHT;
638 hints->x_scale = x_scale;
639 hints->y_scale = y_scale;
640 hints->x_delta = x_delta;
641 hints->y_delta = y_delta;
643 hints->xmin_delta = 0;
644 hints->xmax_delta = 0;
646 points = hints->points;
647 if ( hints->num_points == 0 )
652 AF_Point point_limit = points + hints->num_points;
655 /* compute coordinates & Bezier flags, next and prev */
657 FT_Vector* vec = outline->points;
658 char* tag = outline->tags;
659 AF_Point end = points + outline->contours[0];
661 FT_Int contour_index = 0;
664 for ( point = points; point < point_limit; point++, vec++, tag++ )
666 point->fx = (FT_Short)vec->x;
667 point->fy = (FT_Short)vec->y;
668 point->ox = point->x = FT_MulFix( vec->x, x_scale ) + x_delta;
669 point->oy = point->y = FT_MulFix( vec->y, y_scale ) + y_delta;
671 switch ( FT_CURVE_TAG( *tag ) )
673 case FT_CURVE_TAG_CONIC:
674 point->flags = AF_FLAG_CONIC;
676 case FT_CURVE_TAG_CUBIC:
677 point->flags = AF_FLAG_CUBIC;
680 point->flags = AF_FLAG_NONE;
689 if ( ++contour_index < outline->n_contours )
691 end = points + outline->contours[contour_index];
698 /* set up the contours array */
700 AF_Point* contour = hints->contours;
701 AF_Point* contour_limit = contour + hints->num_contours;
702 short* end = outline->contours;
706 for ( ; contour < contour_limit; contour++, end++ )
708 contour[0] = points + idx;
709 idx = (short)( end[0] + 1 );
713 /* compute directions of in & out vectors */
715 AF_Point first = points;
716 AF_Point prev = NULL;
719 AF_Direction in_dir = AF_DIR_NONE;
722 for ( point = points; point < point_limit; point++ )
728 if ( point == first )
731 in_x = first->fx - prev->fx;
732 in_y = first->fy - prev->fy;
733 in_dir = af_direction_compute( in_x, in_y );
737 point->in_dir = (FT_Char)in_dir;
740 out_x = next->fx - point->fx;
741 out_y = next->fy - point->fy;
743 in_dir = af_direction_compute( out_x, out_y );
744 point->out_dir = (FT_Char)in_dir;
746 /* check for weak points */
748 if ( point->flags & ( AF_FLAG_CONIC | AF_FLAG_CUBIC ) )
751 point->flags |= AF_FLAG_WEAK_INTERPOLATION;
753 else if ( point->out_dir == point->in_dir )
755 if ( point->out_dir != AF_DIR_NONE )
758 if ( ft_corner_is_flat( in_x, in_y, out_x, out_y ) )
761 else if ( point->in_dir == -point->out_dir )
776 /* Store the hinted outline in an FT_Outline structure. */
779 af_glyph_hints_save( AF_GlyphHints hints,
780 FT_Outline* outline )
782 AF_Point point = hints->points;
783 AF_Point limit = point + hints->num_points;
784 FT_Vector* vec = outline->points;
785 char* tag = outline->tags;
788 for ( ; point < limit; point++, vec++, tag++ )
793 if ( point->flags & AF_FLAG_CONIC )
794 tag[0] = FT_CURVE_TAG_CONIC;
795 else if ( point->flags & AF_FLAG_CUBIC )
796 tag[0] = FT_CURVE_TAG_CUBIC;
798 tag[0] = FT_CURVE_TAG_ON;
803 /****************************************************************
805 * EDGE POINT GRID-FITTING
807 ****************************************************************/
810 /* Align all points of an edge to the same coordinate value, */
811 /* either horizontally or vertically. */
814 af_glyph_hints_align_edge_points( AF_GlyphHints hints,
817 AF_AxisHints axis = & hints->axis[dim];
818 AF_Segment segments = axis->segments;
819 AF_Segment segment_limit = segments + axis->num_segments;
823 if ( dim == AF_DIMENSION_HORZ )
825 for ( seg = segments; seg < segment_limit; seg++ )
827 AF_Edge edge = seg->edge;
828 AF_Point point, first, last;
839 point->x = edge->pos;
840 point->flags |= AF_FLAG_TOUCH_X;
851 for ( seg = segments; seg < segment_limit; seg++ )
853 AF_Edge edge = seg->edge;
854 AF_Point point, first, last;
865 point->y = edge->pos;
866 point->flags |= AF_FLAG_TOUCH_Y;
878 /****************************************************************
880 * STRONG POINT INTERPOLATION
882 ****************************************************************/
885 /* Hint the strong points -- this is equivalent to the TrueType `IP' */
886 /* hinting instruction. */
889 af_glyph_hints_align_strong_points( AF_GlyphHints hints,
892 AF_Point points = hints->points;
893 AF_Point point_limit = points + hints->num_points;
894 AF_AxisHints axis = &hints->axis[dim];
895 AF_Edge edges = axis->edges;
896 AF_Edge edge_limit = edges + axis->num_edges;
900 if ( dim == AF_DIMENSION_HORZ )
901 touch_flag = AF_FLAG_TOUCH_X;
903 touch_flag = AF_FLAG_TOUCH_Y;
905 if ( edges < edge_limit )
911 for ( point = points; point < point_limit; point++ )
913 FT_Pos u, ou, fu; /* point position */
917 if ( point->flags & touch_flag )
920 /* if this point is candidate to weak interpolation, we */
921 /* interpolate it after all strong points have been processed */
923 if ( ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) &&
924 !( point->flags & AF_FLAG_INFLECTION ) )
927 if ( dim == AF_DIMENSION_VERT )
940 /* is the point before the first edge? */
942 delta = edge->fpos - u;
945 u = edge->pos - ( edge->opos - ou );
949 /* is the point after the last edge? */
950 edge = edge_limit - 1;
951 delta = u - edge->fpos;
954 u = edge->pos + ( ou - edge->opos );
959 FT_PtrDist min, max, mid;
963 /* find enclosing edges */
965 max = edge_limit - edges;
968 /* for a small number of edges, a linear search is better */
974 for ( nn = 0; nn < max; nn++ )
975 if ( edges[nn].fpos >= u )
978 if ( edges[nn].fpos == u )
989 mid = ( max + min ) >> 1;
999 /* we are on the edge */
1005 /* point is not on an edge */
1007 AF_Edge before = edges + min - 1;
1008 AF_Edge after = edges + min + 0;
1011 /* assert( before && after && before != after ) */
1012 if ( before->scale == 0 )
1013 before->scale = FT_DivFix( after->pos - before->pos,
1014 after->fpos - before->fpos );
1016 u = before->pos + FT_MulFix( fu - before->fpos,
1022 /* save the point position */
1023 if ( dim == AF_DIMENSION_HORZ )
1028 point->flags |= touch_flag;
1034 /****************************************************************
1036 * WEAK POINT INTERPOLATION
1038 ****************************************************************/
1041 /* Shift the original coordinates of all points between `p1' and */
1042 /* `p2' to get hinted coordinates, using the same difference as */
1043 /* given by `ref'. */
1046 af_iup_shift( AF_Point p1,
1051 FT_Pos delta = ref->u - ref->v;
1057 for ( p = p1; p < ref; p++ )
1058 p->u = p->v + delta;
1060 for ( p = ref + 1; p <= p2; p++ )
1061 p->u = p->v + delta;
1065 /* Interpolate the original coordinates of all points between `p1' and */
1066 /* `p2' to get hinted coordinates, using `ref1' and `ref2' as the */
1067 /* reference points. The `u' and `v' members are the current and */
1068 /* original coordinate values, respectively. */
1070 /* Details can be found in the TrueType bytecode specification. */
1073 af_iup_interp( AF_Point p1,
1080 FT_Pos v1 = ref1->v;
1081 FT_Pos v2 = ref2->v;
1082 FT_Pos d1 = ref1->u - v1;
1083 FT_Pos d2 = ref2->u - v2;
1091 for ( p = p1; p <= p2; p++ )
1107 for ( p = p1; p <= p2; p++ )
1116 u = ref1->u + FT_MulDiv( u - v1, ref2->u - ref1->u, v2 - v1 );
1123 for ( p = p1; p <= p2; p++ )
1132 u = ref1->u + FT_MulDiv( u - v1, ref2->u - ref1->u, v2 - v1 );
1140 /* Hint the weak points -- this is equivalent to the TrueType `IUP' */
1141 /* hinting instruction. */
1143 FT_LOCAL_DEF( void )
1144 af_glyph_hints_align_weak_points( AF_GlyphHints hints,
1147 AF_Point points = hints->points;
1148 AF_Point point_limit = points + hints->num_points;
1149 AF_Point* contour = hints->contours;
1150 AF_Point* contour_limit = contour + hints->num_contours;
1151 AF_Flags touch_flag;
1154 AF_Point first_point;
1157 /* PASS 1: Move segment points to edge positions */
1159 if ( dim == AF_DIMENSION_HORZ )
1161 touch_flag = AF_FLAG_TOUCH_X;
1163 for ( point = points; point < point_limit; point++ )
1165 point->u = point->x;
1166 point->v = point->ox;
1171 touch_flag = AF_FLAG_TOUCH_Y;
1173 for ( point = points; point < point_limit; point++ )
1175 point->u = point->y;
1176 point->v = point->oy;
1182 for ( ; contour < contour_limit; contour++ )
1184 AF_Point first_touched, last_touched;
1188 end_point = point->prev;
1189 first_point = point;
1191 /* find first touched point */
1194 if ( point > end_point ) /* no touched point in contour */
1197 if ( point->flags & touch_flag )
1203 first_touched = point;
1204 last_touched = point;
1208 FT_ASSERT( point <= end_point &&
1209 ( point->flags & touch_flag ) != 0 );
1211 /* skip any touched neighbours */
1212 while ( point < end_point &&
1213 ( point[1].flags & touch_flag ) != 0 )
1216 last_touched = point;
1218 /* find the next touched point, if any */
1222 if ( point > end_point )
1225 if ( ( point->flags & touch_flag ) != 0 )
1231 /* interpolate between last_touched and point */
1232 af_iup_interp( last_touched + 1, point - 1,
1233 last_touched, point );
1237 /* special case: only one point was touched */
1238 if ( last_touched == first_touched )
1239 af_iup_shift( first_point, end_point, first_touched );
1241 else /* interpolate the last part */
1243 if ( last_touched < end_point )
1244 af_iup_interp( last_touched + 1, end_point,
1245 last_touched, first_touched );
1247 if ( first_touched > points )
1248 af_iup_interp( first_point, first_touched - 1,
1249 last_touched, first_touched );
1256 /* now save the interpolated values back to x/y */
1257 if ( dim == AF_DIMENSION_HORZ )
1259 for ( point = points; point < point_limit; point++ )
1260 point->x = point->u;
1264 for ( point = points; point < point_limit; point++ )
1265 point->y = point->u;
1270 #ifdef AF_CONFIG_OPTION_USE_WARPER
1272 /* Apply (small) warp scale and warp delta for given dimension. */
1274 FT_LOCAL_DEF( void )
1275 af_glyph_hints_scale_dim( AF_GlyphHints hints,
1280 AF_Point points = hints->points;
1281 AF_Point points_limit = points + hints->num_points;
1285 if ( dim == AF_DIMENSION_HORZ )
1287 for ( point = points; point < points_limit; point++ )
1288 point->x = FT_MulFix( point->fx, scale ) + delta;
1292 for ( point = points; point < points_limit; point++ )
1293 point->y = FT_MulFix( point->fy, scale ) + delta;
1297 #endif /* AF_CONFIG_OPTION_USE_WARPER */