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