src/display/curve.cpp

   1 #define __CURVE_C__
   2
   3 /** \file
   4  * Routines for SPCurve and for NArtBpath arrays in general.
   5  */
   6
   7 /*
   8  * Author:
   9  *   Lauris Kaplinski <lauris@kaplinski.com>
  10  *
  11  * Copyright (C) 2000 Lauris Kaplinski
  12  * Copyright (C) 2000-2001 Ximian, Inc.
  13  * Copyright (C) 2002 Lauris Kaplinski
  14  *
  15  * Released under GNU GPL
  16  */
  17
  18
  19 #include <glib/gmem.h>
  20 #include <display/curve.h>
  21 #include <libnr/n-art-bpath.h>
  22 #include <libnr/nr-point-matrix-ops.h>
  23 #include <libnr/nr-translate-ops.h>
  24
  25 #define SP_CURVE_LENSTEP 32
  26
  27 static bool sp_bpath_good(NArtBpath const bpath[]);
  28 static NArtBpath *sp_bpath_clean(NArtBpath const bpath[]);
  29 static NArtBpath const *sp_bpath_check_subpath(NArtBpath const bpath[]);
  30 static unsigned sp_bpath_length(NArtBpath const bpath[]);
  31 static bool sp_bpath_closed(NArtBpath const bpath[]);
  32
  33 /* Constructors */
  34
  35 /**
  36  * The returned curve's state is as if sp_curve_reset has just been called on it.
  37  */
  38 SPCurve *
  39 sp_curve_new()
  40 {
  41     return sp_curve_new_sized(SP_CURVE_LENSTEP);
  42 }
  43
  44 /**
  45  * Like sp_curve_new, but overriding the default initial capacity.
  46  *
  47  * The returned curve's state is as if sp_curve_reset has just been called on it.
  48  *
  49  * \param length Initial number of NArtBpath elements allocated for bpath (including NR_END
  50  *    element).
  51  */
  52 SPCurve *
  53 sp_curve_new_sized(gint length)
  54 {
  55     g_return_val_if_fail(length > 0, NULL);
  56
  57     SPCurve *curve = g_new(SPCurve, 1);
  58
  59     curve->refcount = 1;
  60     curve->_bpath = g_new(NArtBpath, length);
  61     curve->_bpath->code = NR_END;
  62     curve->end = 0;
  63     curve->length = length;
  64     curve->substart = 0;
  65     curve->hascpt = false;
  66     curve->posSet = false;
  67     curve->moving = false;
  68     curve->closed = false;
  69
  70     return curve;
  71 }
  72
  73 /**
  74  * Convert NArtBpath object to SPCurve object.
  75  *
  76  * \return new SPCurve, or NULL if the curve was not created for some reason.
  77  */
  78 SPCurve *
  79 sp_curve_new_from_bpath(NArtBpath *bpath)
  80 {
  81     g_return_val_if_fail(bpath != NULL, NULL);
  82
  83     SPCurve *curve = sp_curve_new_from_foreign_bpath(bpath);
  84     g_free(bpath);
  85     return curve;
  86 }
  87
  88 /**
  89  * Convert const NArtBpath array to SPCurve.
  90  *
  91  * \return new SPCurve, or NULL if the curve was not created for some reason.
  92  */
  93 SPCurve *sp_curve_new_from_foreign_bpath(NArtBpath const bpath[])
  94 {
  95     g_return_val_if_fail(bpath != NULL, NULL);
  96
  97     NArtBpath *new_bpath;
  98     if (!sp_bpath_good(bpath)) {
  99         new_bpath = sp_bpath_clean(bpath);
 100         g_return_val_if_fail(new_bpath != NULL, NULL);
 101     } else {
 102         unsigned const len = sp_bpath_length(bpath);
 103         new_bpath = g_new(NArtBpath, len);
 104         memcpy(new_bpath, bpath, len * sizeof(NArtBpath));
 105     }
 106
 107     SPCurve *curve = g_new(SPCurve, 1);
 108
 109     curve->refcount = 1;
 110     curve->_bpath = new_bpath;
 111     curve->length = sp_bpath_length(new_bpath);
 112     curve->end = curve->length - 1;
 113     gint i = curve->end;
 114     for (; i > 0; i--)
 115         if ((curve->_bpath[i].code == NR_MOVETO) ||
 116             (curve->_bpath[i].code == NR_MOVETO_OPEN))
 117             break;
 118     curve->substart = i;
 119     curve->hascpt = false;
 120     curve->posSet = false;
 121     curve->moving = false;
 122     curve->closed = sp_bpath_closed(new_bpath);
 123
 124     return curve;
 125 }
 126
 127 /**
 128  * Increase refcount of curve.
 129  *
 130  * \todo should this be shared with other refcounting code?
 131  */
 132 SPCurve *
 133 sp_curve_ref(SPCurve *curve)
 134 {
 135     g_return_val_if_fail(curve != NULL, NULL);
 136
 137     curve->refcount += 1;
 138
 139     return curve;
 140 }
 141
 142 /**
 143  * Decrease refcount of curve, with possible destruction.
 144  *
 145  * \todo should this be shared with other refcounting code?
 146  */
 147 SPCurve *
 148 sp_curve_unref(SPCurve *curve)
 149 {
 150     g_return_val_if_fail(curve != NULL, NULL);
 151
 152     curve->refcount -= 1;
 153
 154     if (curve->refcount < 1) {
 155         if (curve->_bpath) {
 156             g_free(curve->_bpath);
 157         }
 158         g_free(curve);
 159     }
 160
 161     return NULL;
 162 }
 163
 164 /**
 165  * Add space for more paths in curve.
 166  */
 167 static void
 168 sp_curve_ensure_space(SPCurve *curve, gint space)
 169 {
 170     g_return_if_fail(curve != NULL);
 171     g_return_if_fail(space > 0);
 172
 173     if (curve->end + space < curve->length)
 174         return;
 175
 176     if (space < SP_CURVE_LENSTEP)
 177         space = SP_CURVE_LENSTEP;
 178
 179     curve->_bpath = g_renew(NArtBpath, curve->_bpath, curve->length + space);
 180
 181     curve->length += space;
 182 }
 183
 184 /**
 185  * Create new curve from its own bpath array.
 186  */
 187 SPCurve *
 188 sp_curve_copy(SPCurve *curve)
 189 {
 190     g_return_val_if_fail(curve != NULL, NULL);
 191
 192     return sp_curve_new_from_foreign_bpath(curve->_bpath);
 193 }
 194
 195 /**
 196  * Return new curve that is the concatenation of all curves in list.
 197  */
 198 SPCurve *
 199 sp_curve_concat(GSList const *list)
 200 {
 201     g_return_val_if_fail(list != NULL, NULL);
 202
 203     gint length = 0;
 204
 205     for (GSList const *l = list; l != NULL; l = l->next) {
 206         SPCurve *c = (SPCurve *) l->data;
 207         length += c->end;
 208     }
 209
 210     SPCurve *new_curve = sp_curve_new_sized(length + 1);
 211
 212     NArtBpath *bp = new_curve->_bpath;
 213
 214     for (GSList const *l = list; l != NULL; l = l->next) {
 215         SPCurve *c = (SPCurve *) l->data;
 216         memcpy(bp, c->_bpath, c->end * sizeof(NArtBpath));
 217         bp += c->end;
 218     }
 219
 220     bp->code = NR_END;
 221
 222     new_curve->end = length;
 223     gint i;
 224     for (i = new_curve->end; i > 0; i--) {
 225         if ((new_curve->_bpath[i].code == NR_MOVETO)     ||
 226             (new_curve->_bpath[i].code == NR_MOVETO_OPEN)  )
 227             break;
 228     }
 229
 230     new_curve->substart = i;
 231
 232     return new_curve;
 233 }
 234
 235 /**
 236  * Returns a list of new curves corresponding to the subpaths in \a curve.
 237  */
 238 GSList *
 239 sp_curve_split(SPCurve const *curve)
 240 {
 241     g_return_val_if_fail(curve != NULL, NULL);
 242
 243     gint p = 0;
 244     GSList *l = NULL;
 245
 246     while (p < curve->end) {
 247         gint i = 1;
 248         while ((curve->_bpath[p + i].code == NR_LINETO) ||
 249                (curve->_bpath[p + i].code == NR_CURVETO))
 250             i++;
 251         SPCurve *new_curve = sp_curve_new_sized(i + 1);
 252         memcpy(new_curve->_bpath, curve->_bpath + p, i * sizeof(NArtBpath));
 253         new_curve->end = i;
 254         new_curve->_bpath[i].code = NR_END;
 255         new_curve->substart = 0;
 256         new_curve->closed = (new_curve->_bpath->code == NR_MOVETO);
 257         new_curve->hascpt = (new_curve->_bpath->code == NR_MOVETO_OPEN);
 258         l = g_slist_prepend(l, new_curve);
 259         p += i;
 260     }
 261
 262     return l;
 263 }
 264
 265 /**
 266  * Transform all paths in curve, template helper.
 267  */
 268 template<class M>
 269 static void
 270 tmpl_curve_transform(SPCurve *const curve, M const &m)
 271 {
 272     g_return_if_fail(curve != NULL);
 273
 274     for (gint i = 0; i < curve->end; i++) {
 275         NArtBpath *p = curve->_bpath + i;
 276         switch (p->code) {
 277             case NR_MOVETO:
 278             case NR_MOVETO_OPEN:
 279             case NR_LINETO: {
 280                 p->setC(3, p->c(3) * m);
 281                 break;
 282             }
 283             case NR_CURVETO:
 284                 for (unsigned i = 1; i <= 3; ++i) {
 285                     p->setC(i, p->c(i) * m);
 286                 }
 287                 break;
 288             default:
 289                 g_warning("Illegal pathcode %d", p->code);
 290                 break;
 291         }
 292     }
 293 }
 294
 295 /**
 296  * Transform all paths in curve using matrix.
 297  */
 298 void
 299 sp_curve_transform(SPCurve *const curve, NR::Matrix const &m)
 300 {
 301     tmpl_curve_transform<NR::Matrix>(curve, m);
 302 }
 303
 304 /**
 305  * Transform all paths in curve using NR::translate.
 306  */
 307 void
 308 sp_curve_transform(SPCurve *const curve, NR::translate const &m)
 309 {
 310     tmpl_curve_transform<NR::translate>(curve, m);
 311 }
 312
 313
 314 /* Methods */
 315
 316 /**
 317  * Set curve to empty curve.
 318  */
 319 void
 320 sp_curve_reset(SPCurve *curve)
 321 {
 322     g_return_if_fail(curve != NULL);
 323
 324     curve->_bpath->code = NR_END;
 325     curve->end = 0;
 326     curve->substart = 0;
 327     curve->hascpt = false;
 328     curve->posSet = false;
 329     curve->moving = false;
 330     curve->closed = false;
 331 }
 332
 333 /* Several consecutive movetos are ALLOWED */
 334
 335 /**
 336  * Calls sp_curve_moveto() with point made of given coordinates.
 337  */
 338 void
 339 sp_curve_moveto(SPCurve *curve, gdouble x, gdouble y)
 340 {
 341     sp_curve_moveto(curve, NR::Point(x, y));
 342 }
 343
 344 /**
 345  * Perform a moveto to a point, thus starting a new subpath.
 346  */
 347 void
 348 sp_curve_moveto(SPCurve *curve, NR::Point const &p)
 349 {
 350     g_return_if_fail(curve != NULL);
 351     g_return_if_fail(!curve->moving);
 352
 353     curve->substart = curve->end;
 354     curve->hascpt = true;
 355     curve->posSet = true;
 356     curve->movePos = p;
 357 }
 358
 359 /**
 360  * Calls sp_curve_lineto() with a point's coordinates.
 361  */
 362 void
 363 sp_curve_lineto(SPCurve *curve, NR::Point const &p)
 364 {
 365     sp_curve_lineto(curve, p[NR::X], p[NR::Y]);
 366 }
 367
 368 /**
 369  * Adds a line to the current subpath.
 370  */
 371 void
 372 sp_curve_lineto(SPCurve *curve, gdouble x, gdouble y)
 373 {
 374     g_return_if_fail(curve != NULL);
 375     g_return_if_fail(curve->hascpt);
 376
 377     if (curve->moving) {
 378         /* fix endpoint */
 379         g_return_if_fail(!curve->posSet);
 380         g_return_if_fail(curve->end > 1);
 381         NArtBpath *bp = curve->_bpath + curve->end - 1;
 382         g_return_if_fail(bp->code == NR_LINETO);
 383         bp->x3 = x;
 384         bp->y3 = y;
 385         curve->moving = false;
 386         return;
 387     }
 388
 389     if (curve->posSet) {
 390         /* start a new segment */
 391         sp_curve_ensure_space(curve, 2);
 392         NArtBpath *bp = curve->_bpath + curve->end;
 393         bp->code = NR_MOVETO_OPEN;
 394         bp->setC(3, curve->movePos);
 395         bp++;
 396         bp->code = NR_LINETO;
 397         bp->x3 = x;
 398         bp->y3 = y;
 399         bp++;
 400         bp->code = NR_END;
 401         curve->end += 2;
 402         curve->posSet = false;
 403         curve->closed = false;
 404         return;
 405     }
 406
 407     /* add line */
 408
 409     g_return_if_fail(curve->end > 1);
 410     sp_curve_ensure_space(curve, 1);
 411     NArtBpath *bp = curve->_bpath + curve->end;
 412     bp->code = NR_LINETO;
 413     bp->x3 = x;
 414     bp->y3 = y;
 415     bp++;
 416     bp->code = NR_END;
 417     curve->end++;
 418 }
 419
 420 /// Unused
 421 void
 422 sp_curve_lineto_moving(SPCurve *curve, gdouble x, gdouble y)
 423 {
 424     g_return_if_fail(curve != NULL);
 425     g_return_if_fail(curve->hascpt);
 426
 427     if (curve->moving) {
 428         /* change endpoint */
 429         g_return_if_fail(!curve->posSet);
 430         g_return_if_fail(curve->end > 1);
 431         NArtBpath *bp = curve->_bpath + curve->end - 1;
 432         g_return_if_fail(bp->code == NR_LINETO);
 433         bp->x3 = x;
 434         bp->y3 = y;
 435         return;
 436     }
 437
 438     if (curve->posSet) {
 439         /* start a new segment */
 440         sp_curve_ensure_space(curve, 2);
 441         NArtBpath *bp = curve->_bpath + curve->end;
 442         bp->code = NR_MOVETO_OPEN;
 443         bp->setC(3, curve->movePos);
 444         bp++;
 445         bp->code = NR_LINETO;
 446         bp->x3 = x;
 447         bp->y3 = y;
 448         bp++;
 449         bp->code = NR_END;
 450         curve->end += 2;
 451         curve->posSet = false;
 452         curve->moving = true;
 453         curve->closed = false;
 454         return;
 455     }
 456
 457     /* add line */
 458
 459     g_return_if_fail(curve->end > 1);
 460     sp_curve_ensure_space(curve, 1);
 461     NArtBpath *bp = curve->_bpath + curve->end;
 462     bp->code = NR_LINETO;
 463     bp->x3 = x;
 464     bp->y3 = y;
 465     bp++;
 466     bp->code = NR_END;
 467     curve->end++;
 468     curve->moving = true;
 469 }
 470
 471 /**
 472  * Calls sp_curve_curveto() with coordinates of three points.
 473  */
 474 void
 475 sp_curve_curveto(SPCurve *curve, NR::Point const &p0, NR::Point const &p1, NR::Point const &p2)
 476 {
 477     using NR::X;
 478     using NR::Y;
 479     sp_curve_curveto(curve,
 480                      p0[X], p0[Y],
 481                      p1[X], p1[Y],
 482                      p2[X], p2[Y]);
 483 }
 484
 485 /**
 486  * Adds a bezier segment to the current subpath.
 487  */
 488 void
 489 sp_curve_curveto(SPCurve *curve, gdouble x0, gdouble y0, gdouble x1, gdouble y1, gdouble x2, gdouble y2)
 490 {
 491     g_return_if_fail(curve != NULL);
 492     g_return_if_fail(curve->hascpt);
 493     g_return_if_fail(!curve->moving);
 494
 495     if (curve->posSet) {
 496         /* start a new segment */
 497         sp_curve_ensure_space(curve, 2);
 498         NArtBpath *bp = curve->_bpath + curve->end;
 499         bp->code = NR_MOVETO_OPEN;
 500         bp->setC(3, curve->movePos);
 501         bp++;
 502         bp->code = NR_CURVETO;
 503         bp->x1 = x0;
 504         bp->y1 = y0;
 505         bp->x2 = x1;
 506         bp->y2 = y1;
 507         bp->x3 = x2;
 508         bp->y3 = y2;
 509         bp++;
 510         bp->code = NR_END;
 511         curve->end += 2;
 512         curve->posSet = false;
 513         curve->closed = false;
 514         return;
 515     }
 516
 517     /* add curve */
 518
 519     g_return_if_fail(curve->end > 1);
 520     sp_curve_ensure_space(curve, 1);
 521     NArtBpath *bp = curve->_bpath + curve->end;
 522     bp->code = NR_CURVETO;
 523     bp->x1 = x0;
 524     bp->y1 = y0;
 525     bp->x2 = x1;
 526     bp->y2 = y1;
 527     bp->x3 = x2;
 528     bp->y3 = y2;
 529     bp++;
 530     bp->code = NR_END;
 531     curve->end++;
 532 }
 533
 534 /**
 535  * Close current subpath by possibly adding a line between start and end.
 536  */
 537 void
 538 sp_curve_closepath(SPCurve *curve)
 539 {
 540     g_return_if_fail(curve != NULL);
 541     g_return_if_fail(curve->hascpt);
 542     g_return_if_fail(!curve->posSet);
 543     g_return_if_fail(!curve->moving);
 544     g_return_if_fail(!curve->closed);
 545     /* We need at least moveto, curveto, end. */
 546     g_return_if_fail(curve->end - curve->substart > 1);
 547
 548     {
 549         NArtBpath *bs = curve->_bpath + curve->substart;
 550         NArtBpath *be = curve->_bpath + curve->end - 1;
 551
 552         if (bs->c(3) != be->c(3)) {
 553             sp_curve_lineto(curve, bs->c(3));
 554             bs = curve->_bpath + curve->substart;
 555         }
 556
 557         bs->code = NR_MOVETO;
 558     }
 559     curve->closed = true;
 560
 561     for (NArtBpath const *bp = curve->_bpath; bp->code != NR_END; bp++) {
 562         /** \todo
 563          * effic: Maintain a count of NR_MOVETO_OPEN's (e.g. instead of
 564          * the closed boolean).
 565          */
 566         if (bp->code == NR_MOVETO_OPEN) {
 567             curve->closed = false;
 568             break;
 569         }
 570     }
 571
 572     curve->hascpt = false;
 573 }
 574
 575 /** Like sp_curve_closepath() but sets the end point of the current
 576     command to the subpath start point instead of adding a new lineto.
 577
 578     Used for freehand drawing when the user draws back to the start point.
 579 **/
 580 void
 581 sp_curve_closepath_current(SPCurve *curve)
 582 {
 583     g_return_if_fail(curve != NULL);
 584     g_return_if_fail(curve->hascpt);
 585     g_return_if_fail(!curve->posSet);
 586     g_return_if_fail(!curve->closed);
 587     /* We need at least moveto, curveto, end. */
 588     g_return_if_fail(curve->end - curve->substart > 1);
 589
 590     {
 591         NArtBpath *bs = curve->_bpath + curve->substart;
 592         NArtBpath *be = curve->_bpath + curve->end - 1;
 593
 594         be->x3 = bs->x3;
 595         be->y3 = bs->y3;
 596
 597         bs->code = NR_MOVETO;
 598     }
 599     curve->closed = true;
 600
 601     for (NArtBpath const *bp = curve->_bpath; bp->code != NR_END; bp++) {
 602         /** \todo
 603          * effic: Maintain a count of NR_MOVETO_OPEN's (e.g. instead of
 604          * the closed boolean).
 605          */
 606         if (bp->code == NR_MOVETO_OPEN) {
 607             curve->closed = false;
 608             break;
 609         }
 610     }
 611
 612     curve->hascpt = false;
 613     curve->moving = false;
 614 }
 615
 616 /**
 617  * True if no paths are in curve.
 618  */
 619 bool
 620 sp_curve_empty(SPCurve *curve)
 621 {
 622     g_return_val_if_fail(curve != NULL, TRUE);
 623
 624     return (curve->_bpath->code == NR_END);
 625 }
 626
 627 /**
 628  * Return last subpath or NULL.
 629  */
 630 NArtBpath *
 631 sp_curve_last_bpath(SPCurve const *curve)
 632 {
 633     g_return_val_if_fail(curve != NULL, NULL);
 634
 635     if (curve->end == 0) {
 636         return NULL;
 637     }
 638
 639     return curve->_bpath + curve->end - 1;
 640 }
 641
 642 /**
 643  * Return first subpath or NULL.
 644  */
 645 NArtBpath *
 646 sp_curve_first_bpath(SPCurve const *curve)
 647 {
 648     g_return_val_if_fail(curve != NULL, NULL);
 649
 650     if (curve->end == 0) {
 651         return NULL;
 652     }
 653
 654     return curve->_bpath;
 655 }
 656
 657 /**
 658  * Return first point of first subpath or (0,0).
 659  */
 660 NR::Point
 661 sp_curve_first_point(SPCurve const *const curve)
 662 {
 663     NArtBpath *const bpath = sp_curve_first_bpath(curve);
 664     g_return_val_if_fail(bpath != NULL, NR::Point(0, 0));
 665     return bpath->c(3);
 666 }
 667
 668 /**
 669  * Return the second point of first subpath or curve->movePos if curve too short.
 670  */
 671 NR::Point
 672 sp_curve_second_point(SPCurve const *const curve)
 673 {
 674     g_return_val_if_fail(curve != NULL, NR::Point(0, 0));
 675
 676     if (curve->end < 1) {
 677         return curve->movePos;
 678     }
 679
 680     NArtBpath *bpath = NULL;
 681     if (curve->end < 2) {
 682         bpath = curve->_bpath;
 683     } else {
 684         bpath = curve->_bpath + 1;
 685     }
 686     g_return_val_if_fail(bpath != NULL, NR::Point(0, 0));
 687     return bpath->c(3);
 688 }
 689
 690 /**
 691  * Return the second-last point of last subpath or curve->movePos if curve too short.
 692  */
 693 NR::Point
 694 sp_curve_penultimate_point(SPCurve const *const curve)
 695 {
 696     g_return_val_if_fail(curve != NULL, NR::Point(0, 0));
 697
 698     if (curve->end < 2) {
 699         return curve->movePos;
 700     }
 701
 702     NArtBpath *const bpath = curve->_bpath + curve->end - 2;
 703     g_return_val_if_fail(bpath != NULL, NR::Point(0, 0));
 704     return bpath->c(3);
 705 }
 706
 707 /**
 708  * Return last point of last subpath or (0,0).
 709  */
 710 NR::Point
 711 sp_curve_last_point(SPCurve const *const curve)
 712 {
 713     NArtBpath *const bpath = sp_curve_last_bpath(curve);
 714     g_return_val_if_fail(bpath != NULL, NR::Point(0, 0));
 715     return bpath->c(3);
 716 }
 717
 718 inline static bool
 719 is_moveto(NRPathcode const c)
 720 {
 721     return c == NR_MOVETO || c == NR_MOVETO_OPEN;
 722 }
 723
 724 /**
 725  * Returns \a curve but drawn in the opposite direction.
 726  * Should result in the same shape, but
 727  * with all its markers drawn facing the other direction.
 728  **/
 729 SPCurve *
 730 sp_curve_reverse(SPCurve const *curve)
 731 {
 732     /* We need at least moveto, curveto, end. */
 733     g_return_val_if_fail(curve->end - curve->substart > 1, NULL);
 734
 735     NArtBpath const *be = curve->_bpath + curve->end - 1;
 736
 737     g_assert(is_moveto(curve->_bpath[curve->substart].code));
 738     g_assert(is_moveto(curve->_bpath[0].code));
 739     g_assert((be+1)->code == NR_END);
 740
 741     SPCurve  *new_curve = sp_curve_new_sized(curve->length);
 742     sp_curve_moveto(new_curve, be->c(3));
 743
 744     for (NArtBpath const *bp = be; ; --bp) {
 745         switch (bp->code) {
 746             case NR_MOVETO:
 747                 g_assert(new_curve->_bpath[new_curve->substart].code == NR_MOVETO_OPEN);
 748                 new_curve->_bpath[new_curve->substart].code = NR_MOVETO;
 749                 /* FALL-THROUGH */
 750             case NR_MOVETO_OPEN:
 751                 if (bp == curve->_bpath) {
 752                     return new_curve;
 753                 }
 754                 sp_curve_moveto(new_curve, (bp-1)->c(3));
 755                 break;
 756
 757             case NR_LINETO:
 758                 sp_curve_lineto(new_curve, (bp-1)->c(3));
 759                 break;
 760
 761             case NR_CURVETO:
 762                 sp_curve_curveto(new_curve, bp->c(2), bp->c(1), (bp-1)->c(3));
 763                 break;
 764
 765             default:
 766                 g_assert_not_reached();
 767         }
 768     }
 769 }
 770
 771 /**
 772  * Append \a curve2 to \a curve.
 773  */
 774 void
 775 sp_curve_append(SPCurve *curve,
 776                 SPCurve const *curve2,
 777                 bool use_lineto)
 778 {
 779     g_return_if_fail(curve != NULL);
 780     g_return_if_fail(curve2 != NULL);
 781
 782     if (curve2->end < 1)
 783         return;
 784
 785     NArtBpath const *bs = curve2->_bpath;
 786
 787     bool closed = curve->closed;
 788
 789     for (NArtBpath const *bp = bs; bp->code != NR_END; bp++) {
 790         switch (bp->code) {
 791             case NR_MOVETO_OPEN:
 792                 if (use_lineto && curve->hascpt) {
 793                     sp_curve_lineto(curve, bp->x3, bp->y3);
 794                     use_lineto = FALSE;
 795                 } else {
 796                     if (closed) sp_curve_closepath(curve);
 797                     sp_curve_moveto(curve, bp->x3, bp->y3);
 798                 }
 799                 closed = false;
 800                 break;
 801
 802             case NR_MOVETO:
 803                 if (use_lineto && curve->hascpt) {
 804                     sp_curve_lineto(curve, bp->x3, bp->y3);
 805                     use_lineto = FALSE;
 806                 } else {
 807                     if (closed) sp_curve_closepath(curve);
 808                     sp_curve_moveto(curve, bp->x3, bp->y3);
 809                 }
 810                 closed = true;
 811                 break;
 812
 813             case NR_LINETO:
 814                 sp_curve_lineto(curve, bp->x3, bp->y3);
 815                 break;
 816
 817             case NR_CURVETO:
 818                 sp_curve_curveto(curve, bp->x1, bp->y1, bp->x2, bp->y2, bp->x3, bp->y3);
 819                 break;
 820
 821             case NR_END:
 822                 g_assert_not_reached();
 823         }
 824     }
 825
 826     if (closed) {
 827         sp_curve_closepath(curve);
 828     }
 829 }
 830
 831 /**
 832  * Append \a c1 to \a c0 with possible fusing of close endpoints.
 833  */
 834 SPCurve *
 835 sp_curve_append_continuous(SPCurve *c0, SPCurve const *c1, gdouble tolerance)
 836 {
 837     g_return_val_if_fail(c0 != NULL, NULL);
 838     g_return_val_if_fail(c1 != NULL, NULL);
 839     g_return_val_if_fail(!c0->closed, NULL);
 840     g_return_val_if_fail(!c1->closed, NULL);
 841
 842     if (c1->end < 1) {
 843         return c0;
 844     }
 845
 846     NArtBpath *be = sp_curve_last_bpath(c0);
 847     if (be) {
 848         NArtBpath const *bs = sp_curve_first_bpath(c1);
 849         if ( bs
 850              && ( fabs( bs->x3 - be->x3 ) <= tolerance )
 851              && ( fabs( bs->y3 - be->y3 ) <= tolerance ) )
 852         {
 853             /** \todo
 854              * fixme: Strictly we mess in case of multisegment mixed
 855              * open/close curves
 856              */
 857             bool closed = false;
 858             for (bs = bs + 1; bs->code != NR_END; bs++) {
 859                 switch (bs->code) {
 860                     case NR_MOVETO_OPEN:
 861                         if (closed) sp_curve_closepath(c0);
 862                         sp_curve_moveto(c0, bs->x3, bs->y3);
 863                         closed = false;
 864                         break;
 865                     case NR_MOVETO:
 866                         if (closed) sp_curve_closepath(c0);
 867                         sp_curve_moveto(c0, bs->x3, bs->y3);
 868                         closed = true;
 869                         break;
 870                     case NR_LINETO:
 871                         sp_curve_lineto(c0, bs->x3, bs->y3);
 872                         break;
 873                     case NR_CURVETO:
 874                         sp_curve_curveto(c0, bs->x1, bs->y1, bs->x2, bs->y2, bs->x3, bs->y3);
 875                         break;
 876                     case NR_END:
 877                         g_assert_not_reached();
 878                 }
 879             }
 880         } else {
 881             sp_curve_append(c0, c1, TRUE);
 882         }
 883     } else {
 884         sp_curve_append(c0, c1, TRUE);
 885     }
 886
 887     return c0;
 888 }
 889
 890 /**
 891  * Remove last segment of curve.
 892  */
 893 void
 894 sp_curve_backspace(SPCurve *curve)
 895 {
 896     g_return_if_fail(curve != NULL);
 897
 898     if (curve->end > 0) {
 899         curve->end -= 1;
 900         if (curve->end > 0) {
 901             NArtBpath *bp = curve->_bpath + curve->end - 1;
 902             if ((bp->code == NR_MOVETO)     ||
 903                 (bp->code == NR_MOVETO_OPEN)  )
 904             {
 905                 curve->hascpt = true;
 906                 curve->posSet = true;
 907                 curve->closed = false;
 908                 curve->movePos = bp->c(3);
 909                 curve->end -= 1;
 910             }
 911         }
 912         curve->_bpath[curve->end].code = NR_END;
 913     }
 914 }
 915
 916 /* Private methods */
 917
 918 /**
 919  * True if all subpaths in bpath array pass consistency check.
 920  */
 921 static bool sp_bpath_good(NArtBpath const bpath[])
 922 {
 923     g_return_val_if_fail(bpath != NULL, FALSE);
 924
 925     NArtBpath const *bp = bpath;
 926     while (bp->code != NR_END) {
 927         bp = sp_bpath_check_subpath(bp);
 928         if (bp == NULL)
 929             return false;
 930     }
 931
 932     return true;
 933 }
 934
 935 /**
 936  * Return copy of a bpath array, discarding any inconsistencies.
 937  */
 938 static NArtBpath *sp_bpath_clean(NArtBpath const bpath[])
 939 {
 940     NArtBpath *new_bpath = g_new(NArtBpath, sp_bpath_length(bpath));
 941
 942     NArtBpath const *bp = bpath;
 943     NArtBpath *np = new_bpath;
 944
 945     while (bp->code != NR_END) {
 946         if (sp_bpath_check_subpath(bp)) {
 947             *np++ = *bp++;
 948             while ((bp->code == NR_LINETO) ||
 949                    (bp->code == NR_CURVETO))
 950                 *np++ = *bp++;
 951         } else {
 952             bp++;
 953             while ((bp->code == NR_LINETO) ||
 954                    (bp->code == NR_CURVETO))
 955                 bp++;
 956         }
 957     }
 958
 959     if (np == new_bpath) {
 960         g_free(new_bpath);
 961         return NULL;
 962     }
 963
 964     np->code = NR_END;
 965     np += 1;
 966
 967     new_bpath = g_renew(NArtBpath, new_bpath, np - new_bpath);
 968
 969     return new_bpath;
 970 }
 971
 972 /**
 973  * Perform consistency check of bpath array.
 974  * \return Address of NR_END node or NULL.
 975  */
 976 static NArtBpath const *sp_bpath_check_subpath(NArtBpath const bpath[])
 977 {
 978     g_return_val_if_fail(bpath != NULL, NULL);
 979
 980     bool closed;
 981     if (bpath->code == NR_MOVETO) {
 982         closed = true;
 983     } else if (bpath->code == NR_MOVETO_OPEN) {
 984         closed = false;
 985     } else {
 986         return NULL;
 987     }
 988
 989     gint len = 0;
 990     gint i;
 991     /** \todo
 992      * effic: consider checking for END/MOVE/MOVETO inside switch block
 993      */
 994     for (i = 1; (bpath[i].code != NR_END) && (bpath[i].code != NR_MOVETO) && (bpath[i].code != NR_MOVETO_OPEN); i++) {
 995         switch (bpath[i].code) {
 996             case NR_LINETO:
 997             case NR_CURVETO:
 998                 len++;
 999                 break;
1000             default:
1001                 return NULL;
1002         }
1003     }
1004
1005     if (closed) {
1006         if (len < 1)
1007             return NULL;
1008
1009         if ((bpath->x3 != bpath[i-1].x3) || (bpath->y3 != bpath[i-1].y3))
1010             return NULL;
1011     } else {
1012         if (len < 1)
1013             return NULL;
1014     }
1015
1016     return bpath + i;
1017 }
1018
1019 /**
1020  * Returns index of first NR_END bpath in array.
1021  */
1022 static unsigned sp_bpath_length(NArtBpath const bpath[])
1023 {
1024     g_return_val_if_fail(bpath != NULL, FALSE);
1025
1026     unsigned ret = 0;
1027     while ( bpath[ret].code != NR_END ) {
1028         ++ret;
1029     }
1030     ++ret;
1031
1032     return ret;
1033 }
1034
1035 /**
1036  * \brief
1037  *
1038  * \todo
1039  * fixme: this is bogus -- it doesn't check for nr_moveto, which will indicate
1040  * a closing of the subpath it's nonsense to talk about a path as a whole
1041  * being closed, although maybe someone would want that for some other reason?
1042  * Oh, also, if the bpath just ends, then it's *open*.  I hope nobody is using
1043  * this code for anything.
1044  */
1045 static bool sp_bpath_closed(NArtBpath const bpath[])
1046 {
1047     g_return_val_if_fail(bpath != NULL, FALSE);
1048
1049     for (NArtBpath const *bp = bpath; bp->code != NR_END; bp++) {
1050         if (bp->code == NR_MOVETO_OPEN) {
1051             return false;
1052         }
1053     }
1054
1055     return true;
1056 }
1057
1058 /**
1059  * Returns length of bezier segment.
1060  */
1061 static double
1062 bezier_len(NR::Point const &c0,
1063            NR::Point const &c1,
1064            NR::Point const &c2,
1065            NR::Point const &c3,
1066            double const threshold)
1067 {
1068     /** \todo
1069      * The SVG spec claims that a closed form exists, but for the moment I'll
1070      * use a stupid algorithm.
1071      */
1072     double const lbound = L2( c3 - c0 );
1073     double const ubound = L2( c1 - c0 ) + L2( c2 - c1 ) + L2( c3 - c2 );
1074     double ret;
1075     if ( ubound - lbound <= threshold ) {
1076         ret = .5 * ( lbound + ubound );
1077     } else {
1078         NR::Point const a1( .5 * ( c0 + c1 ) );
1079         NR::Point const b2( .5 * ( c2 + c3 ) );
1080         NR::Point const c12( .5 * ( c1 + c2 ) );
1081         NR::Point const a2( .5 * ( a1 + c12 ) );
1082         NR::Point const b1( .5 * ( c12 + b2 ) );
1083         NR::Point const midpoint( .5 * ( a2 + b1 ) );
1084         double const rec_threshold = .625 * threshold;
1085         ret = bezier_len(c0, a1, a2, midpoint, rec_threshold) + bezier_len(midpoint, b1, b2, c3, rec_threshold);
1086         if (!(lbound - 1e-2 <= ret && ret <= ubound + 1e-2)) {
1087             using NR::X; using NR::Y;
1088             g_warning("ret=%f outside of expected bounds [%f, %f] for {(%.0f %.0f) (%.0f %.0f) (%.0f %.0f) (%.0f %.0f)}",
1089                       ret, lbound, ubound, c0[X], c0[Y], c1[X], c1[Y], c2[X], c2[Y], c3[X], c3[Y]);
1090         }
1091     }
1092     return ret;
1093 }
1094
1095 /**
1096  * Returns total length of curve, excluding length of closepath segments.
1097  */
1098 static double
1099 sp_curve_distance_including_space(SPCurve const *const curve, double seg2len[])
1100 {
1101     g_return_val_if_fail(curve != NULL, 0.);
1102
1103     double ret = 0.0;
1104
1105     if ( curve->_bpath->code == NR_END ) {
1106         return ret;
1107     }
1108
1109     NR::Point prev(curve->_bpath->c(3));
1110     for (gint i = 1; i < curve->end; ++i) {
1111         NArtBpath &p = curve->_bpath[i];
1112         double seg_len = 0;
1113         switch (p.code) {
1114             case NR_MOVETO_OPEN:
1115             case NR_MOVETO:
1116             case NR_LINETO:
1117                 seg_len = L2(p.c(3) - prev);
1118                 break;
1119
1120             case NR_CURVETO:
1121                 seg_len = bezier_len(prev, p.c(1), p.c(2), p.c(3), 1.);
1122                 break;
1123
1124             case NR_END:
1125                 return ret;
1126         }
1127         seg2len[i - 1] = seg_len;
1128         ret += seg_len;
1129         prev = p.c(3);
1130     }
1131     g_assert(!(ret < 0));
1132     return ret;
1133 }
1134
1135 /**
1136  * Like sp_curve_distance_including_space(), but ensures that the
1137  * result >= 1e-18:  uses 1 per segment if necessary.
1138  */
1139 static double
1140 sp_curve_nonzero_distance_including_space(SPCurve const *const curve, double seg2len[])
1141 {
1142     double const real_dist(sp_curve_distance_including_space(curve, seg2len));
1143     if (real_dist >= 1e-18) {
1144         return real_dist;
1145     } else {
1146         unsigned const nSegs = SP_CURVE_LENGTH(curve) - 1;
1147         for (unsigned i = 0; i < nSegs; ++i) {
1148             seg2len[i] = 1.;
1149         }
1150         return (double) nSegs;
1151     }
1152 }
1153
1154 void
1155 sp_curve_stretch_endpoints(SPCurve *curve, NR::Point const &new_p0, NR::Point const &new_p1)
1156 {
1157     if (sp_curve_empty(curve)) {
1158         return;
1159     }
1160     g_assert(unsigned(SP_CURVE_LENGTH(curve)) + 1 == sp_bpath_length(curve->_bpath));
1161     unsigned const nSegs = SP_CURVE_LENGTH(curve) - 1;
1162     g_assert(nSegs != 0);
1163     double *const seg2len = new double[nSegs];
1164     double const tot_len = sp_curve_nonzero_distance_including_space(curve, seg2len);
1165     NR::Point const offset0( new_p0 - sp_curve_first_point(curve) );
1166     NR::Point const offset1( new_p1 - sp_curve_last_point(curve) );
1167     curve->_bpath->setC(3, new_p0);
1168     double begin_dist = 0.;
1169     for (unsigned si = 0; si < nSegs; ++si) {
1170         double const end_dist = begin_dist + seg2len[si];
1171         NArtBpath &p = curve->_bpath[1 + si];
1172         switch (p.code) {
1173             case NR_LINETO:
1174             case NR_MOVETO:
1175             case NR_MOVETO_OPEN:
1176                 p.setC(3, p.c(3) + NR::Lerp(end_dist / tot_len, offset0, offset1));
1177                 break;
1178
1179             case NR_CURVETO:
1180                 for (unsigned ci = 1; ci <= 3; ++ci) {
1181                     p.setC(ci, p.c(ci) + Lerp((begin_dist + ci * seg2len[si] / 3.) / tot_len, offset0, offset1));
1182                 }
1183                 break;
1184
1185             default:
1186                 g_assert_not_reached();
1187         }
1188
1189         begin_dist = end_dist;
1190     }
1191     g_assert(L1(curve->_bpath[nSegs].c(3) - new_p1) < 1.);
1192     /* Explicit set for better numerical properties. */
1193     curve->_bpath[nSegs].setC(3, new_p1);
1194     delete [] seg2len;
1195 }
1196
1197 void
1198 sp_curve_move_endpoints(SPCurve *curve, NR::Point const &new_p0,
1199         NR::Point const &new_p1)
1200 {
1201     if (sp_curve_empty(curve)) {
1202         return;
1203     }
1204     unsigned const nSegs = SP_CURVE_LENGTH(curve) - 1;
1205     g_assert(nSegs != 0);
1206
1207     curve->_bpath->setC(3, new_p0);
1208     curve->_bpath[nSegs].setC(3, new_p1);
1209 }
1210
1211
1212 /*
1213   Local Variables:
1214   mode:c++
1215   c-file-style:"stroustrup"
1216   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1217   indent-tabs-mode:nil
1218   fill-column:99
1219   End:
1220 */
1221 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :