1 //---------------------------------------------------------------------------- 2 // Anti-Grain Geometry - Version 2.4 3 // Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com) 4 // Copyright (C) 2005 Tony Juricic (tonygeek@yahoo.com) 5 // 6 // Permission to copy, use, modify, sell and distribute this software 7 // is granted provided this copyright notice appears in all copies. 8 // This software is provided "as is" without express or implied 9 // warranty, and with no claim as to its suitability for any purpose. 10 // 11 //---------------------------------------------------------------------------- 12 // Contact: mcseem@antigrain.com 13 // mcseemagg@yahoo.com 14 // http://www.antigrain.com 15 //---------------------------------------------------------------------------- 16 17 #ifndef AGG_CURVES_INCLUDED 18 #define AGG_CURVES_INCLUDED 19 20 #include "agg_array.h" 21 22 namespace agg 23 { 24 25 // See Implementation agg_curves.cpp 26 27 //--------------------------------------------curve_approximation_method_e 28 enum curve_approximation_method_e 29 { 30 curve_inc, 31 curve_div 32 }; 33 34 //--------------------------------------------------------------curve3_inc 35 class curve3_inc 36 { 37 public: curve3_inc()38 curve3_inc() : 39 m_num_steps(0), m_step(0), m_scale(1.0) { } 40 curve3_inc(double x1,double y1,double x2,double y2,double x3,double y3)41 curve3_inc(double x1, double y1, 42 double x2, double y2, 43 double x3, double y3) : 44 m_num_steps(0), m_step(0), m_scale(1.0) 45 { 46 init(x1, y1, x2, y2, x3, y3); 47 } 48 reset()49 void reset() { m_num_steps = 0; m_step = -1; } 50 void init(double x1, double y1, 51 double x2, double y2, 52 double x3, double y3); 53 approximation_method(curve_approximation_method_e)54 void approximation_method(curve_approximation_method_e) {} approximation_method()55 curve_approximation_method_e approximation_method() const { return curve_inc; } 56 57 void approximation_scale(double s); 58 double approximation_scale() const; 59 angle_tolerance(double)60 void angle_tolerance(double) {} angle_tolerance()61 double angle_tolerance() const { return 0.0; } 62 cusp_limit(double)63 void cusp_limit(double) {} cusp_limit()64 double cusp_limit() const { return 0.0; } 65 66 void rewind(unsigned path_id); 67 unsigned vertex(double* x, double* y); 68 69 private: 70 int m_num_steps; 71 int m_step; 72 double m_scale; 73 double m_start_x; 74 double m_start_y; 75 double m_end_x; 76 double m_end_y; 77 double m_fx; 78 double m_fy; 79 double m_dfx; 80 double m_dfy; 81 double m_ddfx; 82 double m_ddfy; 83 double m_saved_fx; 84 double m_saved_fy; 85 double m_saved_dfx; 86 double m_saved_dfy; 87 }; 88 89 90 91 92 93 //-------------------------------------------------------------curve3_div 94 class curve3_div 95 { 96 public: curve3_div()97 curve3_div() : 98 m_approximation_scale(1.0), 99 m_distance_tolerance_square(0.0), 100 m_angle_tolerance(0.0), 101 m_count(0) 102 {} 103 curve3_div(double x1,double y1,double x2,double y2,double x3,double y3)104 curve3_div(double x1, double y1, 105 double x2, double y2, 106 double x3, double y3) : 107 m_approximation_scale(1.0), 108 m_angle_tolerance(0.0), 109 m_count(0) 110 { 111 init(x1, y1, x2, y2, x3, y3); 112 } 113 reset()114 void reset() { m_points.remove_all(); m_count = 0; } 115 void init(double x1, double y1, 116 double x2, double y2, 117 double x3, double y3); 118 approximation_method(curve_approximation_method_e)119 void approximation_method(curve_approximation_method_e) {} approximation_method()120 curve_approximation_method_e approximation_method() const { return curve_div; } 121 approximation_scale(double s)122 void approximation_scale(double s) { m_approximation_scale = s; } approximation_scale()123 double approximation_scale() const { return m_approximation_scale; } 124 angle_tolerance(double a)125 void angle_tolerance(double a) { m_angle_tolerance = a; } angle_tolerance()126 double angle_tolerance() const { return m_angle_tolerance; } 127 cusp_limit(double)128 void cusp_limit(double) {} cusp_limit()129 double cusp_limit() const { return 0.0; } 130 rewind(unsigned)131 void rewind(unsigned) 132 { 133 m_count = 0; 134 } 135 vertex(double * x,double * y)136 unsigned vertex(double* x, double* y) 137 { 138 if(m_count >= m_points.size()) return path_cmd_stop; 139 const point_d& p = m_points[m_count++]; 140 *x = p.x; 141 *y = p.y; 142 return (m_count == 1) ? path_cmd_move_to : path_cmd_line_to; 143 } 144 145 private: 146 void bezier(double x1, double y1, 147 double x2, double y2, 148 double x3, double y3); 149 void recursive_bezier(double x1, double y1, 150 double x2, double y2, 151 double x3, double y3, 152 unsigned level); 153 154 double m_approximation_scale; 155 double m_distance_tolerance_square; 156 double m_angle_tolerance; 157 unsigned m_count; 158 pod_bvector<point_d> m_points; 159 }; 160 161 162 163 164 165 166 167 //-------------------------------------------------------------curve4_points 168 struct curve4_points 169 { 170 double cp[8]; curve4_pointscurve4_points171 curve4_points() {} curve4_pointscurve4_points172 curve4_points(double x1, double y1, 173 double x2, double y2, 174 double x3, double y3, 175 double x4, double y4) 176 { 177 cp[0] = x1; cp[1] = y1; cp[2] = x2; cp[3] = y2; 178 cp[4] = x3; cp[5] = y3; cp[6] = x4; cp[7] = y4; 179 } initcurve4_points180 void init(double x1, double y1, 181 double x2, double y2, 182 double x3, double y3, 183 double x4, double y4) 184 { 185 cp[0] = x1; cp[1] = y1; cp[2] = x2; cp[3] = y2; 186 cp[4] = x3; cp[5] = y3; cp[6] = x4; cp[7] = y4; 187 } 188 double operator [] (unsigned i) const { return cp[i]; } 189 double& operator [] (unsigned i) { return cp[i]; } 190 }; 191 192 193 194 //-------------------------------------------------------------curve4_inc 195 class curve4_inc 196 { 197 public: curve4_inc()198 curve4_inc() : 199 m_num_steps(0), m_step(0), m_scale(1.0) { } 200 curve4_inc(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)201 curve4_inc(double x1, double y1, 202 double x2, double y2, 203 double x3, double y3, 204 double x4, double y4) : 205 m_num_steps(0), m_step(0), m_scale(1.0) 206 { 207 init(x1, y1, x2, y2, x3, y3, x4, y4); 208 } 209 curve4_inc(const curve4_points & cp)210 curve4_inc(const curve4_points& cp) : 211 m_num_steps(0), m_step(0), m_scale(1.0) 212 { 213 init(cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]); 214 } 215 reset()216 void reset() { m_num_steps = 0; m_step = -1; } 217 void init(double x1, double y1, 218 double x2, double y2, 219 double x3, double y3, 220 double x4, double y4); 221 init(const curve4_points & cp)222 void init(const curve4_points& cp) 223 { 224 init(cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]); 225 } 226 approximation_method(curve_approximation_method_e)227 void approximation_method(curve_approximation_method_e) {} approximation_method()228 curve_approximation_method_e approximation_method() const { return curve_inc; } 229 230 void approximation_scale(double s); 231 double approximation_scale() const; 232 angle_tolerance(double)233 void angle_tolerance(double) {} angle_tolerance()234 double angle_tolerance() const { return 0.0; } 235 cusp_limit(double)236 void cusp_limit(double) {} cusp_limit()237 double cusp_limit() const { return 0.0; } 238 239 void rewind(unsigned path_id); 240 unsigned vertex(double* x, double* y); 241 242 private: 243 int m_num_steps; 244 int m_step; 245 double m_scale; 246 double m_start_x; 247 double m_start_y; 248 double m_end_x; 249 double m_end_y; 250 double m_fx; 251 double m_fy; 252 double m_dfx; 253 double m_dfy; 254 double m_ddfx; 255 double m_ddfy; 256 double m_dddfx; 257 double m_dddfy; 258 double m_saved_fx; 259 double m_saved_fy; 260 double m_saved_dfx; 261 double m_saved_dfy; 262 double m_saved_ddfx; 263 double m_saved_ddfy; 264 }; 265 266 267 268 //-------------------------------------------------------catrom_to_bezier catrom_to_bezier(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)269 inline curve4_points catrom_to_bezier(double x1, double y1, 270 double x2, double y2, 271 double x3, double y3, 272 double x4, double y4) 273 { 274 // Trans. matrix Catmull-Rom to Bezier 275 // 276 // 0 1 0 0 277 // -1/6 1 1/6 0 278 // 0 1/6 1 -1/6 279 // 0 0 1 0 280 // 281 return curve4_points( 282 x2, 283 y2, 284 (-x1 + 6*x2 + x3) / 6, 285 (-y1 + 6*y2 + y3) / 6, 286 ( x2 + 6*x3 - x4) / 6, 287 ( y2 + 6*y3 - y4) / 6, 288 x3, 289 y3); 290 } 291 292 293 //----------------------------------------------------------------------- 294 inline curve4_points catrom_to_bezier(const curve4_points & cp)295 catrom_to_bezier(const curve4_points& cp) 296 { 297 return catrom_to_bezier(cp[0], cp[1], cp[2], cp[3], 298 cp[4], cp[5], cp[6], cp[7]); 299 } 300 301 302 303 //-----------------------------------------------------ubspline_to_bezier ubspline_to_bezier(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)304 inline curve4_points ubspline_to_bezier(double x1, double y1, 305 double x2, double y2, 306 double x3, double y3, 307 double x4, double y4) 308 { 309 // Trans. matrix Uniform BSpline to Bezier 310 // 311 // 1/6 4/6 1/6 0 312 // 0 4/6 2/6 0 313 // 0 2/6 4/6 0 314 // 0 1/6 4/6 1/6 315 // 316 return curve4_points( 317 (x1 + 4*x2 + x3) / 6, 318 (y1 + 4*y2 + y3) / 6, 319 (4*x2 + 2*x3) / 6, 320 (4*y2 + 2*y3) / 6, 321 (2*x2 + 4*x3) / 6, 322 (2*y2 + 4*y3) / 6, 323 (x2 + 4*x3 + x4) / 6, 324 (y2 + 4*y3 + y4) / 6); 325 } 326 327 328 //----------------------------------------------------------------------- 329 inline curve4_points ubspline_to_bezier(const curve4_points & cp)330 ubspline_to_bezier(const curve4_points& cp) 331 { 332 return ubspline_to_bezier(cp[0], cp[1], cp[2], cp[3], 333 cp[4], cp[5], cp[6], cp[7]); 334 } 335 336 337 338 339 //------------------------------------------------------hermite_to_bezier hermite_to_bezier(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)340 inline curve4_points hermite_to_bezier(double x1, double y1, 341 double x2, double y2, 342 double x3, double y3, 343 double x4, double y4) 344 { 345 // Trans. matrix Hermite to Bezier 346 // 347 // 1 0 0 0 348 // 1 0 1/3 0 349 // 0 1 0 -1/3 350 // 0 1 0 0 351 // 352 return curve4_points( 353 x1, 354 y1, 355 (3*x1 + x3) / 3, 356 (3*y1 + y3) / 3, 357 (3*x2 - x4) / 3, 358 (3*y2 - y4) / 3, 359 x2, 360 y2); 361 } 362 363 364 365 //----------------------------------------------------------------------- 366 inline curve4_points hermite_to_bezier(const curve4_points & cp)367 hermite_to_bezier(const curve4_points& cp) 368 { 369 return hermite_to_bezier(cp[0], cp[1], cp[2], cp[3], 370 cp[4], cp[5], cp[6], cp[7]); 371 } 372 373 374 //-------------------------------------------------------------curve4_div 375 class curve4_div 376 { 377 public: curve4_div()378 curve4_div() : 379 m_approximation_scale(1.0), 380 m_distance_tolerance_square(0.0), 381 m_angle_tolerance(0.0), 382 m_cusp_limit(0.0), 383 m_count(0) 384 {} 385 curve4_div(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)386 curve4_div(double x1, double y1, 387 double x2, double y2, 388 double x3, double y3, 389 double x4, double y4) : 390 m_approximation_scale(1.0), 391 m_angle_tolerance(0.0), 392 m_cusp_limit(0.0), 393 m_count(0) 394 { 395 init(x1, y1, x2, y2, x3, y3, x4, y4); 396 } 397 curve4_div(const curve4_points & cp)398 curve4_div(const curve4_points& cp) : 399 m_approximation_scale(1.0), 400 m_angle_tolerance(0.0), 401 m_count(0) 402 { 403 init(cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]); 404 } 405 reset()406 void reset() { m_points.remove_all(); m_count = 0; } 407 void init(double x1, double y1, 408 double x2, double y2, 409 double x3, double y3, 410 double x4, double y4); 411 init(const curve4_points & cp)412 void init(const curve4_points& cp) 413 { 414 init(cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]); 415 } 416 approximation_method(curve_approximation_method_e)417 void approximation_method(curve_approximation_method_e) {} 418 approximation_method()419 curve_approximation_method_e approximation_method() const 420 { 421 return curve_div; 422 } 423 approximation_scale(double s)424 void approximation_scale(double s) { m_approximation_scale = s; } approximation_scale()425 double approximation_scale() const { return m_approximation_scale; } 426 angle_tolerance(double a)427 void angle_tolerance(double a) { m_angle_tolerance = a; } angle_tolerance()428 double angle_tolerance() const { return m_angle_tolerance; } 429 cusp_limit(double v)430 void cusp_limit(double v) 431 { 432 m_cusp_limit = (v == 0.0) ? 0.0 : pi - v; 433 } 434 cusp_limit()435 double cusp_limit() const 436 { 437 return (m_cusp_limit == 0.0) ? 0.0 : pi - m_cusp_limit; 438 } 439 rewind(unsigned)440 void rewind(unsigned) 441 { 442 m_count = 0; 443 } 444 vertex(double * x,double * y)445 unsigned vertex(double* x, double* y) 446 { 447 if(m_count >= m_points.size()) return path_cmd_stop; 448 const point_d& p = m_points[m_count++]; 449 *x = p.x; 450 *y = p.y; 451 return (m_count == 1) ? path_cmd_move_to : path_cmd_line_to; 452 } 453 454 private: 455 void bezier(double x1, double y1, 456 double x2, double y2, 457 double x3, double y3, 458 double x4, double y4); 459 460 void recursive_bezier(double x1, double y1, 461 double x2, double y2, 462 double x3, double y3, 463 double x4, double y4, 464 unsigned level); 465 466 double m_approximation_scale; 467 double m_distance_tolerance_square; 468 double m_angle_tolerance; 469 double m_cusp_limit; 470 unsigned m_count; 471 pod_bvector<point_d> m_points; 472 }; 473 474 475 //-----------------------------------------------------------------curve3 476 class curve3 477 { 478 public: curve3()479 curve3() : m_approximation_method(curve_div) {} curve3(double x1,double y1,double x2,double y2,double x3,double y3)480 curve3(double x1, double y1, 481 double x2, double y2, 482 double x3, double y3) : 483 m_approximation_method(curve_div) 484 { 485 init(x1, y1, x2, y2, x3, y3); 486 } 487 reset()488 void reset() 489 { 490 m_curve_inc.reset(); 491 m_curve_div.reset(); 492 } 493 init(double x1,double y1,double x2,double y2,double x3,double y3)494 void init(double x1, double y1, 495 double x2, double y2, 496 double x3, double y3) 497 { 498 if(m_approximation_method == curve_inc) 499 { 500 m_curve_inc.init(x1, y1, x2, y2, x3, y3); 501 } 502 else 503 { 504 m_curve_div.init(x1, y1, x2, y2, x3, y3); 505 } 506 } 507 approximation_method(curve_approximation_method_e v)508 void approximation_method(curve_approximation_method_e v) 509 { 510 m_approximation_method = v; 511 } 512 approximation_method()513 curve_approximation_method_e approximation_method() const 514 { 515 return m_approximation_method; 516 } 517 approximation_scale(double s)518 void approximation_scale(double s) 519 { 520 m_curve_inc.approximation_scale(s); 521 m_curve_div.approximation_scale(s); 522 } 523 approximation_scale()524 double approximation_scale() const 525 { 526 return m_curve_inc.approximation_scale(); 527 } 528 angle_tolerance(double a)529 void angle_tolerance(double a) 530 { 531 m_curve_div.angle_tolerance(a); 532 } 533 angle_tolerance()534 double angle_tolerance() const 535 { 536 return m_curve_div.angle_tolerance(); 537 } 538 cusp_limit(double v)539 void cusp_limit(double v) 540 { 541 m_curve_div.cusp_limit(v); 542 } 543 cusp_limit()544 double cusp_limit() const 545 { 546 return m_curve_div.cusp_limit(); 547 } 548 rewind(unsigned path_id)549 void rewind(unsigned path_id) 550 { 551 if(m_approximation_method == curve_inc) 552 { 553 m_curve_inc.rewind(path_id); 554 } 555 else 556 { 557 m_curve_div.rewind(path_id); 558 } 559 } 560 vertex(double * x,double * y)561 unsigned vertex(double* x, double* y) 562 { 563 if(m_approximation_method == curve_inc) 564 { 565 return m_curve_inc.vertex(x, y); 566 } 567 return m_curve_div.vertex(x, y); 568 } 569 570 private: 571 curve3_inc m_curve_inc; 572 curve3_div m_curve_div; 573 curve_approximation_method_e m_approximation_method; 574 }; 575 576 577 578 579 580 //-----------------------------------------------------------------curve4 581 class curve4 582 { 583 public: curve4()584 curve4() : m_approximation_method(curve_div) {} curve4(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)585 curve4(double x1, double y1, 586 double x2, double y2, 587 double x3, double y3, 588 double x4, double y4) : 589 m_approximation_method(curve_div) 590 { 591 init(x1, y1, x2, y2, x3, y3, x4, y4); 592 } 593 curve4(const curve4_points & cp)594 curve4(const curve4_points& cp) : 595 m_approximation_method(curve_div) 596 { 597 init(cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]); 598 } 599 reset()600 void reset() 601 { 602 m_curve_inc.reset(); 603 m_curve_div.reset(); 604 } 605 init(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)606 void init(double x1, double y1, 607 double x2, double y2, 608 double x3, double y3, 609 double x4, double y4) 610 { 611 if(m_approximation_method == curve_inc) 612 { 613 m_curve_inc.init(x1, y1, x2, y2, x3, y3, x4, y4); 614 } 615 else 616 { 617 m_curve_div.init(x1, y1, x2, y2, x3, y3, x4, y4); 618 } 619 } 620 init(const curve4_points & cp)621 void init(const curve4_points& cp) 622 { 623 init(cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]); 624 } 625 approximation_method(curve_approximation_method_e v)626 void approximation_method(curve_approximation_method_e v) 627 { 628 m_approximation_method = v; 629 } 630 approximation_method()631 curve_approximation_method_e approximation_method() const 632 { 633 return m_approximation_method; 634 } 635 approximation_scale(double s)636 void approximation_scale(double s) 637 { 638 m_curve_inc.approximation_scale(s); 639 m_curve_div.approximation_scale(s); 640 } approximation_scale()641 double approximation_scale() const { return m_curve_inc.approximation_scale(); } 642 angle_tolerance(double v)643 void angle_tolerance(double v) 644 { 645 m_curve_div.angle_tolerance(v); 646 } 647 angle_tolerance()648 double angle_tolerance() const 649 { 650 return m_curve_div.angle_tolerance(); 651 } 652 cusp_limit(double v)653 void cusp_limit(double v) 654 { 655 m_curve_div.cusp_limit(v); 656 } 657 cusp_limit()658 double cusp_limit() const 659 { 660 return m_curve_div.cusp_limit(); 661 } 662 rewind(unsigned path_id)663 void rewind(unsigned path_id) 664 { 665 if(m_approximation_method == curve_inc) 666 { 667 m_curve_inc.rewind(path_id); 668 } 669 else 670 { 671 m_curve_div.rewind(path_id); 672 } 673 } 674 vertex(double * x,double * y)675 unsigned vertex(double* x, double* y) 676 { 677 if(m_approximation_method == curve_inc) 678 { 679 return m_curve_inc.vertex(x, y); 680 } 681 return m_curve_div.vertex(x, y); 682 } 683 684 private: 685 curve4_inc m_curve_inc; 686 curve4_div m_curve_div; 687 curve_approximation_method_e m_approximation_method; 688 }; 689 690 691 692 693 } 694 695 #endif 696