1 /****************************************************************************
2 *
3 * ftstroke.c
4 *
5 * FreeType path stroker (body).
6 *
7 * Copyright (C) 2002-2023 by
8 * David Turner, Robert Wilhelm, and Werner Lemberg.
9 *
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.
15 *
16 */
17
18
19 #include <freetype/ftstroke.h>
20 #include <freetype/fttrigon.h>
21 #include <freetype/ftoutln.h>
22 #include <freetype/internal/ftmemory.h>
23 #include <freetype/internal/ftdebug.h>
24 #include <freetype/internal/ftobjs.h>
25
26
27 /* declare an extern to access `ft_outline_glyph_class' globally */
28 /* allocated in `ftglyph.c' */
29 FT_CALLBACK_TABLE const FT_Glyph_Class ft_outline_glyph_class;
30
31
32 /* documentation is in ftstroke.h */
33
34 FT_EXPORT_DEF( FT_StrokerBorder )
35 FT_Outline_GetInsideBorder( FT_Outline* outline )
36 {
37 FT_Orientation o = FT_Outline_Get_Orientation( outline );
38
39
40 return o == FT_ORIENTATION_TRUETYPE ? FT_STROKER_BORDER_RIGHT
41 : FT_STROKER_BORDER_LEFT;
42 }
43
44
45 /* documentation is in ftstroke.h */
46
47 FT_EXPORT_DEF( FT_StrokerBorder )
48 FT_Outline_GetOutsideBorder( FT_Outline* outline )
49 {
50 FT_Orientation o = FT_Outline_Get_Orientation( outline );
51
52
53 return o == FT_ORIENTATION_TRUETYPE ? FT_STROKER_BORDER_LEFT
54 : FT_STROKER_BORDER_RIGHT;
55 }
56
57
58 /*************************************************************************/
59 /*************************************************************************/
60 /***** *****/
61 /***** BEZIER COMPUTATIONS *****/
62 /***** *****/
63 /*************************************************************************/
64 /*************************************************************************/
65
66 #define FT_SMALL_CONIC_THRESHOLD ( FT_ANGLE_PI / 6 )
67 #define FT_SMALL_CUBIC_THRESHOLD ( FT_ANGLE_PI / 8 )
68
69 #define FT_EPSILON 2
70
71 #define FT_IS_SMALL( x ) ( (x) > -FT_EPSILON && (x) < FT_EPSILON )
72
73
74 static FT_Pos
75 ft_pos_abs( FT_Pos x )
76 {
77 return x >= 0 ? x : -x;
78 }
79
80
81 static void
82 ft_conic_split( FT_Vector* base )
83 {
84 FT_Pos a, b;
85
86
87 base[4].x = base[2].x;
88 a = base[0].x + base[1].x;
89 b = base[1].x + base[2].x;
90 base[3].x = b >> 1;
91 base[2].x = ( a + b ) >> 2;
92 base[1].x = a >> 1;
93
94 base[4].y = base[2].y;
95 a = base[0].y + base[1].y;
96 b = base[1].y + base[2].y;
97 base[3].y = b >> 1;
98 base[2].y = ( a + b ) >> 2;
99 base[1].y = a >> 1;
100 }
101
102
103 static FT_Bool
104 ft_conic_is_small_enough( FT_Vector* base,
105 FT_Angle *angle_in,
106 FT_Angle *angle_out )
107 {
108 FT_Vector d1, d2;
109 FT_Angle theta;
110 FT_Int close1, close2;
111
112
113 d1.x = base[1].x - base[2].x;
114 d1.y = base[1].y - base[2].y;
115 d2.x = base[0].x - base[1].x;
116 d2.y = base[0].y - base[1].y;
117
118 close1 = FT_IS_SMALL( d1.x ) && FT_IS_SMALL( d1.y );
119 close2 = FT_IS_SMALL( d2.x ) && FT_IS_SMALL( d2.y );
120
121 if ( close1 )
122 {
123 if ( close2 )
124 {
125 /* basically a point; */
126 /* do nothing to retain original direction */
127 }
128 else
129 {
130 *angle_in =
131 *angle_out = FT_Atan2( d2.x, d2.y );
132 }
133 }
134 else /* !close1 */
135 {
136 if ( close2 )
137 {
138 *angle_in =
139 *angle_out = FT_Atan2( d1.x, d1.y );
140 }
141 else
142 {
143 *angle_in = FT_Atan2( d1.x, d1.y );
144 *angle_out = FT_Atan2( d2.x, d2.y );
145 }
146 }
147
148 theta = ft_pos_abs( FT_Angle_Diff( *angle_in, *angle_out ) );
149
150 return FT_BOOL( theta < FT_SMALL_CONIC_THRESHOLD );
151 }
152
153
154 static void
155 ft_cubic_split( FT_Vector* base )
156 {
157 FT_Pos a, b, c;
158
159
160 base[6].x = base[3].x;
161 a = base[0].x + base[1].x;
162 b = base[1].x + base[2].x;
163 c = base[2].x + base[3].x;
164 base[5].x = c >> 1;
165 c += b;
166 base[4].x = c >> 2;
167 base[1].x = a >> 1;
168 a += b;
169 base[2].x = a >> 2;
170 base[3].x = ( a + c ) >> 3;
171
172 base[6].y = base[3].y;
173 a = base[0].y + base[1].y;
174 b = base[1].y + base[2].y;
175 c = base[2].y + base[3].y;
176 base[5].y = c >> 1;
177 c += b;
178 base[4].y = c >> 2;
179 base[1].y = a >> 1;
180 a += b;
181 base[2].y = a >> 2;
182 base[3].y = ( a + c ) >> 3;
183 }
184
185
186 /* Return the average of `angle1' and `angle2'. */
187 /* This gives correct result even if `angle1' and `angle2' */
188 /* have opposite signs. */
189 static FT_Angle
190 ft_angle_mean( FT_Angle angle1,
191 FT_Angle angle2 )
192 {
193 return angle1 + FT_Angle_Diff( angle1, angle2 ) / 2;
194 }
195
196
197 static FT_Bool
198 ft_cubic_is_small_enough( FT_Vector* base,
199 FT_Angle *angle_in,
200 FT_Angle *angle_mid,
201 FT_Angle *angle_out )
202 {
203 FT_Vector d1, d2, d3;
204 FT_Angle theta1, theta2;
205 FT_Int close1, close2, close3;
206
207
208 d1.x = base[2].x - base[3].x;
209 d1.y = base[2].y - base[3].y;
210 d2.x = base[1].x - base[2].x;
211 d2.y = base[1].y - base[2].y;
212 d3.x = base[0].x - base[1].x;
213 d3.y = base[0].y - base[1].y;
214
215 close1 = FT_IS_SMALL( d1.x ) && FT_IS_SMALL( d1.y );
216 close2 = FT_IS_SMALL( d2.x ) && FT_IS_SMALL( d2.y );
217 close3 = FT_IS_SMALL( d3.x ) && FT_IS_SMALL( d3.y );
218
219 if ( close1 )
220 {
221 if ( close2 )
222 {
223 if ( close3 )
224 {
225 /* basically a point; */
226 /* do nothing to retain original direction */
227 }
228 else /* !close3 */
229 {
230 *angle_in =
231 *angle_mid =
232 *angle_out = FT_Atan2( d3.x, d3.y );
233 }
234 }
235 else /* !close2 */
236 {
237 if ( close3 )
238 {
239 *angle_in =
240 *angle_mid =
241 *angle_out = FT_Atan2( d2.x, d2.y );
242 }
243 else /* !close3 */
244 {
245 *angle_in =
246 *angle_mid = FT_Atan2( d2.x, d2.y );
247 *angle_out = FT_Atan2( d3.x, d3.y );
248 }
249 }
250 }
251 else /* !close1 */
252 {
253 if ( close2 )
254 {
255 if ( close3 )
256 {
257 *angle_in =
258 *angle_mid =
259 *angle_out = FT_Atan2( d1.x, d1.y );
260 }
261 else /* !close3 */
262 {
263 *angle_in = FT_Atan2( d1.x, d1.y );
264 *angle_out = FT_Atan2( d3.x, d3.y );
265 *angle_mid = ft_angle_mean( *angle_in, *angle_out );
266 }
267 }
268 else /* !close2 */
269 {
270 if ( close3 )
271 {
272 *angle_in = FT_Atan2( d1.x, d1.y );
273 *angle_mid =
274 *angle_out = FT_Atan2( d2.x, d2.y );
275 }
276 else /* !close3 */
277 {
278 *angle_in = FT_Atan2( d1.x, d1.y );
279 *angle_mid = FT_Atan2( d2.x, d2.y );
280 *angle_out = FT_Atan2( d3.x, d3.y );
281 }
282 }
283 }
284
285 theta1 = ft_pos_abs( FT_Angle_Diff( *angle_in, *angle_mid ) );
286 theta2 = ft_pos_abs( FT_Angle_Diff( *angle_mid, *angle_out ) );
287
288 return FT_BOOL( theta1 < FT_SMALL_CUBIC_THRESHOLD &&
289 theta2 < FT_SMALL_CUBIC_THRESHOLD );
290 }
291
292
293 /*************************************************************************/
294 /*************************************************************************/
295 /***** *****/
296 /***** STROKE BORDERS *****/
297 /***** *****/
298 /*************************************************************************/
299 /*************************************************************************/
300
301 typedef enum FT_StrokeTags_
302 {
303 FT_STROKE_TAG_ON = 1, /* on-curve point */
304 FT_STROKE_TAG_CUBIC = 2, /* cubic off-point */
305 FT_STROKE_TAG_BEGIN = 4, /* sub-path start */
306 FT_STROKE_TAG_END = 8 /* sub-path end */
307
308 } FT_StrokeTags;
309
310 #define FT_STROKE_TAG_BEGIN_END ( FT_STROKE_TAG_BEGIN | FT_STROKE_TAG_END )
311
312 typedef struct FT_StrokeBorderRec_
313 {
314 FT_UInt num_points;
315 FT_UInt max_points;
316 FT_Vector* points;
317 FT_Byte* tags;
318 FT_Bool movable; /* TRUE for ends of lineto borders */
319 FT_Int start; /* index of current sub-path start point */
320 FT_Memory memory;
321 FT_Bool valid;
322
323 } FT_StrokeBorderRec, *FT_StrokeBorder;
324
325
326 static FT_Error
327 ft_stroke_border_grow( FT_StrokeBorder border,
328 FT_UInt new_points )
329 {
330 FT_UInt old_max = border->max_points;
331 FT_UInt new_max = border->num_points + new_points;
332 FT_Error error = FT_Err_Ok;
333
334
335 if ( new_max > old_max )
336 {
337 FT_UInt cur_max = old_max;
338 FT_Memory memory = border->memory;
339
340
341 while ( cur_max < new_max )
342 cur_max += ( cur_max >> 1 ) + 16;
343
344 if ( FT_RENEW_ARRAY( border->points, old_max, cur_max ) ||
345 FT_RENEW_ARRAY( border->tags, old_max, cur_max ) )
346 goto Exit;
347
348 border->max_points = cur_max;
349 }
350
351 Exit:
352 return error;
353 }
354
355
356 static void
357 ft_stroke_border_close( FT_StrokeBorder border,
358 FT_Bool reverse )
359 {
360 FT_UInt start = (FT_UInt)border->start;
361 FT_UInt count = border->num_points;
362
363
364 FT_ASSERT( border->start >= 0 );
365
366 /* don't record empty paths! */
367 if ( count <= start + 1U )
368 border->num_points = start;
369 else
370 {
371 /* copy the last point to the start of this sub-path, since */
372 /* it contains the `adjusted' starting coordinates */
373 border->num_points = --count;
374 border->points[start] = border->points[count];
375 border->tags[start] = border->tags[count];
376
377 if ( reverse )
378 {
379 /* reverse the points */
380 {
381 FT_Vector* vec1 = border->points + start + 1;
382 FT_Vector* vec2 = border->points + count - 1;
383
384
385 for ( ; vec1 < vec2; vec1++, vec2-- )
386 {
387 FT_Vector tmp;
388
389
390 tmp = *vec1;
391 *vec1 = *vec2;
392 *vec2 = tmp;
393 }
394 }
395
396 /* then the tags */
397 {
398 FT_Byte* tag1 = border->tags + start + 1;
399 FT_Byte* tag2 = border->tags + count - 1;
400
401
402 for ( ; tag1 < tag2; tag1++, tag2-- )
403 {
404 FT_Byte tmp;
405
406
407 tmp = *tag1;
408 *tag1 = *tag2;
409 *tag2 = tmp;
410 }
411 }
412 }
413
414 border->tags[start ] |= FT_STROKE_TAG_BEGIN;
415 border->tags[count - 1] |= FT_STROKE_TAG_END;
416 }
417
418 border->start = -1;
419 border->movable = FALSE;
420 }
421
422
423 static FT_Error
424 ft_stroke_border_lineto( FT_StrokeBorder border,
425 FT_Vector* to,
426 FT_Bool movable )
427 {
428 FT_Error error = FT_Err_Ok;
429
430
431 FT_ASSERT( border->start >= 0 );
432
433 if ( border->movable )
434 {
435 /* move last point */
436 border->points[border->num_points - 1] = *to;
437 }
438 else
439 {
440 /* don't add zero-length lineto, but always add moveto */
441 if ( border->num_points > (FT_UInt)border->start &&
442 FT_IS_SMALL( border->points[border->num_points - 1].x - to->x ) &&
443 FT_IS_SMALL( border->points[border->num_points - 1].y - to->y ) )
444 return error;
445
446 /* add one point */
447 error = ft_stroke_border_grow( border, 1 );
448 if ( !error )
449 {
450 FT_Vector* vec = border->points + border->num_points;
451 FT_Byte* tag = border->tags + border->num_points;
452
453
454 vec[0] = *to;
455 tag[0] = FT_STROKE_TAG_ON;
456
457 border->num_points += 1;
458 }
459 }
460 border->movable = movable;
461 return error;
462 }
463
464
465 static FT_Error
466 ft_stroke_border_conicto( FT_StrokeBorder border,
467 FT_Vector* control,
468 FT_Vector* to )
469 {
470 FT_Error error;
471
472
473 FT_ASSERT( border->start >= 0 );
474
475 error = ft_stroke_border_grow( border, 2 );
476 if ( !error )
477 {
478 FT_Vector* vec = border->points + border->num_points;
479 FT_Byte* tag = border->tags + border->num_points;
480
481
482 vec[0] = *control;
483 vec[1] = *to;
484
485 tag[0] = 0;
486 tag[1] = FT_STROKE_TAG_ON;
487
488 border->num_points += 2;
489 }
490
491 border->movable = FALSE;
492
493 return error;
494 }
495
496
497 static FT_Error
498 ft_stroke_border_cubicto( FT_StrokeBorder border,
499 FT_Vector* control1,
500 FT_Vector* control2,
501 FT_Vector* to )
502 {
503 FT_Error error;
504
505
506 FT_ASSERT( border->start >= 0 );
507
508 error = ft_stroke_border_grow( border, 3 );
509 if ( !error )
510 {
511 FT_Vector* vec = border->points + border->num_points;
512 FT_Byte* tag = border->tags + border->num_points;
513
514
515 vec[0] = *control1;
516 vec[1] = *control2;
517 vec[2] = *to;
518
519 tag[0] = FT_STROKE_TAG_CUBIC;
520 tag[1] = FT_STROKE_TAG_CUBIC;
521 tag[2] = FT_STROKE_TAG_ON;
522
523 border->num_points += 3;
524 }
525
526 border->movable = FALSE;
527
528 return error;
529 }
530
531
532 #define FT_ARC_CUBIC_ANGLE ( FT_ANGLE_PI / 2 )
533
534
535 static FT_Error
536 ft_stroke_border_arcto( FT_StrokeBorder border,
537 FT_Vector* center,
538 FT_Fixed radius,
539 FT_Angle angle_start,
540 FT_Angle angle_diff )
541 {
542 FT_Fixed coef;
543 FT_Vector a0, a1, a2, a3;
544 FT_Int i, arcs = 1;
545 FT_Error error = FT_Err_Ok;
546
547
548 /* number of cubic arcs to draw */
549 while ( angle_diff > FT_ARC_CUBIC_ANGLE * arcs ||
550 -angle_diff > FT_ARC_CUBIC_ANGLE * arcs )
551 arcs++;
552
553 /* control tangents */
554 coef = FT_Tan( angle_diff / ( 4 * arcs ) );
555 coef += coef / 3;
556
557 /* compute start and first control point */
558 FT_Vector_From_Polar( &a0, radius, angle_start );
559 a1.x = FT_MulFix( -a0.y, coef );
560 a1.y = FT_MulFix( a0.x, coef );
561
562 a0.x += center->x;
563 a0.y += center->y;
564 a1.x += a0.x;
565 a1.y += a0.y;
566
567 for ( i = 1; i <= arcs; i++ )
568 {
569 /* compute end and second control point */
570 FT_Vector_From_Polar( &a3, radius,
571 angle_start + i * angle_diff / arcs );
572 a2.x = FT_MulFix( a3.y, coef );
573 a2.y = FT_MulFix( -a3.x, coef );
574
575 a3.x += center->x;
576 a3.y += center->y;
577 a2.x += a3.x;
578 a2.y += a3.y;
579
580 /* add cubic arc */
581 error = ft_stroke_border_cubicto( border, &a1, &a2, &a3 );
582 if ( error )
583 break;
584
585 /* a0 = a3; */
586 a1.x = a3.x - a2.x + a3.x;
587 a1.y = a3.y - a2.y + a3.y;
588 }
589
590 return error;
591 }
592
593
594 static FT_Error
595 ft_stroke_border_moveto( FT_StrokeBorder border,
596 FT_Vector* to )
597 {
598 /* close current open path if any ? */
599 if ( border->start >= 0 )
600 ft_stroke_border_close( border, FALSE );
601
602 border->start = (FT_Int)border->num_points;
603 border->movable = FALSE;
604
605 return ft_stroke_border_lineto( border, to, FALSE );
606 }
607
608
609 static void
610 ft_stroke_border_init( FT_StrokeBorder border,
611 FT_Memory memory )
612 {
613 border->memory = memory;
614 border->points = NULL;
615 border->tags = NULL;
616
617 border->num_points = 0;
618 border->max_points = 0;
619 border->start = -1;
620 border->valid = FALSE;
621 }
622
623
624 static void
625 ft_stroke_border_reset( FT_StrokeBorder border )
626 {
627 border->num_points = 0;
628 border->start = -1;
629 border->valid = FALSE;
630 }
631
632
633 static void
634 ft_stroke_border_done( FT_StrokeBorder border )
635 {
636 FT_Memory memory = border->memory;
637
638
639 FT_FREE( border->points );
640 FT_FREE( border->tags );
641
642 border->num_points = 0;
643 border->max_points = 0;
644 border->start = -1;
645 border->valid = FALSE;
646 }
647
648
649 static FT_Error
650 ft_stroke_border_get_counts( FT_StrokeBorder border,
651 FT_UInt *anum_points,
652 FT_UInt *anum_contours )
653 {
654 FT_Error error = FT_Err_Ok;
655 FT_UInt num_points = 0;
656 FT_UInt num_contours = 0;
657
658 FT_UInt count = border->num_points;
659 FT_Vector* point = border->points;
660 FT_Byte* tags = border->tags;
661 FT_Int in_contour = 0;
662
663
664 for ( ; count > 0; count--, num_points++, point++, tags++ )
665 {
666 if ( tags[0] & FT_STROKE_TAG_BEGIN )
667 {
668 if ( in_contour != 0 )
669 goto Fail;
670
671 in_contour = 1;
672 }
673 else if ( in_contour == 0 )
674 goto Fail;
675
676 if ( tags[0] & FT_STROKE_TAG_END )
677 {
678 in_contour = 0;
679 num_contours++;
680 }
681 }
682
683 if ( in_contour != 0 )
684 goto Fail;
685
686 border->valid = TRUE;
687
688 Exit:
689 *anum_points = num_points;
690 *anum_contours = num_contours;
691 return error;
692
693 Fail:
694 num_points = 0;
695 num_contours = 0;
696 goto Exit;
697 }
698
699
700 static void
701 ft_stroke_border_export( FT_StrokeBorder border,
702 FT_Outline* outline )
703 {
704 /* copy point locations */
705 if ( border->num_points )
706 FT_ARRAY_COPY( outline->points + outline->n_points,
707 border->points,
708 border->num_points );
709
710 /* copy tags */
711 {
712 FT_UInt count = border->num_points;
713 FT_Byte* read = border->tags;
714 FT_Byte* write = (FT_Byte*)outline->tags + outline->n_points;
715
716
717 for ( ; count > 0; count--, read++, write++ )
718 {
719 if ( *read & FT_STROKE_TAG_ON )
720 *write = FT_CURVE_TAG_ON;
721 else if ( *read & FT_STROKE_TAG_CUBIC )
722 *write = FT_CURVE_TAG_CUBIC;
723 else
724 *write = FT_CURVE_TAG_CONIC;
725 }
726 }
727
728 /* copy contours */
729 {
730 FT_UInt count = border->num_points;
731 FT_Byte* tags = border->tags;
732 FT_Short* write = outline->contours + outline->n_contours;
733 FT_Short idx = (FT_Short)outline->n_points;
734
735
736 for ( ; count > 0; count--, tags++, idx++ )
737 {
738 if ( *tags & FT_STROKE_TAG_END )
739 {
740 *write++ = idx;
741 outline->n_contours++;
742 }
743 }
744 }
745
746 outline->n_points += (short)border->num_points;
747
748 FT_ASSERT( FT_Outline_Check( outline ) == 0 );
749 }
750
751
752 /*************************************************************************/
753 /*************************************************************************/
754 /***** *****/
755 /***** STROKER *****/
756 /***** *****/
757 /*************************************************************************/
758 /*************************************************************************/
759
760 #define FT_SIDE_TO_ROTATE( s ) ( FT_ANGLE_PI2 - (s) * FT_ANGLE_PI )
761
762 typedef struct FT_StrokerRec_
763 {
764 FT_Angle angle_in; /* direction into curr join */
765 FT_Angle angle_out; /* direction out of join */
766 FT_Vector center; /* current position */
767 FT_Fixed line_length; /* length of last lineto */
768 FT_Bool first_point; /* is this the start? */
769 FT_Bool subpath_open; /* is the subpath open? */
770 FT_Angle subpath_angle; /* subpath start direction */
771 FT_Vector subpath_start; /* subpath start position */
772 FT_Fixed subpath_line_length; /* subpath start lineto len */
773 FT_Bool handle_wide_strokes; /* use wide strokes logic? */
774
775 FT_Stroker_LineCap line_cap;
776 FT_Stroker_LineJoin line_join;
777 FT_Stroker_LineJoin line_join_saved;
778 FT_Fixed miter_limit;
779 FT_Fixed radius;
780
781 FT_StrokeBorderRec borders[2];
782 FT_Library library;
783
784 } FT_StrokerRec;
785
786
787 /* documentation is in ftstroke.h */
788
789 FT_EXPORT_DEF( FT_Error )
790 FT_Stroker_New( FT_Library library,
791 FT_Stroker *astroker )
792 {
793 FT_Error error; /* assigned in FT_NEW */
794 FT_Memory memory;
795 FT_Stroker stroker = NULL;
796
797
798 if ( !library )
799 return FT_THROW( Invalid_Library_Handle );
800
801 if ( !astroker )
802 return FT_THROW( Invalid_Argument );
803
804 memory = library->memory;
805
806 if ( !FT_NEW( stroker ) )
807 {
808 stroker->library = library;
809
810 ft_stroke_border_init( &stroker->borders[0], memory );
811 ft_stroke_border_init( &stroker->borders[1], memory );
812 }
813
814 *astroker = stroker;
815
816 return error;
817 }
818
819
820 /* documentation is in ftstroke.h */
821
822 FT_EXPORT_DEF( void )
823 FT_Stroker_Set( FT_Stroker stroker,
824 FT_Fixed radius,
825 FT_Stroker_LineCap line_cap,
826 FT_Stroker_LineJoin line_join,
827 FT_Fixed miter_limit )
828 {
829 if ( !stroker )
830 return;
831
832 stroker->radius = radius;
833 stroker->line_cap = line_cap;
834 stroker->line_join = line_join;
835 stroker->miter_limit = miter_limit;
836
837 /* ensure miter limit has sensible value */
838 if ( stroker->miter_limit < 0x10000L )
839 stroker->miter_limit = 0x10000L;
840
841 /* save line join style: */
842 /* line join style can be temporarily changed when stroking curves */
843 stroker->line_join_saved = line_join;
844
845 FT_Stroker_Rewind( stroker );
846 }
847
848
849 /* documentation is in ftstroke.h */
850
851 FT_EXPORT_DEF( void )
852 FT_Stroker_Rewind( FT_Stroker stroker )
853 {
854 if ( stroker )
855 {
856 ft_stroke_border_reset( &stroker->borders[0] );
857 ft_stroke_border_reset( &stroker->borders[1] );
858 }
859 }
860
861
862 /* documentation is in ftstroke.h */
863
864 FT_EXPORT_DEF( void )
865 FT_Stroker_Done( FT_Stroker stroker )
866 {
867 if ( stroker )
868 {
869 FT_Memory memory = stroker->library->memory;
870
871
872 ft_stroke_border_done( &stroker->borders[0] );
873 ft_stroke_border_done( &stroker->borders[1] );
874
875 stroker->library = NULL;
876 FT_FREE( stroker );
877 }
878 }
879
880
881 /* create a circular arc at a corner or cap */
882 static FT_Error
883 ft_stroker_arcto( FT_Stroker stroker,
884 FT_Int side )
885 {
886 FT_Angle total, rotate;
887 FT_Fixed radius = stroker->radius;
888 FT_Error error = FT_Err_Ok;
889 FT_StrokeBorder border = stroker->borders + side;
890
891
892 rotate = FT_SIDE_TO_ROTATE( side );
893
894 total = FT_Angle_Diff( stroker->angle_in, stroker->angle_out );
895 if ( total == FT_ANGLE_PI )
896 total = -rotate * 2;
897
898 error = ft_stroke_border_arcto( border,
899 &stroker->center,
900 radius,
901 stroker->angle_in + rotate,
902 total );
903 border->movable = FALSE;
904 return error;
905 }
906
907
908 /* add a cap at the end of an opened path */
909 static FT_Error
910 ft_stroker_cap( FT_Stroker stroker,
911 FT_Angle angle,
912 FT_Int side )
913 {
914 FT_Error error = FT_Err_Ok;
915
916
917 if ( stroker->line_cap == FT_STROKER_LINECAP_ROUND )
918 {
919 /* add a round cap */
920 stroker->angle_in = angle;
921 stroker->angle_out = angle + FT_ANGLE_PI;
922
923 error = ft_stroker_arcto( stroker, side );
924 }
925 else
926 {
927 /* add a square or butt cap */
928 FT_Vector middle, delta;
929 FT_Fixed radius = stroker->radius;
930 FT_StrokeBorder border = stroker->borders + side;
931
932
933 /* compute middle point and first angle point */
934 FT_Vector_From_Polar( &middle, radius, angle );
935 delta.x = side ? middle.y : -middle.y;
936 delta.y = side ? -middle.x : middle.x;
937
938 if ( stroker->line_cap == FT_STROKER_LINECAP_SQUARE )
939 {
940 middle.x += stroker->center.x;
941 middle.y += stroker->center.y;
942 }
943 else /* FT_STROKER_LINECAP_BUTT */
944 {
945 middle.x = stroker->center.x;
946 middle.y = stroker->center.y;
947 }
948
949 delta.x += middle.x;
950 delta.y += middle.y;
951
952 error = ft_stroke_border_lineto( border, &delta, FALSE );
953 if ( error )
954 goto Exit;
955
956 /* compute second angle point */
957 delta.x = middle.x - delta.x + middle.x;
958 delta.y = middle.y - delta.y + middle.y;
959
960 error = ft_stroke_border_lineto( border, &delta, FALSE );
961 }
962
963 Exit:
964 return error;
965 }
966
967
968 /* process an inside corner, i.e. compute intersection */
969 static FT_Error
970 ft_stroker_inside( FT_Stroker stroker,
971 FT_Int side,
972 FT_Fixed line_length )
973 {
974 FT_StrokeBorder border = stroker->borders + side;
975 FT_Angle phi, theta, rotate;
976 FT_Fixed length;
977 FT_Vector sigma = { 0, 0 };
978 FT_Vector delta;
979 FT_Error error = FT_Err_Ok;
980 FT_Bool intersect; /* use intersection of lines? */
981
982
983 rotate = FT_SIDE_TO_ROTATE( side );
984
985 theta = FT_Angle_Diff( stroker->angle_in, stroker->angle_out ) / 2;
986
987 /* Only intersect borders if between two lineto's and both */
988 /* lines are long enough (line_length is zero for curves). */
989 /* Also avoid U-turns of nearly 180 degree. */
990 if ( !border->movable || line_length == 0 ||
991 theta > 0x59C000 || theta < -0x59C000 )
992 intersect = FALSE;
993 else
994 {
995 /* compute minimum required length of lines */
996 FT_Fixed min_length;
997
998
999 FT_Vector_Unit( &sigma, theta );
1000 min_length =
1001 ft_pos_abs( FT_MulDiv( stroker->radius, sigma.y, sigma.x ) );
1002
1003 intersect = FT_BOOL( min_length &&
1004 stroker->line_length >= min_length &&
1005 line_length >= min_length );
1006 }
1007
1008 if ( !intersect )
1009 {
1010 FT_Vector_From_Polar( &delta, stroker->radius,
1011 stroker->angle_out + rotate );
1012 delta.x += stroker->center.x;
1013 delta.y += stroker->center.y;
1014
1015 border->movable = FALSE;
1016 }
1017 else
1018 {
1019 /* compute median angle */
1020 phi = stroker->angle_in + theta + rotate;
1021
1022 length = FT_DivFix( stroker->radius, sigma.x );
1023
1024 FT_Vector_From_Polar( &delta, length, phi );
1025 delta.x += stroker->center.x;
1026 delta.y += stroker->center.y;
1027 }
1028
1029 error = ft_stroke_border_lineto( border, &delta, FALSE );
1030
1031 return error;
1032 }
1033
1034
1035 /* process an outside corner, i.e. compute bevel/miter/round */
1036 static FT_Error
1037 ft_stroker_outside( FT_Stroker stroker,
1038 FT_Int side,
1039 FT_Fixed line_length )
1040 {
1041 FT_StrokeBorder border = stroker->borders + side;
1042 FT_Error error;
1043 FT_Angle rotate;
1044
1045
1046 if ( stroker->line_join == FT_STROKER_LINEJOIN_ROUND )
1047 error = ft_stroker_arcto( stroker, side );
1048 else
1049 {
1050 /* this is a mitered (pointed) or beveled (truncated) corner */
1051 FT_Fixed radius = stroker->radius;
1052 FT_Vector sigma = { 0, 0 };
1053 FT_Angle theta = 0, phi = 0;
1054 FT_Bool bevel, fixed_bevel;
1055
1056
1057 rotate = FT_SIDE_TO_ROTATE( side );
1058
1059 bevel =
1060 FT_BOOL( stroker->line_join == FT_STROKER_LINEJOIN_BEVEL );
1061
1062 fixed_bevel =
1063 FT_BOOL( stroker->line_join != FT_STROKER_LINEJOIN_MITER_VARIABLE );
1064
1065 /* check miter limit first */
1066 if ( !bevel )
1067 {
1068 theta = FT_Angle_Diff( stroker->angle_in, stroker->angle_out ) / 2;
1069
1070 if ( theta == FT_ANGLE_PI2 )
1071 theta = -rotate;
1072
1073 phi = stroker->angle_in + theta + rotate;
1074
1075 FT_Vector_From_Polar( &sigma, stroker->miter_limit, theta );
1076
1077 /* is miter limit exceeded? */
1078 if ( sigma.x < 0x10000L )
1079 {
1080 /* don't create variable bevels for very small deviations; */
1081 /* FT_Sin(x) = 0 for x <= 57 */
1082 if ( fixed_bevel || ft_pos_abs( theta ) > 57 )
1083 bevel = TRUE;
1084 }
1085 }
1086
1087 if ( bevel ) /* this is a bevel (broken angle) */
1088 {
1089 if ( fixed_bevel )
1090 {
1091 /* the outer corners are simply joined together */
1092 FT_Vector delta;
1093
1094
1095 /* add bevel */
1096 FT_Vector_From_Polar( &delta,
1097 radius,
1098 stroker->angle_out + rotate );
1099 delta.x += stroker->center.x;
1100 delta.y += stroker->center.y;
1101
1102 border->movable = FALSE;
1103 error = ft_stroke_border_lineto( border, &delta, FALSE );
1104 }
1105 else /* variable bevel or clipped miter */
1106 {
1107 /* the miter is truncated */
1108 FT_Vector middle, delta;
1109 FT_Fixed coef;
1110
1111
1112 /* compute middle point and first angle point */
1113 FT_Vector_From_Polar( &middle,
1114 FT_MulFix( radius, stroker->miter_limit ),
1115 phi );
1116
1117 coef = FT_DivFix( 0x10000L - sigma.x, sigma.y );
1118 delta.x = FT_MulFix( middle.y, coef );
1119 delta.y = FT_MulFix( -middle.x, coef );
1120
1121 middle.x += stroker->center.x;
1122 middle.y += stroker->center.y;
1123 delta.x += middle.x;
1124 delta.y += middle.y;
1125
1126 error = ft_stroke_border_lineto( border, &delta, FALSE );
1127 if ( error )
1128 goto Exit;
1129
1130 /* compute second angle point */
1131 delta.x = middle.x - delta.x + middle.x;
1132 delta.y = middle.y - delta.y + middle.y;
1133
1134 error = ft_stroke_border_lineto( border, &delta, FALSE );
1135 if ( error )
1136 goto Exit;
1137
1138 /* finally, add an end point; only needed if not lineto */
1139 /* (line_length is zero for curves) */
1140 if ( line_length == 0 )
1141 {
1142 FT_Vector_From_Polar( &delta,
1143 radius,
1144 stroker->angle_out + rotate );
1145
1146 delta.x += stroker->center.x;
1147 delta.y += stroker->center.y;
1148
1149 error = ft_stroke_border_lineto( border, &delta, FALSE );
1150 }
1151 }
1152 }
1153 else /* this is a miter (intersection) */
1154 {
1155 FT_Fixed length;
1156 FT_Vector delta;
1157
1158
1159 length = FT_MulDiv( stroker->radius, stroker->miter_limit, sigma.x );
1160
1161 FT_Vector_From_Polar( &delta, length, phi );
1162 delta.x += stroker->center.x;
1163 delta.y += stroker->center.y;
1164
1165 error = ft_stroke_border_lineto( border, &delta, FALSE );
1166 if ( error )
1167 goto Exit;
1168
1169 /* now add an end point; only needed if not lineto */
1170 /* (line_length is zero for curves) */
1171 if ( line_length == 0 )
1172 {
1173 FT_Vector_From_Polar( &delta,
1174 stroker->radius,
1175 stroker->angle_out + rotate );
1176 delta.x += stroker->center.x;
1177 delta.y += stroker->center.y;
1178
1179 error = ft_stroke_border_lineto( border, &delta, FALSE );
1180 }
1181 }
1182 }
1183
1184 Exit:
1185 return error;
1186 }
1187
1188
1189 static FT_Error
1190 ft_stroker_process_corner( FT_Stroker stroker,
1191 FT_Fixed line_length )
1192 {
1193 FT_Error error = FT_Err_Ok;
1194 FT_Angle turn;
1195 FT_Int inside_side;
1196
1197
1198 turn = FT_Angle_Diff( stroker->angle_in, stroker->angle_out );
1199
1200 /* no specific corner processing is required if the turn is 0 */
1201 if ( turn == 0 )
1202 goto Exit;
1203
1204 /* when we turn to the right, the inside side is 0 */
1205 /* otherwise, the inside side is 1 */
1206 inside_side = ( turn < 0 );
1207
1208 /* process the inside side */
1209 error = ft_stroker_inside( stroker, inside_side, line_length );
1210 if ( error )
1211 goto Exit;
1212
1213 /* process the outside side */
1214 error = ft_stroker_outside( stroker, !inside_side, line_length );
1215
1216 Exit:
1217 return error;
1218 }
1219
1220
1221 /* add two points to the left and right borders corresponding to the */
1222 /* start of the subpath */
1223 static FT_Error
1224 ft_stroker_subpath_start( FT_Stroker stroker,
1225 FT_Angle start_angle,
1226 FT_Fixed line_length )
1227 {
1228 FT_Vector delta;
1229 FT_Vector point;
1230 FT_Error error;
1231 FT_StrokeBorder border;
1232
1233
1234 FT_Vector_From_Polar( &delta, stroker->radius,
1235 start_angle + FT_ANGLE_PI2 );
1236
1237 point.x = stroker->center.x + delta.x;
1238 point.y = stroker->center.y + delta.y;
1239
1240 border = stroker->borders;
1241 error = ft_stroke_border_moveto( border, &point );
1242 if ( error )
1243 goto Exit;
1244
1245 point.x = stroker->center.x - delta.x;
1246 point.y = stroker->center.y - delta.y;
1247
1248 border++;
1249 error = ft_stroke_border_moveto( border, &point );
1250
1251 /* save angle, position, and line length for last join */
1252 /* (line_length is zero for curves) */
1253 stroker->subpath_angle = start_angle;
1254 stroker->first_point = FALSE;
1255 stroker->subpath_line_length = line_length;
1256
1257 Exit:
1258 return error;
1259 }
1260
1261
1262 /* documentation is in ftstroke.h */
1263
1264 FT_EXPORT_DEF( FT_Error )
1265 FT_Stroker_LineTo( FT_Stroker stroker,
1266 FT_Vector* to )
1267 {
1268 FT_Error error = FT_Err_Ok;
1269 FT_StrokeBorder border;
1270 FT_Vector delta;
1271 FT_Angle angle;
1272 FT_Int side;
1273 FT_Fixed line_length;
1274
1275
1276 if ( !stroker || !to )
1277 return FT_THROW( Invalid_Argument );
1278
1279 delta.x = to->x - stroker->center.x;
1280 delta.y = to->y - stroker->center.y;
1281
1282 /* a zero-length lineto is a no-op; avoid creating a spurious corner */
1283 if ( delta.x == 0 && delta.y == 0 )
1284 goto Exit;
1285
1286 /* compute length of line */
1287 line_length = FT_Vector_Length( &delta );
1288
1289 angle = FT_Atan2( delta.x, delta.y );
1290 FT_Vector_From_Polar( &delta, stroker->radius, angle + FT_ANGLE_PI2 );
1291
1292 /* process corner if necessary */
1293 if ( stroker->first_point )
1294 {
1295 /* This is the first segment of a subpath. We need to */
1296 /* add a point to each border at their respective starting */
1297 /* point locations. */
1298 error = ft_stroker_subpath_start( stroker, angle, line_length );
1299 if ( error )
1300 goto Exit;
1301 }
1302 else
1303 {
1304 /* process the current corner */
1305 stroker->angle_out = angle;
1306 error = ft_stroker_process_corner( stroker, line_length );
1307 if ( error )
1308 goto Exit;
1309 }
1310
1311 /* now add a line segment to both the `inside' and `outside' paths */
1312 for ( border = stroker->borders, side = 1; side >= 0; side--, border++ )
1313 {
1314 FT_Vector point;
1315
1316
1317 point.x = to->x + delta.x;
1318 point.y = to->y + delta.y;
1319
1320 /* the ends of lineto borders are movable */
1321 error = ft_stroke_border_lineto( border, &point, TRUE );
1322 if ( error )
1323 goto Exit;
1324
1325 delta.x = -delta.x;
1326 delta.y = -delta.y;
1327 }
1328
1329 stroker->angle_in = angle;
1330 stroker->center = *to;
1331 stroker->line_length = line_length;
1332
1333 Exit:
1334 return error;
1335 }
1336
1337
1338 /* documentation is in ftstroke.h */
1339
1340 FT_EXPORT_DEF( FT_Error )
1341 FT_Stroker_ConicTo( FT_Stroker stroker,
1342 FT_Vector* control,
1343 FT_Vector* to )
1344 {
1345 FT_Error error = FT_Err_Ok;
1346 FT_Vector bez_stack[34];
1347 FT_Vector* arc;
1348 FT_Vector* limit = bez_stack + 30;
1349 FT_Bool first_arc = TRUE;
1350
1351
1352 if ( !stroker || !control || !to )
1353 {
1354 error = FT_THROW( Invalid_Argument );
1355 goto Exit;
1356 }
1357
1358 /* if all control points are coincident, this is a no-op; */
1359 /* avoid creating a spurious corner */
1360 if ( FT_IS_SMALL( stroker->center.x - control->x ) &&
1361 FT_IS_SMALL( stroker->center.y - control->y ) &&
1362 FT_IS_SMALL( control->x - to->x ) &&
1363 FT_IS_SMALL( control->y - to->y ) )
1364 {
1365 stroker->center = *to;
1366 goto Exit;
1367 }
1368
1369 arc = bez_stack;
1370 arc[0] = *to;
1371 arc[1] = *control;
1372 arc[2] = stroker->center;
1373
1374 while ( arc >= bez_stack )
1375 {
1376 FT_Angle angle_in, angle_out;
1377
1378
1379 /* initialize with current direction */
1380 angle_in = angle_out = stroker->angle_in;
1381
1382 if ( arc < limit &&
1383 !ft_conic_is_small_enough( arc, &angle_in, &angle_out ) )
1384 {
1385 if ( stroker->first_point )
1386 stroker->angle_in = angle_in;
1387
1388 ft_conic_split( arc );
1389 arc += 2;
1390 continue;
1391 }
1392
1393 if ( first_arc )
1394 {
1395 first_arc = FALSE;
1396
1397 /* process corner if necessary */
1398 if ( stroker->first_point )
1399 error = ft_stroker_subpath_start( stroker, angle_in, 0 );
1400 else
1401 {
1402 stroker->angle_out = angle_in;
1403 error = ft_stroker_process_corner( stroker, 0 );
1404 }
1405 }
1406 else if ( ft_pos_abs( FT_Angle_Diff( stroker->angle_in, angle_in ) ) >
1407 FT_SMALL_CONIC_THRESHOLD / 4 )
1408 {
1409 /* if the deviation from one arc to the next is too great, */
1410 /* add a round corner */
1411 stroker->center = arc[2];
1412 stroker->angle_out = angle_in;
1413 stroker->line_join = FT_STROKER_LINEJOIN_ROUND;
1414
1415 error = ft_stroker_process_corner( stroker, 0 );
1416
1417 /* reinstate line join style */
1418 stroker->line_join = stroker->line_join_saved;
1419 }
1420
1421 if ( error )
1422 goto Exit;
1423
1424 /* the arc's angle is small enough; we can add it directly to each */
1425 /* border */
1426 {
1427 FT_Vector ctrl, end;
1428 FT_Angle theta, phi, rotate, alpha0 = 0;
1429 FT_Fixed length;
1430 FT_StrokeBorder border;
1431 FT_Int side;
1432
1433
1434 theta = FT_Angle_Diff( angle_in, angle_out ) / 2;
1435 phi = angle_in + theta;
1436 length = FT_DivFix( stroker->radius, FT_Cos( theta ) );
1437
1438 /* compute direction of original arc */
1439 if ( stroker->handle_wide_strokes )
1440 alpha0 = FT_Atan2( arc[0].x - arc[2].x, arc[0].y - arc[2].y );
1441
1442 for ( border = stroker->borders, side = 0;
1443 side <= 1;
1444 side++, border++ )
1445 {
1446 rotate = FT_SIDE_TO_ROTATE( side );
1447
1448 /* compute control point */
1449 FT_Vector_From_Polar( &ctrl, length, phi + rotate );
1450 ctrl.x += arc[1].x;
1451 ctrl.y += arc[1].y;
1452
1453 /* compute end point */
1454 FT_Vector_From_Polar( &end, stroker->radius, angle_out + rotate );
1455 end.x += arc[0].x;
1456 end.y += arc[0].y;
1457
1458 if ( stroker->handle_wide_strokes )
1459 {
1460 FT_Vector start;
1461 FT_Angle alpha1;
1462
1463
1464 /* determine whether the border radius is greater than the */
1465 /* radius of curvature of the original arc */
1466 start = border->points[border->num_points - 1];
1467
1468 alpha1 = FT_Atan2( end.x - start.x, end.y - start.y );
1469
1470 /* is the direction of the border arc opposite to */
1471 /* that of the original arc? */
1472 if ( ft_pos_abs( FT_Angle_Diff( alpha0, alpha1 ) ) >
1473 FT_ANGLE_PI / 2 )
1474 {
1475 FT_Angle beta, gamma;
1476 FT_Vector bvec, delta;
1477 FT_Fixed blen, sinA, sinB, alen;
1478
1479
1480 /* use the sine rule to find the intersection point */
1481 beta = FT_Atan2( arc[2].x - start.x, arc[2].y - start.y );
1482 gamma = FT_Atan2( arc[0].x - end.x, arc[0].y - end.y );
1483
1484 bvec.x = end.x - start.x;
1485 bvec.y = end.y - start.y;
1486
1487 blen = FT_Vector_Length( &bvec );
1488
1489 sinA = ft_pos_abs( FT_Sin( alpha1 - gamma ) );
1490 sinB = ft_pos_abs( FT_Sin( beta - gamma ) );
1491
1492 alen = FT_MulDiv( blen, sinA, sinB );
1493
1494 FT_Vector_From_Polar( &delta, alen, beta );
1495 delta.x += start.x;
1496 delta.y += start.y;
1497
1498 /* circumnavigate the negative sector backwards */
1499 border->movable = FALSE;
1500 error = ft_stroke_border_lineto( border, &delta, FALSE );
1501 if ( error )
1502 goto Exit;
1503 error = ft_stroke_border_lineto( border, &end, FALSE );
1504 if ( error )
1505 goto Exit;
1506 error = ft_stroke_border_conicto( border, &ctrl, &start );
1507 if ( error )
1508 goto Exit;
1509 /* and then move to the endpoint */
1510 error = ft_stroke_border_lineto( border, &end, FALSE );
1511 if ( error )
1512 goto Exit;
1513
1514 continue;
1515 }
1516
1517 /* else fall through */
1518 }
1519
1520 /* simply add an arc */
1521 error = ft_stroke_border_conicto( border, &ctrl, &end );
1522 if ( error )
1523 goto Exit;
1524 }
1525 }
1526
1527 arc -= 2;
1528
1529 stroker->angle_in = angle_out;
1530 }
1531
1532 stroker->center = *to;
1533 stroker->line_length = 0;
1534
1535 Exit:
1536 return error;
1537 }
1538
1539
1540 /* documentation is in ftstroke.h */
1541
1542 FT_EXPORT_DEF( FT_Error )
1543 FT_Stroker_CubicTo( FT_Stroker stroker,
1544 FT_Vector* control1,
1545 FT_Vector* control2,
1546 FT_Vector* to )
1547 {
1548 FT_Error error = FT_Err_Ok;
1549 FT_Vector bez_stack[37];
1550 FT_Vector* arc;
1551 FT_Vector* limit = bez_stack + 32;
1552 FT_Bool first_arc = TRUE;
1553
1554
1555 if ( !stroker || !control1 || !control2 || !to )
1556 {
1557 error = FT_THROW( Invalid_Argument );
1558 goto Exit;
1559 }
1560
1561 /* if all control points are coincident, this is a no-op; */
1562 /* avoid creating a spurious corner */
1563 if ( FT_IS_SMALL( stroker->center.x - control1->x ) &&
1564 FT_IS_SMALL( stroker->center.y - control1->y ) &&
1565 FT_IS_SMALL( control1->x - control2->x ) &&
1566 FT_IS_SMALL( control1->y - control2->y ) &&
1567 FT_IS_SMALL( control2->x - to->x ) &&
1568 FT_IS_SMALL( control2->y - to->y ) )
1569 {
1570 stroker->center = *to;
1571 goto Exit;
1572 }
1573
1574 arc = bez_stack;
1575 arc[0] = *to;
1576 arc[1] = *control2;
1577 arc[2] = *control1;
1578 arc[3] = stroker->center;
1579
1580 while ( arc >= bez_stack )
1581 {
1582 FT_Angle angle_in, angle_mid, angle_out;
1583
1584
1585 /* initialize with current direction */
1586 angle_in = angle_out = angle_mid = stroker->angle_in;
1587
1588 if ( arc < limit &&
1589 !ft_cubic_is_small_enough( arc, &angle_in,
1590 &angle_mid, &angle_out ) )
1591 {
1592 if ( stroker->first_point )
1593 stroker->angle_in = angle_in;
1594
1595 ft_cubic_split( arc );
1596 arc += 3;
1597 continue;
1598 }
1599
1600 if ( first_arc )
1601 {
1602 first_arc = FALSE;
1603
1604 /* process corner if necessary */
1605 if ( stroker->first_point )
1606 error = ft_stroker_subpath_start( stroker, angle_in, 0 );
1607 else
1608 {
1609 stroker->angle_out = angle_in;
1610 error = ft_stroker_process_corner( stroker, 0 );
1611 }
1612 }
1613 else if ( ft_pos_abs( FT_Angle_Diff( stroker->angle_in, angle_in ) ) >
1614 FT_SMALL_CUBIC_THRESHOLD / 4 )
1615 {
1616 /* if the deviation from one arc to the next is too great, */
1617 /* add a round corner */
1618 stroker->center = arc[3];
1619 stroker->angle_out = angle_in;
1620 stroker->line_join = FT_STROKER_LINEJOIN_ROUND;
1621
1622 error = ft_stroker_process_corner( stroker, 0 );
1623
1624 /* reinstate line join style */
1625 stroker->line_join = stroker->line_join_saved;
1626 }
1627
1628 if ( error )
1629 goto Exit;
1630
1631 /* the arc's angle is small enough; we can add it directly to each */
1632 /* border */
1633 {
1634 FT_Vector ctrl1, ctrl2, end;
1635 FT_Angle theta1, phi1, theta2, phi2, rotate, alpha0 = 0;
1636 FT_Fixed length1, length2;
1637 FT_StrokeBorder border;
1638 FT_Int side;
1639
1640
1641 theta1 = FT_Angle_Diff( angle_in, angle_mid ) / 2;
1642 theta2 = FT_Angle_Diff( angle_mid, angle_out ) / 2;
1643 phi1 = ft_angle_mean( angle_in, angle_mid );
1644 phi2 = ft_angle_mean( angle_mid, angle_out );
1645 length1 = FT_DivFix( stroker->radius, FT_Cos( theta1 ) );
1646 length2 = FT_DivFix( stroker->radius, FT_Cos( theta2 ) );
1647
1648 /* compute direction of original arc */
1649 if ( stroker->handle_wide_strokes )
1650 alpha0 = FT_Atan2( arc[0].x - arc[3].x, arc[0].y - arc[3].y );
1651
1652 for ( border = stroker->borders, side = 0;
1653 side <= 1;
1654 side++, border++ )
1655 {
1656 rotate = FT_SIDE_TO_ROTATE( side );
1657
1658 /* compute control points */
1659 FT_Vector_From_Polar( &ctrl1, length1, phi1 + rotate );
1660 ctrl1.x += arc[2].x;
1661 ctrl1.y += arc[2].y;
1662
1663 FT_Vector_From_Polar( &ctrl2, length2, phi2 + rotate );
1664 ctrl2.x += arc[1].x;
1665 ctrl2.y += arc[1].y;
1666
1667 /* compute end point */
1668 FT_Vector_From_Polar( &end, stroker->radius, angle_out + rotate );
1669 end.x += arc[0].x;
1670 end.y += arc[0].y;
1671
1672 if ( stroker->handle_wide_strokes )
1673 {
1674 FT_Vector start;
1675 FT_Angle alpha1;
1676
1677
1678 /* determine whether the border radius is greater than the */
1679 /* radius of curvature of the original arc */
1680 start = border->points[border->num_points - 1];
1681
1682 alpha1 = FT_Atan2( end.x - start.x, end.y - start.y );
1683
1684 /* is the direction of the border arc opposite to */
1685 /* that of the original arc? */
1686 if ( ft_pos_abs( FT_Angle_Diff( alpha0, alpha1 ) ) >
1687 FT_ANGLE_PI / 2 )
1688 {
1689 FT_Angle beta, gamma;
1690 FT_Vector bvec, delta;
1691 FT_Fixed blen, sinA, sinB, alen;
1692
1693
1694 /* use the sine rule to find the intersection point */
1695 beta = FT_Atan2( arc[3].x - start.x, arc[3].y - start.y );
1696 gamma = FT_Atan2( arc[0].x - end.x, arc[0].y - end.y );
1697
1698 bvec.x = end.x - start.x;
1699 bvec.y = end.y - start.y;
1700
1701 blen = FT_Vector_Length( &bvec );
1702
1703 sinA = ft_pos_abs( FT_Sin( alpha1 - gamma ) );
1704 sinB = ft_pos_abs( FT_Sin( beta - gamma ) );
1705
1706 alen = FT_MulDiv( blen, sinA, sinB );
1707
1708 FT_Vector_From_Polar( &delta, alen, beta );
1709 delta.x += start.x;
1710 delta.y += start.y;
1711
1712 /* circumnavigate the negative sector backwards */
1713 border->movable = FALSE;
1714 error = ft_stroke_border_lineto( border, &delta, FALSE );
1715 if ( error )
1716 goto Exit;
1717 error = ft_stroke_border_lineto( border, &end, FALSE );
1718 if ( error )
1719 goto Exit;
1720 error = ft_stroke_border_cubicto( border,
1721 &ctrl2,
1722 &ctrl1,
1723 &start );
1724 if ( error )
1725 goto Exit;
1726 /* and then move to the endpoint */
1727 error = ft_stroke_border_lineto( border, &end, FALSE );
1728 if ( error )
1729 goto Exit;
1730
1731 continue;
1732 }
1733
1734 /* else fall through */
1735 }
1736
1737 /* simply add an arc */
1738 error = ft_stroke_border_cubicto( border, &ctrl1, &ctrl2, &end );
1739 if ( error )
1740 goto Exit;
1741 }
1742 }
1743
1744 arc -= 3;
1745
1746 stroker->angle_in = angle_out;
1747 }
1748
1749 stroker->center = *to;
1750 stroker->line_length = 0;
1751
1752 Exit:
1753 return error;
1754 }
1755
1756
1757 /* documentation is in ftstroke.h */
1758
1759 FT_EXPORT_DEF( FT_Error )
1760 FT_Stroker_BeginSubPath( FT_Stroker stroker,
1761 FT_Vector* to,
1762 FT_Bool open )
1763 {
1764 if ( !stroker || !to )
1765 return FT_THROW( Invalid_Argument );
1766
1767 /* We cannot process the first point, because there is not enough */
1768 /* information regarding its corner/cap. The latter will be processed */
1769 /* in the `FT_Stroker_EndSubPath' routine. */
1770 /* */
1771 stroker->first_point = TRUE;
1772 stroker->center = *to;
1773 stroker->subpath_open = open;
1774
1775 /* Determine if we need to check whether the border radius is greater */
1776 /* than the radius of curvature of a curve, to handle this case */
1777 /* specially. This is only required if bevel joins or butt caps may */
1778 /* be created, because round & miter joins and round & square caps */
1779 /* cover the negative sector created with wide strokes. */
1780 stroker->handle_wide_strokes =
1781 FT_BOOL( stroker->line_join != FT_STROKER_LINEJOIN_ROUND ||
1782 ( stroker->subpath_open &&
1783 stroker->line_cap == FT_STROKER_LINECAP_BUTT ) );
1784
1785 /* record the subpath start point for each border */
1786 stroker->subpath_start = *to;
1787
1788 stroker->angle_in = 0;
1789
1790 return FT_Err_Ok;
1791 }
1792
1793
1794 static FT_Error
1795 ft_stroker_add_reverse_left( FT_Stroker stroker,
1796 FT_Bool open )
1797 {
1798 FT_StrokeBorder right = stroker->borders + 0;
1799 FT_StrokeBorder left = stroker->borders + 1;
1800 FT_Int new_points;
1801 FT_Error error = FT_Err_Ok;
1802
1803
1804 FT_ASSERT( left->start >= 0 );
1805
1806 new_points = (FT_Int)left->num_points - left->start;
1807 if ( new_points > 0 )
1808 {
1809 error = ft_stroke_border_grow( right, (FT_UInt)new_points );
1810 if ( error )
1811 goto Exit;
1812
1813 {
1814 FT_Vector* dst_point = right->points + right->num_points;
1815 FT_Byte* dst_tag = right->tags + right->num_points;
1816 FT_Vector* src_point = left->points + left->num_points - 1;
1817 FT_Byte* src_tag = left->tags + left->num_points - 1;
1818
1819
1820 while ( src_point >= left->points + left->start )
1821 {
1822 *dst_point = *src_point;
1823 *dst_tag = *src_tag;
1824
1825 if ( open )
1826 dst_tag[0] &= ~FT_STROKE_TAG_BEGIN_END;
1827 else
1828 {
1829 FT_Byte ttag =
1830 (FT_Byte)( dst_tag[0] & FT_STROKE_TAG_BEGIN_END );
1831
1832
1833 /* switch begin/end tags if necessary */
1834 if ( ttag == FT_STROKE_TAG_BEGIN ||
1835 ttag == FT_STROKE_TAG_END )
1836 dst_tag[0] ^= FT_STROKE_TAG_BEGIN_END;
1837 }
1838
1839 src_point--;
1840 src_tag--;
1841 dst_point++;
1842 dst_tag++;
1843 }
1844 }
1845
1846 left->num_points = (FT_UInt)left->start;
1847 right->num_points += (FT_UInt)new_points;
1848
1849 right->movable = FALSE;
1850 left->movable = FALSE;
1851 }
1852
1853 Exit:
1854 return error;
1855 }
1856
1857
1858 /* documentation is in ftstroke.h */
1859
1860 /* there's a lot of magic in this function! */
1861 FT_EXPORT_DEF( FT_Error )
1862 FT_Stroker_EndSubPath( FT_Stroker stroker )
1863 {
1864 FT_Error error = FT_Err_Ok;
1865
1866
1867 if ( !stroker )
1868 {
1869 error = FT_THROW( Invalid_Argument );
1870 goto Exit;
1871 }
1872
1873 if ( stroker->subpath_open )
1874 {
1875 FT_StrokeBorder right = stroker->borders;
1876
1877
1878 /* All right, this is an opened path, we need to add a cap between */
1879 /* right & left, add the reverse of left, then add a final cap */
1880 /* between left & right. */
1881 error = ft_stroker_cap( stroker, stroker->angle_in, 0 );
1882 if ( error )
1883 goto Exit;
1884
1885 /* add reversed points from `left' to `right' */
1886 error = ft_stroker_add_reverse_left( stroker, TRUE );
1887 if ( error )
1888 goto Exit;
1889
1890 /* now add the final cap */
1891 stroker->center = stroker->subpath_start;
1892 error = ft_stroker_cap( stroker,
1893 stroker->subpath_angle + FT_ANGLE_PI, 0 );
1894 if ( error )
1895 goto Exit;
1896
1897 /* Now end the right subpath accordingly. The left one is */
1898 /* rewind and doesn't need further processing. */
1899 ft_stroke_border_close( right, FALSE );
1900 }
1901 else
1902 {
1903 /* close the path if needed */
1904 if ( !FT_IS_SMALL( stroker->center.x - stroker->subpath_start.x ) ||
1905 !FT_IS_SMALL( stroker->center.y - stroker->subpath_start.y ) )
1906 {
1907 error = FT_Stroker_LineTo( stroker, &stroker->subpath_start );
1908 if ( error )
1909 goto Exit;
1910 }
1911
1912 /* process the corner */
1913 stroker->angle_out = stroker->subpath_angle;
1914
1915 error = ft_stroker_process_corner( stroker,
1916 stroker->subpath_line_length );
1917 if ( error )
1918 goto Exit;
1919
1920 /* then end our two subpaths */
1921 ft_stroke_border_close( stroker->borders + 0, FALSE );
1922 ft_stroke_border_close( stroker->borders + 1, TRUE );
1923 }
1924
1925 Exit:
1926 return error;
1927 }
1928
1929
1930 /* documentation is in ftstroke.h */
1931
1932 FT_EXPORT_DEF( FT_Error )
1933 FT_Stroker_GetBorderCounts( FT_Stroker stroker,
1934 FT_StrokerBorder border,
1935 FT_UInt *anum_points,
1936 FT_UInt *anum_contours )
1937 {
1938 FT_UInt num_points = 0, num_contours = 0;
1939 FT_Error error;
1940
1941
1942 if ( !stroker || border > 1 )
1943 {
1944 error = FT_THROW( Invalid_Argument );
1945 goto Exit;
1946 }
1947
1948 error = ft_stroke_border_get_counts( stroker->borders + border,
1949 &num_points, &num_contours );
1950 Exit:
1951 if ( anum_points )
1952 *anum_points = num_points;
1953
1954 if ( anum_contours )
1955 *anum_contours = num_contours;
1956
1957 return error;
1958 }
1959
1960
1961 /* documentation is in ftstroke.h */
1962
1963 FT_EXPORT_DEF( FT_Error )
1964 FT_Stroker_GetCounts( FT_Stroker stroker,
1965 FT_UInt *anum_points,
1966 FT_UInt *anum_contours )
1967 {
1968 FT_UInt count1, count2, num_points = 0;
1969 FT_UInt count3, count4, num_contours = 0;
1970 FT_Error error;
1971
1972
1973 if ( !stroker )
1974 {
1975 error = FT_THROW( Invalid_Argument );
1976 goto Exit;
1977 }
1978
1979 error = ft_stroke_border_get_counts( stroker->borders + 0,
1980 &count1, &count2 );
1981 if ( error )
1982 goto Exit;
1983
1984 error = ft_stroke_border_get_counts( stroker->borders + 1,
1985 &count3, &count4 );
1986 if ( error )
1987 goto Exit;
1988
1989 num_points = count1 + count3;
1990 num_contours = count2 + count4;
1991
1992 Exit:
1993 if ( anum_points )
1994 *anum_points = num_points;
1995
1996 if ( anum_contours )
1997 *anum_contours = num_contours;
1998
1999 return error;
2000 }
2001
2002
2003 /* documentation is in ftstroke.h */
2004
2005 FT_EXPORT_DEF( void )
2006 FT_Stroker_ExportBorder( FT_Stroker stroker,
2007 FT_StrokerBorder border,
2008 FT_Outline* outline )
2009 {
2010 if ( !stroker || !outline )
2011 return;
2012
2013 if ( border == FT_STROKER_BORDER_LEFT ||
2014 border == FT_STROKER_BORDER_RIGHT )
2015 {
2016 FT_StrokeBorder sborder = & stroker->borders[border];
2017
2018
2019 if ( sborder->valid )
2020 ft_stroke_border_export( sborder, outline );
2021 }
2022 }
2023
2024
2025 /* documentation is in ftstroke.h */
2026
2027 FT_EXPORT_DEF( void )
2028 FT_Stroker_Export( FT_Stroker stroker,
2029 FT_Outline* outline )
2030 {
2031 FT_Stroker_ExportBorder( stroker, FT_STROKER_BORDER_LEFT, outline );
2032 FT_Stroker_ExportBorder( stroker, FT_STROKER_BORDER_RIGHT, outline );
2033 }
2034
2035
2036 /* documentation is in ftstroke.h */
2037
2038 /*
2039 * The following is very similar to FT_Outline_Decompose, except
2040 * that we do support opened paths, and do not scale the outline.
2041 */
2042 FT_EXPORT_DEF( FT_Error )
2043 FT_Stroker_ParseOutline( FT_Stroker stroker,
2044 FT_Outline* outline,
2045 FT_Bool opened )
2046 {
2047 FT_Vector v_last;
2048 FT_Vector v_control;
2049 FT_Vector v_start;
2050
2051 FT_Vector* point;
2052 FT_Vector* limit;
2053 char* tags;
2054
2055 FT_Error error;
2056
2057 FT_Int n; /* index of contour in outline */
2058 FT_Int first; /* index of first point in contour */
2059 FT_Int last; /* index of last point in contour */
2060
2061 FT_Int tag; /* current point's state */
2062
2063
2064 if ( !outline )
2065 return FT_THROW( Invalid_Outline );
2066
2067 if ( !stroker )
2068 return FT_THROW( Invalid_Argument );
2069
2070 FT_Stroker_Rewind( stroker );
2071
2072 last = -1;
2073 for ( n = 0; n < outline->n_contours; n++ )
2074 {
2075 first = last + 1;
2076 last = outline->contours[n];
2077
2078 /* skip empty points; we don't stroke these */
2079 if ( last <= first )
2080 continue;
2081
2082 limit = outline->points + last;
2083
2084 v_start = outline->points[first];
2085 v_last = outline->points[last];
2086
2087 v_control = v_start;
2088
2089 point = outline->points + first;
2090 tags = outline->tags + first;
2091 tag = FT_CURVE_TAG( tags[0] );
2092
2093 /* A contour cannot start with a cubic control point! */
2094 if ( tag == FT_CURVE_TAG_CUBIC )
2095 goto Invalid_Outline;
2096
2097 /* check first point to determine origin */
2098 if ( tag == FT_CURVE_TAG_CONIC )
2099 {
2100 /* First point is conic control. Yes, this happens. */
2101 if ( FT_CURVE_TAG( outline->tags[last] ) == FT_CURVE_TAG_ON )
2102 {
2103 /* start at last point if it is on the curve */
2104 v_start = v_last;
2105 limit--;
2106 }
2107 else
2108 {
2109 /* if both first and last points are conic, */
2110 /* start at their middle */
2111 v_start.x = ( v_start.x + v_last.x ) / 2;
2112 v_start.y = ( v_start.y + v_last.y ) / 2;
2113 }
2114 point--;
2115 tags--;
2116 }
2117
2118 error = FT_Stroker_BeginSubPath( stroker, &v_start, opened );
2119 if ( error )
2120 goto Exit;
2121
2122 while ( point < limit )
2123 {
2124 point++;
2125 tags++;
2126
2127 tag = FT_CURVE_TAG( tags[0] );
2128 switch ( tag )
2129 {
2130 case FT_CURVE_TAG_ON: /* emit a single line_to */
2131 {
2132 FT_Vector vec;
2133
2134
2135 vec.x = point->x;
2136 vec.y = point->y;
2137
2138 error = FT_Stroker_LineTo( stroker, &vec );
2139 if ( error )
2140 goto Exit;
2141 continue;
2142 }
2143
2144 case FT_CURVE_TAG_CONIC: /* consume conic arcs */
2145 v_control.x = point->x;
2146 v_control.y = point->y;
2147
2148 Do_Conic:
2149 if ( point < limit )
2150 {
2151 FT_Vector vec;
2152 FT_Vector v_middle;
2153
2154
2155 point++;
2156 tags++;
2157 tag = FT_CURVE_TAG( tags[0] );
2158
2159 vec = point[0];
2160
2161 if ( tag == FT_CURVE_TAG_ON )
2162 {
2163 error = FT_Stroker_ConicTo( stroker, &v_control, &vec );
2164 if ( error )
2165 goto Exit;
2166 continue;
2167 }
2168
2169 if ( tag != FT_CURVE_TAG_CONIC )
2170 goto Invalid_Outline;
2171
2172 v_middle.x = ( v_control.x + vec.x ) / 2;
2173 v_middle.y = ( v_control.y + vec.y ) / 2;
2174
2175 error = FT_Stroker_ConicTo( stroker, &v_control, &v_middle );
2176 if ( error )
2177 goto Exit;
2178
2179 v_control = vec;
2180 goto Do_Conic;
2181 }
2182
2183 error = FT_Stroker_ConicTo( stroker, &v_control, &v_start );
2184 goto Close;
2185
2186 default: /* FT_CURVE_TAG_CUBIC */
2187 {
2188 FT_Vector vec1, vec2;
2189
2190
2191 if ( point + 1 > limit ||
2192 FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC )
2193 goto Invalid_Outline;
2194
2195 point += 2;
2196 tags += 2;
2197
2198 vec1 = point[-2];
2199 vec2 = point[-1];
2200
2201 if ( point <= limit )
2202 {
2203 FT_Vector vec;
2204
2205
2206 vec = point[0];
2207
2208 error = FT_Stroker_CubicTo( stroker, &vec1, &vec2, &vec );
2209 if ( error )
2210 goto Exit;
2211 continue;
2212 }
2213
2214 error = FT_Stroker_CubicTo( stroker, &vec1, &vec2, &v_start );
2215 goto Close;
2216 }
2217 }
2218 }
2219
2220 Close:
2221 if ( error )
2222 goto Exit;
2223
2224 /* don't try to end the path if no segments have been generated */
2225 if ( !stroker->first_point )
2226 {
2227 error = FT_Stroker_EndSubPath( stroker );
2228 if ( error )
2229 goto Exit;
2230 }
2231 }
2232
2233 return FT_Err_Ok;
2234
2235 Exit:
2236 return error;
2237
2238 Invalid_Outline:
2239 return FT_THROW( Invalid_Outline );
2240 }
2241
2242
2243 /* documentation is in ftstroke.h */
2244
2245 FT_EXPORT_DEF( FT_Error )
2246 FT_Glyph_Stroke( FT_Glyph *pglyph,
2247 FT_Stroker stroker,
2248 FT_Bool destroy )
2249 {
2250 FT_Error error = FT_ERR( Invalid_Argument );
2251 FT_Glyph glyph = NULL;
2252
2253
2254 if ( !pglyph )
2255 goto Exit;
2256
2257 glyph = *pglyph;
2258 if ( !glyph || glyph->clazz != &ft_outline_glyph_class )
2259 goto Exit;
2260
2261 {
2262 FT_Glyph copy;
2263
2264
2265 error = FT_Glyph_Copy( glyph, © );
2266 if ( error )
2267 goto Exit;
2268
2269 glyph = copy;
2270 }
2271
2272 {
2273 FT_OutlineGlyph oglyph = (FT_OutlineGlyph)glyph;
2274 FT_Outline* outline = &oglyph->outline;
2275 FT_UInt num_points, num_contours;
2276
2277
2278 error = FT_Stroker_ParseOutline( stroker, outline, FALSE );
2279 if ( error )
2280 goto Fail;
2281
2282 FT_Stroker_GetCounts( stroker, &num_points, &num_contours );
2283
2284 FT_Outline_Done( glyph->library, outline );
2285
2286 error = FT_Outline_New( glyph->library,
2287 num_points,
2288 (FT_Int)num_contours,
2289 outline );
2290 if ( error )
2291 goto Fail;
2292
2293 outline->n_points = 0;
2294 outline->n_contours = 0;
2295
2296 FT_Stroker_Export( stroker, outline );
2297 }
2298
2299 if ( destroy )
2300 FT_Done_Glyph( *pglyph );
2301
2302 *pglyph = glyph;
2303 goto Exit;
2304
2305 Fail:
2306 FT_Done_Glyph( glyph );
2307 glyph = NULL;
2308
2309 if ( !destroy )
2310 *pglyph = NULL;
2311
2312 Exit:
2313 return error;
2314 }
2315
2316
2317 /* documentation is in ftstroke.h */
2318
2319 FT_EXPORT_DEF( FT_Error )
2320 FT_Glyph_StrokeBorder( FT_Glyph *pglyph,
2321 FT_Stroker stroker,
2322 FT_Bool inside,
2323 FT_Bool destroy )
2324 {
2325 FT_Error error = FT_ERR( Invalid_Argument );
2326 FT_Glyph glyph = NULL;
2327
2328
2329 if ( !pglyph )
2330 goto Exit;
2331
2332 glyph = *pglyph;
2333 if ( !glyph || glyph->clazz != &ft_outline_glyph_class )
2334 goto Exit;
2335
2336 {
2337 FT_Glyph copy;
2338
2339
2340 error = FT_Glyph_Copy( glyph, © );
2341 if ( error )
2342 goto Exit;
2343
2344 glyph = copy;
2345 }
2346
2347 {
2348 FT_OutlineGlyph oglyph = (FT_OutlineGlyph)glyph;
2349 FT_StrokerBorder border;
2350 FT_Outline* outline = &oglyph->outline;
2351 FT_UInt num_points, num_contours;
2352
2353
2354 border = FT_Outline_GetOutsideBorder( outline );
2355 if ( inside )
2356 {
2357 if ( border == FT_STROKER_BORDER_LEFT )
2358 border = FT_STROKER_BORDER_RIGHT;
2359 else
2360 border = FT_STROKER_BORDER_LEFT;
2361 }
2362
2363 error = FT_Stroker_ParseOutline( stroker, outline, FALSE );
2364 if ( error )
2365 goto Fail;
2366
2367 FT_Stroker_GetBorderCounts( stroker, border,
2368 &num_points, &num_contours );
2369
2370 FT_Outline_Done( glyph->library, outline );
2371
2372 error = FT_Outline_New( glyph->library,
2373 num_points,
2374 (FT_Int)num_contours,
2375 outline );
2376 if ( error )
2377 goto Fail;
2378
2379 outline->n_points = 0;
2380 outline->n_contours = 0;
2381
2382 FT_Stroker_ExportBorder( stroker, border, outline );
2383 }
2384
2385 if ( destroy )
2386 FT_Done_Glyph( *pglyph );
2387
2388 *pglyph = glyph;
2389 goto Exit;
2390
2391 Fail:
2392 FT_Done_Glyph( glyph );
2393 glyph = NULL;
2394
2395 if ( !destroy )
2396 *pglyph = NULL;
2397
2398 Exit:
2399 return error;
2400 }
2401
2402
2403 /* END */