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