1 /************************************************************************** 2 * 3 * Copyright 2009 VMware, Inc. All Rights Reserved. 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a 6 * copy of this software and associated documentation files (the 7 * "Software"), to deal in the Software without restriction, including 8 * without limitation the rights to use, copy, modify, merge, publish, 9 * distribute, sub license, and/or sell copies of the Software, and to 10 * permit persons to whom the Software is furnished to do so, subject to 11 * the following conditions: 12 * 13 * The above copyright notice and this permission notice (including the 14 * next paragraph) shall be included in all copies or substantial portions 15 * of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. 20 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR 21 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 22 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 23 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 24 * 25 **************************************************************************/ 26 27 #include "stroker.h" 28 29 #include "path.h" 30 #include "vg_state.h" 31 #include "util_array.h" 32 #include "arc.h" 33 #include "bezier.h" 34 #include "matrix.h" 35 #include "path_utils.h" 36 #include "polygon.h" 37 38 #include "util/u_math.h" 39 40 #ifndef M_2PI 41 #define M_2PI 6.28318530717958647692528676655900576 42 #endif 43 44 #define STROKE_SEGMENTS 0 45 #define STROKE_DEBUG 0 46 #define DEBUG_EMITS 0 47 48 static const VGfloat curve_threshold = 0.25f; 49 50 static const VGfloat zero_coords[] = {0.f, 0.f}; 51 52 enum intersection_type { 53 NoIntersections, 54 BoundedIntersection, 55 UnboundedIntersection, 56 }; 57 58 enum line_join_mode { 59 FlatJoin, 60 SquareJoin, 61 MiterJoin, 62 RoundJoin, 63 RoundCap 64 }; 65 66 struct stroke_iterator { 67 void (*next)(struct stroke_iterator *); 68 VGboolean (*has_next)(struct stroke_iterator *); 69 70 VGPathCommand (*current_command)(struct stroke_iterator *it); 71 void (*current_coords)(struct stroke_iterator *it, VGfloat *coords); 72 73 VGint position; 74 VGint coord_position; 75 76 const VGubyte *cmds; 77 const VGfloat *coords; 78 VGint num_commands; 79 VGint num_coords; 80 81 struct polygon *curve_poly; 82 VGint curve_index; 83 }; 84 85 static VGPathCommand stroke_itr_command(struct stroke_iterator *itr) 86 { 87 return itr->current_command(itr); 88 } 89 90 static void stroke_itr_coords(struct stroke_iterator *itr, VGfloat *coords) 91 { 92 itr->current_coords(itr, coords); 93 } 94 95 static void stroke_fw_itr_coords(struct stroke_iterator *itr, VGfloat *coords) 96 { 97 if (itr->position >= itr->num_commands) 98 return; 99 switch (stroke_itr_command(itr)) { 100 case VG_MOVE_TO_ABS: 101 coords[0] = itr->coords[itr->coord_position]; 102 coords[1] = itr->coords[itr->coord_position + 1]; 103 break; 104 case VG_LINE_TO_ABS: 105 coords[0] = itr->coords[itr->coord_position]; 106 coords[1] = itr->coords[itr->coord_position + 1]; 107 break; 108 case VG_CUBIC_TO_ABS: 109 coords[0] = itr->coords[itr->coord_position]; 110 coords[1] = itr->coords[itr->coord_position + 1]; 111 coords[2] = itr->coords[itr->coord_position + 2]; 112 coords[3] = itr->coords[itr->coord_position + 3]; 113 coords[4] = itr->coords[itr->coord_position + 4]; 114 coords[5] = itr->coords[itr->coord_position + 5]; 115 break; 116 default: 117 debug_assert(!"invalid command!\n"); 118 } 119 } 120 121 122 static void stroke_bw_itr_coords(struct stroke_iterator *itr, VGfloat *coords) 123 { 124 if (itr->position >= itr->num_commands) 125 return; 126 switch (stroke_itr_command(itr)) { 127 case VG_MOVE_TO_ABS: 128 coords[0] = itr->coords[itr->coord_position]; 129 coords[1] = itr->coords[itr->coord_position + 1]; 130 break; 131 case VG_LINE_TO_ABS: 132 coords[0] = itr->coords[itr->coord_position]; 133 coords[1] = itr->coords[itr->coord_position + 1]; 134 break; 135 case VG_CUBIC_TO_ABS: 136 coords[0] = itr->coords[itr->coord_position + 4]; 137 coords[1] = itr->coords[itr->coord_position + 5]; 138 coords[2] = itr->coords[itr->coord_position + 2]; 139 coords[3] = itr->coords[itr->coord_position + 3]; 140 coords[4] = itr->coords[itr->coord_position + 0]; 141 coords[5] = itr->coords[itr->coord_position + 1]; 142 break; 143 default: 144 debug_assert(!"invalid command!\n"); 145 } 146 } 147 148 149 static VGPathCommand stroke_fw_current_command(struct stroke_iterator *it) 150 { 151 return it->cmds[it->position]; 152 } 153 154 static VGPathCommand stroke_bw_current_command(struct stroke_iterator *it) 155 { 156 VGPathCommand prev_cmd; 157 if (it->position == it->num_commands -1) 158 return VG_MOVE_TO_ABS; 159 160 prev_cmd = it->cmds[it->position + 1]; 161 return prev_cmd; 162 } 163 164 static VGboolean stroke_fw_has_next(struct stroke_iterator *itr) 165 { 166 return itr->position < (itr->num_commands - 1); 167 } 168 169 static VGboolean stroke_bw_has_next(struct stroke_iterator *itr) 170 { 171 return itr->position > 0; 172 } 173 174 static void stroke_fw_next(struct stroke_iterator *itr) 175 { 176 VGubyte cmd; 177 debug_assert(stroke_fw_has_next(itr)); 178 179 cmd = stroke_itr_command(itr); 180 181 itr->coord_position += num_elements_for_segments(&cmd, 1); 182 ++itr->position; 183 } 184 185 static void stroke_bw_next(struct stroke_iterator *itr) 186 { 187 VGubyte cmd; 188 debug_assert(stroke_bw_has_next(itr)); 189 190 --itr->position; 191 cmd = stroke_itr_command(itr); 192 193 itr->coord_position -= num_elements_for_segments(&cmd, 1); 194 } 195 196 static void stroke_itr_common_init(struct stroke_iterator *itr, 197 struct array *cmds, 198 struct array *coords) 199 { 200 itr->cmds = (VGubyte*)cmds->data; 201 itr->num_commands = cmds->num_elements; 202 203 itr->coords = (VGfloat*)coords->data; 204 itr->num_coords = coords->num_elements; 205 } 206 207 static void stroke_forward_iterator(struct stroke_iterator *itr, 208 struct array *cmds, 209 struct array *coords) 210 { 211 stroke_itr_common_init(itr, cmds, coords); 212 itr->position = 0; 213 itr->coord_position = 0; 214 215 itr->next = stroke_fw_next; 216 itr->has_next = stroke_fw_has_next; 217 itr->current_command = stroke_fw_current_command; 218 itr->current_coords = stroke_fw_itr_coords; 219 } 220 221 static void stroke_backward_iterator(struct stroke_iterator *itr, 222 struct array *cmds, 223 struct array *coords) 224 { 225 VGubyte cmd; 226 stroke_itr_common_init(itr, cmds, coords); 227 itr->position = itr->num_commands - 1; 228 229 cmd = stroke_bw_current_command(itr); 230 itr->coord_position = itr->num_coords - 231 num_elements_for_segments(&cmd, 1); 232 233 itr->next = stroke_bw_next; 234 itr->has_next = stroke_bw_has_next; 235 itr->current_command = stroke_bw_current_command; 236 itr->current_coords = stroke_bw_itr_coords; 237 } 238 239 240 241 static void stroke_flat_next(struct stroke_iterator *itr) 242 { 243 VGubyte cmd; 244 245 if (itr->curve_index >= 0) { 246 ++itr->curve_index; 247 if (itr->curve_index >= polygon_vertex_count(itr->curve_poly)) { 248 itr->curve_index = -1; 249 polygon_destroy(itr->curve_poly); 250 itr->curve_poly = 0; 251 } else 252 return; 253 } 254 debug_assert(stroke_fw_has_next(itr)); 255 256 cmd = itr->cmds[itr->position]; 257 itr->coord_position += num_elements_for_segments(&cmd, 1); 258 ++itr->position; 259 260 cmd = itr->cmds[itr->position]; 261 262 if (cmd == VG_CUBIC_TO_ABS) { 263 struct bezier bezier; 264 VGfloat bez[8]; 265 266 bez[0] = itr->coords[itr->coord_position - 2]; 267 bez[1] = itr->coords[itr->coord_position - 1]; 268 bez[2] = itr->coords[itr->coord_position]; 269 bez[3] = itr->coords[itr->coord_position + 1]; 270 bez[4] = itr->coords[itr->coord_position + 2]; 271 bez[5] = itr->coords[itr->coord_position + 3]; 272 bez[6] = itr->coords[itr->coord_position + 4]; 273 bez[7] = itr->coords[itr->coord_position + 5]; 274 275 bezier_init(&bezier, 276 bez[0], bez[1], 277 bez[2], bez[3], 278 bez[4], bez[5], 279 bez[6], bez[7]); 280 /* skip the first one, it's the same as the prev point */ 281 itr->curve_index = 1; 282 if (itr->curve_poly) { 283 polygon_destroy(itr->curve_poly); 284 itr->curve_poly = 0; 285 } 286 itr->curve_poly = bezier_to_polygon(&bezier); 287 } 288 } 289 290 static VGboolean stroke_flat_has_next(struct stroke_iterator *itr) 291 { 292 return (itr->curve_index >= 0 && 293 itr->curve_index < (polygon_vertex_count(itr->curve_poly)-1)) 294 || itr->position < (itr->num_commands - 1); 295 } 296 297 static VGPathCommand stroke_flat_current_command(struct stroke_iterator *it) 298 { 299 if (it->cmds[it->position] == VG_CUBIC_TO_ABS) { 300 return VG_LINE_TO_ABS; 301 } 302 return it->cmds[it->position]; 303 } 304 305 static void stroke_flat_itr_coords(struct stroke_iterator *itr, VGfloat *coords) 306 { 307 if (itr->curve_index <= -1 && itr->position >= itr->num_commands) 308 return; 309 310 if (itr->curve_index >= 0) { 311 polygon_vertex(itr->curve_poly, itr->curve_index, 312 coords); 313 return; 314 } 315 316 switch (stroke_itr_command(itr)) { 317 case VG_MOVE_TO_ABS: 318 coords[0] = itr->coords[itr->coord_position]; 319 coords[1] = itr->coords[itr->coord_position + 1]; 320 break; 321 case VG_LINE_TO_ABS: 322 coords[0] = itr->coords[itr->coord_position]; 323 coords[1] = itr->coords[itr->coord_position + 1]; 324 break; 325 case VG_CUBIC_TO_ABS: 326 default: 327 debug_assert(!"invalid command!\n"); 328 } 329 } 330 331 static void stroke_flat_iterator(struct stroke_iterator *itr, 332 struct array *cmds, 333 struct array *coords) 334 { 335 stroke_itr_common_init(itr, cmds, coords); 336 itr->position = 0; 337 itr->coord_position = 0; 338 339 itr->next = stroke_flat_next; 340 itr->has_next = stroke_flat_has_next; 341 itr->current_command = stroke_flat_current_command; 342 itr->current_coords = stroke_flat_itr_coords; 343 itr->curve_index = -1; 344 itr->curve_poly = 0; 345 } 346 347 348 static INLINE VGboolean finite_coords4(const VGfloat *c) 349 { 350 return 351 isfinite(c[0]) && isfinite(c[1]) && 352 isfinite(c[2]) && isfinite(c[3]); 353 } 354 355 /* from Graphics Gems II */ 356 #define SAME_SIGNS(a, b) ((a) * (b) >= 0) 357 static VGboolean do_lines_intersect(VGfloat x1, VGfloat y1, VGfloat x2, VGfloat y2, 358 VGfloat x3, VGfloat y3, VGfloat x4, VGfloat y4) 359 { 360 VGfloat a1, a2, b1, b2, c1, c2; /* Coefficients of line eqns */ 361 VGfloat r1, r2, r3, r4; /* 'sign' values */ 362 363 a1 = y2 - y1; 364 b1 = x1 - x2; 365 c1 = x2 * y1 - x1 * y2; 366 367 r3 = a1 * x3 + b1 * y3 + c1; 368 r4 = a1 * x4 + b1 * y4 + c1; 369 370 if (r3 != 0 && r4 != 0 && SAME_SIGNS(r3, r4)) 371 return VG_FALSE; 372 373 a2 = y4 - y3; 374 b2 = x3 - x4; 375 c2 = x4 * y3 - x3 * y4; 376 377 r1 = a2 * x1 + b2 * y1 + c2; 378 r2 = a2 * x2 + b2 * y2 + c2; 379 380 if (r1 != 0 && r2 != 0 && SAME_SIGNS(r1, r2)) 381 return VG_FALSE; 382 383 return VG_TRUE; 384 } 385 386 static INLINE VGfloat line_dx(const VGfloat *l) 387 { 388 return l[2] - l[0]; 389 } 390 391 static INLINE VGfloat line_dy(const VGfloat *l) 392 { 393 return l[3] - l[1]; 394 } 395 396 static INLINE VGfloat line_angle(const VGfloat *l) 397 { 398 const VGfloat dx = line_dx(l); 399 const VGfloat dy = line_dy(l); 400 401 const VGfloat theta = atan2(-dy, dx) * 360.0 / M_2PI; 402 403 const VGfloat theta_normalized = theta < 0 ? theta + 360 : theta; 404 405 if (floatsEqual(theta_normalized, 360.f)) 406 return 0; 407 else 408 return theta_normalized; 409 } 410 411 static INLINE void line_set_length(VGfloat *l, VGfloat len) 412 { 413 VGfloat uv[] = {l[0], l[1], l[2], l[3]}; 414 if (null_line(l)) 415 return; 416 line_normalize(uv); 417 l[2] = l[0] + line_dx(uv) * len; 418 l[3] = l[1] + line_dy(uv) * len; 419 } 420 421 static INLINE void line_translate(VGfloat *l, VGfloat x, VGfloat y) 422 { 423 l[0] += x; 424 l[1] += y; 425 l[2] += x; 426 l[3] += y; 427 } 428 429 static INLINE VGfloat line_angle_to(const VGfloat *l1, 430 const VGfloat *l2) 431 { 432 VGfloat a1, a2, delta, delta_normalized; 433 if (null_line(l1) || null_line(l1)) 434 return 0; 435 436 a1 = line_angle(l1); 437 a2 = line_angle(l2); 438 439 delta = a2 - a1; 440 delta_normalized = delta < 0 ? delta + 360 : delta; 441 442 if (floatsEqual(delta, 360.f)) 443 return 0; 444 else 445 return delta_normalized; 446 } 447 448 static INLINE VGfloat line_angles(const VGfloat *l1, 449 const VGfloat *l2) 450 { 451 VGfloat cos_line, rad = 0; 452 453 if (null_line(l1) || null_line(l2)) 454 return 0; 455 456 cos_line = (line_dx(l1)*line_dx(l2) + line_dy(l1)*line_dy(l2)) / 457 (line_lengthv(l1)*line_lengthv(l2)); 458 rad = 0; 459 460 if (cos_line >= -1.0 && cos_line <= 1.0) 461 rad = acos(cos_line); 462 return rad * 360 / M_2PI; 463 } 464 465 466 static INLINE VGfloat adapted_angle_on_x(const VGfloat *line) 467 { 468 const VGfloat identity[] = {0, 0, 1, 0}; 469 VGfloat angle = line_angles(line, identity); 470 if (line_dy(line) > 0) 471 angle = 360 - angle; 472 return angle; 473 } 474 475 static enum intersection_type line_intersect(const VGfloat *l1, 476 const VGfloat *l2, 477 float *intersection_point) 478 { 479 VGfloat isect[2] = { 0 }; 480 enum intersection_type type; 481 VGboolean dx_zero, ldx_zero; 482 483 if (null_line(l1) || null_line(l2) || 484 !finite_coords4(l1) || !finite_coords4(l2)) 485 return NoIntersections; 486 487 type = do_lines_intersect(l1[0], l1[1], l1[2], l1[3], l2[0], l2[1], l2[2], l2[3]) 488 ? BoundedIntersection : UnboundedIntersection; 489 490 dx_zero = floatsEqual(line_dx(l1) + 1, 1); 491 ldx_zero = floatsEqual(line_dx(l2) + 1, 1); 492 493 /* one of the lines is vertical */ 494 if (dx_zero && ldx_zero) { 495 type = NoIntersections; 496 } else if (dx_zero) { 497 VGfloat la = line_dy(l2) / line_dx(l2); 498 isect[0] = l1[0]; 499 isect[1] = la * l1[0] + l2[1] - la * l2[0]; 500 } else if (ldx_zero) { 501 VGfloat ta = line_dy(l1) / line_dx(l1); 502 isect[0] = l2[0]; 503 isect[1] = ta * l2[0] + l1[1] - ta*l1[0]; 504 } else { 505 VGfloat x; 506 VGfloat ta = line_dy(l1) / line_dx(l1); 507 VGfloat la = line_dy(l2) / line_dx(l2); 508 if (ta == la) 509 return NoIntersections; 510 511 x = ( - l2[1] + la * l2[0] + l1[1] - ta * l1[0] ) / (la - ta); 512 isect[0] = x; 513 isect[1] = ta*(x - l1[0]) + l1[1]; 514 } 515 if (intersection_point) { 516 intersection_point[0] = isect[0]; 517 intersection_point[1] = isect[1]; 518 } 519 return type; 520 } 521 522 static INLINE enum line_join_mode stroker_join_mode(struct stroker *s) 523 { 524 switch(s->join_style) { 525 case VG_JOIN_MITER: 526 return MiterJoin; 527 case VG_JOIN_ROUND: 528 return RoundJoin; 529 case VG_JOIN_BEVEL: 530 return FlatJoin; 531 default: 532 return FlatJoin; 533 } 534 } 535 536 static INLINE enum line_join_mode stroker_cap_mode(struct stroker *s) 537 { 538 switch(s->cap_style) { 539 case VG_CAP_BUTT: 540 return FlatJoin; 541 case VG_CAP_ROUND: 542 return RoundCap; 543 case VG_CAP_SQUARE: 544 return SquareJoin; 545 default: 546 return FlatJoin; 547 } 548 } 549 550 void stroker_emit_move_to(struct stroker *stroker, VGfloat x, VGfloat y) 551 { 552 VGubyte cmds = VG_MOVE_TO_ABS; 553 VGfloat coords[2] = {x, y}; 554 #if DEBUG_EMITS 555 debug_printf("emit move %f, %f\n", x, y); 556 #endif 557 stroker->back2_x = stroker->back1_x; 558 stroker->back2_y = stroker->back1_y; 559 stroker->back1_x = x; 560 stroker->back1_y = y; 561 562 path_append_data(stroker->path, 563 1, 564 &cmds, &coords); 565 } 566 567 void stroker_emit_line_to(struct stroker *stroker, VGfloat x, VGfloat y) 568 { 569 VGubyte cmds = VG_LINE_TO_ABS; 570 VGfloat coords[2] = {x, y}; 571 #if DEBUG_EMITS 572 debug_printf("emit line %f, %f\n", x, y); 573 #endif 574 stroker->back2_x = stroker->back1_x; 575 stroker->back2_y = stroker->back1_y; 576 stroker->back1_x = x; 577 stroker->back1_y = y; 578 path_append_data(stroker->path, 579 1, 580 &cmds, &coords); 581 } 582 583 void stroker_emit_curve_to(struct stroker *stroker, VGfloat px1, VGfloat py1, 584 VGfloat px2, VGfloat py2, 585 VGfloat x, VGfloat y) 586 { 587 VGubyte cmds = VG_CUBIC_TO_ABS; 588 VGfloat coords[6] = {px1, py1, px2, py2, x, y}; 589 #if DEBUG_EMITS 590 debug_printf("emit curve %f, %f, %f, %f, %f, %f\n", px1, py1, 591 px2, py2, x, y); 592 #endif 593 594 if (px2 == x && py2 == y) { 595 if (px1 == x && py1 == y) { 596 stroker->back2_x = stroker->back1_x; 597 stroker->back2_y = stroker->back1_y; 598 } else { 599 stroker->back2_x = px1; 600 stroker->back2_y = py1; 601 } 602 } else { 603 stroker->back2_x = px2; 604 stroker->back2_y = py2; 605 } 606 stroker->back1_x = x; 607 stroker->back1_y = y; 608 609 path_append_data(stroker->path, 610 1, 611 &cmds, &coords); 612 } 613 614 static INLINE void create_round_join(struct stroker *stroker, 615 VGfloat x1, VGfloat y1, 616 VGfloat x2, VGfloat y2, 617 VGfloat width, VGfloat height) 618 { 619 struct arc arc; 620 struct matrix matrix; 621 622 matrix_load_identity(&matrix); 623 624 /*stroker_emit_line_to(stroker, nx, ny);*/ 625 626 arc_init(&arc, VG_SCCWARC_TO, 627 x1, y1, x2, y2, width/2, height/2, 0); 628 arc_stroker_emit(&arc, stroker, &matrix); 629 } 630 631 632 static void create_joins(struct stroker *stroker, 633 VGfloat focal_x, VGfloat focal_y, 634 const VGfloat *next_line, enum line_join_mode join) 635 { 636 #if DEBUG_EMITS 637 debug_printf("create_joins: focal=[%f, %f], next_line=[%f, %f,%f, %f]\n", 638 focal_x, focal_y, 639 next_line[0], next_line[1], next_line[2], next_line[3]); 640 #endif 641 /* if we're alredy connected do nothing */ 642 if (floatsEqual(stroker->back1_x, next_line[0]) && 643 floatsEqual(stroker->back1_y, next_line[1])) 644 return; 645 646 if (join == FlatJoin) { 647 stroker_emit_line_to(stroker, next_line[0], next_line[1]); 648 } else { 649 VGfloat prev_line[] = {stroker->back2_x, stroker->back2_y, 650 stroker->back1_x, stroker->back1_y}; 651 652 VGfloat isect[2] = { 0 }; 653 enum intersection_type type = line_intersect(prev_line, next_line, isect); 654 655 if (join == SquareJoin) { 656 VGfloat offset = stroker->stroke_width / 2; 657 VGfloat l1[4] = {prev_line[0], 658 prev_line[1], 659 prev_line[2], 660 prev_line[3]}; 661 VGfloat l2[4] = {next_line[2], 662 next_line[3], 663 next_line[0], 664 next_line[1]}; 665 666 line_translate(l1, line_dx(l1), line_dy(l1)); 667 line_set_length(l1, offset); 668 669 line_translate(l2, line_dx(l2), line_dy(l2)); 670 line_set_length(l2, offset); 671 672 stroker_emit_line_to(stroker, l1[2], l1[3]); 673 stroker_emit_line_to(stroker, l2[2], l2[3]); 674 stroker_emit_line_to(stroker, l2[0], l2[1]); 675 } else if (join == RoundJoin) { 676 VGfloat offset = stroker->stroke_width / 2; 677 VGfloat short_cut[4] = {prev_line[2], prev_line[3], 678 next_line[0], next_line[1]}; 679 VGfloat angle = line_angles(prev_line, short_cut); 680 681 if (type == BoundedIntersection || 682 (angle > 90 && !floatsEqual(angle, 90.f))) { 683 stroker_emit_line_to(stroker, next_line[0], next_line[1]); 684 return; 685 } 686 create_round_join(stroker, prev_line[2], prev_line[3], 687 next_line[0], next_line[1], 688 offset * 2, offset * 2); 689 690 stroker_emit_line_to(stroker, next_line[0], next_line[1]); 691 } else if (join == RoundCap) { 692 VGfloat offset = stroker->stroke_width / 2; 693 VGfloat l1[4] = { prev_line[0], prev_line[1], 694 prev_line[2], prev_line[3] }; 695 VGfloat l2[4] = {focal_x, focal_y, 696 prev_line[2], prev_line[3]}; 697 698 line_translate(l1, line_dx(l1), line_dy(l1)); 699 line_set_length(l1, KAPPA * offset); 700 701 /* normal between prev_line and focal */ 702 line_translate(l2, -line_dy(l2), line_dx(l2)); 703 line_set_length(l2, KAPPA * offset); 704 705 stroker_emit_curve_to(stroker, l1[2], l1[3], 706 l2[2], l2[3], 707 l2[0], l2[1]); 708 709 l2[0] = l2[0]; 710 l2[1] = l2[1]; 711 l2[2] = l2[0] - line_dx(l2); 712 l2[3] = l2[1] - line_dy(l2); 713 714 line_translate(l1, next_line[0] - l1[0], next_line[1] - l1[1]); 715 716 stroker_emit_curve_to(stroker, 717 l2[2], l2[3], 718 l1[2], l1[3], 719 l1[0], l1[1]); 720 } else if (join == MiterJoin) { 721 VGfloat miter_line[4] = {stroker->back1_x, stroker->back1_y, 722 isect[0], isect[1]}; 723 VGfloat sl = (stroker->stroke_width * stroker->miter_limit); 724 VGfloat inside_line[4] = {prev_line[2], prev_line[3], 725 next_line[0], next_line[1]}; 726 VGfloat angle = line_angle_to(inside_line, prev_line); 727 728 if (type == BoundedIntersection || 729 (angle > 90 && !floatsEqual(angle, 90.f))) { 730 /* 731 debug_printf("f = %f, nl = %f, pl = %f, is = %f\n", 732 focal_x, next_line[0], 733 prev_line[2], isect[0]);*/ 734 stroker_emit_line_to(stroker, next_line[0], next_line[1]); 735 return; 736 } 737 738 if (type == NoIntersections || line_lengthv(miter_line) > sl) { 739 stroker_emit_line_to(stroker, next_line[0], next_line[1]); 740 } else { 741 stroker_emit_line_to(stroker, isect[0], isect[1]); 742 stroker_emit_line_to(stroker, next_line[0], next_line[1]); 743 } 744 } else { 745 debug_assert(!"create_joins bad join style"); 746 } 747 } 748 } 749 750 static void stroker_add_segment(struct stroker *stroker, 751 VGPathCommand cmd, 752 const VGfloat *coords, 753 VGint num_coords) 754 { 755 /* skip duplicated points */ 756 if (stroker->segments->num_elements && 757 stroker->last_cmd == cmd) { 758 VGfloat *data = stroker->control_points->data; 759 data += stroker->control_points->num_elements; 760 data -= num_coords; 761 switch (cmd) { 762 case VG_MOVE_TO_ABS: 763 if (floatsEqual(coords[0], data[0]) && 764 floatsEqual(coords[1], data[1])) 765 return; 766 break; 767 case VG_LINE_TO_ABS: 768 if (floatsEqual(coords[0], data[0]) && 769 floatsEqual(coords[1], data[1])) 770 return; 771 break; 772 case VG_CUBIC_TO_ABS: 773 if (floatsEqual(coords[0], data[0]) && 774 floatsEqual(coords[1], data[1]) && 775 floatsEqual(coords[2], data[2]) && 776 floatsEqual(coords[3], data[3]) && 777 floatsEqual(coords[4], data[4]) && 778 floatsEqual(coords[5], data[5])) 779 return; 780 break; 781 default: 782 debug_assert(!"Invalid stroke segment"); 783 } 784 } else if (stroker->last_cmd == VG_CUBIC_TO_ABS && 785 cmd == VG_LINE_TO_ABS) { 786 VGfloat *data = stroker->control_points->data; 787 data += stroker->control_points->num_elements; 788 data -= 2; 789 if (floatsEqual(coords[0], data[0]) && 790 floatsEqual(coords[1], data[1])) 791 return; 792 } 793 stroker->last_cmd = cmd; 794 array_append_data(stroker->segments, &cmd, 1); 795 array_append_data(stroker->control_points, coords, num_coords); 796 } 797 798 void stroker_move_to(struct stroker *stroker, VGfloat x, VGfloat y) 799 { 800 VGfloat coords[2] = {x, y}; 801 #if STROKE_SEGMENTS 802 debug_printf("stroker_move_to(%f, %f)\n", x, y); 803 #endif 804 805 if (stroker->segments->num_elements > 0) 806 stroker->process_subpath(stroker); 807 808 array_reset(stroker->segments); 809 array_reset(stroker->control_points); 810 811 stroker_add_segment(stroker, VG_MOVE_TO_ABS, coords, 2); 812 } 813 814 void stroker_line_to(struct stroker *stroker, VGfloat x, VGfloat y) 815 { 816 VGfloat coords[] = {x, y}; 817 818 #if STROKE_SEGMENTS 819 debug_printf("stroker_line_to(%f, %f)\n", x, y); 820 #endif 821 if (!stroker->segments->num_elements) 822 stroker_add_segment(stroker, VG_MOVE_TO_ABS, zero_coords, 2); 823 824 stroker_add_segment(stroker, VG_LINE_TO_ABS, coords, 2); 825 } 826 827 void stroker_curve_to(struct stroker *stroker, VGfloat px1, VGfloat py1, 828 VGfloat px2, VGfloat py2, 829 VGfloat x, VGfloat y) 830 { 831 VGfloat coords[] = {px1, py1, 832 px2, py2, 833 x, y}; 834 #if STROKE_SEGMENTS 835 debug_printf("stroker_curve_to(%f, %f, %f, %f, %f, %f)\n", 836 px1, py1, px2, py2, x, y); 837 #endif 838 if (!stroker->segments->num_elements) 839 stroker_add_segment(stroker, VG_MOVE_TO_ABS, zero_coords, 2); 840 841 stroker_add_segment(stroker, VG_CUBIC_TO_ABS, coords, 6); 842 } 843 844 static INLINE VGboolean is_segment_null(VGPathCommand cmd, 845 VGfloat *coords, 846 VGfloat *res) 847 { 848 switch(cmd) { 849 case VG_MOVE_TO_ABS: 850 case VG_LINE_TO_ABS: 851 return floatsEqual(coords[0], res[0]) && 852 floatsEqual(coords[1], res[1]); 853 break; 854 case VG_CUBIC_TO_ABS: 855 return floatsEqual(coords[0], res[0]) && 856 floatsEqual(coords[1], res[1]) && 857 floatsEqual(coords[2], res[0]) && 858 floatsEqual(coords[3], res[1]) && 859 floatsEqual(coords[4], res[0]) && 860 floatsEqual(coords[5], res[1]); 861 break; 862 default: 863 assert(0); 864 } 865 return VG_FALSE; 866 } 867 868 static VGboolean vg_stroke_outline(struct stroke_iterator *it, 869 struct stroker *stroker, 870 VGboolean cap_first, 871 VGfloat *start_tangent) 872 { 873 #define MAX_OFFSET 16 874 struct bezier offset_curves[MAX_OFFSET]; 875 VGPathCommand first_element; 876 VGfloat start[2], prev[2]; 877 VGboolean first = VG_TRUE; 878 VGfloat offset; 879 880 first_element = stroke_itr_command(it); 881 if (first_element != VG_MOVE_TO_ABS) { 882 stroker_emit_move_to(stroker, 0.f, 0.f); 883 prev[0] = 0.f; 884 prev[1] = 0.f; 885 } 886 stroke_itr_coords(it, start); 887 #if STROKE_DEBUG 888 debug_printf(" -> (side) [%.2f, %.2f]\n", 889 start[0], 890 start[1]); 891 #endif 892 893 prev[0] = start[0]; 894 prev[1] = start[1]; 895 896 offset = stroker->stroke_width / 2; 897 898 if (!it->has_next(it)) { 899 /* single point */ 900 901 return VG_TRUE; 902 } 903 904 while (it->has_next(it)) { 905 VGPathCommand cmd; 906 VGfloat coords[8]; 907 908 it->next(it); 909 cmd = stroke_itr_command(it); 910 stroke_itr_coords(it, coords); 911 912 if (cmd == VG_LINE_TO_ABS) { 913 VGfloat line[4] = {prev[0], prev[1], coords[0], coords[1]}; 914 VGfloat normal[4]; 915 line_normal(line, normal); 916 917 #if STROKE_DEBUG 918 debug_printf("\n ---> (side) lineto [%.2f, %.2f]\n", coords[0], coords[1]); 919 #endif 920 line_set_length(normal, offset); 921 line_translate(line, line_dx(normal), line_dy(normal)); 922 923 /* if we are starting a new subpath, move to correct starting point */ 924 if (first) { 925 if (cap_first) 926 create_joins(stroker, prev[0], prev[1], line, 927 stroker_cap_mode(stroker)); 928 else 929 stroker_emit_move_to(stroker, line[0], line[1]); 930 memcpy(start_tangent, line, 931 sizeof(VGfloat) * 4); 932 first = VG_FALSE; 933 } else { 934 create_joins(stroker, prev[0], prev[1], line, 935 stroker_join_mode(stroker)); 936 } 937 938 /* add the stroke for this line */ 939 stroker_emit_line_to(stroker, line[2], line[3]); 940 prev[0] = coords[0]; 941 prev[1] = coords[1]; 942 } else if (cmd == VG_CUBIC_TO_ABS) { 943 #if STROKE_DEBUG 944 debug_printf("\n ---> (side) cubicTo [%.2f, %.2f]\n", 945 coords[4], 946 coords[5]); 947 #endif 948 struct bezier bezier; 949 int count; 950 951 bezier_init(&bezier, 952 prev[0], prev[1], coords[0], coords[1], 953 coords[2], coords[3], coords[4], coords[5]); 954 955 count = bezier_translate_by_normal(&bezier, 956 offset_curves, 957 MAX_OFFSET, 958 offset, 959 curve_threshold); 960 961 if (count) { 962 /* if we are starting a new subpath, move to correct starting point */ 963 VGfloat tangent[4]; 964 VGint i; 965 966 bezier_start_tangent(&bezier, tangent); 967 line_translate(tangent, 968 offset_curves[0].x1 - bezier.x1, 969 offset_curves[0].y1 - bezier.y1); 970 if (first) { 971 VGfloat pt[2] = {offset_curves[0].x1, 972 offset_curves[0].y1}; 973 974 if (cap_first) { 975 create_joins(stroker, prev[0], prev[1], tangent, 976 stroker_cap_mode(stroker)); 977 } else { 978 stroker_emit_move_to(stroker, pt[0], pt[1]); 979 } 980 start_tangent[0] = tangent[0]; 981 start_tangent[1] = tangent[1]; 982 start_tangent[2] = tangent[2]; 983 start_tangent[3] = tangent[3]; 984 first = VG_FALSE; 985 } else { 986 create_joins(stroker, prev[0], prev[1], tangent, 987 stroker_join_mode(stroker)); 988 } 989 990 /* add these beziers */ 991 for (i = 0; i < count; ++i) { 992 struct bezier *bez = &offset_curves[i]; 993 stroker_emit_curve_to(stroker, 994 bez->x2, bez->y2, 995 bez->x3, bez->y3, 996 bez->x4, bez->y4); 997 } 998 } 999 1000 prev[0] = coords[4]; 1001 prev[1] = coords[5]; 1002 } 1003 } 1004 1005 if (floatsEqual(start[0], prev[0]) && 1006 floatsEqual(start[1], prev[1])) { 1007 /* closed subpath, join first and last point */ 1008 #if STROKE_DEBUG 1009 debug_printf("\n stroker: closed subpath\n"); 1010 #endif 1011 create_joins(stroker, prev[0], prev[1], start_tangent, 1012 stroker_join_mode(stroker)); 1013 return VG_TRUE; 1014 } else { 1015 #if STROKE_DEBUG 1016 debug_printf("\n stroker: open subpath\n"); 1017 #endif 1018 return VG_FALSE; 1019 } 1020 #undef MAX_OFFSET 1021 } 1022 1023 static void stroker_process_subpath(struct stroker *stroker) 1024 { 1025 VGboolean fwclosed, bwclosed; 1026 VGfloat fw_start_tangent[4], bw_start_tangent[4]; 1027 struct stroke_iterator fwit; 1028 struct stroke_iterator bwit; 1029 debug_assert(stroker->segments->num_elements > 0); 1030 1031 memset(fw_start_tangent, 0, 1032 sizeof(VGfloat)*4); 1033 memset(bw_start_tangent, 0, 1034 sizeof(VGfloat)*4); 1035 1036 stroke_forward_iterator(&fwit, stroker->segments, 1037 stroker->control_points); 1038 stroke_backward_iterator(&bwit, stroker->segments, 1039 stroker->control_points); 1040 1041 debug_assert(fwit.cmds[0] == VG_MOVE_TO_ABS); 1042 1043 fwclosed = vg_stroke_outline(&fwit, stroker, VG_FALSE, fw_start_tangent); 1044 bwclosed = vg_stroke_outline(&bwit, stroker, !fwclosed, bw_start_tangent); 1045 1046 if (!bwclosed) 1047 create_joins(stroker, 1048 fwit.coords[0], fwit.coords[1], fw_start_tangent, 1049 stroker_cap_mode(stroker)); 1050 else { 1051 /* hack to handle the requirement of the VG spec that says that strokes 1052 * of len==0 that have butt cap or round cap still need 1053 * to be rendered. (8.7.4 Stroke Generation) */ 1054 if (stroker->segments->num_elements <= 3) { 1055 VGPathCommand cmd; 1056 VGfloat data[8], coords[8]; 1057 struct stroke_iterator *it = &fwit; 1058 1059 stroke_forward_iterator(it, stroker->segments, 1060 stroker->control_points); 1061 cmd = stroke_itr_command(it); 1062 stroke_itr_coords(it, coords); 1063 if (cmd != VG_MOVE_TO_ABS) { 1064 memset(data, 0, sizeof(VGfloat) * 8); 1065 if (!is_segment_null(cmd, coords, data)) 1066 return; 1067 } else { 1068 data[0] = coords[0]; 1069 data[1] = coords[1]; 1070 } 1071 while (it->has_next(it)) { 1072 it->next(it); 1073 cmd = stroke_itr_command(it); 1074 stroke_itr_coords(it, coords); 1075 if (!is_segment_null(cmd, coords, data)) 1076 return; 1077 } 1078 /* generate the square/round cap */ 1079 if (stroker->cap_style == VG_CAP_SQUARE) { 1080 VGfloat offset = stroker->stroke_width / 2; 1081 stroker_emit_move_to(stroker, data[0] - offset, 1082 data[1] - offset); 1083 stroker_emit_line_to(stroker, data[0] + offset, 1084 data[1] - offset); 1085 stroker_emit_line_to(stroker, data[0] + offset, 1086 data[1] + offset); 1087 stroker_emit_line_to(stroker, data[0] - offset, 1088 data[1] + offset); 1089 stroker_emit_line_to(stroker, data[0] - offset, 1090 data[1] - offset); 1091 } else if (stroker->cap_style == VG_CAP_ROUND) { 1092 VGfloat offset = stroker->stroke_width / 2; 1093 VGfloat cx = data[0], cy = data[1]; 1094 { /*circle */ 1095 struct arc arc; 1096 struct matrix matrix; 1097 matrix_load_identity(&matrix); 1098 1099 stroker_emit_move_to(stroker, cx + offset, cy); 1100 arc_init(&arc, VG_SCCWARC_TO, 1101 cx + offset, cy, 1102 cx - offset, cy, 1103 offset, offset, 0); 1104 arc_stroker_emit(&arc, stroker, &matrix); 1105 arc_init(&arc, VG_SCCWARC_TO, 1106 cx - offset, cy, 1107 cx + offset, cy, 1108 offset, offset, 0); 1109 arc_stroker_emit(&arc, stroker, &matrix); 1110 } 1111 } 1112 } 1113 } 1114 } 1115 1116 static INLINE VGfloat dash_pattern(struct dash_stroker *stroker, 1117 VGint idx) 1118 { 1119 if (stroker->dash_pattern[idx] < 0) 1120 return 0.f; 1121 return stroker->dash_pattern[idx]; 1122 } 1123 1124 static void dash_stroker_process_subpath(struct stroker *str) 1125 { 1126 struct dash_stroker *stroker = (struct dash_stroker *)str; 1127 VGfloat sum_length = 0; 1128 VGint i; 1129 VGint idash = 0; 1130 VGfloat pos = 0; 1131 VGfloat elen = 0; 1132 VGfloat doffset = stroker->dash_phase; 1133 VGfloat estart = 0; 1134 VGfloat estop = 0; 1135 VGfloat cline[4]; 1136 struct stroke_iterator it; 1137 VGfloat prev[2]; 1138 VGfloat move_to_pos[2]; 1139 VGfloat line_to_pos[2]; 1140 1141 VGboolean has_move_to = VG_FALSE; 1142 1143 stroke_flat_iterator(&it, stroker->base.segments, 1144 stroker->base.control_points); 1145 1146 stroke_itr_coords(&it, prev); 1147 move_to_pos[0] = prev[0]; 1148 move_to_pos[1] = prev[1]; 1149 1150 debug_assert(stroker->dash_pattern_num > 0); 1151 1152 for (i = 0; i < stroker->dash_pattern_num; ++i) { 1153 sum_length += dash_pattern(stroker, i); 1154 } 1155 1156 if (floatIsZero(sum_length)) { 1157 return; 1158 } 1159 1160 doffset -= floorf(doffset / sum_length) * sum_length; 1161 1162 while (!floatIsZero(doffset) && doffset >= dash_pattern(stroker, idash)) { 1163 doffset -= dash_pattern(stroker, idash); 1164 idash = (idash + 1) % stroker->dash_pattern_num; 1165 } 1166 1167 while (it.has_next(&it)) { 1168 VGPathCommand cmd; 1169 VGfloat coords[8]; 1170 VGboolean done; 1171 1172 it.next(&it); 1173 cmd = stroke_itr_command(&it); 1174 stroke_itr_coords(&it, coords); 1175 1176 debug_assert(cmd == VG_LINE_TO_ABS); 1177 cline[0] = prev[0]; 1178 cline[1] = prev[1]; 1179 cline[2] = coords[0]; 1180 cline[3] = coords[1]; 1181 1182 elen = line_lengthv(cline); 1183 1184 estop = estart + elen; 1185 1186 done = pos >= estop; 1187 while (!done) { 1188 VGfloat p2[2]; 1189 1190 VGint idash_incr = 0; 1191 VGboolean has_offset = doffset > 0; 1192 VGfloat dpos = pos + dash_pattern(stroker, idash) - doffset - estart; 1193 1194 debug_assert(dpos >= 0); 1195 1196 if (dpos > elen) { /* dash extends this line */ 1197 doffset = dash_pattern(stroker, idash) - (dpos - elen); 1198 pos = estop; 1199 done = VG_TRUE; 1200 p2[0] = cline[2]; 1201 p2[1] = cline[3]; 1202 } else { /* Dash is on this line */ 1203 line_point_at(cline, dpos/elen, p2); 1204 pos = dpos + estart; 1205 done = pos >= estop; 1206 idash_incr = 1; 1207 doffset = 0; 1208 } 1209 1210 if (idash % 2 == 0) { 1211 line_to_pos[0] = p2[0]; 1212 line_to_pos[1] = p2[1]; 1213 1214 if (!has_offset || !has_move_to) { 1215 stroker_move_to(&stroker->stroker, move_to_pos[0], move_to_pos[1]); 1216 has_move_to = VG_TRUE; 1217 } 1218 stroker_line_to(&stroker->stroker, line_to_pos[0], line_to_pos[1]); 1219 } else { 1220 move_to_pos[0] = p2[0]; 1221 move_to_pos[1] = p2[1]; 1222 } 1223 1224 idash = (idash + idash_incr) % stroker->dash_pattern_num; 1225 } 1226 1227 estart = estop; 1228 prev[0] = coords[0]; 1229 prev[1] = coords[1]; 1230 } 1231 1232 if (it.curve_poly) { 1233 polygon_destroy(it.curve_poly); 1234 it.curve_poly = 0; 1235 } 1236 1237 stroker->base.path = stroker->stroker.path; 1238 } 1239 1240 static void default_begin(struct stroker *stroker) 1241 { 1242 array_reset(stroker->segments); 1243 array_reset(stroker->control_points); 1244 } 1245 1246 static void default_end(struct stroker *stroker) 1247 { 1248 if (stroker->segments->num_elements > 0) 1249 stroker->process_subpath(stroker); 1250 } 1251 1252 1253 static void dash_stroker_begin(struct stroker *stroker) 1254 { 1255 struct dash_stroker *dasher = 1256 (struct dash_stroker *)stroker; 1257 1258 default_begin(&dasher->stroker); 1259 default_begin(stroker); 1260 } 1261 1262 static void dash_stroker_end(struct stroker *stroker) 1263 { 1264 struct dash_stroker *dasher = 1265 (struct dash_stroker *)stroker; 1266 1267 default_end(stroker); 1268 default_end(&dasher->stroker); 1269 } 1270 1271 void stroker_init(struct stroker *stroker, 1272 struct vg_state *state) 1273 { 1274 stroker->stroke_width = state->stroke.line_width.f; 1275 stroker->miter_limit = state->stroke.miter_limit.f; 1276 stroker->cap_style = state->stroke.cap_style; 1277 stroker->join_style = state->stroke.join_style; 1278 1279 stroker->begin = default_begin; 1280 stroker->process_subpath = stroker_process_subpath; 1281 stroker->end = default_end; 1282 1283 stroker->segments = array_create(sizeof(VGubyte)); 1284 stroker->control_points = array_create(sizeof(VGfloat)); 1285 1286 stroker->back1_x = 0; 1287 stroker->back1_y = 0; 1288 stroker->back2_x = 0; 1289 stroker->back2_y = 0; 1290 1291 stroker->path = path_create(VG_PATH_DATATYPE_F, 1.0f, 0.0f, 1292 0, 0, VG_PATH_CAPABILITY_ALL); 1293 1294 /* Initialize with an invalid value */ 1295 stroker->last_cmd = (VGPathCommand)0; 1296 } 1297 1298 void dash_stroker_init(struct stroker *str, 1299 struct vg_state *state) 1300 { 1301 struct dash_stroker *stroker = (struct dash_stroker *)str; 1302 int i; 1303 1304 stroker_init(str, state); 1305 stroker_init(&stroker->stroker, state); 1306 1307 { 1308 int real_num = state->stroke.dash_pattern_num; 1309 if (real_num % 2)/* if odd, ignore the last one */ 1310 --real_num; 1311 for (i = 0; i < real_num; ++i) 1312 stroker->dash_pattern[i] = state->stroke.dash_pattern[i].f; 1313 stroker->dash_pattern_num = real_num; 1314 } 1315 1316 stroker->dash_phase = state->stroke.dash_phase.f; 1317 stroker->dash_phase_reset = state->stroke.dash_phase_reset; 1318 1319 stroker->base.begin = dash_stroker_begin; 1320 stroker->base.process_subpath = dash_stroker_process_subpath; 1321 stroker->base.end = dash_stroker_end; 1322 path_destroy(stroker->base.path); 1323 stroker->base.path = NULL; 1324 } 1325 1326 void stroker_begin(struct stroker *stroker) 1327 { 1328 stroker->begin(stroker); 1329 } 1330 1331 void stroker_end(struct stroker *stroker) 1332 { 1333 stroker->end(stroker); 1334 } 1335 1336 void stroker_cleanup(struct stroker *stroker) 1337 { 1338 array_destroy(stroker->segments); 1339 array_destroy(stroker->control_points); 1340 } 1341 1342 void dash_stroker_cleanup(struct dash_stroker *stroker) 1343 { 1344 /* if stroker->base.path is null means we never 1345 * processed a valid path so delete the temp one 1346 * we already created */ 1347 if (!stroker->base.path) 1348 path_destroy(stroker->stroker.path); 1349 stroker_cleanup(&stroker->stroker); 1350 stroker_cleanup((struct stroker*)stroker); 1351 } 1352
