1 #include <ft2build.h> 2 #include FT_STROKER_H 3 #include FT_TRIGONOMETRY_H 4 #include FT_INTERNAL_MEMORY_H 5 #include FT_INTERNAL_DEBUG_H 6 7 /***************************************************************************/ 8 /***************************************************************************/ 9 /***** *****/ 10 /***** BEZIER COMPUTATIONS *****/ 11 /***** *****/ 12 /***************************************************************************/ 13 /***************************************************************************/ 14 15 #define FT_SMALL_CONIC_THRESHOLD (FT_ANGLE_PI/6) 16 #define FT_SMALL_CUBIC_THRESHOLD (FT_ANGLE_PI/6) 17 #define FT_EPSILON 2 18 19 #define FT_IS_SMALL(x) ((x) > -FT_EPSILON && (x) < FT_EPSILON) 20 21 static FT_Pos ft_pos_abs(FT_Pos x)22 ft_pos_abs( FT_Pos x ) 23 { 24 return x >= 0 ? x : -x ; 25 } 26 27 static void ft_conic_split(FT_Vector * base)28 ft_conic_split( FT_Vector* base ) 29 { 30 FT_Pos a, b; 31 32 33 base[4].x = base[2].x; 34 b = base[1].x; 35 a = base[3].x = ( base[2].x + b )/2; 36 b = base[1].x = ( base[0].x + b )/2; 37 base[2].x = ( a + b )/2; 38 39 base[4].y = base[2].y; 40 b = base[1].y; 41 a = base[3].y = ( base[2].y + b )/2; 42 b = base[1].y = ( base[0].y + b )/2; 43 base[2].y = ( a + b )/2; 44 } 45 46 47 static FT_Bool ft_conic_is_small_enough(FT_Vector * base,FT_Angle * angle_in,FT_Angle * angle_out)48 ft_conic_is_small_enough( FT_Vector* base, 49 FT_Angle *angle_in, 50 FT_Angle *angle_out ) 51 { 52 FT_Vector d1, d2; 53 FT_Angle theta; 54 FT_Int close1, close2; 55 56 d1.x = base[1].x - base[2].x; 57 d1.y = base[1].y - base[2].y; 58 d2.x = base[0].x - base[1].x; 59 d2.y = base[0].y - base[1].y; 60 61 close1 = FT_IS_SMALL(d1.x) && FT_IS_SMALL(d1.y); 62 close2 = FT_IS_SMALL(d2.x) && FT_IS_SMALL(d2.y); 63 64 if (close1) 65 { 66 if (close2) 67 *angle_in = *angle_out = 0; 68 else 69 *angle_in = *angle_out = FT_Atan2( d2.x, d2.y ); 70 } 71 else if (close2) 72 { 73 *angle_in = *angle_out = FT_Atan2( d1.x, d1.y ); 74 } 75 else 76 { 77 *angle_in = FT_Atan2( d1.x, d1.y ); 78 *angle_out = FT_Atan2( d2.x, d2.y ); 79 } 80 81 theta = ft_pos_abs( FT_Angle_Diff( *angle_in, *angle_out ) ); 82 83 return FT_BOOL( theta < FT_SMALL_CONIC_THRESHOLD ); 84 } 85 86 87 static void ft_cubic_split(FT_Vector * base)88 ft_cubic_split( FT_Vector* base ) 89 { 90 FT_Pos a, b, c, d; 91 92 93 base[6].x = base[3].x; 94 c = base[1].x; 95 d = base[2].x; 96 base[1].x = a = ( base[0].x + c )/2; 97 base[5].x = b = ( base[3].x + d )/2; 98 c = ( c + d )/2; 99 base[2].x = a = ( a + c )/2; 100 base[4].x = b = ( b + c )/2; 101 base[3].x = ( a + b )/2; 102 103 base[6].y = base[3].y; 104 c = base[1].y; 105 d = base[2].y; 106 base[1].y = a = ( base[0].y + c )/2; 107 base[5].y = b = ( base[3].y + d )/2; 108 c = ( c + d )/2; 109 base[2].y = a = ( a + c )/2; 110 base[4].y = b = ( b + c )/2; 111 base[3].y = ( a + b )/2; 112 } 113 114 115 static FT_Bool ft_cubic_is_small_enough(FT_Vector * base,FT_Angle * angle_in,FT_Angle * angle_mid,FT_Angle * angle_out)116 ft_cubic_is_small_enough( FT_Vector* base, 117 FT_Angle *angle_in, 118 FT_Angle *angle_mid, 119 FT_Angle *angle_out ) 120 { 121 FT_Vector d1, d2, d3; 122 FT_Angle theta1, theta2; 123 FT_Int close1, close2, close3; 124 125 d1.x = base[2].x - base[3].x; 126 d1.y = base[2].y - base[3].y; 127 d2.x = base[1].x - base[2].x; 128 d2.y = base[1].y - base[2].y; 129 d3.x = base[0].x - base[1].x; 130 d3.y = base[0].y - base[1].y; 131 132 close1 = FT_IS_SMALL(d1.x) && FT_IS_SMALL(d1.y); 133 close2 = FT_IS_SMALL(d2.x) && FT_IS_SMALL(d2.y); 134 close3 = FT_IS_SMALL(d3.x) && FT_IS_SMALL(d3.y); 135 136 if (close1 || close3) 137 { 138 if (close2) 139 { 140 /* basically a point */ 141 *angle_in = *angle_out = *angle_mid = 0; 142 } 143 else if (close1) 144 { 145 *angle_in = *angle_mid = FT_Atan2( d2.x, d2.y ); 146 *angle_out = FT_Atan2( d3.x, d3.y ); 147 } 148 else /* close2 */ 149 { 150 *angle_in = FT_Atan2( d1.x, d1.y ); 151 *angle_mid = *angle_out = FT_Atan2( d2.x, d2.y ); 152 } 153 } 154 else if (close2) 155 { 156 *angle_in = *angle_mid = FT_Atan2( d1.x, d1.y ); 157 *angle_out = FT_Atan2( d3.x, d3.y ); 158 } 159 else 160 { 161 *angle_in = FT_Atan2( d1.x, d1.y ); 162 *angle_mid = FT_Atan2( d2.x, d2.y ); 163 *angle_out = FT_Atan2( d3.x, d3.y ); 164 } 165 theta1 = ft_pos_abs( FT_Angle_Diff( *angle_in, *angle_mid ) ); 166 theta2 = ft_pos_abs( FT_Angle_Diff( *angle_mid, *angle_out ) ); 167 168 return FT_BOOL( theta1 < FT_SMALL_CUBIC_THRESHOLD && 169 theta2 < FT_SMALL_CUBIC_THRESHOLD ); 170 } 171 172 173 174 /***************************************************************************/ 175 /***************************************************************************/ 176 /***** *****/ 177 /***** STROKE BORDERS *****/ 178 /***** *****/ 179 /***************************************************************************/ 180 /***************************************************************************/ 181 182 typedef enum 183 { 184 FT_STROKE_TAG_ON = 1, /* on-curve point */ 185 FT_STROKE_TAG_CUBIC = 2, /* cubic off-point */ 186 FT_STROKE_TAG_BEGIN = 4, /* sub-path start */ 187 FT_STROKE_TAG_END = 8 /* sub-path end */ 188 189 } FT_StrokeTags; 190 191 192 typedef struct FT_StrokeBorderRec_ 193 { 194 FT_UInt num_points; 195 FT_UInt max_points; 196 FT_Vector* points; 197 FT_Byte* tags; 198 FT_Bool movable; 199 FT_Int start; /* index of current sub-path start point */ 200 FT_Memory memory; 201 202 } FT_StrokeBorderRec, *FT_StrokeBorder; 203 204 205 static FT_Error ft_stroke_border_grow(FT_StrokeBorder border,FT_UInt new_points)206 ft_stroke_border_grow( FT_StrokeBorder border, 207 FT_UInt new_points ) 208 { 209 FT_UInt old_max = border->max_points; 210 FT_UInt new_max = border->num_points + new_points; 211 FT_Error error = 0; 212 213 if ( new_max > old_max ) 214 { 215 FT_UInt cur_max = old_max; 216 FT_Memory memory = border->memory; 217 218 while ( cur_max < new_max ) 219 cur_max += (cur_max >> 1) + 16; 220 221 if ( FT_RENEW_ARRAY( border->points, old_max, cur_max ) || 222 FT_RENEW_ARRAY( border->tags, old_max, cur_max ) ) 223 goto Exit; 224 225 border->max_points = cur_max; 226 } 227 Exit: 228 return error; 229 } 230 231 static void ft_stroke_border_close(FT_StrokeBorder border)232 ft_stroke_border_close( FT_StrokeBorder border ) 233 { 234 FT_ASSERT( border->start >= 0 ); 235 236 border->tags[ border->start ] |= FT_STROKE_TAG_BEGIN; 237 border->tags[ border->num_points-1 ] |= FT_STROKE_TAG_END; 238 239 border->start = -1; 240 border->movable = 0; 241 } 242 243 244 static FT_Error ft_stroke_border_lineto(FT_StrokeBorder border,FT_Vector * to,FT_Bool movable)245 ft_stroke_border_lineto( FT_StrokeBorder border, 246 FT_Vector* to, 247 FT_Bool movable ) 248 { 249 FT_Error error = 0; 250 251 FT_ASSERT( border->start >= 0 ); 252 253 if ( border->movable ) 254 { 255 /* move last point */ 256 border->points[ border->num_points-1 ] = *to; 257 } 258 else 259 { 260 /* add one point */ 261 error = ft_stroke_border_grow( border, 1 ); 262 if (!error) 263 { 264 FT_Vector* vec = border->points + border->num_points; 265 FT_Byte* tag = border->tags + border->num_points; 266 267 vec[0] = *to; 268 tag[0] = FT_STROKE_TAG_ON; 269 270 border->num_points += 1; 271 } 272 } 273 border->movable = movable; 274 return error; 275 } 276 277 278 static FT_Error ft_stroke_border_conicto(FT_StrokeBorder border,FT_Vector * control,FT_Vector * to)279 ft_stroke_border_conicto( FT_StrokeBorder border, 280 FT_Vector* control, 281 FT_Vector* to ) 282 { 283 FT_Error error; 284 285 FT_ASSERT( border->start >= 0 ); 286 287 error = ft_stroke_border_grow( border, 2 ); 288 if (!error) 289 { 290 FT_Vector* vec = border->points + border->num_points; 291 FT_Byte* tag = border->tags + border->num_points; 292 293 vec[0] = *control; 294 vec[1] = *to; 295 296 tag[0] = 0; 297 tag[1] = FT_STROKE_TAG_ON; 298 299 border->num_points += 2; 300 } 301 border->movable = 0; 302 return error; 303 } 304 305 306 static FT_Error ft_stroke_border_cubicto(FT_StrokeBorder border,FT_Vector * control1,FT_Vector * control2,FT_Vector * to)307 ft_stroke_border_cubicto( FT_StrokeBorder border, 308 FT_Vector* control1, 309 FT_Vector* control2, 310 FT_Vector* to ) 311 { 312 FT_Error error; 313 314 FT_ASSERT( border->start >= 0 ); 315 316 error = ft_stroke_border_grow( border, 3 ); 317 if (!error) 318 { 319 FT_Vector* vec = border->points + border->num_points; 320 FT_Byte* tag = border->tags + border->num_points; 321 322 vec[0] = *control1; 323 vec[1] = *control2; 324 vec[2] = *to; 325 326 tag[0] = FT_STROKE_TAG_CUBIC; 327 tag[1] = FT_STROKE_TAG_CUBIC; 328 tag[2] = FT_STROKE_TAG_ON; 329 330 border->num_points += 3; 331 } 332 border->movable = 0; 333 return error; 334 } 335 336 337 #define FT_ARC_CUBIC_ANGLE (FT_ANGLE_PI/2) 338 339 340 static FT_Error ft_stroke_border_arcto(FT_StrokeBorder border,FT_Vector * center,FT_Fixed radius,FT_Angle angle_start,FT_Angle angle_diff)341 ft_stroke_border_arcto( FT_StrokeBorder border, 342 FT_Vector* center, 343 FT_Fixed radius, 344 FT_Angle angle_start, 345 FT_Angle angle_diff ) 346 { 347 FT_Angle total, angle, step, rotate, next, theta; 348 FT_Vector a, b, a2, b2; 349 FT_Fixed length; 350 FT_Error error = 0; 351 352 /* compute start point */ 353 FT_Vector_From_Polar( &a, radius, angle_start ); 354 a.x += center->x; 355 a.y += center->y; 356 357 total = angle_diff; 358 angle = angle_start; 359 rotate = ( angle_diff >= 0 ) ? FT_ANGLE_PI2 : -FT_ANGLE_PI2; 360 361 while (total != 0) 362 { 363 step = total; 364 if ( step > FT_ARC_CUBIC_ANGLE ) 365 step = FT_ARC_CUBIC_ANGLE; 366 367 else if ( step < -FT_ARC_CUBIC_ANGLE ) 368 step = -FT_ARC_CUBIC_ANGLE; 369 370 next = angle + step; 371 theta = step; 372 if ( theta < 0 ) 373 theta = -theta; 374 375 theta >>= 1; 376 377 /* compute end point */ 378 FT_Vector_From_Polar( &b, radius, next ); 379 b.x += center->x; 380 b.y += center->y; 381 382 /* compute first and second control points */ 383 length = FT_MulDiv( radius, FT_Sin(theta)*4, 384 (0x10000L + FT_Cos(theta))*3 ); 385 386 FT_Vector_From_Polar( &a2, length, angle + rotate ); 387 a2.x += a.x; 388 a2.y += a.y; 389 390 FT_Vector_From_Polar( &b2, length, next - rotate ); 391 b2.x += b.x; 392 b2.y += b.y; 393 394 /* add cubic arc */ 395 error = ft_stroke_border_cubicto( border, &a2, &b2, &b ); 396 if (error) break; 397 398 /* process the rest of the arc ?? */ 399 a = b; 400 total -= step; 401 angle = next; 402 } 403 return error; 404 } 405 406 407 static FT_Error ft_stroke_border_moveto(FT_StrokeBorder border,FT_Vector * to)408 ft_stroke_border_moveto( FT_StrokeBorder border, 409 FT_Vector* to ) 410 { 411 /* close current open path if any ? */ 412 if ( border->start >= 0 ) 413 ft_stroke_border_close( border ); 414 415 border->start = border->num_points; 416 border->movable = 0; 417 418 return ft_stroke_border_lineto( border, to, 0 ); 419 } 420 421 422 static void ft_stroke_border_init(FT_StrokeBorder border,FT_Memory memory)423 ft_stroke_border_init( FT_StrokeBorder border, 424 FT_Memory memory ) 425 { 426 border->memory = memory; 427 border->points = NULL; 428 border->tags = NULL; 429 430 border->num_points = 0; 431 border->max_points = 0; 432 border->start = -1; 433 } 434 435 436 static void ft_stroke_border_reset(FT_StrokeBorder border)437 ft_stroke_border_reset( FT_StrokeBorder border ) 438 { 439 border->num_points = 0; 440 border->start = -1; 441 } 442 443 444 static void ft_stroke_border_done(FT_StrokeBorder border)445 ft_stroke_border_done( FT_StrokeBorder border ) 446 { 447 FT_Memory memory = border->memory; 448 449 FT_FREE( border->points ); 450 FT_FREE( border->tags ); 451 452 border->num_points = 0; 453 border->max_points = 0; 454 border->start = -1; 455 } 456 457 458 static FT_Error ft_stroke_border_get_counts(FT_StrokeBorder border,FT_UInt * anum_points,FT_UInt * anum_contours)459 ft_stroke_border_get_counts( FT_StrokeBorder border, 460 FT_UInt *anum_points, 461 FT_UInt *anum_contours ) 462 { 463 FT_Error error = 0; 464 FT_UInt num_points = 0; 465 FT_UInt num_contours = 0; 466 467 FT_UInt count = border->num_points; 468 FT_Vector* point = border->points; 469 FT_Byte* tags = border->tags; 470 FT_Int in_contour = 0; 471 472 for ( ; count > 0; count--, point++, tags++ ) 473 { 474 if ( tags[0] & FT_STROKE_TAG_BEGIN ) 475 { 476 if ( in_contour != 0 ) 477 goto Fail; 478 479 in_contour = 1; 480 } 481 else if ( in_contour == 0 ) 482 goto Fail; 483 484 if ( tags[0] & FT_STROKE_TAG_END ) 485 { 486 if ( in_contour == 0 ) 487 goto Fail; 488 489 in_contour = 0; 490 num_contours++; 491 } 492 } 493 if ( in_contour != 0 ) 494 goto Fail; 495 496 Exit: 497 *anum_points = num_points; 498 *anum_contours = num_contours; 499 return error; 500 501 Fail: 502 num_points = 0; 503 num_contours = 0; 504 goto Exit; 505 } 506 507 508 static void ft_stroke_border_export(FT_StrokeBorder border,FT_Outline * outline)509 ft_stroke_border_export( FT_StrokeBorder border, 510 FT_Outline* outline ) 511 { 512 /* copy point locations */ 513 FT_MEM_COPY( outline->points + outline->n_points, 514 border->points, 515 border->num_points * sizeof(FT_Vector) ); 516 517 /* copy tags */ 518 { 519 FT_UInt count = border->num_points; 520 FT_Byte* read = border->tags; 521 FT_Byte* write = (FT_Byte*) outline->tags + outline->n_points; 522 523 for ( ; count > 0; count--, read++, write++ ) 524 { 525 if ( *read & FT_STROKE_TAG_ON ) 526 *write = FT_CURVE_TAG_ON; 527 else if ( *read & FT_STROKE_TAG_CUBIC ) 528 *write = FT_CURVE_TAG_CUBIC; 529 else 530 *write = FT_CURVE_TAG_CONIC; 531 } 532 } 533 534 /* copy contours */ 535 { 536 FT_UInt count = border->num_points; 537 FT_Byte* tags = border->tags; 538 FT_Short* write = outline->contours + outline->n_contours; 539 FT_Short index = (FT_Short) outline->n_points; 540 541 for ( ; count > 0; count--, tags++, write++, index++ ) 542 { 543 if ( *tags & FT_STROKE_TAG_END ) 544 { 545 *write++ = index; 546 outline->n_contours++; 547 } 548 } 549 } 550 551 outline->n_points = (short)( outline->n_points + border->num_points ); 552 553 FT_ASSERT( FT_Outline_Check( outline ) == 0 ); 554 } 555 556 557 /***************************************************************************/ 558 /***************************************************************************/ 559 /***** *****/ 560 /***** STROKER *****/ 561 /***** *****/ 562 /***************************************************************************/ 563 /***************************************************************************/ 564 565 #define FT_SIDE_TO_ROTATE(s) (FT_ANGLE_PI2 - (s)*FT_ANGLE_PI) 566 567 typedef struct FT_StrokerRec_ 568 { 569 FT_Angle angle_in; 570 FT_Angle angle_out; 571 FT_Vector center; 572 FT_Bool first_point; 573 FT_Bool subpath_open; 574 FT_Angle subpath_angle; 575 FT_Vector subpath_start; 576 577 FT_Stroker_LineCap line_cap; 578 FT_Stroker_LineJoin line_join; 579 FT_Fixed miter_limit; 580 FT_Fixed radius; 581 582 FT_Bool valid; 583 FT_StrokeBorderRec borders[2]; 584 FT_Memory memory; 585 586 } FT_StrokerRec; 587 588 589 FT_EXPORT_DEF( FT_Error ) FT_Stroker_New(FT_Memory memory,FT_Stroker * astroker)590 FT_Stroker_New( FT_Memory memory, 591 FT_Stroker *astroker ) 592 { 593 FT_Error error; 594 FT_Stroker stroker; 595 596 if ( !FT_NEW( stroker ) ) 597 { 598 stroker->memory = memory; 599 600 ft_stroke_border_init( &stroker->borders[0], memory ); 601 ft_stroke_border_init( &stroker->borders[1], memory ); 602 } 603 *astroker = stroker; 604 return error; 605 } 606 607 608 FT_EXPORT_DEF( void ) FT_Stroker_Set(FT_Stroker stroker,FT_Fixed radius,FT_Stroker_LineCap line_cap,FT_Stroker_LineJoin line_join,FT_Fixed miter_limit)609 FT_Stroker_Set( FT_Stroker stroker, 610 FT_Fixed radius, 611 FT_Stroker_LineCap line_cap, 612 FT_Stroker_LineJoin line_join, 613 FT_Fixed miter_limit ) 614 { 615 stroker->radius = radius; 616 stroker->line_cap = line_cap; 617 stroker->line_join = line_join; 618 stroker->miter_limit = miter_limit; 619 620 stroker->valid = 0; 621 622 ft_stroke_border_reset( &stroker->borders[0] ); 623 ft_stroke_border_reset( &stroker->borders[1] ); 624 } 625 626 627 FT_EXPORT_DEF( void ) FT_Stroker_Done(FT_Stroker stroker)628 FT_Stroker_Done( FT_Stroker stroker ) 629 { 630 if ( stroker ) 631 { 632 FT_Memory memory = stroker->memory; 633 634 ft_stroke_border_done( &stroker->borders[0] ); 635 ft_stroke_border_done( &stroker->borders[1] ); 636 637 stroker->memory = NULL; 638 FT_FREE( stroker ); 639 } 640 } 641 642 643 644 /* creates a circular arc at a corner or cap */ 645 static FT_Error ft_stroker_arcto(FT_Stroker stroker,FT_Int side)646 ft_stroker_arcto( FT_Stroker stroker, 647 FT_Int side ) 648 { 649 FT_Angle total, rotate; 650 FT_Fixed radius = stroker->radius; 651 FT_Error error = 0; 652 FT_StrokeBorder border = stroker->borders + side; 653 654 rotate = FT_SIDE_TO_ROTATE(side); 655 656 total = FT_Angle_Diff( stroker->angle_in, stroker->angle_out ); 657 if (total == FT_ANGLE_PI) 658 total = -rotate*2; 659 660 error = ft_stroke_border_arcto( border, 661 &stroker->center, 662 radius, 663 stroker->angle_in + rotate, 664 total ); 665 border->movable = 0; 666 return error; 667 } 668 669 670 /* adds a cap at the end of an opened path */ 671 static FT_Error ft_stroker_cap(FT_Stroker stroker,FT_Angle angle,FT_Int side)672 ft_stroker_cap( FT_Stroker stroker, 673 FT_Angle angle, 674 FT_Int side ) 675 { 676 FT_Error error = 0; 677 678 if ( stroker->line_cap == FT_STROKER_LINECAP_ROUND ) 679 { 680 /* add a round cap */ 681 stroker->angle_in = angle; 682 stroker->angle_out = angle + FT_ANGLE_PI; 683 error = ft_stroker_arcto( stroker, side ); 684 } 685 else if ( stroker->line_cap == FT_STROKER_LINECAP_SQUARE ) 686 { 687 /* add a square cap */ 688 FT_Vector delta, delta2; 689 FT_Angle rotate = FT_SIDE_TO_ROTATE(side); 690 FT_Fixed radius = stroker->radius; 691 FT_StrokeBorder border = stroker->borders + side; 692 693 FT_Vector_From_Polar( &delta2, radius, angle+rotate ); 694 FT_Vector_From_Polar( &delta, radius, angle ); 695 696 delta.x += stroker->center.x + delta2.x; 697 delta.y += stroker->center.y + delta2.y; 698 699 error = ft_stroke_border_lineto( border, &delta, 0 ); 700 if (error) goto Exit; 701 702 FT_Vector_From_Polar( &delta2, radius, angle-rotate ); 703 FT_Vector_From_Polar( &delta, radius, angle ); 704 705 delta.x += delta2.x + stroker->center.x; 706 delta.y += delta2.y + stroker->center.y; 707 708 error = ft_stroke_border_lineto( border, &delta, 0 ); 709 } 710 Exit: 711 return error; 712 } 713 714 715 716 /* process an inside corner, i.e. compute intersection */ 717 static FT_Error ft_stroker_inside(FT_Stroker stroker,FT_Int side)718 ft_stroker_inside( FT_Stroker stroker, 719 FT_Int side) 720 { 721 FT_StrokeBorder border = stroker->borders + side; 722 FT_Angle phi, theta, rotate; 723 FT_Fixed length, thcos, sigma; 724 FT_Vector delta; 725 FT_Error error = 0; 726 727 728 rotate = FT_SIDE_TO_ROTATE(side); 729 730 /* compute median angle */ 731 theta = FT_Angle_Diff( stroker->angle_in, stroker->angle_out ); 732 if ( theta == FT_ANGLE_PI ) 733 theta = rotate; 734 else 735 theta = theta/2; 736 737 phi = stroker->angle_in + theta; 738 739 thcos = FT_Cos( theta ); 740 sigma = FT_MulFix( stroker->miter_limit, thcos ); 741 742 if ( sigma < 0x10000L ) 743 { 744 FT_Vector_From_Polar( &delta, stroker->radius, stroker->angle_out + rotate ); 745 delta.x += stroker->center.x; 746 delta.y += stroker->center.y; 747 border->movable = 0; 748 } 749 else 750 { 751 length = FT_DivFix( stroker->radius, thcos ); 752 753 FT_Vector_From_Polar( &delta, length, phi + rotate ); 754 delta.x += stroker->center.x; 755 delta.y += stroker->center.y; 756 } 757 758 error = ft_stroke_border_lineto( border, &delta, 0 ); 759 760 return error; 761 } 762 763 764 /* process an outside corner, i.e. compute bevel/miter/round */ 765 static FT_Error ft_stroker_outside(FT_Stroker stroker,FT_Int side)766 ft_stroker_outside( FT_Stroker stroker, 767 FT_Int side ) 768 { 769 FT_StrokeBorder border = stroker->borders + side; 770 FT_Error error; 771 FT_Angle rotate; 772 773 if ( stroker->line_join == FT_STROKER_LINEJOIN_ROUND ) 774 { 775 error = ft_stroker_arcto( stroker, side ); 776 } 777 else 778 { 779 /* this is a mitered or beveled corner */ 780 FT_Fixed sigma, radius = stroker->radius; 781 FT_Angle theta, phi; 782 FT_Fixed thcos; 783 FT_Bool miter; 784 785 rotate = FT_SIDE_TO_ROTATE(side); 786 miter = FT_BOOL( stroker->line_join == FT_STROKER_LINEJOIN_MITER ); 787 788 theta = FT_Angle_Diff( stroker->angle_in, stroker->angle_out ); 789 if (theta == FT_ANGLE_PI) 790 theta = rotate; 791 else 792 theta = theta/2; 793 794 thcos = FT_Cos( theta ); 795 sigma = FT_MulFix( stroker->miter_limit, thcos ); 796 797 if ( sigma >= 0x10000L ) 798 miter = 0; 799 800 phi = stroker->angle_in + theta + rotate; 801 802 if (miter) /* this is a miter (broken angle) */ 803 { 804 FT_Vector middle, delta; 805 FT_Fixed length; 806 807 /* compute middle point */ 808 FT_Vector_From_Polar( &middle, FT_MulFix( radius, stroker->miter_limit ), 809 phi ); 810 middle.x += stroker->center.x; 811 middle.y += stroker->center.y; 812 813 /* compute first angle point */ 814 length = FT_MulFix( radius, FT_DivFix( 0x10000L - sigma, 815 ft_pos_abs( FT_Sin( theta ) ) ) ); 816 817 FT_Vector_From_Polar( &delta, length, phi + rotate ); 818 delta.x += middle.x; 819 delta.y += middle.y; 820 821 error = ft_stroke_border_lineto( border, &delta, 0 ); 822 if (error) goto Exit; 823 824 /* compute second angle point */ 825 FT_Vector_From_Polar( &delta, length, phi - rotate ); 826 delta.x += middle.x; 827 delta.y += middle.y; 828 829 error = ft_stroke_border_lineto( border, &delta, 0 ); 830 if (error) goto Exit; 831 832 /* finally, add a movable end point */ 833 FT_Vector_From_Polar( &delta, radius, stroker->angle_out + rotate ); 834 delta.x += stroker->center.x; 835 delta.y += stroker->center.y; 836 837 error = ft_stroke_border_lineto( border, &delta, 1 ); 838 } 839 else /* this is a bevel (intersection) */ 840 { 841 FT_Fixed length; 842 FT_Vector delta; 843 844 length = FT_DivFix( stroker->radius, thcos ); 845 846 FT_Vector_From_Polar( &delta, length, phi ); 847 delta.x += stroker->center.x; 848 delta.y += stroker->center.y; 849 850 error = ft_stroke_border_lineto( border, &delta, 0 ); 851 if (error) goto Exit; 852 853 /* now add end point */ 854 FT_Vector_From_Polar( &delta, stroker->radius, stroker->angle_out + rotate ); 855 delta.x += stroker->center.x; 856 delta.y += stroker->center.y; 857 858 error = ft_stroke_border_lineto( border, &delta, 1 ); 859 } 860 } 861 Exit: 862 return error; 863 } 864 865 866 static FT_Error ft_stroker_process_corner(FT_Stroker stroker)867 ft_stroker_process_corner( FT_Stroker stroker ) 868 { 869 FT_Error error = 0; 870 FT_Angle turn; 871 FT_Int inside_side; 872 873 turn = FT_Angle_Diff( stroker->angle_in, stroker->angle_out ); 874 875 /* no specific corner processing is required if the turn is 0 */ 876 if (turn == 0) 877 goto Exit; 878 879 /* when we turn to the right, the inside side is 0 */ 880 inside_side = 0; 881 882 /* otherwise, the inside side is 1 */ 883 if (turn < 0) 884 inside_side = 1; 885 886 /* process the inside side */ 887 error = ft_stroker_inside( stroker, inside_side ); 888 if (error) goto Exit; 889 890 /* process the outside side */ 891 error = ft_stroker_outside( stroker, 1-inside_side ); 892 893 Exit: 894 return error; 895 } 896 897 898 /* add two points to the left and right borders corresponding to the */ 899 /* start of the subpath.. */ 900 static FT_Error ft_stroker_subpath_start(FT_Stroker stroker,FT_Angle start_angle)901 ft_stroker_subpath_start( FT_Stroker stroker, 902 FT_Angle start_angle ) 903 { 904 FT_Vector delta; 905 FT_Vector point; 906 FT_Error error; 907 FT_StrokeBorder border; 908 909 FT_Vector_From_Polar( &delta, stroker->radius, start_angle + FT_ANGLE_PI2 ); 910 911 point.x = stroker->center.x + delta.x; 912 point.y = stroker->center.y + delta.y; 913 914 border = stroker->borders; 915 error = ft_stroke_border_moveto( border, &point ); 916 if (error) goto Exit; 917 918 point.x = stroker->center.x - delta.x; 919 point.y = stroker->center.y - delta.y; 920 921 border++; 922 error = ft_stroke_border_moveto( border, &point ); 923 924 /* save angle for last cap */ 925 stroker->subpath_angle = start_angle; 926 stroker->first_point = 0; 927 928 Exit: 929 return error; 930 } 931 932 933 FT_EXPORT_DEF( FT_Error ) FT_Stroker_LineTo(FT_Stroker stroker,FT_Vector * to)934 FT_Stroker_LineTo( FT_Stroker stroker, 935 FT_Vector* to ) 936 { 937 FT_Error error = 0; 938 FT_StrokeBorder border; 939 FT_Vector delta; 940 FT_Angle angle; 941 FT_Int side; 942 943 delta.x = to->x - stroker->center.x; 944 delta.y = to->y - stroker->center.y; 945 946 angle = FT_Atan2( delta.x, delta.y ); 947 FT_Vector_From_Polar( &delta, stroker->radius, angle + FT_ANGLE_PI2 ); 948 949 /* process corner if necessary */ 950 if ( stroker->first_point ) 951 { 952 /* this is the first segment of a subpath. We need to */ 953 /* add a point to each border at their respective starting */ 954 /* point locations.. */ 955 error = ft_stroker_subpath_start( stroker, angle ); 956 if (error) goto Exit; 957 } 958 else 959 { 960 /* process the current corner */ 961 stroker->angle_out = angle; 962 error = ft_stroker_process_corner( stroker ); 963 if (error) goto Exit; 964 } 965 966 /* now add a line segment to both the "inside" and "outside" paths */ 967 968 for ( border = stroker->borders, side = 1; side >= 0; side--, border++ ) 969 { 970 FT_Vector point; 971 972 point.x = to->x + delta.x; 973 point.y = to->y + delta.y; 974 975 error = ft_stroke_border_lineto( border, &point, 1 ); 976 if (error) goto Exit; 977 978 delta.x = -delta.x; 979 delta.y = -delta.y; 980 } 981 982 stroker->angle_in = angle; 983 stroker->center = *to; 984 985 Exit: 986 return error; 987 } 988 989 990 991 FT_EXPORT_DEF( FT_Error ) FT_Stroker_ConicTo(FT_Stroker stroker,FT_Vector * control,FT_Vector * to)992 FT_Stroker_ConicTo( FT_Stroker stroker, 993 FT_Vector* control, 994 FT_Vector* to ) 995 { 996 FT_Error error = 0; 997 FT_Vector bez_stack[34]; 998 FT_Vector* arc; 999 FT_Vector* limit = bez_stack + 30; 1000 FT_Angle start_angle; 1001 FT_Bool first_arc = 1; 1002 1003 arc = bez_stack; 1004 arc[0] = *to; 1005 arc[1] = *control; 1006 arc[2] = stroker->center; 1007 1008 while ( arc >= bez_stack ) 1009 { 1010 FT_Angle angle_in, angle_out; 1011 1012 angle_in = angle_out = 0; /* remove compiler warnings */ 1013 1014 if ( arc < limit && 1015 !ft_conic_is_small_enough( arc, &angle_in, &angle_out ) ) 1016 { 1017 ft_conic_split( arc ); 1018 arc += 2; 1019 continue; 1020 } 1021 1022 if ( first_arc ) 1023 { 1024 first_arc = 0; 1025 1026 start_angle = angle_in; 1027 1028 /* process corner if necessary */ 1029 if ( stroker->first_point ) 1030 error = ft_stroker_subpath_start( stroker, start_angle ); 1031 else 1032 { 1033 stroker->angle_out = start_angle; 1034 error = ft_stroker_process_corner( stroker ); 1035 } 1036 } 1037 1038 /* the arc's angle is small enough, we can add it directly to each */ 1039 /* border.. */ 1040 { 1041 FT_Vector ctrl, end; 1042 FT_Angle theta, phi, rotate; 1043 FT_Fixed length; 1044 FT_Int side; 1045 1046 theta = FT_Angle_Diff( angle_in, angle_out )/2; 1047 phi = angle_in + theta; 1048 length = FT_DivFix( stroker->radius, FT_Cos(theta) ); 1049 1050 for ( side = 0; side <= 1; side++ ) 1051 { 1052 rotate = FT_SIDE_TO_ROTATE(side); 1053 1054 /* compute control point */ 1055 FT_Vector_From_Polar( &ctrl, length, phi + rotate ); 1056 ctrl.x += arc[1].x; 1057 ctrl.y += arc[1].y; 1058 1059 /* compute end point */ 1060 FT_Vector_From_Polar( &end, stroker->radius, angle_out + rotate ); 1061 end.x += arc[0].x; 1062 end.y += arc[0].y; 1063 1064 error = ft_stroke_border_conicto( stroker->borders + side, &ctrl, &end ); 1065 if (error) goto Exit; 1066 } 1067 } 1068 1069 arc -= 2; 1070 1071 if (arc < bez_stack) 1072 stroker->angle_in = angle_out; 1073 } 1074 1075 stroker->center = *to; 1076 1077 Exit: 1078 return error; 1079 } 1080 1081 1082 1083 FT_EXPORT_DEF( FT_Error ) FT_Stroker_CubicTo(FT_Stroker stroker,FT_Vector * control1,FT_Vector * control2,FT_Vector * to)1084 FT_Stroker_CubicTo( FT_Stroker stroker, 1085 FT_Vector* control1, 1086 FT_Vector* control2, 1087 FT_Vector* to ) 1088 { 1089 FT_Error error = 0; 1090 FT_Vector bez_stack[37]; 1091 FT_Vector* arc; 1092 FT_Vector* limit = bez_stack + 32; 1093 FT_Angle start_angle; 1094 FT_Bool first_arc = 1; 1095 1096 arc = bez_stack; 1097 arc[0] = *to; 1098 arc[1] = *control2; 1099 arc[2] = *control1; 1100 arc[3] = stroker->center; 1101 1102 while ( arc >= bez_stack ) 1103 { 1104 FT_Angle angle_in, angle_mid, angle_out; 1105 1106 /* remove compiler warnings */ 1107 angle_in = angle_out = angle_mid = 0; 1108 1109 if ( arc < limit && 1110 !ft_cubic_is_small_enough( arc, &angle_in, &angle_mid, &angle_out ) ) 1111 { 1112 ft_cubic_split( arc ); 1113 arc += 3; 1114 continue; 1115 } 1116 1117 if ( first_arc ) 1118 { 1119 first_arc = 0; 1120 1121 /* process corner if necessary */ 1122 start_angle = angle_in; 1123 1124 if ( stroker->first_point ) 1125 error = ft_stroker_subpath_start( stroker, start_angle ); 1126 else 1127 { 1128 stroker->angle_out = start_angle; 1129 error = ft_stroker_process_corner( stroker ); 1130 } 1131 if (error) goto Exit; 1132 } 1133 1134 /* the arc's angle is small enough, we can add it directly to each */ 1135 /* border.. */ 1136 { 1137 FT_Vector ctrl1, ctrl2, end; 1138 FT_Angle theta1, phi1, theta2, phi2, rotate; 1139 FT_Fixed length1, length2; 1140 FT_Int side; 1141 1142 theta1 = ft_pos_abs( angle_mid - angle_in )/2; 1143 theta2 = ft_pos_abs( angle_out - angle_mid )/2; 1144 phi1 = (angle_mid+angle_in)/2; 1145 phi2 = (angle_mid+angle_out)/2; 1146 length1 = FT_DivFix( stroker->radius, FT_Cos(theta1) ); 1147 length2 = FT_DivFix( stroker->radius, FT_Cos(theta2) ); 1148 1149 for ( side = 0; side <= 1; side++ ) 1150 { 1151 rotate = FT_SIDE_TO_ROTATE(side); 1152 1153 /* compute control points */ 1154 FT_Vector_From_Polar( &ctrl1, length1, phi1 + rotate ); 1155 ctrl1.x += arc[2].x; 1156 ctrl1.y += arc[2].y; 1157 1158 FT_Vector_From_Polar( &ctrl2, length2, phi2 + rotate ); 1159 ctrl2.x += arc[1].x; 1160 ctrl2.y += arc[1].y; 1161 1162 /* compute end point */ 1163 FT_Vector_From_Polar( &end, stroker->radius, angle_out + rotate ); 1164 end.x += arc[0].x; 1165 end.y += arc[0].y; 1166 1167 error = ft_stroke_border_cubicto( stroker->borders + side, &ctrl1, &ctrl2, &end ); 1168 if (error) goto Exit; 1169 } 1170 } 1171 1172 arc -= 3; 1173 if (arc < bez_stack) 1174 stroker->angle_in = angle_out; 1175 } 1176 1177 stroker->center = *to; 1178 1179 Exit: 1180 return error; 1181 } 1182 1183 1184 FT_EXPORT_DEF( FT_Error ) FT_Stroker_BeginSubPath(FT_Stroker stroker,FT_Vector * to,FT_Bool open)1185 FT_Stroker_BeginSubPath( FT_Stroker stroker, 1186 FT_Vector* to, 1187 FT_Bool open ) 1188 { 1189 /* we cannot process the first point, because there is not enough */ 1190 /* information regarding its corner/cap. The latter will be processed */ 1191 /* in the "end_subpath" routine */ 1192 /* */ 1193 stroker->first_point = 1; 1194 stroker->center = *to; 1195 stroker->subpath_open = open; 1196 1197 /* record the subpath start point index for each border */ 1198 stroker->subpath_start = *to; 1199 return 0; 1200 } 1201 1202 1203 static ft_stroker_add_reverse_left(FT_Stroker stroker,FT_Bool open)1204 FT_Error ft_stroker_add_reverse_left( FT_Stroker stroker, 1205 FT_Bool open ) 1206 { 1207 FT_StrokeBorder right = stroker->borders + 0; 1208 FT_StrokeBorder left = stroker->borders + 1; 1209 FT_Int new_points; 1210 FT_Error error = 0; 1211 1212 FT_ASSERT( left->start >= 0 ); 1213 1214 new_points = left->num_points - left->start; 1215 if ( new_points > 0 ) 1216 { 1217 error = ft_stroke_border_grow( right, (FT_UInt)new_points ); 1218 if (error) goto Exit; 1219 { 1220 FT_Vector* dst_point = right->points + right->num_points; 1221 FT_Byte* dst_tag = right->tags + right->num_points; 1222 FT_Vector* src_point = left->points + left->num_points - 1; 1223 FT_Byte* src_tag = left->tags + left->num_points - 1; 1224 1225 while ( src_point >= left->points + left->start ) 1226 { 1227 *dst_point = *src_point; 1228 *dst_tag = *src_tag; 1229 1230 if (open) 1231 dst_tag[0] &= ~(FT_STROKE_TAG_BEGIN | FT_STROKE_TAG_END); 1232 else 1233 { 1234 /* switch begin/end tags if necessary.. */ 1235 if (dst_tag[0] & (FT_STROKE_TAG_BEGIN | FT_STROKE_TAG_END)) 1236 dst_tag[0] ^= (FT_STROKE_TAG_BEGIN | FT_STROKE_TAG_END); 1237 } 1238 1239 src_point--; 1240 src_tag--; 1241 dst_point++; 1242 dst_tag++; 1243 } 1244 } 1245 left->num_points = left->start; 1246 right->num_points += new_points; 1247 1248 right->movable = 0; 1249 left->movable = 0; 1250 } 1251 Exit: 1252 return error; 1253 } 1254 1255 1256 /* there's a lot of magic in this function !! */ 1257 FT_EXPORT_DEF( FT_Error ) FT_Stroker_EndSubPath(FT_Stroker stroker)1258 FT_Stroker_EndSubPath( FT_Stroker stroker ) 1259 { 1260 FT_Error error = 0; 1261 1262 if ( stroker->subpath_open ) 1263 { 1264 FT_StrokeBorder right = stroker->borders; 1265 1266 /* all right, this is an opened path, we need to add a cap between */ 1267 /* right & left, add the reverse of left, then add a final cap between */ 1268 /* left & right.. */ 1269 error = ft_stroker_cap( stroker, stroker->angle_in, 0 ); 1270 if (error) goto Exit; 1271 1272 /* add reversed points from "left" to "right" */ 1273 error = ft_stroker_add_reverse_left( stroker, 1 ); 1274 if (error) goto Exit; 1275 1276 /* now add the final cap */ 1277 stroker->center = stroker->subpath_start; 1278 error = ft_stroker_cap( stroker, stroker->subpath_angle+FT_ANGLE_PI, 0 ); 1279 if (error) goto Exit; 1280 1281 /* now, end the right subpath accordingly. the left one is */ 1282 /* rewind and doesn't need further processing.. */ 1283 ft_stroke_border_close( right ); 1284 } 1285 else 1286 { 1287 FT_Angle turn; 1288 FT_Int inside_side; 1289 1290 /* process the corner ... */ 1291 stroker->angle_out = stroker->subpath_angle; 1292 turn = FT_Angle_Diff( stroker->angle_in, stroker->angle_out ); 1293 1294 /* no specific corner processing is required if the turn is 0 */ 1295 if (turn != 0) 1296 { 1297 /* when we turn to the right, the inside side is 0 */ 1298 inside_side = 0; 1299 1300 /* otherwise, the inside side is 1 */ 1301 if (turn < 0) 1302 inside_side = 1; 1303 1304 /* IMPORTANT: WE DO NOT PROCESS THE INSIDE BORDER HERE !! */ 1305 /* process the inside side */ 1306 /* error = ft_stroker_inside( stroker, inside_side ); 1307 if (error) goto Exit; */ 1308 1309 /* process the outside side */ 1310 error = ft_stroker_outside( stroker, 1-inside_side ); 1311 if (error) goto Exit; 1312 } 1313 1314 /* we will first end our two subpaths */ 1315 ft_stroke_border_close( stroker->borders + 0 ); 1316 ft_stroke_border_close( stroker->borders + 1 ); 1317 1318 /* now, add the reversed left subpath to "right" */ 1319 error = ft_stroker_add_reverse_left( stroker, 0 ); 1320 if (error) goto Exit; 1321 } 1322 1323 Exit: 1324 return error; 1325 } 1326 1327 1328 FT_EXPORT_DEF( FT_Error ) FT_Stroker_GetCounts(FT_Stroker stroker,FT_UInt * anum_points,FT_UInt * anum_contours)1329 FT_Stroker_GetCounts( FT_Stroker stroker, 1330 FT_UInt *anum_points, 1331 FT_UInt *anum_contours ) 1332 { 1333 FT_UInt count1, count2, num_points = 0; 1334 FT_UInt count3, count4, num_contours = 0; 1335 FT_Error error; 1336 1337 error = ft_stroke_border_get_counts( stroker->borders+0, &count1, &count2 ); 1338 if (error) goto Exit; 1339 1340 error = ft_stroke_border_get_counts( stroker->borders+1, &count3, &count4 ); 1341 if (error) goto Exit; 1342 1343 num_points = count1 + count3; 1344 num_contours = count2 + count4; 1345 1346 stroker->valid = 1; 1347 1348 Exit: 1349 *anum_points = num_points; 1350 *anum_contours = num_contours; 1351 return error; 1352 } 1353 1354 1355 FT_EXPORT_DEF( void ) FT_Stroker_Export(FT_Stroker stroker,FT_Outline * outline)1356 FT_Stroker_Export( FT_Stroker stroker, 1357 FT_Outline* outline ) 1358 { 1359 if ( stroker->valid ) 1360 { 1361 ft_stroke_border_export( stroker->borders+0, outline ); 1362 ft_stroke_border_export( stroker->borders+1, outline ); 1363 } 1364 } 1365