1 /***************************************************************************/
5 /* Auto-fitter hinting routines (body). */
7 /* Copyright 2003, 2004, 2005, 2006, 2007, 2009, 2010 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 FT_LOCAL_DEF( FT_Error )
25 af_axis_hints_new_segment( AF_AxisHints axis,
27 AF_Segment *asegment )
29 FT_Error error = AF_Err_Ok;
30 AF_Segment segment = NULL;
33 if ( axis->num_segments >= axis->max_segments )
35 FT_Int old_max = axis->max_segments;
36 FT_Int new_max = old_max;
37 FT_Int big_max = (FT_Int)( FT_INT_MAX / sizeof ( *segment ) );
40 if ( old_max >= big_max )
42 error = AF_Err_Out_Of_Memory;
46 new_max += ( new_max >> 2 ) + 4;
47 if ( new_max < old_max || new_max > big_max )
50 if ( FT_RENEW_ARRAY( axis->segments, old_max, new_max ) )
53 axis->max_segments = new_max;
56 segment = axis->segments + axis->num_segments++;
65 af_axis_hints_new_edge( AF_AxisHints axis,
71 FT_Error error = AF_Err_Ok;
76 if ( axis->num_edges >= axis->max_edges )
78 FT_Int old_max = axis->max_edges;
79 FT_Int new_max = old_max;
80 FT_Int big_max = (FT_Int)( FT_INT_MAX / sizeof ( *edge ) );
83 if ( old_max >= big_max )
85 error = AF_Err_Out_Of_Memory;
89 new_max += ( new_max >> 2 ) + 4;
90 if ( new_max < old_max || new_max > big_max )
93 if ( FT_RENEW_ARRAY( axis->edges, old_max, new_max ) )
96 axis->max_edges = new_max;
100 edge = edges + axis->num_edges;
102 while ( edge > edges )
104 if ( edge[-1].fpos < fpos )
107 /* we want the edge with same position and minor direction */
108 /* to appear before those in the major one in the list */
109 if ( edge[-1].fpos == fpos && dir == axis->major_dir )
119 edge->fpos = (FT_Short)fpos;
120 edge->dir = (FT_Char)dir;
130 #include FT_CONFIG_STANDARD_LIBRARY_H
133 af_dir_str( AF_Direction dir )
160 #define AF_INDEX_NUM( ptr, base ) ( (ptr) ? ( (ptr) - (base) ) : -1 )
164 af_glyph_hints_dump_points( AF_GlyphHints hints )
166 AF_Point points = hints->points;
167 AF_Point limit = points + hints->num_points;
171 printf( "Table of points:\n" );
172 printf( " [ index | xorg | yorg | xscale | yscale "
173 "| xfit | yfit | flags ]\n" );
175 for ( point = points; point < limit; point++ )
177 printf( " [ %5d | %5d | %5d | %-5.2f | %-5.2f "
178 "| %-5.2f | %-5.2f | %c%c%c%c%c%c ]\n",
186 ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) ? 'w' : ' ',
187 ( point->flags & AF_FLAG_INFLECTION ) ? 'i' : ' ',
188 ( point->flags & AF_FLAG_EXTREMA_X ) ? '<' : ' ',
189 ( point->flags & AF_FLAG_EXTREMA_Y ) ? 'v' : ' ',
190 ( point->flags & AF_FLAG_ROUND_X ) ? '(' : ' ',
191 ( point->flags & AF_FLAG_ROUND_Y ) ? 'u' : ' ');
198 af_edge_flags_to_string( AF_Edge_Flags flags )
200 static char temp[32];
204 if ( flags & AF_EDGE_ROUND )
206 ft_memcpy( temp + pos, "round", 5 );
209 if ( flags & AF_EDGE_SERIF )
213 ft_memcpy( temp + pos, "serif", 5 );
225 /* A function to dump the array of linked segments. */
227 af_glyph_hints_dump_segments( AF_GlyphHints hints )
232 for ( dimension = 1; dimension >= 0; dimension-- )
234 AF_AxisHints axis = &hints->axis[dimension];
235 AF_Segment segments = axis->segments;
236 AF_Segment limit = segments + axis->num_segments;
240 printf ( "Table of %s segments:\n",
241 dimension == AF_DIMENSION_HORZ ? "vertical" : "horizontal" );
242 printf ( " [ index | pos | dir | link | serif |"
243 " height | extra | flags ]\n" );
245 for ( seg = segments; seg < limit; seg++ )
247 printf ( " [ %5d | %5.2g | %5s | %4d | %5d | %5d | %5d | %s ]\n",
249 dimension == AF_DIMENSION_HORZ ? (int)seg->first->ox / 64.0
250 : (int)seg->first->oy / 64.0,
251 af_dir_str( (AF_Direction)seg->dir ),
252 AF_INDEX_NUM( seg->link, segments ),
253 AF_INDEX_NUM( seg->serif, segments ),
255 seg->height - ( seg->max_coord - seg->min_coord ),
256 af_edge_flags_to_string( seg->flags ) );
264 af_glyph_hints_dump_edges( AF_GlyphHints hints )
269 for ( dimension = 1; dimension >= 0; dimension-- )
271 AF_AxisHints axis = &hints->axis[dimension];
272 AF_Edge edges = axis->edges;
273 AF_Edge limit = edges + axis->num_edges;
278 * note: AF_DIMENSION_HORZ corresponds to _vertical_ edges
279 * since they have constant a X coordinate.
281 printf ( "Table of %s edges:\n",
282 dimension == AF_DIMENSION_HORZ ? "vertical" : "horizontal" );
283 printf ( " [ index | pos | dir | link |"
284 " serif | blue | opos | pos | flags ]\n" );
286 for ( edge = edges; edge < limit; edge++ )
288 printf ( " [ %5d | %5.2g | %5s | %4d |"
289 " %5d | %c | %5.2f | %5.2f | %s ]\n",
291 (int)edge->opos / 64.0,
292 af_dir_str( (AF_Direction)edge->dir ),
293 AF_INDEX_NUM( edge->link, edges ),
294 AF_INDEX_NUM( edge->serif, edges ),
295 edge->blue_edge ? 'y' : 'n',
298 af_edge_flags_to_string( edge->flags ) );
304 #else /* !AF_DEBUG */
306 /* these empty stubs are only used to link the `ftgrid' test program */
307 /* when debugging is disabled */
310 af_glyph_hints_dump_points( AF_GlyphHints hints )
317 af_glyph_hints_dump_segments( AF_GlyphHints hints )
324 af_glyph_hints_dump_edges( AF_GlyphHints hints )
329 #endif /* !AF_DEBUG */
332 /* compute the direction value of a given vector */
333 FT_LOCAL_DEF( AF_Direction )
334 af_direction_compute( FT_Pos dx,
337 FT_Pos ll, ss; /* long and short arm lengths */
338 AF_Direction dir; /* candidate direction */
373 if ( FT_ABS( ll ) <= FT_ABS( ss ) )
381 af_glyph_hints_init( AF_GlyphHints hints,
385 hints->memory = memory;
390 af_glyph_hints_done( AF_GlyphHints hints )
392 if ( hints && hints->memory )
394 FT_Memory memory = hints->memory;
399 * note that we don't need to free the segment and edge
400 * buffers, since they are really within the hints->points array
402 for ( dim = 0; dim < AF_DIMENSION_MAX; dim++ )
404 AF_AxisHints axis = &hints->axis[dim];
407 axis->num_segments = 0;
408 axis->max_segments = 0;
409 FT_FREE( axis->segments );
413 FT_FREE( axis->edges );
416 FT_FREE( hints->contours );
417 hints->max_contours = 0;
418 hints->num_contours = 0;
420 FT_FREE( hints->points );
421 hints->num_points = 0;
422 hints->max_points = 0;
424 hints->memory = NULL;
430 af_glyph_hints_rescale( AF_GlyphHints hints,
431 AF_ScriptMetrics metrics )
433 hints->metrics = metrics;
434 hints->scaler_flags = metrics->scaler.flags;
438 FT_LOCAL_DEF( FT_Error )
439 af_glyph_hints_reload( AF_GlyphHints hints,
440 FT_Outline* outline )
442 FT_Error error = AF_Err_Ok;
444 FT_UInt old_max, new_max;
445 FT_Fixed x_scale = hints->x_scale;
446 FT_Fixed y_scale = hints->y_scale;
447 FT_Pos x_delta = hints->x_delta;
448 FT_Pos y_delta = hints->y_delta;
449 FT_Memory memory = hints->memory;
452 hints->num_points = 0;
453 hints->num_contours = 0;
455 hints->axis[0].num_segments = 0;
456 hints->axis[0].num_edges = 0;
457 hints->axis[1].num_segments = 0;
458 hints->axis[1].num_edges = 0;
460 /* first of all, reallocate the contours array when necessary */
461 new_max = (FT_UInt)outline->n_contours;
462 old_max = hints->max_contours;
463 if ( new_max > old_max )
465 new_max = ( new_max + 3 ) & ~3;
467 if ( FT_RENEW_ARRAY( hints->contours, old_max, new_max ) )
470 hints->max_contours = new_max;
474 * then reallocate the points arrays if necessary --
475 * note that we reserve two additional point positions, used to
476 * hint metrics appropriately
478 new_max = (FT_UInt)( outline->n_points + 2 );
479 old_max = hints->max_points;
480 if ( new_max > old_max )
482 new_max = ( new_max + 2 + 7 ) & ~7;
484 if ( FT_RENEW_ARRAY( hints->points, old_max, new_max ) )
487 hints->max_points = new_max;
490 hints->num_points = outline->n_points;
491 hints->num_contours = outline->n_contours;
493 /* We can't rely on the value of `FT_Outline.flags' to know the fill */
494 /* direction used for a glyph, given that some fonts are broken (e.g., */
495 /* the Arphic ones). We thus recompute it each time we need to. */
497 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_UP;
498 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_LEFT;
500 if ( FT_Outline_Get_Orientation( outline ) == FT_ORIENTATION_POSTSCRIPT )
502 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_DOWN;
503 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_RIGHT;
506 hints->x_scale = x_scale;
507 hints->y_scale = y_scale;
508 hints->x_delta = x_delta;
509 hints->y_delta = y_delta;
511 hints->xmin_delta = 0;
512 hints->xmax_delta = 0;
514 points = hints->points;
515 if ( hints->num_points == 0 )
520 AF_Point point_limit = points + hints->num_points;
523 /* compute coordinates & Bezier flags, next and prev */
525 FT_Vector* vec = outline->points;
526 char* tag = outline->tags;
527 AF_Point end = points + outline->contours[0];
529 FT_Int contour_index = 0;
532 for ( point = points; point < point_limit; point++, vec++, tag++ )
534 point->fx = (FT_Short)vec->x;
535 point->fy = (FT_Short)vec->y;
536 point->ox = point->x = FT_MulFix( vec->x, x_scale ) + x_delta;
537 point->oy = point->y = FT_MulFix( vec->y, y_scale ) + y_delta;
539 switch ( FT_CURVE_TAG( *tag ) )
541 case FT_CURVE_TAG_CONIC:
542 point->flags = AF_FLAG_CONIC;
544 case FT_CURVE_TAG_CUBIC:
545 point->flags = AF_FLAG_CUBIC;
557 if ( ++contour_index < outline->n_contours )
559 end = points + outline->contours[contour_index];
566 /* set-up the contours array */
568 AF_Point* contour = hints->contours;
569 AF_Point* contour_limit = contour + hints->num_contours;
570 short* end = outline->contours;
574 for ( ; contour < contour_limit; contour++, end++ )
576 contour[0] = points + idx;
577 idx = (short)( end[0] + 1 );
581 /* compute directions of in & out vectors */
583 AF_Point first = points;
584 AF_Point prev = NULL;
587 AF_Direction in_dir = AF_DIR_NONE;
590 for ( point = points; point < point_limit; point++ )
596 if ( point == first )
599 in_x = first->fx - prev->fx;
600 in_y = first->fy - prev->fy;
601 in_dir = af_direction_compute( in_x, in_y );
605 point->in_dir = (FT_Char)in_dir;
608 out_x = next->fx - point->fx;
609 out_y = next->fy - point->fy;
611 in_dir = af_direction_compute( out_x, out_y );
612 point->out_dir = (FT_Char)in_dir;
614 if ( point->flags & ( AF_FLAG_CONIC | AF_FLAG_CUBIC ) )
617 point->flags |= AF_FLAG_WEAK_INTERPOLATION;
619 else if ( point->out_dir == point->in_dir )
621 if ( point->out_dir != AF_DIR_NONE )
624 if ( ft_corner_is_flat( in_x, in_y, out_x, out_y ) )
627 else if ( point->in_dir == -point->out_dir )
643 af_glyph_hints_save( AF_GlyphHints hints,
644 FT_Outline* outline )
646 AF_Point point = hints->points;
647 AF_Point limit = point + hints->num_points;
648 FT_Vector* vec = outline->points;
649 char* tag = outline->tags;
652 for ( ; point < limit; point++, vec++, tag++ )
657 if ( point->flags & AF_FLAG_CONIC )
658 tag[0] = FT_CURVE_TAG_CONIC;
659 else if ( point->flags & AF_FLAG_CUBIC )
660 tag[0] = FT_CURVE_TAG_CUBIC;
662 tag[0] = FT_CURVE_TAG_ON;
667 /****************************************************************
669 * EDGE POINT GRID-FITTING
671 ****************************************************************/
675 af_glyph_hints_align_edge_points( AF_GlyphHints hints,
678 AF_AxisHints axis = & hints->axis[dim];
679 AF_Segment segments = axis->segments;
680 AF_Segment segment_limit = segments + axis->num_segments;
684 if ( dim == AF_DIMENSION_HORZ )
686 for ( seg = segments; seg < segment_limit; seg++ )
688 AF_Edge edge = seg->edge;
689 AF_Point point, first, last;
700 point->x = edge->pos;
701 point->flags |= AF_FLAG_TOUCH_X;
713 for ( seg = segments; seg < segment_limit; seg++ )
715 AF_Edge edge = seg->edge;
716 AF_Point point, first, last;
727 point->y = edge->pos;
728 point->flags |= AF_FLAG_TOUCH_Y;
740 /****************************************************************
742 * STRONG POINT INTERPOLATION
744 ****************************************************************/
747 /* hint the strong points -- this is equivalent to the TrueType `IP' */
748 /* hinting instruction */
751 af_glyph_hints_align_strong_points( AF_GlyphHints hints,
754 AF_Point points = hints->points;
755 AF_Point point_limit = points + hints->num_points;
756 AF_AxisHints axis = &hints->axis[dim];
757 AF_Edge edges = axis->edges;
758 AF_Edge edge_limit = edges + axis->num_edges;
762 if ( dim == AF_DIMENSION_HORZ )
763 touch_flag = AF_FLAG_TOUCH_X;
765 touch_flag = AF_FLAG_TOUCH_Y;
767 if ( edges < edge_limit )
773 for ( point = points; point < point_limit; point++ )
775 FT_Pos u, ou, fu; /* point position */
779 if ( point->flags & touch_flag )
782 /* if this point is candidate to weak interpolation, we */
783 /* interpolate it after all strong points have been processed */
785 if ( ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) &&
786 !( point->flags & AF_FLAG_INFLECTION ) )
789 if ( dim == AF_DIMENSION_VERT )
802 /* is the point before the first edge? */
804 delta = edge->fpos - u;
807 u = edge->pos - ( edge->opos - ou );
811 /* is the point after the last edge? */
812 edge = edge_limit - 1;
813 delta = u - edge->fpos;
816 u = edge->pos + ( ou - edge->opos );
821 FT_PtrDist min, max, mid;
825 /* find enclosing edges */
827 max = edge_limit - edges;
830 /* for small edge counts, a linear search is better */
835 for ( nn = 0; nn < max; nn++ )
836 if ( edges[nn].fpos >= u )
839 if ( edges[nn].fpos == u )
850 mid = ( max + min ) >> 1;
860 /* we are on the edge */
867 AF_Edge before = edges + min - 1;
868 AF_Edge after = edges + min + 0;
871 /* assert( before && after && before != after ) */
872 if ( before->scale == 0 )
873 before->scale = FT_DivFix( after->pos - before->pos,
874 after->fpos - before->fpos );
876 u = before->pos + FT_MulFix( fu - before->fpos,
882 /* save the point position */
883 if ( dim == AF_DIMENSION_HORZ )
888 point->flags |= touch_flag;
894 /****************************************************************
896 * WEAK POINT INTERPOLATION
898 ****************************************************************/
902 af_iup_shift( AF_Point p1,
907 FT_Pos delta = ref->u - ref->v;
912 for ( p = p1; p < ref; p++ )
915 for ( p = ref + 1; p <= p2; p++ )
921 af_iup_interp( AF_Point p1,
930 FT_Pos d1 = ref1->u - v1;
931 FT_Pos d2 = ref2->u - v2;
939 for ( p = p1; p <= p2; p++ )
955 for ( p = p1; p <= p2; p++ )
964 u = ref1->u + FT_MulDiv( u - v1, ref2->u - ref1->u, v2 - v1 );
971 for ( p = p1; p <= p2; p++ )
980 u = ref1->u + FT_MulDiv( u - v1, ref2->u - ref1->u, v2 - v1 );
989 af_glyph_hints_align_weak_points( AF_GlyphHints hints,
992 AF_Point points = hints->points;
993 AF_Point point_limit = points + hints->num_points;
994 AF_Point* contour = hints->contours;
995 AF_Point* contour_limit = contour + hints->num_contours;
999 AF_Point first_point;
1002 /* PASS 1: Move segment points to edge positions */
1004 if ( dim == AF_DIMENSION_HORZ )
1006 touch_flag = AF_FLAG_TOUCH_X;
1008 for ( point = points; point < point_limit; point++ )
1010 point->u = point->x;
1011 point->v = point->ox;
1016 touch_flag = AF_FLAG_TOUCH_Y;
1018 for ( point = points; point < point_limit; point++ )
1020 point->u = point->y;
1021 point->v = point->oy;
1027 for ( ; contour < contour_limit; contour++ )
1029 AF_Point first_touched, last_touched;
1033 end_point = point->prev;
1034 first_point = point;
1036 /* find first touched point */
1039 if ( point > end_point ) /* no touched point in contour */
1042 if ( point->flags & touch_flag )
1048 first_touched = point;
1049 last_touched = point;
1053 FT_ASSERT( point <= end_point &&
1054 ( point->flags & touch_flag ) != 0 );
1056 /* skip any touched neighbhours */
1057 while ( point < end_point && ( point[1].flags & touch_flag ) != 0 )
1060 last_touched = point;
1062 /* find the next touched point, if any */
1066 if ( point > end_point )
1069 if ( ( point->flags & touch_flag ) != 0 )
1075 /* interpolate between last_touched and point */
1076 af_iup_interp( last_touched + 1, point - 1,
1077 last_touched, point );
1081 /* special case: only one point was touched */
1082 if ( last_touched == first_touched )
1084 af_iup_shift( first_point, end_point, first_touched );
1086 else /* interpolate the last part */
1088 if ( last_touched < end_point )
1089 af_iup_interp( last_touched + 1, end_point,
1090 last_touched, first_touched );
1092 if ( first_touched > points )
1093 af_iup_interp( first_point, first_touched - 1,
1094 last_touched, first_touched );
1101 /* now save the interpolated values back to x/y */
1102 if ( dim == AF_DIMENSION_HORZ )
1104 for ( point = points; point < point_limit; point++ )
1105 point->x = point->u;
1109 for ( point = points; point < point_limit; point++ )
1110 point->y = point->u;
1115 #ifdef AF_USE_WARPER
1117 FT_LOCAL_DEF( void )
1118 af_glyph_hints_scale_dim( AF_GlyphHints hints,
1123 AF_Point points = hints->points;
1124 AF_Point points_limit = points + hints->num_points;
1128 if ( dim == AF_DIMENSION_HORZ )
1130 for ( point = points; point < points_limit; point++ )
1131 point->x = FT_MulFix( point->fx, scale ) + delta;
1135 for ( point = points; point < points_limit; point++ )
1136 point->y = FT_MulFix( point->fy, scale ) + delta;
1140 #endif /* AF_USE_WARPER */