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