src/display/curve.cpp

   1 #define __CURVE_C__
   2
   3 /** \file
   4  * Routines for SPCurve and for NArtBpath arrays / Geom::PathVector in general.
   5  */
   6
   7 /*
   8  * Authors:
   9  *   Lauris Kaplinski <lauris@kaplinski.com>
  10  *   Johan Engelen
  11  *
  12  * Copyright (C) 2000 Lauris Kaplinski
  13  * Copyright (C) 2000-2001 Ximian, Inc.
  14  * Copyright (C) 2002 Lauris Kaplinski
  15  * Copyright (C) 2008 Johan Engelen
  16  *
  17  * Released under GNU GPL
  18  */
  19
  20 #include "display/curve.h"
  21
  22 #include <string.h>
  23 #include <glib/gmem.h>
  24 #include "libnr/nr-point.h"
  25 #include "libnr/nr-rect.h"
  26 #include <libnr/n-art-bpath.h>
  27 #include <libnr/nr-point-matrix-ops.h>
  28 #include <libnr/nr-translate-ops.h>
  29 #include <libnr/n-art-bpath-2geom.h>
  30 #include <libnr/nr-convert2geom.h>
  31 #include <cstring>
  32 #include <string>
  33 #include <2geom/pathvector.h>
  34 #include <2geom/sbasis-geometric.h>
  35 #include <2geom/sbasis-to-bezier.h>
  36 #include "svg/svg.h"
  37 #include <2geom/point.h>
  38
  39 static unsigned sp_bpath_length(NArtBpath const bpath[]);
  40 static bool sp_bpath_closed(NArtBpath const bpath[]);
  41
  42 /* Constructors */
  43
  44 /**
  45  * The returned curve's state is as if SPCurve::reset has just been called on it.
  46  * \param length Initial number of NArtBpath elements allocated for bpath (including NR_END
  47  *    element).
  48  * 2GEOMproof
  49  */
  50 SPCurve::SPCurve(guint length)
  51   : _refcount(1),
  52     _bpath(NULL),
  53     _pathv(),
  54     _end(0),
  55     _length(length),
  56     _substart(0),
  57     _hascpt(false),
  58     _posSet(false),
  59     _moving(false),
  60     _closed(false)
  61 {
  62     if (length <= 0) {
  63         g_error("SPCurve::SPCurve called with invalid length parameter");
  64         throw;
  65     }
  66
  67     _bpath = g_new(NArtBpath, length);
  68     _bpath->code = NR_END;
  69
  70     _pathv.clear();
  71 }
  72
  73 SPCurve::SPCurve(Geom::PathVector const& pathv)
  74   : _refcount(1),
  75     _bpath(NULL),
  76     _pathv(pathv),
  77     _end(0),
  78     _length(0),
  79     _substart(0),
  80     _hascpt(false),
  81     _posSet(false),
  82     _moving(false),
  83     _closed(false)
  84 {
  85     // temporary code to convert to _bpath as well:
  86     _bpath = BPath_from_2GeomPath(_pathv);
  87     unsigned const len = sp_bpath_length(_bpath);
  88     _length = len;
  89     _end = _length - 1;
  90     gint i = _end;
  91     for (; i > 0; i--)
  92         if ((_bpath[i].code == NR_MOVETO) ||
  93             (_bpath[i].code == NR_MOVETO_OPEN))
  94             break;
  95     _substart = i;
  96     _closed = sp_bpath_closed(_bpath);
  97 }
  98
  99 // * 2GEOMproof
 100 SPCurve *
 101 SPCurve::new_from_foreign_bpath(NArtBpath const *bpath)
 102 {
 103     g_return_val_if_fail(bpath != NULL, NULL);
 104
 105     NArtBpath *new_bpath;
 106     unsigned const len = sp_bpath_length(bpath);
 107     new_bpath = g_new(NArtBpath, len);
 108     memcpy(new_bpath, bpath, len * sizeof(NArtBpath));
 109
 110     SPCurve *curve = new SPCurve();
 111
 112     curve->_bpath = new_bpath;
 113     curve->_length = len;
 114     curve->_end = curve->_length - 1;
 115     gint i = curve->_end;
 116     for (; i > 0; i--)
 117         if ((curve->_bpath[i].code == NR_MOVETO) ||
 118             (curve->_bpath[i].code == NR_MOVETO_OPEN))
 119             break;
 120     curve->_substart = i;
 121     curve->_closed = sp_bpath_closed(new_bpath);
 122
 123     curve->_pathv = BPath_to_2GeomPath(curve->_bpath);
 124
 125     return curve;
 126 }
 127
 128 /**
 129  * Convert NArtBpath object to SPCurve object.
 130  *
 131  * \return new SPCurve, or NULL if the curve was not created for some reason.
 132  * 2GEOMproof
 133  */
 134 SPCurve *
 135 SPCurve::new_from_bpath(NArtBpath *bpath)
 136 {
 137     g_return_val_if_fail(bpath != NULL, NULL);
 138
 139     SPCurve *curve = SPCurve::new_from_foreign_bpath(bpath);
 140     g_free(bpath);
 141
 142     return curve;
 143 }
 144
 145 // * 2GEOMproof
 146 SPCurve *
 147 SPCurve::new_from_rect(Geom::Rect const &rect)
 148 {
 149     SPCurve *c =  new SPCurve();
 150
 151     NR::Point p = rect.corner(0);
 152     c->moveto(p);
 153
 154     for (int i=3; i>=0; i--) {
 155         c->lineto(rect.corner(i));
 156     }
 157     c->closepath_current();
 158
 159     return c;
 160 }
 161
 162 // * 2GEOMproof
 163 SPCurve::~SPCurve()
 164 {
 165     if (_bpath) {
 166         g_free(_bpath);
 167         _bpath = NULL;
 168     }
 169 }
 170
 171 /* Methods */
 172
 173 void
 174 SPCurve::set_pathvector(Geom::PathVector const & new_pathv)
 175 {
 176     _pathv = new_pathv;
 177
 178     _hascpt = false;
 179     _posSet = false;
 180     _moving = false;
 181
 182     // temporary code to convert to _bpath as well:
 183     if (_bpath) {
 184         g_free(_bpath);
 185         _bpath = NULL;
 186     }
 187     _bpath = BPath_from_2GeomPath(_pathv);
 188     unsigned const len = sp_bpath_length(_bpath);
 189     _length = len;
 190     _end = _length - 1;
 191     gint i = _end;
 192     for (; i > 0; i--)
 193         if ((_bpath[i].code == NR_MOVETO) ||
 194             (_bpath[i].code == NR_MOVETO_OPEN))
 195             break;
 196     _substart = i;
 197     _closed = sp_bpath_closed(_bpath);
 198 }
 199
 200 /**
 201  * Get pointer to bpath data. Don't keep this reference too long, because the path might change by another function.
 202  */
 203 NArtBpath const *
 204 SPCurve::get_bpath() const
 205 {
 206     return _bpath;
 207 };
 208
 209 Geom::PathVector const &
 210 SPCurve::get_pathvector() const
 211 {
 212     return _pathv;
 213 }
 214
 215 /**
 216  *Returns index in bpath[] of NR_END element.
 217  * remove for 2geom
 218  */
 219 guint
 220 SPCurve::get_length() const
 221 {
 222 //    g_message("SPCurve::get_length must be removed");
 223
 224     return _end;
 225 }
 226
 227 /*
 228  * Returns the number of segments of all paths summed
 229  * This count includes the closing line segment of a closed path.
 230  */
 231 guint
 232 SPCurve::get_segment_count() const
 233 {
 234     guint nr = 0;
 235     for(Geom::PathVector::const_iterator it = _pathv.begin(); it != _pathv.end(); ++it) {
 236         nr += (*it).size();
 237
 238         if (it->closed())   nr += 1;
 239     }
 240     return nr;
 241 }
 242
 243 /**
 244  * Increase _refcount of curve.
 245  *
 246  * \todo should this be shared with other refcounting code?
 247  */
 248 SPCurve *
 249 SPCurve::ref()
 250 {
 251     _refcount += 1;
 252
 253     return this;
 254 }
 255
 256 /**
 257  * Decrease refcount of curve, with possible destruction.
 258  *
 259  * \todo should this be shared with other refcounting code?
 260  */
 261 SPCurve *
 262 SPCurve::unref()
 263 {
 264     _refcount -= 1;
 265
 266     if (_refcount < 1) {
 267         delete this;
 268     }
 269
 270     return NULL;
 271 }
 272
 273 /**
 274  * Add space for more paths in curve.
 275  * This function has no meaning for 2geom representation, other than maybe for optimization issues (enlargening the vector for what is to come)
 276  * 2GEOMproof
 277  */
 278 void
 279 SPCurve::ensure_space(guint space)
 280 {
 281     g_return_if_fail(this != NULL);
 282     g_return_if_fail(space > 0);
 283
 284     if (_end + space < _length)
 285         return;
 286
 287     if (space < SP_CURVE_LENSTEP)
 288         space = SP_CURVE_LENSTEP;
 289
 290     _bpath = g_renew(NArtBpath, _bpath, _length + space);
 291
 292     _length += space;
 293 }
 294
 295 /**
 296  * Create new curve from its own bpath array.
 297  * 2GEOMproof
 298  */
 299 SPCurve *
 300 SPCurve::copy() const
 301 {
 302     return SPCurve::new_from_foreign_bpath(_bpath);
 303 }
 304
 305 /**
 306  * Return new curve that is the concatenation of all curves in list.
 307  * 2GEOMified
 308  */
 309 SPCurve *
 310 SPCurve::concat(GSList const *list)
 311 {
 312     gint length = 0;
 313
 314     for (GSList const *l = list; l != NULL; l = l->next) {
 315         SPCurve *c = (SPCurve *) l->data;
 316         length += c->_end;
 317     }
 318
 319     SPCurve *new_curve = new SPCurve(length + 1);
 320
 321     NArtBpath *bp = new_curve->_bpath;
 322
 323     for (GSList const *l = list; l != NULL; l = l->next) {
 324         SPCurve *c = (SPCurve *) l->data;
 325         memcpy(bp, c->_bpath, c->_end * sizeof(NArtBpath));
 326         bp += c->_end;
 327     }
 328
 329     bp->code = NR_END;
 330
 331     new_curve->_end = length;
 332     gint i;
 333     for (i = new_curve->_end; i > 0; i--) {
 334         if ((new_curve->_bpath[i].code == NR_MOVETO)     ||
 335             (new_curve->_bpath[i].code == NR_MOVETO_OPEN)  )
 336             break;
 337     }
 338
 339     new_curve->_substart = i;
 340
 341     for (GSList const *l = list; l != NULL; l = l->next) {
 342         SPCurve *c = (SPCurve *) l->data;
 343         new_curve->_pathv.insert( new_curve->_pathv.end(), c->get_pathvector().begin(), c->get_pathvector().end() );
 344     }
 345
 346     return new_curve;
 347 }
 348
 349 /**
 350  * Returns a list of new curves corresponding to the subpaths in \a curve.
 351  * 2geomified
 352  */
 353 GSList *
 354 SPCurve::split() const
 355 {
 356     guint p = 0;
 357     GSList *l = NULL;
 358
 359     gint pathnr = 0;
 360     while (p < _end) {
 361         gint i = 1;
 362         while ((_bpath[p + i].code == NR_LINETO) ||
 363                (_bpath[p + i].code == NR_CURVETO))
 364             i++;
 365         SPCurve *new_curve = new SPCurve(i + 1);
 366         memcpy(new_curve->_bpath, _bpath + p, i * sizeof(NArtBpath));
 367         new_curve->_end = i;
 368         new_curve->_bpath[i].code = NR_END;
 369         new_curve->_substart = 0;
 370         new_curve->_closed = (new_curve->_bpath->code == NR_MOVETO);
 371         new_curve->_hascpt = (new_curve->_bpath->code == NR_MOVETO_OPEN);
 372         new_curve->_pathv = Geom::PathVector(1, _pathv[pathnr]);
 373         l = g_slist_prepend(l, new_curve);
 374         p += i;
 375         pathnr++;
 376     }
 377
 378     return l;
 379 }
 380
 381 /**
 382  * Transform all paths in curve, template helper.
 383  */
 384 template<class M>
 385 static void
 386 tmpl_curve_transform(SPCurve * curve, M const &m)
 387 {
 388     g_return_if_fail(curve != NULL);
 389
 390     for (guint i = 0; i < curve->_end; i++) {
 391         NArtBpath *p = curve->_bpath + i;
 392         switch (p->code) {
 393             case NR_MOVETO:
 394             case NR_MOVETO_OPEN:
 395             case NR_LINETO: {
 396                 p->setC(3, p->c(3) * m);
 397                 break;
 398             }
 399             case NR_CURVETO:
 400                 for (unsigned i = 1; i <= 3; ++i) {
 401                     p->setC(i, p->c(i) * m);
 402                 }
 403                 break;
 404             default:
 405                 g_warning("Illegal pathcode %d", p->code);
 406                 break;
 407         }
 408     }
 409 }
 410
 411
 412 void
 413 SPCurve::transform(NR::Matrix const &m)
 414 {
 415     transform(to_2geom(m));
 416 };
 417
 418
 419 /**
 420  * Transform all paths in curve using matrix.
 421  */
 422 void
 423 SPCurve::transform(Geom::Matrix const &m)
 424 {
 425     tmpl_curve_transform<NR::Matrix>(this, from_2geom(m));
 426
 427     _pathv = _pathv * m;
 428 }
 429
 430 /**
 431  * Set curve to empty curve.
 432  * 2GEOMified
 433  */
 434 void
 435 SPCurve::reset()
 436 {
 437     _bpath->code = NR_END;
 438     _end = 0;
 439     _substart = 0;
 440     _hascpt = false;
 441     _posSet = false;
 442     _moving = false;
 443     _closed = false;
 444
 445     _pathv.clear();
 446 }
 447
 448 /* Several consecutive movetos are ALLOWED */
 449
 450 /**
 451  * Calls SPCurve::moveto() with point made of given coordinates.
 452  */
 453 void
 454 SPCurve::moveto(gdouble x, gdouble y)
 455 {
 456     moveto(NR::Point(x, y));
 457 }
 458 /**
 459  * Calls SPCurve::moveto() with point made of given coordinates.
 460  */
 461 void
 462 SPCurve::moveto(Geom::Point const &p)
 463 {
 464     moveto(from_2geom(p));
 465 }
 466 /**
 467  * Perform a moveto to a point, thus starting a new subpath.
 468  * 2GEOMified
 469  */
 470 void
 471 SPCurve::moveto(NR::Point const &p)
 472 {
 473     g_return_if_fail(!_moving);
 474
 475     _substart = _end;
 476     _hascpt = true;
 477     _posSet = true;
 478     _movePos = p;
 479     _pathv.push_back( Geom::Path() );  // for some reason Geom::Path(p) does not work...
 480     _pathv.back().start(to_2geom(p));
 481 }
 482
 483 /**
 484  * Calls SPCurve::lineto() with a point's coordinates.
 485  */
 486 void
 487 SPCurve::lineto(Geom::Point const &p)
 488 {
 489     lineto(p[Geom::X], p[Geom::Y]);
 490 }
 491 /**
 492  * Calls SPCurve::lineto() with a point's coordinates.
 493  */
 494 void
 495 SPCurve::lineto(NR::Point const &p)
 496 {
 497     lineto(p[NR::X], p[NR::Y]);
 498 }
 499 /**
 500  * Adds a line to the current subpath.
 501  * 2GEOMified
 502  */
 503 void
 504 SPCurve::lineto(gdouble x, gdouble y)
 505 {
 506     g_return_if_fail(_hascpt);
 507
 508     if (_moving) {
 509         /* fix endpoint */
 510         g_return_if_fail(!_posSet);
 511         g_return_if_fail(_end > 1);
 512         NArtBpath *bp = _bpath + _end - 1;
 513         g_return_if_fail(bp->code == NR_LINETO);
 514         bp->x3 = x;
 515         bp->y3 = y;
 516         _moving = false;
 517
 518         Geom::Path::iterator it = _pathv.back().end();
 519         if ( Geom::LineSegment const *last_line_segment = dynamic_cast<Geom::LineSegment const *>( &(*it) )) {
 520             Geom::LineSegment new_seg( *last_line_segment );
 521             new_seg.setFinal( Geom::Point(x,y) );
 522             _pathv.back().replace(it, new_seg);
 523         }
 524     } else if (_posSet) {
 525         /* start a new segment */
 526         ensure_space(2);
 527         NArtBpath *bp = _bpath + _end;
 528         bp->code = NR_MOVETO_OPEN;
 529         bp->setC(3, _movePos);
 530         bp++;
 531         bp->code = NR_LINETO;
 532         bp->x3 = x;
 533         bp->y3 = y;
 534         bp++;
 535         bp->code = NR_END;
 536         _end += 2;
 537         _posSet = false;
 538         _closed = false;
 539
 540         _pathv.back().appendNew<Geom::LineSegment>( Geom::Point(x,y) );
 541         return;
 542     } else {
 543         /* add line */
 544
 545         g_return_if_fail(_end > 1);
 546         ensure_space(1);
 547         NArtBpath *bp = _bpath + _end;
 548         bp->code = NR_LINETO;
 549         bp->x3 = x;
 550         bp->y3 = y;
 551         bp++;
 552         bp->code = NR_END;
 553         _end++;
 554         _pathv.back().appendNew<Geom::LineSegment>( Geom::Point(x,y) );
 555     }
 556 }
 557
 558 /**
 559  * Calls SPCurve::curveto() with coordinates of three points.
 560  */
 561 void
 562 SPCurve::curveto(Geom::Point const &p0, Geom::Point const &p1, Geom::Point const &p2)
 563 {
 564     using Geom::X;
 565     using Geom::Y;
 566     curveto( p0[X], p0[Y],
 567              p1[X], p1[Y],
 568              p2[X], p2[Y] );
 569 }
 570 /**
 571  * Calls SPCurve::curveto() with coordinates of three points.
 572  */
 573 void
 574 SPCurve::curveto(NR::Point const &p0, NR::Point const &p1, NR::Point const &p2)
 575 {
 576     using NR::X;
 577     using NR::Y;
 578     curveto( p0[X], p0[Y],
 579              p1[X], p1[Y],
 580              p2[X], p2[Y] );
 581 }
 582 /**
 583  * Adds a bezier segment to the current subpath.
 584  * 2GEOMified
 585  */
 586 void
 587 SPCurve::curveto(gdouble x0, gdouble y0, gdouble x1, gdouble y1, gdouble x2, gdouble y2)
 588 {
 589     g_return_if_fail(_hascpt);
 590     g_return_if_fail(!_moving);
 591
 592     if (_posSet) {
 593         /* start a new segment */
 594         ensure_space(2);
 595         NArtBpath *bp = _bpath + _end;
 596         bp->code = NR_MOVETO_OPEN;
 597         bp->setC(3, _movePos);
 598         bp++;
 599         bp->code = NR_CURVETO;
 600         bp->x1 = x0;
 601         bp->y1 = y0;
 602         bp->x2 = x1;
 603         bp->y2 = y1;
 604         bp->x3 = x2;
 605         bp->y3 = y2;
 606         bp++;
 607         bp->code = NR_END;
 608         _end += 2;
 609         _posSet = false;
 610         _closed = false;
 611         _pathv.back().appendNew<Geom::CubicBezier>( Geom::Point(x0,y0), Geom::Point(x1,y1), Geom::Point(x2,y2) );
 612     } else {
 613         /* add curve */
 614
 615         g_return_if_fail(_end > 1);
 616         ensure_space(1);
 617         NArtBpath *bp = _bpath + _end;
 618         bp->code = NR_CURVETO;
 619         bp->x1 = x0;
 620         bp->y1 = y0;
 621         bp->x2 = x1;
 622         bp->y2 = y1;
 623         bp->x3 = x2;
 624         bp->y3 = y2;
 625         bp++;
 626         bp->code = NR_END;
 627         _end++;
 628         if (_pathv.empty())  g_message("leeg");
 629         else _pathv.back().appendNew<Geom::CubicBezier>( Geom::Point(x0,y0), Geom::Point(x1,y1), Geom::Point(x2,y2) );
 630     }
 631 }
 632
 633 /**
 634  * Close current subpath by possibly adding a line between start and end.
 635   * 2GEOMified
 636  */
 637 void
 638 SPCurve::closepath()
 639 {
 640     g_return_if_fail(_hascpt);
 641     g_return_if_fail(!_posSet);
 642     g_return_if_fail(!_moving);
 643     g_return_if_fail(!_closed);
 644     /* We need at least moveto, curveto, end. */
 645     g_return_if_fail(_end - _substart > 1);
 646
 647     {
 648         NArtBpath *bs = _bpath + _substart;
 649         NArtBpath *be = _bpath + _end - 1;
 650
 651         if (bs->c(3) != be->c(3)) {
 652             lineto(bs->c(3));
 653             bs = _bpath + _substart;
 654         }
 655
 656         bs->code = NR_MOVETO;
 657     }
 658     // Inkscape always manually adds the closing line segment to SPCurve with a lineto.
 659     // This lineto is removed in the writing function for NArtBpath,
 660     // so when path is closed and the last segment is a lineto, the closing line segment must really be removed first!
 661     // TODO: fix behavior in Inkscape!
 662     if ( /*Geom::LineSegment const *line_segment = */ dynamic_cast<Geom::LineSegment const  *>(&_pathv.back().back())) {
 663         _pathv.back().erase_last();
 664     }
 665     _pathv.back().close(true);
 666     _closed = true;
 667
 668     for (Geom::PathVector::const_iterator it = _pathv.begin(); it != _pathv.end(); it++) {
 669          if ( ! it->closed() ) {
 670             _closed = false;
 671             break;
 672         }
 673     }
 674
 675     for (NArtBpath const *bp = _bpath; bp->code != NR_END; bp++) {
 676         /** \todo
 677          * effic: Maintain a count of NR_MOVETO_OPEN's (e.g. instead of
 678          * the closed boolean).
 679          */
 680         if (bp->code == NR_MOVETO_OPEN) {
 681             _closed = false;
 682             break;
 683         }
 684     }
 685
 686     _hascpt = false;
 687 }
 688
 689 /** Like SPCurve::closepath() but sets the end point of the current
 690     command to the subpath start point instead of adding a new lineto.
 691
 692     Used for freehand drawing when the user draws back to the start point.
 693
 694   2GEOMified
 695 **/
 696 void
 697 SPCurve::closepath_current()
 698 {
 699     g_return_if_fail(_hascpt);
 700     g_return_if_fail(!_posSet);
 701     g_return_if_fail(!_closed);
 702     /* We need at least moveto, curveto, end. */
 703     g_return_if_fail(_end - _substart > 1);
 704
 705     {
 706         NArtBpath *bs = _bpath + _substart;
 707         NArtBpath *be = _bpath + _end - 1;
 708
 709         be->x3 = bs->x3;
 710         be->y3 = bs->y3;
 711
 712         bs->code = NR_MOVETO;
 713     }
 714     // Inkscape always manually adds the closing line segment to SPCurve with a lineto.
 715     // This lineto is removed in the writing function for NArtBpath,
 716     // so when path is closed and the last segment is a lineto, the closing line segment must really be removed first!
 717     // TODO: fix behavior in Inkscape!
 718     if ( /*Geom::LineSegment const *line_segment = */ dynamic_cast<Geom::LineSegment const  *>(&_pathv.back().back())) {
 719         _pathv.back().erase_last();
 720     }
 721     _pathv.back().close(true);
 722     _closed = true;
 723
 724     for (Geom::PathVector::const_iterator it = _pathv.begin(); it != _pathv.end(); it++) {
 725          if ( ! it->closed() ) {
 726             _closed = false;
 727             break;
 728         }
 729     }
 730
 731     for (NArtBpath const *bp = _bpath; bp->code != NR_END; bp++) {
 732         /** \todo
 733          * effic: Maintain a count of NR_MOVETO_OPEN's (e.g. instead of
 734          * the closed boolean).
 735          */
 736         if (bp->code == NR_MOVETO_OPEN) {
 737             _closed = false;
 738             break;
 739         }
 740     }
 741
 742     _hascpt = false;
 743     _moving = false;
 744 }
 745
 746 /**
 747  * True if no paths are in curve. If it only contains a path with only a moveto, the path is considered NON-empty
 748  */
 749 bool
 750 SPCurve::is_empty() const
 751 {
 752     bool empty = _pathv.empty();
 753
 754     return empty;
 755 }
 756
 757 /**
 758  * True iff all subpaths are closed.
 759  */
 760 bool
 761 SPCurve::is_closed() const
 762 {
 763     bool closed = true;
 764     for (Geom::PathVector::const_iterator it = _pathv.begin(); it != _pathv.end(); it++) {
 765          if ( ! it->closed() ) {
 766             closed = false;
 767             break;
 768         }
 769     }
 770
 771     return closed;
 772 }
 773
 774 /**
 775  * Return last subpath or NULL.
 776  */
 777 NArtBpath const *
 778 SPCurve::last_bpath() const
 779 {
 780     if (_end == 0) {
 781         return NULL;
 782     }
 783
 784     return _bpath + _end - 1;
 785 }
 786
 787 /**
 788  * Return last pathsegment (possibly the closing path segment) of the last path in PathVector or NULL.
 789  * If the last path is empty (contains only a moveto), the function returns NULL
 790  */
 791 Geom::Curve const *
 792 SPCurve::last_segment() const
 793 {
 794     if (is_empty()) {
 795         return NULL;
 796     }
 797     if (_pathv.back().empty()) {
 798         return NULL;
 799     }
 800
 801     return &_pathv.back().back_default();
 802 }
 803
 804 /**
 805  * Return last path in PathVector or NULL.
 806  */
 807 Geom::Path const *
 808 SPCurve::last_path() const
 809 {
 810     if (is_empty()) {
 811         return NULL;
 812     }
 813
 814     return &_pathv.back();
 815 }
 816
 817 /**
 818  * Return first pathsegment in PathVector or NULL.
 819  * equal in functionality to SPCurve::first_bpath()
 820  */
 821 Geom::Curve const *
 822 SPCurve::first_segment() const
 823 {
 824     if (is_empty()) {
 825         return NULL;
 826     }
 827     if (_pathv.front().empty()) {
 828         return NULL;
 829     }
 830
 831     return &_pathv.front().front();
 832 }
 833
 834 /**
 835  * Return first path in PathVector or NULL.
 836  */
 837 Geom::Path const *
 838 SPCurve::first_path() const
 839 {
 840     if (is_empty()) {
 841         return NULL;
 842     }
 843
 844     return &_pathv.front();
 845 }
 846
 847 /**
 848  * Return first point of first subpath or (0,0).  TODO: shouldn't this be (NR_HUGE, NR_HUGE) to be able to tell it apart from normal (0,0) ?
 849  */
 850 NR::Point
 851 SPCurve::first_point() const
 852 {
 853     if (is_empty())
 854         return NR::Point(0, 0);
 855
 856     return from_2geom( _pathv.front().initialPoint() );
 857 }
 858
 859 /**
 860  * Return the second point of first subpath or _movePos if curve too short.
 861  * If the pathvector is empty, this returns (0,0). If the first path is only a moveto, this method
 862  * returns the first point of the second path, if it exists. If there is no 2nd path, it returns the
 863  * first point of the first path.
 864  *
 865  * FIXME: for empty paths shouldn't this return (NR_HUGE,NR_HUGE)
 866  */
 867 NR::Point
 868 SPCurve::second_point() const
 869 {
 870     if (is_empty()) {
 871         return NR::Point(0,0);
 872     }
 873     else if (_pathv.front().empty()) {
 874         // first path is only a moveto
 875         // check if there is second path
 876         if (_pathv.size() > 1) {
 877             return _pathv[1].initialPoint();
 878         } else {
 879             return _pathv[0].initialPoint();
 880         }
 881     }
 882     else
 883         return _pathv.front()[0].finalPoint();
 884 }
 885
 886 /**
 887  * Return the second-last point of last subpath or _movePos if curve too short.
 888  */
 889 NR::Point
 890 SPCurve::penultimate_point() const
 891 {
 892     if (_end < 2) {
 893         return _movePos;
 894     }
 895
 896     NArtBpath *const bpath = _bpath + _end - 2;
 897     g_return_val_if_fail(bpath != NULL, NR::Point(0, 0));
 898
 899
 900     Geom::Curve const& back = _pathv.back().back_default();
 901     Geom::Point p = back.initialPoint();
 902     return from_2geom(p);
 903 }
 904
 905 /**
 906  * Return last point of last subpath or (0,0).  TODO: shouldn't this be (NR_HUGE, NR_HUGE) to be able to tell it apart from normal (0,0) ?
 907  * If the last path is only a moveto, then return that point.
 908  */
 909 NR::Point
 910 SPCurve::last_point() const
 911 {
 912     if (is_empty())
 913         return NR::Point(0, 0);
 914
 915     return from_2geom( _pathv.back().finalPoint() );
 916 }
 917
 918 inline static bool
 919 is_moveto(NRPathcode const c)
 920 {
 921     return c == NR_MOVETO || c == NR_MOVETO_OPEN;
 922 }
 923
 924 /**
 925  * Returns a *new* \a curve but drawn in the opposite direction.
 926  * Should result in the same shape, but
 927  * with all its markers drawn facing the other direction.
 928  * Reverses the order of subpaths as well
 929  * 2GEOMified
 930  **/
 931 SPCurve *
 932 SPCurve::create_reverse() const
 933 {
 934     /* We need at least moveto, curveto, end. */
 935     g_return_val_if_fail(_end - _substart > 1, NULL);
 936
 937     NArtBpath const *be = _bpath + _end - 1;
 938
 939     g_assert(is_moveto(_bpath[_substart].code));
 940     g_assert(is_moveto(_bpath[0].code));
 941     g_assert((be+1)->code == NR_END);
 942
 943     SPCurve  *new_curve = new SPCurve(_length);
 944     new_curve->moveto(be->c(3));
 945
 946     for (NArtBpath const *bp = be; ; --bp) {
 947         switch (bp->code) {
 948             case NR_MOVETO:
 949                 g_assert(new_curve->_bpath[new_curve->_substart].code == NR_MOVETO_OPEN);
 950                 new_curve->_bpath[new_curve->_substart].code = NR_MOVETO;
 951                 /* FALL-THROUGH */
 952             case NR_MOVETO_OPEN:
 953                 if (bp == _bpath) {
 954                     return new_curve;
 955                 }
 956                 new_curve->moveto((bp-1)->c(3));
 957                 break;
 958
 959             case NR_LINETO:
 960                 new_curve->lineto((bp-1)->c(3));
 961                 break;
 962
 963             case NR_CURVETO:
 964                 new_curve->curveto(bp->c(2), bp->c(1), (bp-1)->c(3));
 965                 break;
 966
 967             default:
 968                 g_assert_not_reached();
 969         }
 970     }
 971
 972     new_curve->_pathv = Geom::reverse_paths_and_order(_pathv);
 973 }
 974
 975 /**
 976  * Append \a curve2 to \a this.
 977  * If \a use_lineto is false, simply add all paths in \a curve2 to \a this;
 978  * if \a use_lineto is true, combine \a this's last path and \a curve2's first path and add the rest of the paths in \a curve2 to \a this.
 979  * 2GEOMified
 980  */
 981 void
 982 SPCurve::append(SPCurve const *curve2,
 983                 bool use_lineto)
 984 {
 985     g_return_if_fail(curve2 != NULL);
 986
 987     if (curve2->is_empty())
 988         return;
 989     if (curve2->_end < 1)
 990         return;
 991
 992     NArtBpath const *bs = curve2->_bpath;
 993
 994     bool closed = this->_closed;
 995
 996     for (NArtBpath const *bp = bs; bp->code != NR_END; bp++) {
 997         switch (bp->code) {
 998             case NR_MOVETO_OPEN:
 999                 if (use_lineto && _hascpt) {
1000                     lineto(bp->x3, bp->y3);
1001                     use_lineto = false;
1002                 } else {
1003                     if (closed && _hascpt) closepath();
1004                     moveto(bp->x3, bp->y3);
1005                 }
1006                 closed = false;
1007                 break;
1008
1009             case NR_MOVETO:
1010                 if (use_lineto && _hascpt) {
1011                     lineto(bp->x3, bp->y3);
1012                     use_lineto = FALSE;
1013                 } else {
1014                     if (closed && _hascpt) closepath();
1015                     moveto(bp->x3, bp->y3);
1016                 }
1017                 closed = true;
1018                 break;
1019
1020             case NR_LINETO:
1021                 lineto(bp->x3, bp->y3);
1022                 break;
1023
1024             case NR_CURVETO:
1025                 curveto(bp->x1, bp->y1, bp->x2, bp->y2, bp->x3, bp->y3);
1026                 break;
1027
1028             case NR_END:
1029                 g_assert_not_reached();
1030         }
1031     }
1032
1033     if (closed) {
1034         closepath();
1035     }
1036
1037     /* 2GEOM code when code above is removed:
1038     if (use_lineto) {
1039         Geom::PathVector::const_iterator it = curve2->_pathv.begin();
1040         if ( ! _pathv.empty() ) {
1041             Geom::Path & lastpath = _pathv.back();
1042             lastpath.appendNew<Geom::LineSegment>( (*it).initialPoint() );
1043             lastpath.append( (*it) );
1044         } else {
1045             _pathv.push_back( (*it) );
1046         }
1047
1048         for (it++; it != curve2->_pathv.end(); it++) {
1049             _pathv.push_back( (*it) );
1050         }
1051     } else {
1052         for (Geom::PathVector::const_iterator it = curve2->_pathv.begin(); it != curve2->_pathv.end(); it++) {
1053             _pathv.push_back( (*it) );
1054         }
1055     }
1056     */
1057 }
1058
1059 /**
1060  * Append \a c1 to \a this with possible fusing of close endpoints.
1061  * 2GEOMproof. Needs to be recoded when NArtBpath is no longer there. Right now, it applies the same changes to bpath and pathv depending on bpath
1062  */
1063 SPCurve *
1064 SPCurve::append_continuous(SPCurve const *c1, gdouble tolerance)
1065 {
1066     g_return_val_if_fail(c1 != NULL, NULL);
1067     g_return_val_if_fail(!_closed, NULL);
1068     g_return_val_if_fail(!c1->_closed, NULL);
1069
1070     if (c1->_end < 1) {
1071         return this;
1072     }
1073
1074     NArtBpath const *be = last_bpath();
1075     if (be) {
1076         NArtBpath const *bs = c1->get_bpath();
1077         if ( bs
1078              && ( fabs( bs->x3 - be->x3 ) <= tolerance )
1079              && ( fabs( bs->y3 - be->y3 ) <= tolerance ) )
1080         {
1081             /** \todo
1082              * fixme: Strictly we mess in case of multisegment mixed
1083              * open/close curves
1084              */
1085             bool closed = false;
1086             for (bs = bs + 1; bs->code != NR_END; bs++) {
1087                 switch (bs->code) {
1088                     case NR_MOVETO_OPEN:
1089                         if (closed) closepath();
1090                         moveto(bs->x3, bs->y3);
1091                         closed = false;
1092                         break;
1093                     case NR_MOVETO:
1094                         if (closed) closepath();
1095                         moveto(bs->x3, bs->y3);
1096                         closed = true;
1097                         break;
1098                     case NR_LINETO:
1099                         lineto(bs->x3, bs->y3);
1100                         break;
1101                     case NR_CURVETO:
1102                         curveto(bs->x1, bs->y1, bs->x2, bs->y2, bs->x3, bs->y3);
1103                         break;
1104                     case NR_END:
1105                         g_assert_not_reached();
1106                 }
1107             }
1108         } else {
1109             append(c1, TRUE);
1110         }
1111     } else {
1112         append(c1, TRUE);
1113     }
1114
1115     return this;
1116 }
1117
1118 /**
1119  * Remove last segment of curve.
1120  * (Only used once in /src/pen-context.cpp)
1121  * 2GEOMified
1122  */
1123 void
1124 SPCurve::backspace()
1125 {
1126     if ( is_empty() )
1127         return;
1128
1129     if (_end > 0) {
1130         _end -= 1;
1131         if (_end > 0) {
1132             NArtBpath *bp = _bpath + _end - 1;
1133             if ((bp->code == NR_MOVETO)     ||
1134                 (bp->code == NR_MOVETO_OPEN)  )
1135             {
1136                 _hascpt = true;
1137                 _posSet = true;
1138                 _closed = false;
1139                 _movePos = bp->c(3);
1140                 _end -= 1;
1141             }
1142         }
1143         _bpath[_end].code = NR_END;
1144     }
1145
1146     if ( !_pathv.back().empty() ) {
1147         _pathv.back().erase_last();
1148         _pathv.back().close(false);
1149     }
1150 }
1151
1152 /* Private methods */
1153
1154 /**
1155  * Returns index of first NR_END bpath in array.
1156  */
1157 static unsigned sp_bpath_length(NArtBpath const bpath[])
1158 {
1159     g_return_val_if_fail(bpath != NULL, FALSE);
1160
1161     unsigned ret = 0;
1162     while ( bpath[ret].code != NR_END ) {
1163         ++ret;
1164     }
1165     ++ret;
1166
1167     return ret;
1168 }
1169
1170 /**
1171  * \brief
1172  *
1173  * \todo
1174  * fixme: this is bogus -- it doesn't check for nr_moveto, which will indicate
1175  * a closing of the subpath it's nonsense to talk about a path as a whole
1176  * being closed, although maybe someone would want that for some other reason?
1177  * Oh, also, if the bpath just ends, then it's *open*.  I hope nobody is using
1178  * this code for anything.
1179  */
1180 static bool sp_bpath_closed(NArtBpath const bpath[])
1181 {
1182     g_return_val_if_fail(bpath != NULL, FALSE);
1183
1184     for (NArtBpath const *bp = bpath; bp->code != NR_END; bp++) {
1185         if (bp->code == NR_MOVETO_OPEN) {
1186             return false;
1187         }
1188     }
1189
1190     return true;
1191 }
1192
1193 /**
1194  * Returns length of bezier segment.
1195  */
1196 static double
1197 bezier_len(NR::Point const &c0,
1198            NR::Point const &c1,
1199            NR::Point const &c2,
1200            NR::Point const &c3,
1201            double const threshold)
1202 {
1203     /** \todo
1204      * The SVG spec claims that a closed form exists, but for the moment I'll
1205      * use a stupid algorithm.
1206      */
1207     double const lbound = L2( c3 - c0 );
1208     double const ubound = L2( c1 - c0 ) + L2( c2 - c1 ) + L2( c3 - c2 );
1209     double ret;
1210     if ( ubound - lbound <= threshold ) {
1211         ret = .5 * ( lbound + ubound );
1212     } else {
1213         NR::Point const a1( .5 * ( c0 + c1 ) );
1214         NR::Point const b2( .5 * ( c2 + c3 ) );
1215         NR::Point const c12( .5 * ( c1 + c2 ) );
1216         NR::Point const a2( .5 * ( a1 + c12 ) );
1217         NR::Point const b1( .5 * ( c12 + b2 ) );
1218         NR::Point const midpoint( .5 * ( a2 + b1 ) );
1219         double const rec_threshold = .625 * threshold;
1220         ret = bezier_len(c0, a1, a2, midpoint, rec_threshold) + bezier_len(midpoint, b1, b2, c3, rec_threshold);
1221         if (!(lbound - 1e-2 <= ret && ret <= ubound + 1e-2)) {
1222             using NR::X; using NR::Y;
1223             g_warning("ret=%f outside of expected bounds [%f, %f] for {(%.0f %.0f) (%.0f %.0f) (%.0f %.0f) (%.0f %.0f)}",
1224                       ret, lbound, ubound, c0[X], c0[Y], c1[X], c1[Y], c2[X], c2[Y], c3[X], c3[Y]);
1225         }
1226     }
1227     return ret;
1228 }
1229
1230 /**
1231  * Returns total length of curve, excluding length of closepath segments.
1232  */
1233 double
1234 sp_curve_distance_including_space(SPCurve const *const curve, double seg2len[])
1235 {
1236     g_return_val_if_fail(curve != NULL, 0.);
1237
1238     double ret = 0.0;
1239
1240     if ( curve->_bpath->code == NR_END ) {
1241         return ret;
1242     }
1243
1244     NR::Point prev(curve->_bpath->c(3));
1245     for (guint i = 1; i < curve->_end; ++i) {
1246         NArtBpath &p = curve->_bpath[i];
1247         double seg_len = 0;
1248         switch (p.code) {
1249             case NR_MOVETO_OPEN:
1250             case NR_MOVETO:
1251             case NR_LINETO:
1252                 seg_len = L2(p.c(3) - prev);
1253                 break;
1254
1255             case NR_CURVETO:
1256                 seg_len = bezier_len(prev, p.c(1), p.c(2), p.c(3), 1.);
1257                 break;
1258
1259             case NR_END:
1260                 return ret;
1261         }
1262         seg2len[i - 1] = seg_len;
1263         ret += seg_len;
1264         prev = p.c(3);
1265     }
1266     g_assert(!(ret < 0));
1267     return ret;
1268 }
1269
1270 /**
1271  * Like sp_curve_distance_including_space(), but ensures that the
1272  * result >= 1e-18:  uses 1 per segment if necessary.
1273  */
1274 double
1275 sp_curve_nonzero_distance_including_space(SPCurve const *const curve, double seg2len[])
1276 {
1277     double const real_dist(sp_curve_distance_including_space(curve, seg2len));
1278     if (real_dist >= 1e-18) {
1279         return real_dist;
1280     } else {
1281         unsigned const nSegs = SP_CURVE_LENGTH(curve) - 1;
1282         for (unsigned i = 0; i < nSegs; ++i) {
1283             seg2len[i] = 1.;
1284         }
1285         return (double) nSegs;
1286     }
1287 }
1288
1289 /**
1290  * 2GEOMified
1291  */
1292 void
1293 SPCurve::stretch_endpoints(NR::Point const &new_p0, NR::Point const &new_p1)
1294 {
1295     if (is_empty()) {
1296         return;
1297     }
1298     g_assert(unsigned(SP_CURVE_LENGTH(this)) + 1 == sp_bpath_length(_bpath));
1299     unsigned const nSegs = SP_CURVE_LENGTH(this) - 1;
1300     g_assert(nSegs != 0);
1301     double *const seg2len = new double[nSegs];
1302     double const tot_len = sp_curve_nonzero_distance_including_space(this, seg2len);
1303     NR::Point const offset0( new_p0 - first_point() );
1304     NR::Point const offset1( new_p1 - last_point() );
1305     _bpath->setC(3, new_p0);
1306     double begin_dist = 0.;
1307     for (unsigned si = 0; si < nSegs; ++si) {
1308         double const end_dist = begin_dist + seg2len[si];
1309         NArtBpath &p = _bpath[1 + si];
1310         switch (p.code) {
1311             case NR_LINETO:
1312             case NR_MOVETO:
1313             case NR_MOVETO_OPEN:
1314                 p.setC(3, p.c(3) + NR::Lerp(end_dist / tot_len, offset0, offset1));
1315                 break;
1316
1317             case NR_CURVETO:
1318                 for (unsigned ci = 1; ci <= 3; ++ci) {
1319                     p.setC(ci, p.c(ci) + Lerp((begin_dist + ci * seg2len[si] / 3.) / tot_len, offset0, offset1));
1320                 }
1321                 break;
1322
1323             default:
1324                 g_assert_not_reached();
1325         }
1326
1327         begin_dist = end_dist;
1328     }
1329     g_assert(L1(_bpath[nSegs].c(3) - new_p1) < 1.);
1330     /* Explicit set for better numerical properties. */
1331     _bpath[nSegs].setC(3, new_p1);
1332     delete [] seg2len;
1333
1334     Geom::Piecewise<Geom::D2<Geom::SBasis> > pwd2 = _pathv.front().toPwSb();
1335     Geom::Piecewise<Geom::SBasis> arclength = Geom::arcLengthSb(pwd2);
1336     if ( arclength.lastValue() <= 0 ) {
1337         g_error("SPCurve::stretch_endpoints - arclength <= 0");
1338         throw;
1339     }
1340     arclength *= 1./arclength.lastValue();
1341     Geom::Point const A( to_2geom(offset0) );
1342     Geom::Point const B( to_2geom(offset1) );
1343     Geom::Piecewise<Geom::SBasis> offsetx = (arclength*-1.+1)*A[0] + arclength*B[0];
1344     Geom::Piecewise<Geom::SBasis> offsety = (arclength*-1.+1)*A[1] + arclength*B[1];
1345     Geom::Piecewise<Geom::D2<Geom::SBasis> > offsetpath = Geom::sectionize( Geom::D2<Geom::Piecewise<Geom::SBasis> >(offsetx, offsety) );
1346     pwd2 += offsetpath;
1347     _pathv = Geom::path_from_piecewise( pwd2, 0.001 );
1348 }
1349
1350 /**
1351  *  sets start of first path to new_p0, and end of first path to  new_p1
1352  * 2GEOMified
1353  */
1354 void
1355 SPCurve::move_endpoints(NR::Point const &new_p0, NR::Point const &new_p1)
1356 {
1357     if (is_empty()) {
1358         return;
1359     }
1360     unsigned const nSegs = SP_CURVE_LENGTH(this) - 1;
1361     g_assert(nSegs != 0);
1362
1363     _bpath->setC(3, new_p0);
1364     _bpath[nSegs].setC(3, new_p1);
1365
1366     _pathv.front().setInitial(to_2geom(new_p0));
1367     _pathv.front().setFinal(to_2geom(new_p1));
1368 }
1369
1370 /**
1371  * returns the number of nodes in a path, used for statusbar text when selecting an spcurve.
1372  * 2GEOMified
1373  */
1374 guint
1375 SPCurve::nodes_in_path() const
1376 {
1377     gint r = _end;
1378     gint i = _length - 1;
1379     if (i > r) i = r; // sometimes after switching from node editor length is wrong, e.g. f6 - draw - f2 - tab - f1, this fixes it
1380     for (; i >= 0; i --)
1381         if (_bpath[i].code == NR_MOVETO)
1382             r --;
1383
1384     guint nr = 0;
1385     for(Geom::PathVector::const_iterator it = _pathv.begin(); it != _pathv.end(); ++it) {
1386         nr += (*it).size();
1387
1388         nr++; // count last node (this works also for closed paths because although they don't have a 'last node', they do have an extra segment
1389     }
1390
1391     return r;
1392 }
1393
1394 /**
1395  *  Adds p to the last point (and last handle if present) of the last path
1396  * 2GEOMified
1397  */
1398 void
1399 SPCurve::last_point_additive_move(Geom::Point const & p)
1400 {
1401     if (is_empty()) {
1402         return;
1403     }
1404     if (_end == 0) {
1405         return;
1406     }
1407     NArtBpath * path = _bpath + _end - 1;
1408
1409     if (path->code == NR_CURVETO) {
1410         path->x2 += p[Geom::X];
1411         path->y2 += p[Geom::Y];
1412     }
1413     path->x3 += p[Geom::X];
1414     path->y3 += p[Geom::Y];
1415
1416     _pathv.back().setFinal( _pathv.back().finalPoint() + p );
1417
1418     // Move handle as well when the last segment is a cubic bezier segment:
1419     // TODO: what to do for quadratic beziers?
1420     if ( Geom::CubicBezier const *lastcube = dynamic_cast<Geom::CubicBezier const *>(&_pathv.back().back()) ) {
1421         Geom::CubicBezier newcube( *lastcube );
1422         newcube.setPoint(2, newcube[2] + p);
1423         _pathv.back().replace( --_pathv.back().end(), newcube );
1424     }
1425 }
1426
1427 /*
1428   Local Variables:
1429   mode:c++
1430   c-file-style:"stroustrup"
1431   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1432   indent-tabs-mode:nil
1433   fill-column:99
1434   End:
1435 */
1436 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :