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