1 /***************************************************************************/
5 /* FreeType outline management (body). */
7 /* Copyright 1996-2008, 2010, 2012 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 /***************************************************************************/
19 /*************************************************************************/
21 /* All functions are declared in freetype.h. */
23 /*************************************************************************/
28 #include FT_INTERNAL_OBJECTS_H
29 #include FT_INTERNAL_DEBUG_H
30 #include FT_TRIGONOMETRY_H
33 /*************************************************************************/
35 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */
36 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
37 /* messages during execution. */
40 #define FT_COMPONENT trace_outline
44 const FT_Outline null_outline = { 0, 0, 0, 0, 0, 0 };
47 /* documentation is in ftoutln.h */
49 FT_EXPORT_DEF( FT_Error )
50 FT_Outline_Decompose( FT_Outline* outline,
51 const FT_Outline_Funcs* func_interface,
55 #define SCALED( x ) ( ( (x) << shift ) - delta )
67 FT_Int n; /* index of contour in outline */
68 FT_UInt first; /* index of first point in contour */
69 FT_Int tag; /* current point's state */
75 if ( !outline || !func_interface )
76 return FT_Err_Invalid_Argument;
78 shift = func_interface->shift;
79 delta = func_interface->delta;
82 for ( n = 0; n < outline->n_contours; n++ )
84 FT_Int last; /* index of last point in contour */
87 FT_TRACE5(( "FT_Outline_Decompose: Outline %d\n", n ));
89 last = outline->contours[n];
92 limit = outline->points + last;
94 v_start = outline->points[first];
95 v_start.x = SCALED( v_start.x );
96 v_start.y = SCALED( v_start.y );
98 v_last = outline->points[last];
99 v_last.x = SCALED( v_last.x );
100 v_last.y = SCALED( v_last.y );
104 point = outline->points + first;
105 tags = outline->tags + first;
106 tag = FT_CURVE_TAG( tags[0] );
108 /* A contour cannot start with a cubic control point! */
109 if ( tag == FT_CURVE_TAG_CUBIC )
110 goto Invalid_Outline;
112 /* check first point to determine origin */
113 if ( tag == FT_CURVE_TAG_CONIC )
115 /* first point is conic control. Yes, this happens. */
116 if ( FT_CURVE_TAG( outline->tags[last] ) == FT_CURVE_TAG_ON )
118 /* start at last point if it is on the curve */
124 /* if both first and last points are conic, */
125 /* start at their middle and record its position */
127 v_start.x = ( v_start.x + v_last.x ) / 2;
128 v_start.y = ( v_start.y + v_last.y ) / 2;
136 FT_TRACE5(( " move to (%.2f, %.2f)\n",
137 v_start.x / 64.0, v_start.y / 64.0 ));
138 error = func_interface->move_to( &v_start, user );
142 while ( point < limit )
147 tag = FT_CURVE_TAG( tags[0] );
150 case FT_CURVE_TAG_ON: /* emit a single line_to */
155 vec.x = SCALED( point->x );
156 vec.y = SCALED( point->y );
158 FT_TRACE5(( " line to (%.2f, %.2f)\n",
159 vec.x / 64.0, vec.y / 64.0 ));
160 error = func_interface->line_to( &vec, user );
166 case FT_CURVE_TAG_CONIC: /* consume conic arcs */
167 v_control.x = SCALED( point->x );
168 v_control.y = SCALED( point->y );
179 tag = FT_CURVE_TAG( tags[0] );
181 vec.x = SCALED( point->x );
182 vec.y = SCALED( point->y );
184 if ( tag == FT_CURVE_TAG_ON )
186 FT_TRACE5(( " conic to (%.2f, %.2f)"
187 " with control (%.2f, %.2f)\n",
188 vec.x / 64.0, vec.y / 64.0,
189 v_control.x / 64.0, v_control.y / 64.0 ));
190 error = func_interface->conic_to( &v_control, &vec, user );
196 if ( tag != FT_CURVE_TAG_CONIC )
197 goto Invalid_Outline;
199 v_middle.x = ( v_control.x + vec.x ) / 2;
200 v_middle.y = ( v_control.y + vec.y ) / 2;
202 FT_TRACE5(( " conic to (%.2f, %.2f)"
203 " with control (%.2f, %.2f)\n",
204 v_middle.x / 64.0, v_middle.y / 64.0,
205 v_control.x / 64.0, v_control.y / 64.0 ));
206 error = func_interface->conic_to( &v_control, &v_middle, user );
214 FT_TRACE5(( " conic to (%.2f, %.2f)"
215 " with control (%.2f, %.2f)\n",
216 v_start.x / 64.0, v_start.y / 64.0,
217 v_control.x / 64.0, v_control.y / 64.0 ));
218 error = func_interface->conic_to( &v_control, &v_start, user );
221 default: /* FT_CURVE_TAG_CUBIC */
223 FT_Vector vec1, vec2;
226 if ( point + 1 > limit ||
227 FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC )
228 goto Invalid_Outline;
233 vec1.x = SCALED( point[-2].x );
234 vec1.y = SCALED( point[-2].y );
236 vec2.x = SCALED( point[-1].x );
237 vec2.y = SCALED( point[-1].y );
239 if ( point <= limit )
244 vec.x = SCALED( point->x );
245 vec.y = SCALED( point->y );
247 FT_TRACE5(( " cubic to (%.2f, %.2f)"
248 " with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
249 vec.x / 64.0, vec.y / 64.0,
250 vec1.x / 64.0, vec1.y / 64.0,
251 vec2.x / 64.0, vec2.y / 64.0 ));
252 error = func_interface->cubic_to( &vec1, &vec2, &vec, user );
258 FT_TRACE5(( " cubic to (%.2f, %.2f)"
259 " with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
260 v_start.x / 64.0, v_start.y / 64.0,
261 vec1.x / 64.0, vec1.y / 64.0,
262 vec2.x / 64.0, vec2.y / 64.0 ));
263 error = func_interface->cubic_to( &vec1, &vec2, &v_start, user );
269 /* close the contour with a line segment */
270 FT_TRACE5(( " line to (%.2f, %.2f)\n",
271 v_start.x / 64.0, v_start.y / 64.0 ));
272 error = func_interface->line_to( &v_start, user );
281 FT_TRACE5(( "FT_Outline_Decompose: Done\n", n ));
285 FT_TRACE5(( "FT_Outline_Decompose: Error %d\n", error ));
289 return FT_Err_Invalid_Outline;
293 FT_EXPORT_DEF( FT_Error )
294 FT_Outline_New_Internal( FT_Memory memory,
297 FT_Outline *anoutline )
302 if ( !anoutline || !memory )
303 return FT_Err_Invalid_Argument;
305 *anoutline = null_outline;
307 if ( FT_NEW_ARRAY( anoutline->points, numPoints ) ||
308 FT_NEW_ARRAY( anoutline->tags, numPoints ) ||
309 FT_NEW_ARRAY( anoutline->contours, numContours ) )
312 anoutline->n_points = (FT_UShort)numPoints;
313 anoutline->n_contours = (FT_Short)numContours;
314 anoutline->flags |= FT_OUTLINE_OWNER;
319 anoutline->flags |= FT_OUTLINE_OWNER;
320 FT_Outline_Done_Internal( memory, anoutline );
326 /* documentation is in ftoutln.h */
328 FT_EXPORT_DEF( FT_Error )
329 FT_Outline_New( FT_Library library,
332 FT_Outline *anoutline )
335 return FT_Err_Invalid_Library_Handle;
337 return FT_Outline_New_Internal( library->memory, numPoints,
338 numContours, anoutline );
342 /* documentation is in ftoutln.h */
344 FT_EXPORT_DEF( FT_Error )
345 FT_Outline_Check( FT_Outline* outline )
349 FT_Int n_points = outline->n_points;
350 FT_Int n_contours = outline->n_contours;
356 if ( n_points == 0 && n_contours == 0 )
359 /* check point and contour counts */
360 if ( n_points <= 0 || n_contours <= 0 )
364 for ( n = 0; n < n_contours; n++ )
366 end = outline->contours[n];
368 /* note that we don't accept empty contours */
369 if ( end <= end0 || end >= n_points )
375 if ( end != n_points - 1 )
378 /* XXX: check the tags array */
383 return FT_Err_Invalid_Argument;
387 /* documentation is in ftoutln.h */
389 FT_EXPORT_DEF( FT_Error )
390 FT_Outline_Copy( const FT_Outline* source,
396 if ( !source || !target ||
397 source->n_points != target->n_points ||
398 source->n_contours != target->n_contours )
399 return FT_Err_Invalid_Argument;
401 if ( source == target )
404 FT_ARRAY_COPY( target->points, source->points, source->n_points );
406 FT_ARRAY_COPY( target->tags, source->tags, source->n_points );
408 FT_ARRAY_COPY( target->contours, source->contours, source->n_contours );
410 /* copy all flags, except the `FT_OUTLINE_OWNER' one */
411 is_owner = target->flags & FT_OUTLINE_OWNER;
412 target->flags = source->flags;
414 target->flags &= ~FT_OUTLINE_OWNER;
415 target->flags |= is_owner;
421 FT_EXPORT_DEF( FT_Error )
422 FT_Outline_Done_Internal( FT_Memory memory,
423 FT_Outline* outline )
425 if ( memory && outline )
427 if ( outline->flags & FT_OUTLINE_OWNER )
429 FT_FREE( outline->points );
430 FT_FREE( outline->tags );
431 FT_FREE( outline->contours );
433 *outline = null_outline;
438 return FT_Err_Invalid_Argument;
442 /* documentation is in ftoutln.h */
444 FT_EXPORT_DEF( FT_Error )
445 FT_Outline_Done( FT_Library library,
446 FT_Outline* outline )
448 /* check for valid `outline' in FT_Outline_Done_Internal() */
451 return FT_Err_Invalid_Library_Handle;
453 return FT_Outline_Done_Internal( library->memory, outline );
457 /* documentation is in ftoutln.h */
459 FT_EXPORT_DEF( void )
460 FT_Outline_Get_CBox( const FT_Outline* outline,
463 FT_Pos xMin, yMin, xMax, yMax;
466 if ( outline && acbox )
468 if ( outline->n_points == 0 )
477 FT_Vector* vec = outline->points;
478 FT_Vector* limit = vec + outline->n_points;
481 xMin = xMax = vec->x;
482 yMin = yMax = vec->y;
485 for ( ; vec < limit; vec++ )
491 if ( x < xMin ) xMin = x;
492 if ( x > xMax ) xMax = x;
495 if ( y < yMin ) yMin = y;
496 if ( y > yMax ) yMax = y;
507 /* documentation is in ftoutln.h */
509 FT_EXPORT_DEF( void )
510 FT_Outline_Translate( const FT_Outline* outline,
521 vec = outline->points;
523 for ( n = 0; n < outline->n_points; n++ )
532 /* documentation is in ftoutln.h */
534 FT_EXPORT_DEF( void )
535 FT_Outline_Reverse( FT_Outline* outline )
546 for ( n = 0; n < outline->n_contours; n++ )
548 last = outline->contours[n];
550 /* reverse point table */
552 FT_Vector* p = outline->points + first;
553 FT_Vector* q = outline->points + last;
567 /* reverse tags table */
569 char* p = outline->tags + first;
570 char* q = outline->tags + last;
587 outline->flags ^= FT_OUTLINE_REVERSE_FILL;
591 /* documentation is in ftoutln.h */
593 FT_EXPORT_DEF( FT_Error )
594 FT_Outline_Render( FT_Library library,
596 FT_Raster_Params* params )
599 FT_Bool update = FALSE;
600 FT_Renderer renderer;
605 return FT_Err_Invalid_Library_Handle;
607 if ( !outline || !params )
608 return FT_Err_Invalid_Argument;
610 renderer = library->cur_renderer;
611 node = library->renderers.head;
613 params->source = (void*)outline;
615 error = FT_Err_Cannot_Render_Glyph;
618 error = renderer->raster_render( renderer->raster, params );
619 if ( !error || FT_ERROR_BASE( error ) != FT_Err_Cannot_Render_Glyph )
622 /* FT_Err_Cannot_Render_Glyph is returned if the render mode */
623 /* is unsupported by the current renderer for this glyph image */
626 /* now, look for another renderer that supports the same */
628 renderer = FT_Lookup_Renderer( library, FT_GLYPH_FORMAT_OUTLINE,
633 /* if we changed the current renderer for the glyph image format */
634 /* we need to select it as the next current one */
635 if ( !error && update && renderer )
636 FT_Set_Renderer( library, renderer, 0, 0 );
642 /* documentation is in ftoutln.h */
644 FT_EXPORT_DEF( FT_Error )
645 FT_Outline_Get_Bitmap( FT_Library library,
647 const FT_Bitmap *abitmap )
649 FT_Raster_Params params;
653 return FT_Err_Invalid_Argument;
655 /* other checks are delayed to FT_Outline_Render() */
657 params.target = abitmap;
660 if ( abitmap->pixel_mode == FT_PIXEL_MODE_GRAY ||
661 abitmap->pixel_mode == FT_PIXEL_MODE_LCD ||
662 abitmap->pixel_mode == FT_PIXEL_MODE_LCD_V )
663 params.flags |= FT_RASTER_FLAG_AA;
665 return FT_Outline_Render( library, outline, ¶ms );
669 /* documentation is in freetype.h */
671 FT_EXPORT_DEF( void )
672 FT_Vector_Transform( FT_Vector* vector,
673 const FT_Matrix* matrix )
678 if ( !vector || !matrix )
681 xz = FT_MulFix( vector->x, matrix->xx ) +
682 FT_MulFix( vector->y, matrix->xy );
684 yz = FT_MulFix( vector->x, matrix->yx ) +
685 FT_MulFix( vector->y, matrix->yy );
692 /* documentation is in ftoutln.h */
694 FT_EXPORT_DEF( void )
695 FT_Outline_Transform( const FT_Outline* outline,
696 const FT_Matrix* matrix )
702 if ( !outline || !matrix )
705 vec = outline->points;
706 limit = vec + outline->n_points;
708 for ( ; vec < limit; vec++ )
709 FT_Vector_Transform( vec, matrix );
715 #define FT_OUTLINE_GET_CONTOUR( outline, c, first, last ) \
717 (first) = ( c > 0 ) ? (outline)->points + \
718 (outline)->contours[c - 1] + 1 \
719 : (outline)->points; \
720 (last) = (outline)->points + (outline)->contours[c]; \
724 /* Is a point in some contour? */
726 /* We treat every point of the contour as if it */
727 /* it were ON. That is, we allow false positives, */
728 /* but disallow false negatives. (XXX really?) */
730 ft_contour_has( FT_Outline* outline,
741 FT_OUTLINE_GET_CONTOUR( outline, c, first, last );
743 for ( a = first; a <= last; a++ )
749 b = ( a == last ) ? first : a + 1;
751 intersect = ( a->y - point->y ) ^ ( b->y - point->y );
753 /* a and b are on the same side */
754 if ( intersect >= 0 )
756 if ( intersect == 0 && a->y == point->y )
758 if ( ( a->x <= point->x && b->x >= point->x ) ||
759 ( a->x >= point->x && b->x <= point->x ) )
766 x = a->x + ( b->x - a->x ) * (point->y - a->y ) / ( b->y - a->y );
770 else if ( x == point->x )
779 ft_contour_enclosed( FT_Outline* outline,
787 FT_OUTLINE_GET_CONTOUR( outline, c, first, last );
789 for ( i = 0; i < outline->n_contours; i++ )
791 if ( i != c && ft_contour_has( outline, i, first ) )
796 for ( pt = first + 1; pt <= last; pt++ )
797 if ( !ft_contour_has( outline, i, pt ) )
808 /* This version differs from the public one in that each */
809 /* part (contour not enclosed in another contour) of the */
810 /* outline is checked for orientation. This is */
811 /* necessary for some buggy CJK fonts. */
812 static FT_Orientation
813 ft_outline_get_orientation( FT_Outline* outline )
818 FT_Orientation orient = FT_ORIENTATION_NONE;
821 first = outline->points;
822 for ( i = 0; i < outline->n_contours; i++, first = last + 1 )
825 FT_Vector* xmin_point;
829 last = outline->points + outline->contours[i];
831 /* skip degenerate contours */
832 if ( last < first + 2 )
835 if ( ft_contour_enclosed( outline, i ) )
841 for ( point = first + 1; point <= last; point++ )
843 if ( point->x < xmin )
850 /* check the orientation of the contour */
857 prev = ( xmin_point == first ) ? last : xmin_point - 1;
858 next = ( xmin_point == last ) ? first : xmin_point + 1;
860 if ( FT_Atan2( prev->x - xmin_point->x, prev->y - xmin_point->y ) >
861 FT_Atan2( next->x - xmin_point->x, next->y - xmin_point->y ) )
862 o = FT_ORIENTATION_POSTSCRIPT;
864 o = FT_ORIENTATION_TRUETYPE;
866 if ( orient == FT_ORIENTATION_NONE )
868 else if ( orient != o )
869 return FT_ORIENTATION_NONE;
879 /* documentation is in ftoutln.h */
881 FT_EXPORT_DEF( FT_Error )
882 FT_Outline_Embolden( FT_Outline* outline,
886 FT_Vector v_prev, v_first, v_next, v_cur;
887 FT_Angle rotate, angle_in, angle_out;
893 return FT_Err_Invalid_Argument;
899 orientation = FT_Outline_Get_Orientation( outline );
900 if ( orientation == FT_ORIENTATION_NONE )
902 if ( outline->n_contours )
903 return FT_Err_Invalid_Argument;
908 if ( orientation == FT_ORIENTATION_TRUETYPE )
909 rotate = -FT_ANGLE_PI2;
911 rotate = FT_ANGLE_PI2;
913 points = outline->points;
916 for ( c = 0; c < outline->n_contours; c++ )
918 int last = outline->contours[c];
921 v_first = points[first];
922 v_prev = points[last];
925 for ( n = first; n <= last; n++ )
934 v_next = points[n + 1];
938 /* compute the in and out vectors */
939 in.x = v_cur.x - v_prev.x;
940 in.y = v_cur.y - v_prev.y;
942 out.x = v_next.x - v_cur.x;
943 out.y = v_next.y - v_cur.y;
945 angle_in = FT_Atan2( in.x, in.y );
946 angle_out = FT_Atan2( out.x, out.y );
947 angle_diff = FT_Angle_Diff( angle_in, angle_out );
948 scale = FT_Cos( angle_diff / 2 );
950 if ( scale < 0x4000L && scale > -0x4000L )
954 d = FT_DivFix( strength, scale );
956 FT_Vector_From_Polar( &in, d, angle_in + angle_diff / 2 - rotate );
959 outline->points[n].x = v_cur.x + strength + in.x;
960 outline->points[n].y = v_cur.y + strength + in.y;
973 /* documentation is in ftoutln.h */
975 FT_EXPORT_DEF( FT_Orientation )
976 FT_Outline_Get_Orientation( FT_Outline* outline )
978 FT_Pos xmin = 32768L;
979 FT_Pos xmin_ymin = 32768L;
980 FT_Pos xmin_ymax = -32768L;
981 FT_Vector* xmin_first = NULL;
982 FT_Vector* xmin_last = NULL;
993 FT_Orientation result[3] =
994 { FT_ORIENTATION_NONE, FT_ORIENTATION_NONE, FT_ORIENTATION_NONE };
997 if ( !outline || outline->n_points <= 0 )
998 return FT_ORIENTATION_TRUETYPE;
1000 /* We use the nonzero winding rule to find the orientation. */
1001 /* Since glyph outlines behave much more `regular' than arbitrary */
1002 /* cubic or quadratic curves, this test deals with the polygon */
1003 /* only which is spanned up by the control points. */
1005 first = outline->points;
1006 for ( contour = outline->contours;
1007 contour < outline->contours + outline->n_contours;
1008 contour++, first = last + 1 )
1010 FT_Pos contour_xmin = 32768L;
1011 FT_Pos contour_xmax = -32768L;
1012 FT_Pos contour_ymin = 32768L;
1013 FT_Pos contour_ymax = -32768L;
1016 last = outline->points + *contour;
1018 /* skip degenerate contours */
1019 if ( last < first + 2 )
1022 for ( point = first; point <= last; ++point )
1024 if ( point->x < contour_xmin )
1025 contour_xmin = point->x;
1027 if ( point->x > contour_xmax )
1028 contour_xmax = point->x;
1030 if ( point->y < contour_ymin )
1031 contour_ymin = point->y;
1033 if ( point->y > contour_ymax )
1034 contour_ymax = point->y;
1037 if ( contour_xmin < xmin &&
1038 contour_xmin != contour_xmax &&
1039 contour_ymin != contour_ymax )
1041 xmin = contour_xmin;
1042 xmin_ymin = contour_ymin;
1043 xmin_ymax = contour_ymax;
1049 if ( xmin == 32768L )
1050 return FT_ORIENTATION_TRUETYPE;
1052 ray_y[0] = ( xmin_ymin * 3 + xmin_ymax ) >> 2;
1053 ray_y[1] = ( xmin_ymin + xmin_ymax ) >> 1;
1054 ray_y[2] = ( xmin_ymin + xmin_ymax * 3 ) >> 2;
1056 for ( i = 0; i < 3; i++ )
1070 left1 = left2 = right1 = right2 = NULL;
1073 for ( point = xmin_first; point <= xmin_last; prev = point, ++point )
1078 if ( point->y == ray_y[i] || prev->y == ray_y[i] )
1084 if ( ( point->y < ray_y[i] && prev->y < ray_y[i] ) ||
1085 ( point->y > ray_y[i] && prev->y > ray_y[i] ) )
1088 tmp_x = FT_MulDiv( point->x - prev->x,
1090 point->y - prev->y ) + prev->x;
1092 if ( tmp_x < left_x )
1099 if ( tmp_x > right_x )
1107 if ( left1 && right1 )
1109 if ( left1->y < left2->y && right1->y > right2->y )
1110 result[i] = FT_ORIENTATION_TRUETYPE;
1111 else if ( left1->y > left2->y && right1->y < right2->y )
1112 result[i] = FT_ORIENTATION_POSTSCRIPT;
1114 result[i] = FT_ORIENTATION_NONE;
1118 if ( result[0] != FT_ORIENTATION_NONE &&
1119 ( result[0] == result[1] || result[0] == result[2] ) )
1122 if ( result[1] != FT_ORIENTATION_NONE && result[1] == result[2] )
1125 return FT_ORIENTATION_TRUETYPE;