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