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