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 */