1 /****************************************************************************
5 * Auto-fitter hinting routines (body).
7 * Copyright (C) 2003-2023 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.
21 #include <freetype/internal/ftcalc.h>
22 #include <freetype/internal/ftdebug.h>
25 /**************************************************************************
27 * The macro FT_COMPONENT is used in trace mode. It is an implicit
28 * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log
29 * messages during execution.
32 #define FT_COMPONENT afhints
36 af_sort_pos( FT_UInt count,
43 for ( i = 1; i < count; i++ )
45 for ( j = i; j > 0; j-- )
47 if ( table[j] >= table[j - 1] )
51 table[j] = table[j - 1];
59 af_sort_and_quantize_widths( FT_UInt* count,
74 for ( i = 1; i < *count; i++ )
76 for ( j = i; j > 0; j-- )
78 if ( table[j].org >= table[j - 1].org )
82 table[j] = table[j - 1];
88 cur_val = table[cur_idx].org;
90 /* compute and use mean values for clusters not larger than */
91 /* `threshold'; this is very primitive and might not yield */
92 /* the best result, but normally, using reference character */
93 /* `o', `*count' is 2, so the code below is fully sufficient */
94 for ( i = 1; i < *count; i++ )
96 if ( table[i].org - cur_val > threshold ||
101 /* fix loop for end of array */
102 if ( table[i].org - cur_val <= threshold &&
106 for ( j = cur_idx; j < i; j++ )
111 table[cur_idx].org = sum / (FT_Pos)j;
113 if ( i < *count - 1 )
116 cur_val = table[cur_idx].org;
123 /* compress array to remove zero values */
124 for ( i = 1; i < *count; i++ )
127 table[cur_idx++] = table[i];
133 /* Get new segment for given axis. */
135 FT_LOCAL_DEF( FT_Error )
136 af_axis_hints_new_segment( AF_AxisHints axis,
138 AF_Segment *asegment )
140 FT_Error error = FT_Err_Ok;
141 AF_Segment segment = NULL;
144 if ( axis->num_segments < AF_SEGMENTS_EMBEDDED )
146 if ( !axis->segments )
148 axis->segments = axis->embedded.segments;
149 axis->max_segments = AF_SEGMENTS_EMBEDDED;
152 else if ( axis->num_segments >= axis->max_segments )
154 FT_UInt old_max = axis->max_segments;
155 FT_UInt new_max = old_max;
156 FT_UInt big_max = FT_INT_MAX / sizeof ( *segment );
159 if ( old_max >= big_max )
161 error = FT_THROW( Out_Of_Memory );
165 new_max += ( new_max >> 2 ) + 4;
166 if ( new_max < old_max || new_max > big_max )
169 if ( axis->segments == axis->embedded.segments )
171 if ( FT_NEW_ARRAY( axis->segments, new_max ) )
173 ft_memcpy( axis->segments, axis->embedded.segments,
174 sizeof ( axis->embedded.segments ) );
178 if ( FT_RENEW_ARRAY( axis->segments, old_max, new_max ) )
182 axis->max_segments = new_max;
185 segment = axis->segments + axis->num_segments++;
193 /* Get new edge for given axis, direction, and position, */
194 /* without initializing the edge itself. */
196 FT_LOCAL_DEF( FT_Error )
197 af_axis_hints_new_edge( AF_AxisHints axis,
200 FT_Bool top_to_bottom_hinting,
204 FT_Error error = FT_Err_Ok;
209 if ( axis->num_edges < AF_EDGES_EMBEDDED )
213 axis->edges = axis->embedded.edges;
214 axis->max_edges = AF_EDGES_EMBEDDED;
217 else if ( axis->num_edges >= axis->max_edges )
219 FT_UInt old_max = axis->max_edges;
220 FT_UInt new_max = old_max;
221 FT_UInt big_max = FT_INT_MAX / sizeof ( *edge );
224 if ( old_max >= big_max )
226 error = FT_THROW( Out_Of_Memory );
230 new_max += ( new_max >> 2 ) + 4;
231 if ( new_max < old_max || new_max > big_max )
234 if ( axis->edges == axis->embedded.edges )
236 if ( FT_NEW_ARRAY( axis->edges, new_max ) )
238 ft_memcpy( axis->edges, axis->embedded.edges,
239 sizeof ( axis->embedded.edges ) );
243 if ( FT_RENEW_ARRAY( axis->edges, old_max, new_max ) )
247 axis->max_edges = new_max;
251 edge = edges + axis->num_edges;
253 while ( edge > edges )
255 if ( top_to_bottom_hinting ? ( edge[-1].fpos > fpos )
256 : ( edge[-1].fpos < fpos ) )
259 /* we want the edge with same position and minor direction */
260 /* to appear before those in the major one in the list */
261 if ( edge[-1].fpos == fpos && dir == axis->major_dir )
276 #ifdef FT_DEBUG_AUTOFIT
278 #include FT_CONFIG_STANDARD_LIBRARY_H
280 /* The dump functions are used in the `ftgrid' demo program, too. */
281 #define AF_DUMP( varformat ) \
287 FT_TRACE7( varformat ); \
292 af_dir_str( AF_Direction dir )
319 #define AF_INDEX_NUM( ptr, base ) (int)( (ptr) ? ( (ptr) - (base) ) : -1 )
323 af_print_idx( char* p,
334 ft_snprintf( p, n, "%d", idx );
341 af_get_segment_index( AF_GlyphHints hints,
345 AF_AxisHints axis = &hints->axis[dimension];
346 AF_Point point = hints->points + point_idx;
347 AF_Segment segments = axis->segments;
348 AF_Segment limit = segments + axis->num_segments;
352 for ( segment = segments; segment < limit; segment++ )
354 if ( segment->first <= segment->last )
356 if ( point >= segment->first && point <= segment->last )
361 AF_Point p = segment->first;
369 if ( p == segment->last )
378 if ( segment == limit )
381 return (int)( segment - segments );
386 af_get_edge_index( AF_GlyphHints hints,
390 AF_AxisHints axis = &hints->axis[dimension];
391 AF_Edge edges = axis->edges;
392 AF_Segment segment = axis->segments + segment_idx;
395 return segment_idx == -1 ? -1 : AF_INDEX_NUM( segment->edge, edges );
400 af_get_strong_edge_index( AF_GlyphHints hints,
401 AF_Edge* strong_edges,
404 AF_AxisHints axis = &hints->axis[dimension];
405 AF_Edge edges = axis->edges;
408 return AF_INDEX_NUM( strong_edges[dimension], edges );
416 af_glyph_hints_dump_points( AF_GlyphHints hints,
419 AF_Point points = hints->points;
420 AF_Point limit = points + hints->num_points;
421 AF_Point* contour = hints->contours;
422 AF_Point* climit = contour + hints->num_contours;
426 AF_DUMP(( "Table of points:\n" ));
428 if ( hints->num_points )
430 AF_DUMP(( " index hedge hseg vedge vseg flags "
431 /* " XXXXX XXXXX XXXXX XXXXX XXXXX XXXXXX" */
432 " xorg yorg xscale yscale xfit yfit "
433 /* " XXXXX XXXXX XXXX.XX XXXX.XX XXXX.XX XXXX.XX" */
434 " hbef haft vbef vaft" ));
435 /* " XXXXX XXXXX XXXXX XXXXX" */
438 AF_DUMP(( " (none)\n" ));
440 for ( point = points; point < limit; point++ )
442 int point_idx = AF_INDEX_NUM( point, points );
443 int segment_idx_0 = af_get_segment_index( hints, point_idx, 0 );
444 int segment_idx_1 = af_get_segment_index( hints, point_idx, 1 );
446 char buf1[16], buf2[16], buf3[16], buf4[16];
447 char buf5[16], buf6[16], buf7[16], buf8[16];
450 /* insert extra newline at the beginning of a contour */
451 if ( contour < climit && *contour == point )
457 AF_DUMP(( " %5d %5s %5s %5s %5s %s"
458 " %5d %5d %7.2f %7.2f %7.2f %7.2f"
459 " %5s %5s %5s %5s\n",
461 af_print_idx( buf1, 16,
462 af_get_edge_index( hints, segment_idx_1, 1 ) ),
463 af_print_idx( buf2, 16, segment_idx_1 ),
464 af_print_idx( buf3, 16,
465 af_get_edge_index( hints, segment_idx_0, 0 ) ),
466 af_print_idx( buf4, 16, segment_idx_0 ),
467 ( point->flags & AF_FLAG_NEAR )
469 : ( point->flags & AF_FLAG_WEAK_INTERPOLATION )
475 (double)point->ox / 64,
476 (double)point->oy / 64,
477 (double)point->x / 64,
478 (double)point->y / 64,
480 af_print_idx( buf5, 16,
481 af_get_strong_edge_index( hints,
484 af_print_idx( buf6, 16,
485 af_get_strong_edge_index( hints,
488 af_print_idx( buf7, 16,
489 af_get_strong_edge_index( hints,
492 af_print_idx( buf8, 16,
493 af_get_strong_edge_index( hints,
505 af_edge_flags_to_string( FT_UInt flags )
507 static char temp[32];
511 if ( flags & AF_EDGE_ROUND )
513 ft_memcpy( temp + pos, "round", 5 );
516 if ( flags & AF_EDGE_SERIF )
520 ft_memcpy( temp + pos, "serif", 5 );
532 /* Dump the array of linked segments. */
538 af_glyph_hints_dump_segments( AF_GlyphHints hints,
544 for ( dimension = 1; dimension >= 0; dimension-- )
546 AF_AxisHints axis = &hints->axis[dimension];
547 AF_Point points = hints->points;
548 AF_Edge edges = axis->edges;
549 AF_Segment segments = axis->segments;
550 AF_Segment limit = segments + axis->num_segments;
553 char buf1[16], buf2[16], buf3[16];
556 AF_DUMP(( "Table of %s segments:\n",
557 dimension == AF_DIMENSION_HORZ ? "vertical"
559 if ( axis->num_segments )
561 AF_DUMP(( " index pos delta dir from to "
562 /* " XXXXX XXXXX XXXXX XXXXX XXXX XXXX" */
564 /* " XXXX XXXXX XXXX" */
565 " height extra flags\n" ));
566 /* " XXXXXX XXXXX XXXXXXXXXXX" */
569 AF_DUMP(( " (none)\n" ));
571 for ( seg = segments; seg < limit; seg++ )
572 AF_DUMP(( " %5d %5d %5d %5s %4d %4d"
575 AF_INDEX_NUM( seg, segments ),
578 af_dir_str( (AF_Direction)seg->dir ),
579 AF_INDEX_NUM( seg->first, points ),
580 AF_INDEX_NUM( seg->last, points ),
582 af_print_idx( buf1, 16,
583 AF_INDEX_NUM( seg->link, segments ) ),
584 af_print_idx( buf2, 16,
585 AF_INDEX_NUM( seg->serif, segments ) ),
586 af_print_idx( buf3, 16,
587 AF_INDEX_NUM( seg->edge, edges ) ),
590 seg->height - ( seg->max_coord - seg->min_coord ),
591 af_edge_flags_to_string( seg->flags ) ));
600 /* Fetch number of segments. */
606 af_glyph_hints_get_num_segments( AF_GlyphHints hints,
608 FT_UInt* num_segments )
614 dim = ( dimension == 0 ) ? AF_DIMENSION_HORZ : AF_DIMENSION_VERT;
616 axis = &hints->axis[dim];
617 *num_segments = axis->num_segments;
626 /* Fetch offset of segments into user supplied offset array. */
632 af_glyph_hints_get_segment_offset( AF_GlyphHints hints,
637 FT_Pos *blue_offset )
645 return FT_THROW( Invalid_Argument );
647 dim = ( dimension == 0 ) ? AF_DIMENSION_HORZ : AF_DIMENSION_VERT;
649 axis = &hints->axis[dim];
651 if ( idx >= axis->num_segments )
652 return FT_THROW( Invalid_Argument );
654 seg = &axis->segments[idx];
655 *offset = ( dim == AF_DIMENSION_HORZ ) ? seg->first->fx
658 *is_blue = FT_BOOL( seg->edge->blue_edge );
663 *blue_offset = seg->edge->blue_edge->org;
674 /* Dump the array of linked edges. */
680 af_glyph_hints_dump_edges( AF_GlyphHints hints,
686 for ( dimension = 1; dimension >= 0; dimension-- )
688 AF_AxisHints axis = &hints->axis[dimension];
689 AF_Edge edges = axis->edges;
690 AF_Edge limit = edges + axis->num_edges;
693 char buf1[16], buf2[16];
697 * note: AF_DIMENSION_HORZ corresponds to _vertical_ edges
698 * since they have a constant X coordinate.
700 if ( dimension == AF_DIMENSION_HORZ )
701 AF_DUMP(( "Table of %s edges (1px=%.2fu, 10u=%.2fpx):\n",
703 65536 * 64 / (double)hints->x_scale,
704 10 * (double)hints->x_scale / 65536 / 64 ));
706 AF_DUMP(( "Table of %s edges (1px=%.2fu, 10u=%.2fpx):\n",
708 65536 * 64 / (double)hints->y_scale,
709 10 * (double)hints->y_scale / 65536 / 64 ));
711 if ( axis->num_edges )
713 AF_DUMP(( " index pos dir link serif"
714 /* " XXXXX XXXX.XX XXXXX XXXX XXXXX" */
715 " blue opos pos flags\n" ));
716 /* " X XXXX.XX XXXX.XX XXXXXXXXXXX" */
719 AF_DUMP(( " (none)\n" ));
721 for ( edge = edges; edge < limit; edge++ )
722 AF_DUMP(( " %5d %7.2f %5s %4s %5s"
723 " %c %7.2f %7.2f %11s\n",
724 AF_INDEX_NUM( edge, edges ),
725 (double)(int)edge->opos / 64,
726 af_dir_str( (AF_Direction)edge->dir ),
727 af_print_idx( buf1, 16,
728 AF_INDEX_NUM( edge->link, edges ) ),
729 af_print_idx( buf2, 16,
730 AF_INDEX_NUM( edge->serif, edges ) ),
732 edge->blue_edge ? 'y' : 'n',
733 (double)edge->opos / 64,
734 (double)edge->pos / 64,
735 af_edge_flags_to_string( edge->flags ) ));
745 #endif /* !FT_DEBUG_AUTOFIT */
748 /* Compute the direction value of a given vector. */
750 FT_LOCAL_DEF( AF_Direction )
751 af_direction_compute( FT_Pos dx,
754 FT_Pos ll, ss; /* long and short arm lengths */
755 AF_Direction dir; /* candidate direction */
789 /* return no direction if arm lengths do not differ enough */
790 /* (value 14 is heuristic, corresponding to approx. 4.1 degrees) */
791 /* the long arm is never negative */
792 if ( ll <= 14 * FT_ABS( ss ) )
800 af_glyph_hints_init( AF_GlyphHints hints,
803 /* no need to initialize the embedded items */
804 FT_MEM_ZERO( hints, sizeof ( *hints ) - sizeof ( hints->embedded ) );
805 hints->memory = memory;
810 af_glyph_hints_done( AF_GlyphHints hints )
816 if ( !( hints && hints->memory ) )
819 memory = hints->memory;
822 * note that we don't need to free the segment and edge
823 * buffers since they are really within the hints->points array
825 for ( dim = 0; dim < AF_DIMENSION_MAX; dim++ )
827 AF_AxisHints axis = &hints->axis[dim];
830 axis->num_segments = 0;
831 axis->max_segments = 0;
832 if ( axis->segments != axis->embedded.segments )
833 FT_FREE( axis->segments );
837 if ( axis->edges != axis->embedded.edges )
838 FT_FREE( axis->edges );
841 if ( hints->contours != hints->embedded.contours )
842 FT_FREE( hints->contours );
843 hints->max_contours = 0;
844 hints->num_contours = 0;
846 if ( hints->points != hints->embedded.points )
847 FT_FREE( hints->points );
848 hints->max_points = 0;
849 hints->num_points = 0;
851 hints->memory = NULL;
858 af_glyph_hints_rescale( AF_GlyphHints hints,
859 AF_StyleMetrics metrics )
861 hints->metrics = metrics;
862 hints->scaler_flags = metrics->scaler.flags;
866 /* Recompute all AF_Point in AF_GlyphHints from the definitions */
867 /* in a source outline. */
869 FT_LOCAL_DEF( FT_Error )
870 af_glyph_hints_reload( AF_GlyphHints hints,
871 FT_Outline* outline )
873 FT_Error error = FT_Err_Ok;
875 FT_Int old_max, new_max;
876 FT_Fixed x_scale = hints->x_scale;
877 FT_Fixed y_scale = hints->y_scale;
878 FT_Pos x_delta = hints->x_delta;
879 FT_Pos y_delta = hints->y_delta;
880 FT_Memory memory = hints->memory;
883 hints->num_points = 0;
884 hints->num_contours = 0;
886 hints->axis[0].num_segments = 0;
887 hints->axis[0].num_edges = 0;
888 hints->axis[1].num_segments = 0;
889 hints->axis[1].num_edges = 0;
891 /* first of all, reallocate the contours array if necessary */
892 new_max = outline->n_contours;
893 old_max = hints->max_contours;
895 if ( new_max <= AF_CONTOURS_EMBEDDED )
897 if ( !hints->contours )
899 hints->contours = hints->embedded.contours;
900 hints->max_contours = AF_CONTOURS_EMBEDDED;
903 else if ( new_max > old_max )
905 if ( hints->contours == hints->embedded.contours )
906 hints->contours = NULL;
908 new_max = ( new_max + 3 ) & ~3; /* round up to a multiple of 4 */
910 if ( FT_RENEW_ARRAY( hints->contours, old_max, new_max ) )
913 hints->max_contours = new_max;
917 * then reallocate the points arrays if necessary --
918 * note that we reserve two additional point positions, used to
919 * hint metrics appropriately
921 new_max = outline->n_points + 2;
922 old_max = hints->max_points;
924 if ( new_max <= AF_POINTS_EMBEDDED )
926 if ( !hints->points )
928 hints->points = hints->embedded.points;
929 hints->max_points = AF_POINTS_EMBEDDED;
932 else if ( new_max > old_max )
934 if ( hints->points == hints->embedded.points )
935 hints->points = NULL;
937 new_max = ( new_max + 2 + 7 ) & ~7; /* round up to a multiple of 8 */
939 if ( FT_RENEW_ARRAY( hints->points, old_max, new_max ) )
942 hints->max_points = new_max;
945 hints->num_points = outline->n_points;
946 hints->num_contours = outline->n_contours;
948 /* We can't rely on the value of `FT_Outline.flags' to know the fill */
949 /* direction used for a glyph, given that some fonts are broken (e.g., */
950 /* the Arphic ones). We thus recompute it each time we need to. */
952 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_UP;
953 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_LEFT;
955 if ( FT_Outline_Get_Orientation( outline ) == FT_ORIENTATION_POSTSCRIPT )
957 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_DOWN;
958 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_RIGHT;
961 hints->x_scale = x_scale;
962 hints->y_scale = y_scale;
963 hints->x_delta = x_delta;
964 hints->y_delta = y_delta;
966 points = hints->points;
967 if ( hints->num_points == 0 )
972 AF_Point point_limit = points + hints->num_points;
974 /* value 20 in `near_limit' is heuristic */
975 FT_UInt units_per_em = hints->metrics->scaler.face->units_per_EM;
976 FT_Int near_limit = 20 * units_per_em / 2048;
979 /* compute coordinates & Bezier flags, next and prev */
981 FT_Vector* vec = outline->points;
982 char* tag = outline->tags;
983 FT_Short endpoint = outline->contours[0];
984 AF_Point end = points + endpoint;
986 FT_Int contour_index = 0;
989 for ( point = points; point < point_limit; point++, vec++, tag++ )
994 point->in_dir = (FT_Char)AF_DIR_NONE;
995 point->out_dir = (FT_Char)AF_DIR_NONE;
997 point->fx = (FT_Short)vec->x;
998 point->fy = (FT_Short)vec->y;
999 point->ox = point->x = FT_MulFix( vec->x, x_scale ) + x_delta;
1000 point->oy = point->y = FT_MulFix( vec->y, y_scale ) + y_delta;
1002 end->fx = (FT_Short)outline->points[endpoint].x;
1003 end->fy = (FT_Short)outline->points[endpoint].y;
1005 switch ( FT_CURVE_TAG( *tag ) )
1007 case FT_CURVE_TAG_CONIC:
1008 point->flags = AF_FLAG_CONIC;
1010 case FT_CURVE_TAG_CUBIC:
1011 point->flags = AF_FLAG_CUBIC;
1014 point->flags = AF_FLAG_NONE;
1017 out_x = point->fx - prev->fx;
1018 out_y = point->fy - prev->fy;
1020 if ( FT_ABS( out_x ) + FT_ABS( out_y ) < near_limit )
1021 prev->flags |= AF_FLAG_NEAR;
1029 if ( ++contour_index < outline->n_contours )
1031 endpoint = outline->contours[contour_index];
1032 end = points + endpoint;
1037 #ifdef FT_DEBUG_AUTOFIT
1038 point->before[0] = NULL;
1039 point->before[1] = NULL;
1040 point->after[0] = NULL;
1041 point->after[1] = NULL;
1047 /* set up the contours array */
1049 AF_Point* contour = hints->contours;
1050 AF_Point* contour_limit = contour + hints->num_contours;
1051 short* end = outline->contours;
1055 for ( ; contour < contour_limit; contour++, end++ )
1057 contour[0] = points + idx;
1058 idx = (short)( end[0] + 1 );
1064 * Compute directions of `in' and `out' vectors.
1066 * Note that distances between points that are very near to each
1067 * other are accumulated. In other words, the auto-hinter either
1068 * prepends the small vectors between near points to the first
1069 * non-near vector, or the sum of small vector lengths exceeds a
1070 * threshold, thus `grouping' the small vectors. All intermediate
1071 * points are tagged as weak; the directions are adjusted also to
1072 * be equal to the accumulated one.
1075 FT_Int near_limit2 = 2 * near_limit - 1;
1078 AF_Point* contour_limit = hints->contours + hints->num_contours;
1081 for ( contour = hints->contours; contour < contour_limit; contour++ )
1083 AF_Point first = *contour;
1084 AF_Point next, prev, curr;
1086 FT_Pos out_x, out_y;
1089 /* since the first point of a contour could be part of a */
1090 /* series of near points, go backwards to find the first */
1091 /* non-near point and adjust `first' */
1096 while ( prev != first )
1098 out_x = point->fx - prev->fx;
1099 out_y = point->fy - prev->fy;
1102 * We use Taxicab metrics to measure the vector length.
1104 * Note that the accumulated distances so far could have the
1105 * opposite direction of the distance measured here. For this
1106 * reason we use `near_limit2' for the comparison to get a
1107 * non-near point even in the worst case.
1109 if ( FT_ABS( out_x ) + FT_ABS( out_y ) >= near_limit2 )
1116 /* adjust first point */
1119 /* now loop over all points of the contour to get */
1120 /* `in' and `out' vector directions */
1125 * We abuse the `u' and `v' fields to store index deltas to the
1126 * next and previous non-near point, respectively.
1128 * To avoid problems with not having non-near points, we point to
1129 * `first' by default as the next non-near point.
1132 curr->u = (FT_Pos)( first - curr );
1133 first->v = -curr->u;
1141 AF_Direction out_dir;
1147 out_x += next->fx - point->fx;
1148 out_y += next->fy - point->fy;
1150 if ( FT_ABS( out_x ) + FT_ABS( out_y ) < near_limit )
1152 next->flags |= AF_FLAG_WEAK_INTERPOLATION;
1156 curr->u = (FT_Pos)( next - curr );
1159 out_dir = af_direction_compute( out_x, out_y );
1161 /* adjust directions for all points inbetween; */
1162 /* the loop also updates position of `curr' */
1163 curr->out_dir = (FT_Char)out_dir;
1164 for ( curr = curr->next; curr != next; curr = curr->next )
1166 curr->in_dir = (FT_Char)out_dir;
1167 curr->out_dir = (FT_Char)out_dir;
1169 next->in_dir = (FT_Char)out_dir;
1171 curr->u = (FT_Pos)( first - curr );
1172 first->v = -curr->u;
1177 } while ( next != first );
1181 * The next step is to `simplify' an outline's topology so that we
1182 * can identify local extrema more reliably: A series of
1183 * non-horizontal or non-vertical vectors pointing into the same
1184 * quadrant are handled as a single, long vector. From a
1185 * topological point of the view, the intermediate points are of no
1186 * interest and thus tagged as weak.
1189 for ( point = points; point < point_limit; point++ )
1191 if ( point->flags & AF_FLAG_WEAK_INTERPOLATION )
1194 if ( point->in_dir == AF_DIR_NONE &&
1195 point->out_dir == AF_DIR_NONE )
1197 /* check whether both vectors point into the same quadrant */
1200 FT_Pos out_x, out_y;
1202 AF_Point next_u = point + point->u;
1203 AF_Point prev_v = point + point->v;
1206 in_x = point->fx - prev_v->fx;
1207 in_y = point->fy - prev_v->fy;
1209 out_x = next_u->fx - point->fx;
1210 out_y = next_u->fy - point->fy;
1212 if ( ( in_x ^ out_x ) >= 0 && ( in_y ^ out_y ) >= 0 )
1214 /* yes, so tag current point as weak */
1215 /* and update index deltas */
1217 point->flags |= AF_FLAG_WEAK_INTERPOLATION;
1219 prev_v->u = (FT_Pos)( next_u - prev_v );
1220 next_u->v = -prev_v->u;
1226 * Finally, check for remaining weak points. Everything else not
1227 * collected in edges so far is then implicitly classified as strong
1231 for ( point = points; point < point_limit; point++ )
1233 if ( point->flags & AF_FLAG_WEAK_INTERPOLATION )
1236 if ( point->flags & AF_FLAG_CONTROL )
1238 /* control points are always weak */
1240 point->flags |= AF_FLAG_WEAK_INTERPOLATION;
1242 else if ( point->out_dir == point->in_dir )
1244 if ( point->out_dir != AF_DIR_NONE )
1246 /* current point lies on a horizontal or */
1247 /* vertical segment (but doesn't start or end it) */
1252 AF_Point next_u = point + point->u;
1253 AF_Point prev_v = point + point->v;
1256 if ( ft_corner_is_flat( point->fx - prev_v->fx,
1257 point->fy - prev_v->fy,
1258 next_u->fx - point->fx,
1259 next_u->fy - point->fy ) )
1261 /* either the `in' or the `out' vector is much more */
1262 /* dominant than the other one, so tag current point */
1263 /* as weak and update index deltas */
1265 prev_v->u = (FT_Pos)( next_u - prev_v );
1266 next_u->v = -prev_v->u;
1272 else if ( point->in_dir == -point->out_dir )
1274 /* current point forms a spike */
1286 /* Store the hinted outline in an FT_Outline structure. */
1288 FT_LOCAL_DEF( void )
1289 af_glyph_hints_save( AF_GlyphHints hints,
1290 FT_Outline* outline )
1292 AF_Point point = hints->points;
1293 AF_Point limit = point + hints->num_points;
1294 FT_Vector* vec = outline->points;
1295 char* tag = outline->tags;
1298 for ( ; point < limit; point++, vec++, tag++ )
1303 if ( point->flags & AF_FLAG_CONIC )
1304 tag[0] = FT_CURVE_TAG_CONIC;
1305 else if ( point->flags & AF_FLAG_CUBIC )
1306 tag[0] = FT_CURVE_TAG_CUBIC;
1308 tag[0] = FT_CURVE_TAG_ON;
1313 /****************************************************************
1315 * EDGE POINT GRID-FITTING
1317 ****************************************************************/
1320 /* Align all points of an edge to the same coordinate value, */
1321 /* either horizontally or vertically. */
1323 FT_LOCAL_DEF( void )
1324 af_glyph_hints_align_edge_points( AF_GlyphHints hints,
1327 AF_AxisHints axis = & hints->axis[dim];
1328 AF_Segment segments = axis->segments;
1329 AF_Segment segment_limit = FT_OFFSET( segments, axis->num_segments );
1333 if ( dim == AF_DIMENSION_HORZ )
1335 for ( seg = segments; seg < segment_limit; seg++ )
1337 AF_Edge edge = seg->edge;
1338 AF_Point point, first, last;
1349 point->x = edge->pos;
1350 point->flags |= AF_FLAG_TOUCH_X;
1352 if ( point == last )
1355 point = point->next;
1361 for ( seg = segments; seg < segment_limit; seg++ )
1363 AF_Edge edge = seg->edge;
1364 AF_Point point, first, last;
1375 point->y = edge->pos;
1376 point->flags |= AF_FLAG_TOUCH_Y;
1378 if ( point == last )
1381 point = point->next;
1388 /****************************************************************
1390 * STRONG POINT INTERPOLATION
1392 ****************************************************************/
1395 /* Hint the strong points -- this is equivalent to the TrueType `IP' */
1396 /* hinting instruction. */
1398 FT_LOCAL_DEF( void )
1399 af_glyph_hints_align_strong_points( AF_GlyphHints hints,
1402 AF_Point points = hints->points;
1403 AF_Point point_limit = points + hints->num_points;
1404 AF_AxisHints axis = &hints->axis[dim];
1405 AF_Edge edges = axis->edges;
1406 AF_Edge edge_limit = FT_OFFSET( edges, axis->num_edges );
1410 if ( dim == AF_DIMENSION_HORZ )
1411 touch_flag = AF_FLAG_TOUCH_X;
1413 touch_flag = AF_FLAG_TOUCH_Y;
1415 if ( edges < edge_limit )
1421 for ( point = points; point < point_limit; point++ )
1423 FT_Pos u, ou, fu; /* point position */
1427 if ( point->flags & touch_flag )
1430 /* if this point is candidate to weak interpolation, we */
1431 /* interpolate it after all strong points have been processed */
1433 if ( ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) )
1436 if ( dim == AF_DIMENSION_VERT )
1449 /* is the point before the first edge? */
1451 delta = edge->fpos - u;
1454 u = edge->pos - ( edge->opos - ou );
1456 #ifdef FT_DEBUG_AUTOFIT
1457 point->before[dim] = edge;
1458 point->after[dim] = NULL;
1464 /* is the point after the last edge? */
1465 edge = edge_limit - 1;
1466 delta = u - edge->fpos;
1469 u = edge->pos + ( ou - edge->opos );
1471 #ifdef FT_DEBUG_AUTOFIT
1472 point->before[dim] = NULL;
1473 point->after[dim] = edge;
1480 FT_PtrDist min, max, mid;
1484 /* find enclosing edges */
1486 max = edge_limit - edges;
1489 /* for a small number of edges, a linear search is better */
1495 for ( nn = 0; nn < max; nn++ )
1496 if ( edges[nn].fpos >= u )
1499 if ( edges[nn].fpos == u )
1510 mid = ( max + min ) >> 1;
1516 else if ( u > fpos )
1520 /* we are on the edge */
1523 #ifdef FT_DEBUG_AUTOFIT
1524 point->before[dim] = NULL;
1525 point->after[dim] = NULL;
1532 /* point is not on an edge */
1534 AF_Edge before = edges + min - 1;
1535 AF_Edge after = edges + min + 0;
1538 #ifdef FT_DEBUG_AUTOFIT
1539 point->before[dim] = before;
1540 point->after[dim] = after;
1543 /* assert( before && after && before != after ) */
1544 if ( before->scale == 0 )
1545 before->scale = FT_DivFix( after->pos - before->pos,
1546 after->fpos - before->fpos );
1548 u = before->pos + FT_MulFix( fu - before->fpos,
1554 /* save the point position */
1555 if ( dim == AF_DIMENSION_HORZ )
1560 point->flags |= touch_flag;
1566 /****************************************************************
1568 * WEAK POINT INTERPOLATION
1570 ****************************************************************/
1573 /* Shift the original coordinates of all points between `p1' and */
1574 /* `p2' to get hinted coordinates, using the same difference as */
1575 /* given by `ref'. */
1578 af_iup_shift( AF_Point p1,
1583 FT_Pos delta = ref->u - ref->v;
1589 for ( p = p1; p < ref; p++ )
1590 p->u = p->v + delta;
1592 for ( p = ref + 1; p <= p2; p++ )
1593 p->u = p->v + delta;
1597 /* Interpolate the original coordinates of all points between `p1' and */
1598 /* `p2' to get hinted coordinates, using `ref1' and `ref2' as the */
1599 /* reference points. The `u' and `v' members are the current and */
1600 /* original coordinate values, respectively. */
1602 /* Details can be found in the TrueType bytecode specification. */
1605 af_iup_interp( AF_Point p1,
1611 FT_Pos u, v1, v2, u1, u2, d1, d2;
1617 if ( ref1->v > ref2->v )
1631 if ( u1 == u2 || v1 == v2 )
1633 for ( p = p1; p <= p2; p++ )
1649 FT_Fixed scale = FT_DivFix( u2 - u1, v2 - v1 );
1652 for ( p = p1; p <= p2; p++ )
1661 u = u1 + FT_MulFix( u - v1, scale );
1669 /* Hint the weak points -- this is equivalent to the TrueType `IUP' */
1670 /* hinting instruction. */
1672 FT_LOCAL_DEF( void )
1673 af_glyph_hints_align_weak_points( AF_GlyphHints hints,
1676 AF_Point points = hints->points;
1677 AF_Point point_limit = points + hints->num_points;
1678 AF_Point* contour = hints->contours;
1679 AF_Point* contour_limit = contour + hints->num_contours;
1683 AF_Point first_point;
1686 /* PASS 1: Move segment points to edge positions */
1688 if ( dim == AF_DIMENSION_HORZ )
1690 touch_flag = AF_FLAG_TOUCH_X;
1692 for ( point = points; point < point_limit; point++ )
1694 point->u = point->x;
1695 point->v = point->ox;
1700 touch_flag = AF_FLAG_TOUCH_Y;
1702 for ( point = points; point < point_limit; point++ )
1704 point->u = point->y;
1705 point->v = point->oy;
1709 for ( ; contour < contour_limit; contour++ )
1711 AF_Point first_touched, last_touched;
1715 end_point = point->prev;
1716 first_point = point;
1718 /* find first touched point */
1721 if ( point > end_point ) /* no touched point in contour */
1724 if ( point->flags & touch_flag )
1730 first_touched = point;
1734 FT_ASSERT( point <= end_point &&
1735 ( point->flags & touch_flag ) != 0 );
1737 /* skip any touched neighbours */
1738 while ( point < end_point &&
1739 ( point[1].flags & touch_flag ) != 0 )
1742 last_touched = point;
1744 /* find the next touched point, if any */
1748 if ( point > end_point )
1751 if ( ( point->flags & touch_flag ) != 0 )
1757 /* interpolate between last_touched and point */
1758 af_iup_interp( last_touched + 1, point - 1,
1759 last_touched, point );
1763 /* special case: only one point was touched */
1764 if ( last_touched == first_touched )
1765 af_iup_shift( first_point, end_point, first_touched );
1767 else /* interpolate the last part */
1769 if ( last_touched < end_point )
1770 af_iup_interp( last_touched + 1, end_point,
1771 last_touched, first_touched );
1773 if ( first_touched > points )
1774 af_iup_interp( first_point, first_touched - 1,
1775 last_touched, first_touched );
1782 /* now save the interpolated values back to x/y */
1783 if ( dim == AF_DIMENSION_HORZ )
1785 for ( point = points; point < point_limit; point++ )
1786 point->x = point->u;
1790 for ( point = points; point < point_limit; point++ )
1791 point->y = point->u;