src/livarot/PathConversion.cpp

   1 /*
   2  *  PathConversion.cpp
   3  *  nlivarot
   4  *
   5  *  Created by fred on Mon Nov 03 2003.
   6  *
   7  */
   8
   9 #include "Path.h"
  10 #include "Shape.h"
  11 #include "livarot/path-description.h"
  12
  13 #include <libnr/nr-matrix.h>
  14 #include <2geom/transforms.h>
  15
  16 /*
  17  * path description -> polyline
  18  * and Path -> Shape (the Fill() function at the bottom)
  19  * nathing fancy here: take each command and append an approximation of it to the polyline
  20  */
  21
  22 void Path::ConvertWithBackData(double treshhold)
  23 {
  24     if ( descr_flags & descr_adding_bezier ) {
  25         CancelBezier();
  26     }
  27
  28     if ( descr_flags & descr_doing_subpath ) {
  29         CloseSubpath();
  30     }
  31
  32     SetBackData(true);
  33     ResetPoints();
  34     if ( descr_cmd.empty() ) {
  35         return;
  36     }
  37
  38     NR::Point curX;
  39     int curP = 1;
  40     int lastMoveTo = -1;
  41
  42     // The initial moveto.
  43     {
  44         int const firstTyp = descr_cmd[0]->getType();
  45         if ( firstTyp == descr_moveto ) {
  46             curX = dynamic_cast<PathDescrMoveTo *>(descr_cmd[0])->p;
  47         } else {
  48             curP = 0;
  49             curX[NR::X] = curX[NR::Y] = 0;
  50         }
  51         lastMoveTo = AddPoint(curX, 0, 0.0, true);
  52     }
  53
  54     // And the rest, one by one.
  55     while ( curP < int(descr_cmd.size()) ) {
  56
  57         int const nType = descr_cmd[curP]->getType();
  58         NR::Point nextX;
  59
  60         switch (nType) {
  61             case descr_forced: {
  62                 AddForcedPoint(curX, curP, 1.0);
  63                 curP++;
  64                 break;
  65             }
  66
  67             case descr_moveto: {
  68                 PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo*>(descr_cmd[curP]);
  69                 nextX = nData->p;
  70                 lastMoveTo = AddPoint(nextX, curP, 0.0, true);
  71                 // et on avance
  72                 curP++;
  73                 break;
  74             }
  75
  76             case descr_close: {
  77                 nextX = pts[lastMoveTo].p;
  78                 AddPoint(nextX, curP, 1.0, false);
  79                 curP++;
  80                 break;
  81             }
  82
  83             case descr_lineto: {
  84                 PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[curP]);
  85                 nextX = nData->p;
  86                 AddPoint(nextX,curP,1.0,false);
  87                 // et on avance
  88                 curP++;
  89                 break;
  90             }
  91
  92             case descr_cubicto: {
  93                 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[curP]);
  94                 nextX = nData->p;
  95                 RecCubicTo(curX, nData->start, nextX, nData->end, treshhold, 8, 0.0, 1.0, curP);
  96                 AddPoint(nextX, curP, 1.0, false);
  97                 // et on avance
  98                 curP++;
  99                 break;
 100             }
 101
 102             case descr_arcto: {
 103                 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[curP]);
 104                 nextX = nData->p;
 105                 DoArc(curX, nextX, nData->rx, nData->ry, nData->angle, nData->large, nData->clockwise, treshhold, curP);
 106                 AddPoint(nextX, curP, 1.0, false);
 107                 // et on avance
 108                 curP++;
 109                 break;
 110             }
 111
 112             case descr_bezierto: {
 113                 PathDescrBezierTo *nBData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[curP]);
 114                 int nbInterm = nBData->nb;
 115                 nextX = nBData->p;
 116
 117                 int ip = curP + 1;
 118                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 119
 120                 if ( nbInterm >= 1 ) {
 121                     NR::Point bx = curX;
 122                     NR::Point cx = curX;
 123                     NR::Point dx = curX;
 124
 125                     dx = nData->p;
 126                     ip++;
 127                     nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 128
 129                     cx = 2 * bx - dx;
 130
 131                     for (int k = 0; k < nbInterm - 1; k++) {
 132                         bx = cx;
 133                         cx = dx;
 134
 135                         dx = nData->p;
 136                         ip++;
 137                         nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 138
 139                         NR::Point stx;
 140                         stx = (bx + cx) / 2;
 141                         if ( k > 0 ) {
 142                             AddPoint(stx,curP - 1+k,1.0,false);
 143                         }
 144
 145                         {
 146                             NR::Point mx;
 147                             mx = (cx + dx) / 2;
 148                             RecBezierTo(cx, stx, mx, treshhold, 8, 0.0, 1.0, curP + k);
 149                         }
 150                     }
 151                     {
 152                         bx = cx;
 153                         cx = dx;
 154
 155                         dx = nextX;
 156                         dx = 2 * dx - cx;
 157
 158                         NR::Point stx;
 159                         stx = (bx + cx) / 2;
 160
 161                         if ( nbInterm > 1 ) {
 162                             AddPoint(stx, curP + nbInterm - 2, 1.0, false);
 163                         }
 164
 165                         {
 166                             NR::Point mx;
 167                             mx = (cx + dx) / 2;
 168                             RecBezierTo(cx, stx, mx, treshhold, 8, 0.0, 1.0, curP + nbInterm - 1);
 169                         }
 170                     }
 171
 172                 }
 173
 174
 175                 AddPoint(nextX, curP - 1 + nbInterm, 1.0, false);
 176
 177                 // et on avance
 178                 curP += 1 + nbInterm;
 179                 break;
 180             }
 181         }
 182         curX = nextX;
 183     }
 184 }
 185
 186
 187 void Path::Convert(double treshhold)
 188 {
 189     if ( descr_flags & descr_adding_bezier ) {
 190         CancelBezier();
 191     }
 192
 193     if ( descr_flags & descr_doing_subpath ) {
 194         CloseSubpath();
 195     }
 196
 197     SetBackData(false);
 198     ResetPoints();
 199     if ( descr_cmd.empty() ) {
 200         return;
 201     }
 202
 203     NR::Point curX;
 204     int curP = 1;
 205     int lastMoveTo = 0;
 206
 207     // le moveto
 208     {
 209         int const firstTyp = descr_cmd[0]->getType();
 210         if ( firstTyp == descr_moveto ) {
 211             curX = dynamic_cast<PathDescrMoveTo *>(descr_cmd[0])->p;
 212         } else {
 213             curP = 0;
 214             curX[0] = curX[1] = 0;
 215         }
 216         lastMoveTo = AddPoint(curX, true);
 217     }
 218     descr_cmd[0]->associated = lastMoveTo;
 219
 220     // et le reste, 1 par 1
 221     while ( curP < int(descr_cmd.size()) ) {
 222
 223         int const nType = descr_cmd[curP]->getType();
 224         NR::Point nextX;
 225
 226         switch (nType) {
 227             case descr_forced: {
 228                 descr_cmd[curP]->associated = AddForcedPoint(curX);
 229                 curP++;
 230                 break;
 231             }
 232
 233             case descr_moveto: {
 234                 PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[curP]);
 235                 nextX = nData->p;
 236                 lastMoveTo = AddPoint(nextX, true);
 237                 descr_cmd[curP]->associated = lastMoveTo;
 238
 239                 // et on avance
 240                 curP++;
 241                 break;
 242             }
 243
 244             case descr_close: {
 245                 nextX = pts[lastMoveTo].p;
 246                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 247                 if ( descr_cmd[curP]->associated < 0 ) {
 248                     if ( curP == 0 ) {
 249                         descr_cmd[curP]->associated = 0;
 250                     } else {
 251                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 252                     }
 253                 }
 254                 curP++;
 255                 break;
 256             }
 257
 258             case descr_lineto: {
 259                 PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[curP]);
 260                 nextX = nData->p;
 261                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 262                 if ( descr_cmd[curP]->associated < 0 ) {
 263                     if ( curP == 0 ) {
 264                         descr_cmd[curP]->associated = 0;
 265                     } else {
 266                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 267                     }
 268                 }
 269                 // et on avance
 270                 curP++;
 271                 break;
 272             }
 273
 274             case descr_cubicto: {
 275                 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[curP]);
 276                 nextX = nData->p;
 277                 RecCubicTo(curX, nData->start, nextX, nData->end, treshhold, 8);
 278                 descr_cmd[curP]->associated = AddPoint(nextX,false);
 279                 if ( descr_cmd[curP]->associated < 0 ) {
 280                     if ( curP == 0 ) {
 281                         descr_cmd[curP]->associated = 0;
 282                     } else {
 283                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 284                     }
 285                 }
 286                 // et on avance
 287                 curP++;
 288                 break;
 289             }
 290
 291             case descr_arcto: {
 292                 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[curP]);
 293                 nextX = nData->p;
 294                 DoArc(curX, nextX, nData->rx, nData->ry, nData->angle, nData->large, nData->clockwise, treshhold);
 295                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 296                 if ( descr_cmd[curP]->associated < 0 ) {
 297                     if ( curP == 0 ) {
 298                         descr_cmd[curP]->associated = 0;
 299                     } else {
 300                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 301                     }
 302                 }
 303                 // et on avance
 304                 curP++;
 305                 break;
 306             }
 307
 308             case descr_bezierto: {
 309                 PathDescrBezierTo *nBData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[curP]);
 310                 int nbInterm = nBData->nb;
 311                 nextX = nBData->p;
 312                 int curBD = curP;
 313
 314                 curP++;
 315                 int ip = curP;
 316                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 317
 318                 if ( nbInterm == 1 ) {
 319                     NR::Point const midX = nData->p;
 320                     RecBezierTo(midX, curX, nextX, treshhold, 8);
 321                 } else if ( nbInterm > 1 ) {
 322                     NR::Point bx = curX;
 323                     NR::Point cx = curX;
 324                     NR::Point dx = curX;
 325
 326                     dx = nData->p;
 327                     ip++;
 328                     nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 329
 330                     cx = 2 * bx - dx;
 331
 332                     for (int k = 0; k < nbInterm - 1; k++) {
 333                         bx = cx;
 334                         cx = dx;
 335
 336                         dx = nData->p;
 337                         ip++;
 338                         nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 339
 340                         NR::Point stx = (bx + cx) / 2;
 341                         if ( k > 0 ) {
 342                             descr_cmd[ip - 2]->associated = AddPoint(stx, false);
 343                             if ( descr_cmd[ip - 2]->associated < 0 ) {
 344                                 if ( curP == 0 ) {
 345                                     descr_cmd[ip - 2]->associated = 0;
 346                                 } else {
 347                                     descr_cmd[ip - 2]->associated = descr_cmd[ip - 3]->associated;
 348                                 }
 349                             }
 350                         }
 351
 352                         {
 353                             NR::Point const mx = (cx + dx) / 2;
 354                             RecBezierTo(cx, stx, mx, treshhold, 8);
 355                         }
 356                     }
 357
 358                     {
 359                         bx = cx;
 360                         cx = dx;
 361
 362                         dx = nextX;
 363                         dx = 2 * dx - cx;
 364
 365                         NR::Point stx = (bx + cx) / 2;
 366
 367                         descr_cmd[ip - 1]->associated = AddPoint(stx, false);
 368                         if ( descr_cmd[ip - 1]->associated < 0 ) {
 369                             if ( curP == 0 ) {
 370                                 descr_cmd[ip - 1]->associated = 0;
 371                             } else {
 372                                 descr_cmd[ip - 1]->associated = descr_cmd[ip - 2]->associated;
 373                             }
 374                         }
 375
 376                         {
 377                             NR::Point mx = (cx + dx) / 2;
 378                             RecBezierTo(cx, stx, mx, treshhold, 8);
 379                         }
 380                     }
 381                 }
 382
 383                 descr_cmd[curBD]->associated = AddPoint(nextX, false);
 384                 if ( descr_cmd[curBD]->associated < 0 ) {
 385                     if ( curP == 0 ) {
 386                         descr_cmd[curBD]->associated = 0;
 387                     } else {
 388                         descr_cmd[curBD]->associated = descr_cmd[curBD - 1]->associated;
 389                     }
 390                 }
 391
 392                 // et on avance
 393                 curP += nbInterm;
 394                 break;
 395             }
 396         }
 397
 398         curX = nextX;
 399     }
 400 }
 401
 402 #define POINT_RELATION_TO_AREA(pt, area) ((pt)[0] < (area)->x0 ? 1 : ((pt)[0] > (area)->x1 ? 2 : ((pt)[1] < (area)->y0 ? 3 : ((pt)[1] > (area)->y1 ? 4 : 0))))
 403
 404 void Path::Convert(NRRectL *area, double treshhold)
 405 {
 406     if ( descr_flags & descr_adding_bezier ) {
 407         CancelBezier();
 408     }
 409
 410     if ( descr_flags & descr_doing_subpath ) {
 411         CloseSubpath();
 412     }
 413
 414     SetBackData(false);
 415     ResetPoints();
 416     if ( descr_cmd.empty() ) {
 417         return;
 418     }
 419
 420     NR::Point curX;
 421     int curP = 1;
 422     int lastMoveTo = 0;
 423     short last_point_relation = 0;
 424     short curent_point_relation = 0;
 425     bool last_start_elimination = false;
 426     bool start_elimination = false;
 427     bool replace = false;
 428
 429     // first point
 430     {
 431         int const firstTyp = descr_cmd[0]->getType();
 432         if ( firstTyp == descr_moveto ) {
 433             curX = dynamic_cast<PathDescrMoveTo *>(descr_cmd[0])->p;
 434         } else {
 435             curP = 0;
 436             curX[0] = curX[1] = 0;
 437         }
 438
 439         last_point_relation = POINT_RELATION_TO_AREA(curX, area);
 440         lastMoveTo = AddPoint(curX, true);
 441     }
 442     descr_cmd[0]->associated = lastMoveTo;
 443
 444     // process nodes one by one
 445     while ( curP < int(descr_cmd.size()) ) {
 446
 447         int const nType = descr_cmd[curP]->getType();
 448         NR::Point nextX;
 449
 450         switch (nType) {
 451             case descr_forced: {
 452                 descr_cmd[curP]->associated = AddForcedPoint(curX);
 453                 last_point_relation = 0;
 454                 curP++;
 455                 break;
 456             }
 457
 458             case descr_moveto: {
 459                 PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[curP]);
 460                 nextX = nData->p;
 461                 lastMoveTo = AddPoint(nextX, true);
 462                 descr_cmd[curP]->associated = lastMoveTo;
 463                 last_point_relation = POINT_RELATION_TO_AREA(nextX, area);
 464                 start_elimination = false;
 465
 466                 curP++;
 467                 break;
 468             }
 469
 470             case descr_close: {
 471                 nextX = pts[lastMoveTo].p;
 472                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 473                 if ( descr_cmd[curP]->associated < 0 ) {
 474                     if ( curP == 0 ) {
 475                         descr_cmd[curP]->associated = 0;
 476                     } else {
 477                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 478                     }
 479                 }
 480                 last_point_relation = 0;
 481                 curP++;
 482                 break;
 483             }
 484
 485             case descr_lineto: {
 486                 PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[curP]);
 487                 nextX = nData->p;
 488                 curent_point_relation = POINT_RELATION_TO_AREA(nextX, area);
 489                 replace = false;
 490                 last_start_elimination = start_elimination;
 491                 if (curent_point_relation > 0 && curent_point_relation == last_point_relation) {
 492                     if (!start_elimination) {
 493                         start_elimination = true;
 494                     } else {
 495                         replace = true;
 496                         descr_cmd[curP]->associated = ReplacePoint(nextX);
 497                     }
 498                 } else {
 499                     start_elimination = false;
 500                 }
 501
 502                 if (!replace) {
 503                     descr_cmd[curP]->associated = AddPoint(nextX, false);
 504                 }
 505
 506                 if ( descr_cmd[curP]->associated < 0 ) {
 507                     // point is not added as position is equal to the last added
 508                     start_elimination = last_start_elimination;
 509                     if ( curP == 0 ) {
 510                         descr_cmd[curP]->associated = 0;
 511                     } else {
 512                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 513                     }
 514                 }
 515                 last_point_relation = curent_point_relation;
 516                 curP++;
 517                 break;
 518             }
 519
 520             case descr_cubicto: {
 521                 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[curP]);
 522                 nextX = nData->p;
 523
 524                 curent_point_relation = POINT_RELATION_TO_AREA(nextX, area);
 525                 replace = false;
 526                 last_start_elimination = start_elimination;
 527                 if (curent_point_relation > 0 && curent_point_relation == last_point_relation &&
 528                     curent_point_relation == POINT_RELATION_TO_AREA(curX + (nData->start), area) &&
 529                     curent_point_relation == POINT_RELATION_TO_AREA(nextX + (nData->end), area))
 530                 {
 531                     if (!start_elimination) {
 532                         start_elimination = true;
 533                     } else {
 534                         replace = true;
 535                         descr_cmd[curP]->associated = ReplacePoint(nextX);
 536                     }
 537                 } else {
 538                     start_elimination = false;
 539                 }
 540
 541                 if (!replace) {
 542                     RecCubicTo(curX, nData->start, nextX, nData->end, treshhold, 8);
 543                     descr_cmd[curP]->associated = AddPoint(nextX,false);
 544                 }
 545
 546                 if ( descr_cmd[curP]->associated < 0 ) {
 547                     // point is not added as position is equal to the last added
 548                     start_elimination = last_start_elimination;
 549                     if ( curP == 0 ) {
 550                         descr_cmd[curP]->associated = 0;
 551                     } else {
 552                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 553                     }
 554                 }
 555                 last_point_relation = curent_point_relation;
 556                 curP++;
 557                 break;
 558             }
 559
 560             case descr_arcto: {
 561                 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[curP]);
 562                 nextX = nData->p;
 563                 DoArc(curX, nextX, nData->rx, nData->ry, nData->angle, nData->large, nData->clockwise, treshhold);
 564                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 565                 if ( descr_cmd[curP]->associated < 0 ) {
 566                     if ( curP == 0 ) {
 567                         descr_cmd[curP]->associated = 0;
 568                     } else {
 569                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 570                     }
 571                 }
 572                 last_point_relation = 0;
 573
 574                 curP++;
 575                 break;
 576             }
 577
 578             case descr_bezierto: {
 579                 PathDescrBezierTo *nBData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[curP]);
 580                 int nbInterm = nBData->nb;
 581                 nextX = nBData->p;
 582                 int curBD = curP;
 583
 584                 curP++;
 585                 int ip = curP;
 586                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 587
 588                 if ( nbInterm == 1 ) {
 589                     NR::Point const midX = nData->p;
 590                     RecBezierTo(midX, curX, nextX, treshhold, 8);
 591                 } else if ( nbInterm > 1 ) {
 592                     NR::Point bx = curX;
 593                     NR::Point cx = curX;
 594                     NR::Point dx = curX;
 595
 596                     dx = nData->p;
 597                     ip++;
 598                     nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 599
 600                     cx = 2 * bx - dx;
 601
 602                     for (int k = 0; k < nbInterm - 1; k++) {
 603                         bx = cx;
 604                         cx = dx;
 605
 606                         dx = nData->p;
 607                         ip++;
 608                         nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 609
 610                         NR::Point stx = (bx + cx) / 2;
 611                         if ( k > 0 ) {
 612                             descr_cmd[ip - 2]->associated = AddPoint(stx, false);
 613                             if ( descr_cmd[ip - 2]->associated < 0 ) {
 614                                 if ( curP == 0 ) {
 615                                     descr_cmd[ip - 2]->associated = 0;
 616                                 } else {
 617                                     descr_cmd[ip - 2]->associated = descr_cmd[ip - 3]->associated;
 618                                 }
 619                             }
 620                         }
 621
 622                         {
 623                             NR::Point const mx = (cx + dx) / 2;
 624                             RecBezierTo(cx, stx, mx, treshhold, 8);
 625                         }
 626                     }
 627
 628                     {
 629                         bx = cx;
 630                         cx = dx;
 631
 632                         dx = nextX;
 633                         dx = 2 * dx - cx;
 634
 635                         NR::Point stx = (bx + cx) / 2;
 636
 637                         descr_cmd[ip - 1]->associated = AddPoint(stx, false);
 638                         if ( descr_cmd[ip - 1]->associated < 0 ) {
 639                             if ( curP == 0 ) {
 640                                 descr_cmd[ip - 1]->associated = 0;
 641                             } else {
 642                                 descr_cmd[ip - 1]->associated = descr_cmd[ip - 2]->associated;
 643                             }
 644                         }
 645
 646                         {
 647                             NR::Point mx = (cx + dx) / 2;
 648                             RecBezierTo(cx, stx, mx, treshhold, 8);
 649                         }
 650                     }
 651                 }
 652
 653                 descr_cmd[curBD]->associated = AddPoint(nextX, false);
 654                 if ( descr_cmd[curBD]->associated < 0 ) {
 655                     if ( curP == 0 ) {
 656                         descr_cmd[curBD]->associated = 0;
 657                     } else {
 658                         descr_cmd[curBD]->associated = descr_cmd[curBD - 1]->associated;
 659                     }
 660                 }
 661
 662                 last_point_relation = 0;
 663
 664                 curP += nbInterm;
 665                 break;
 666             }
 667         }
 668
 669         curX = nextX;
 670     }
 671 }
 672
 673
 674 void Path::ConvertEvenLines(double treshhold)
 675 {
 676     if ( descr_flags & descr_adding_bezier ) {
 677         CancelBezier();
 678     }
 679
 680     if ( descr_flags & descr_doing_subpath ) {
 681         CloseSubpath();
 682     }
 683
 684     SetBackData(false);
 685     ResetPoints();
 686     if ( descr_cmd.empty() ) {
 687         return;
 688     }
 689
 690     NR::Point curX;
 691     int curP = 1;
 692     int lastMoveTo = 0;
 693
 694     // le moveto
 695     {
 696         int const firstTyp = descr_cmd[0]->getType();
 697         if ( firstTyp == descr_moveto ) {
 698             curX = dynamic_cast<PathDescrMoveTo *>(descr_cmd[0])->p;
 699         } else {
 700             curP = 0;
 701             curX[0] = curX[1] = 0;
 702         }
 703         lastMoveTo = AddPoint(curX, true);
 704     }
 705     descr_cmd[0]->associated = lastMoveTo;
 706
 707     // et le reste, 1 par 1
 708     while ( curP < int(descr_cmd.size()) ) {
 709
 710         int const nType = descr_cmd[curP]->getType();
 711         NR::Point nextX;
 712
 713         switch (nType) {
 714             case descr_forced: {
 715                 descr_cmd[curP]->associated = AddForcedPoint(curX);
 716                 curP++;
 717                 break;
 718             }
 719
 720             case descr_moveto: {
 721                 PathDescrMoveTo* nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[curP]);
 722                 nextX = nData->p;
 723                 lastMoveTo = AddPoint(nextX,true);
 724                 descr_cmd[curP]->associated = lastMoveTo;
 725
 726                 // et on avance
 727                 curP++;
 728                 break;
 729             }
 730
 731             case descr_close: {
 732                 nextX = pts[lastMoveTo].p;
 733                 {
 734                     NR::Point nexcur;
 735                     nexcur = nextX - curX;
 736                     const double segL = NR::L2(nexcur);
 737                     if ( segL > treshhold ) {
 738                         for (double i = treshhold; i < segL; i += treshhold) {
 739                             NR::Point nX;
 740                             nX = (segL - i) * curX + i * nextX;
 741                             nX /= segL;
 742                             AddPoint(nX);
 743                         }
 744                     }
 745                 }
 746
 747                 descr_cmd[curP]->associated = AddPoint(nextX,false);
 748                 if ( descr_cmd[curP]->associated < 0 ) {
 749                     if ( curP == 0 ) {
 750                         descr_cmd[curP]->associated = 0;
 751                     } else {
 752                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 753                     }
 754                 }
 755
 756                 curP++;
 757                 break;
 758             }
 759
 760             case descr_lineto: {
 761                 PathDescrLineTo* nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[curP]);
 762                 nextX = nData->p;
 763                 NR::Point nexcur = nextX - curX;
 764                 const double segL = L2(nexcur);
 765                 if ( segL > treshhold ) {
 766                     for (double i = treshhold; i < segL; i += treshhold) {
 767                         NR::Point nX = ((segL - i) * curX + i * nextX) / segL;
 768                         AddPoint(nX);
 769                     }
 770                 }
 771
 772                 descr_cmd[curP]->associated = AddPoint(nextX,false);
 773                 if ( descr_cmd[curP]->associated < 0 ) {
 774                     if ( curP == 0 ) {
 775                         descr_cmd[curP]->associated = 0;
 776                     } else {
 777                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 778                     }
 779                 }
 780                 // et on avance
 781                 curP++;
 782                 break;
 783             }
 784
 785             case descr_cubicto: {
 786                 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[curP]);
 787                 nextX = nData->p;
 788                 RecCubicTo(curX, nData->start, nextX, nData->end, treshhold, 8, 4 * treshhold);
 789                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 790                 if ( descr_cmd[curP]->associated < 0 ) {
 791                     if ( curP == 0 ) {
 792                         descr_cmd[curP]->associated = 0;
 793                     } else {
 794                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 795                     }
 796                 }
 797                 // et on avance
 798                 curP++;
 799                 break;
 800             }
 801
 802             case descr_arcto: {
 803                 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[curP]);
 804                 nextX = nData->p;
 805                 DoArc(curX, nextX, nData->rx, nData->ry, nData->angle, nData->large, nData->clockwise, treshhold);
 806                 descr_cmd[curP]->associated =AddPoint(nextX, false);
 807                 if ( descr_cmd[curP]->associated < 0 ) {
 808                     if ( curP == 0 ) {
 809                         descr_cmd[curP]->associated = 0;
 810                     } else {
 811                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 812                     }
 813                 }
 814
 815                 // et on avance
 816                 curP++;
 817                 break;
 818             }
 819
 820             case descr_bezierto: {
 821                 PathDescrBezierTo *nBData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[curP]);
 822                 int nbInterm = nBData->nb;
 823                 nextX = nBData->p;
 824                 int curBD = curP;
 825
 826                 curP++;
 827                 int ip = curP;
 828                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 829
 830                 if ( nbInterm == 1 ) {
 831                     NR::Point const midX = nData->p;
 832                     RecBezierTo(midX, curX, nextX, treshhold, 8, 4 * treshhold);
 833                 } else if ( nbInterm > 1 ) {
 834                     NR::Point bx = curX;
 835                     NR::Point cx = curX;
 836                     NR::Point dx = curX;
 837
 838                     dx = nData->p;
 839                     ip++;
 840                     nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 841
 842                     cx = 2 * bx - dx;
 843
 844                     for (int k = 0; k < nbInterm - 1; k++) {
 845                         bx = cx;
 846                         cx = dx;
 847                         dx = nData->p;
 848
 849                         ip++;
 850                         nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 851
 852                         NR::Point stx = (bx+cx) / 2;
 853                         if ( k > 0 ) {
 854                             descr_cmd[ip - 2]->associated = AddPoint(stx, false);
 855                             if ( descr_cmd[ip - 2]->associated < 0 ) {
 856                                 if ( curP == 0 ) {
 857                                     descr_cmd[ip- 2]->associated = 0;
 858                                 } else {
 859                                     descr_cmd[ip - 2]->associated = descr_cmd[ip - 3]->associated;
 860                                 }
 861                             }
 862                         }
 863
 864                         {
 865                             NR::Point const mx = (cx + dx) / 2;
 866                             RecBezierTo(cx, stx, mx, treshhold, 8, 4 * treshhold);
 867                         }
 868                     }
 869
 870                     {
 871                         bx = cx;
 872                         cx = dx;
 873
 874                         dx = nextX;
 875                         dx = 2 * dx - cx;
 876
 877                         NR::Point const stx = (bx + cx) / 2;
 878
 879                         descr_cmd[ip - 1]->associated = AddPoint(stx, false);
 880                         if ( descr_cmd[ip - 1]->associated < 0 ) {
 881                             if ( curP == 0 ) {
 882                                 descr_cmd[ip - 1]->associated = 0;
 883                             } else {
 884                                 descr_cmd[ip - 1]->associated = descr_cmd[ip - 2]->associated;
 885                             }
 886                         }
 887
 888                         {
 889                             NR::Point const mx = (cx + dx) / 2;
 890                             RecBezierTo(cx, stx, mx, treshhold, 8, 4 * treshhold);
 891                         }
 892                     }
 893                 }
 894
 895                 descr_cmd[curBD]->associated = AddPoint(nextX, false);
 896                 if ( descr_cmd[curBD]->associated < 0 ) {
 897                     if ( curP == 0 ) {
 898                         descr_cmd[curBD]->associated = 0;
 899                     } else {
 900                         descr_cmd[curBD]->associated = descr_cmd[curBD - 1]->associated;
 901                     }
 902                 }
 903
 904                 // et on avance
 905                 curP += nbInterm;
 906                 break;
 907             }
 908         }
 909         if ( Geom::LInfty(curX - nextX) > 0.00001 ) {
 910             curX = nextX;
 911         }
 912     }
 913 }
 914
 915 const NR::Point Path::PrevPoint(int i) const
 916 {
 917     /* TODO: I suspect this should assert `(unsigned) i < descr_nb'.  We can probably change
 918        the argument to unsigned.  descr_nb should probably be changed to unsigned too. */
 919     g_assert( i >= 0 );
 920     switch ( descr_cmd[i]->getType() ) {
 921         case descr_moveto: {
 922             PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[i]);
 923             return nData->p;
 924         }
 925         case descr_lineto: {
 926             PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[i]);
 927             return nData->p;
 928         }
 929         case descr_arcto: {
 930             PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[i]);
 931             return nData->p;
 932         }
 933         case descr_cubicto: {
 934             PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[i]);
 935             return nData->p;
 936         }
 937         case descr_bezierto: {
 938             PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[i]);
 939             return nData->p;
 940         }
 941         case descr_interm_bezier:
 942         case descr_close:
 943         case descr_forced:
 944             return PrevPoint(i - 1);
 945         default:
 946             g_assert_not_reached();
 947             return NR::Point(0, 0);
 948     }
 949 }
 950
 951 // utilitaries: given a quadratic bezier curve (start point, control point, end point, ie that's a clamped curve),
 952 // and an abcissis on it, get the point with that abcissis.
 953 // warning: it's NOT a curvilign abcissis (or whatever you call that in english), so "t" is NOT the length of "start point"->"result point"
 954 void Path::QuadraticPoint(double t, NR::Point &oPt,
 955                           const NR::Point &iS, const NR::Point &iM, const NR::Point &iE)
 956 {
 957     NR::Point const ax = iE - 2 * iM + iS;
 958     NR::Point const bx = 2 * iM - 2 * iS;
 959     NR::Point const cx = iS;
 960
 961     oPt = t * t * ax + t * bx + cx;
 962 }
 963 // idem for cubic bezier patch
 964 void Path::CubicTangent(double t, NR::Point &oPt, const NR::Point &iS, const NR::Point &isD,
 965                         const NR::Point &iE, const NR::Point &ieD)
 966 {
 967     NR::Point const ax = ieD - 2 * iE + 2 * iS + isD;
 968     NR::Point const bx = 3 * iE - ieD - 2 * isD - 3 * iS;
 969     NR::Point const cx = isD;
 970
 971     oPt = 3 * t * t * ax + 2 * t * bx + cx;
 972 }
 973
 974 // extract interesting info of a SVG arc description
 975 static void ArcAnglesAndCenter(NR::Point const &iS, NR::Point const &iE,
 976                                double rx, double ry, double angle,
 977                                bool large, bool wise,
 978                                double &sang, double &eang, NR::Point &dr);
 979
 980 void Path::ArcAngles(const NR::Point &iS, const NR::Point &iE,
 981                      double rx, double ry, double angle, bool large, bool wise, double &sang, double &eang)
 982 {
 983     NR::Point dr;
 984     ArcAnglesAndCenter(iS, iE, rx, ry, angle, large, wise, sang, eang, dr);
 985 }
 986
 987 /* N.B. If iS == iE then sang,eang,dr each become NaN.  Probably a bug. */
 988 static void ArcAnglesAndCenter(NR::Point const &iS, NR::Point const &iE,
 989                                double rx, double ry, double angle,
 990                                bool large, bool wise,
 991                                double &sang, double &eang, NR::Point &dr)
 992 {
 993     NR::Point se = iE - iS;
 994     NR::Point ca(cos(angle), sin(angle));
 995     NR::Point cse(dot(se, ca), cross(se, ca));
 996     cse[0] /= rx;
 997     cse[1] /= ry;
 998     double const lensq = dot(cse,cse);
 999     NR::Point csd = ( ( lensq < 4
1000                         ? sqrt( 1/lensq - .25 )
1001                         : 0.0 )
1002                       * cse.ccw() );
1003
1004     NR::Point ra = -csd - 0.5 * cse;
1005     if ( ra[0] <= -1 ) {
1006         sang = M_PI;
1007     } else if ( ra[0] >= 1 ) {
1008         sang = 0;
1009     } else {
1010         sang = acos(ra[0]);
1011         if ( ra[1] < 0 ) {
1012             sang = 2 * M_PI - sang;
1013         }
1014     }
1015
1016     ra = -csd + 0.5 * cse;
1017     if ( ra[0] <= -1 ) {
1018         eang = M_PI;
1019     } else if ( ra[0] >= 1 ) {
1020         eang = 0;
1021     } else {
1022         eang = acos(ra[0]);
1023         if ( ra[1] < 0 ) {
1024             eang = 2 * M_PI - eang;
1025         }
1026     }
1027
1028     csd[0] *= rx;
1029     csd[1] *= ry;
1030     ca[1] = -ca[1]; // because it's the inverse rotation
1031
1032     dr[0] = dot(csd, ca);
1033     dr[1] = cross(csd, ca);
1034
1035     ca[1] = -ca[1];
1036
1037     if ( wise ) {
1038
1039         if (large) {
1040             dr = -dr;
1041             double swap = eang;
1042             eang = sang;
1043             sang = swap;
1044             eang += M_PI;
1045             sang += M_PI;
1046             if ( eang >= 2*M_PI ) {
1047                 eang -= 2*M_PI;
1048             }
1049             if ( sang >= 2*M_PI ) {
1050                 sang -= 2*M_PI;
1051             }
1052         }
1053
1054     } else {
1055         if (!large) {
1056             dr = -dr;
1057             double swap = eang;
1058             eang = sang;
1059             sang = swap;
1060             eang += M_PI;
1061             sang += M_PI;
1062             if ( eang >= 2*M_PI ) {
1063                 eang -= 2 * M_PI;
1064             }
1065             if ( sang >= 2*M_PI ) {
1066                 sang -= 2 * M_PI;
1067             }
1068         }
1069     }
1070
1071     dr += 0.5 * (iS + iE);
1072 }
1073
1074
1075
1076 void Path::DoArc(NR::Point const &iS, NR::Point const &iE,
1077                  double const rx, double const ry, double const angle,
1078                  bool const large, bool const wise, double const /*tresh*/)
1079 {
1080     /* TODO: Check that our behaviour is standards-conformant if iS and iE are (much) further
1081        apart than the diameter.  Also check that we do the right thing for negative radius.
1082        (Same for the other DoArc functions in this file.) */
1083     if ( rx <= 0.0001 || ry <= 0.0001 ) {
1084         return;
1085         // We always add a lineto afterwards, so this is fine.
1086         // [on ajoute toujours un lineto apres, donc c bon]
1087     }
1088
1089     double sang;
1090     double eang;
1091     NR::Point dr_temp;
1092     ArcAnglesAndCenter(iS, iE, rx, ry, angle, large, wise, sang, eang, dr_temp);
1093     Geom::Point dr = dr_temp;
1094     /* TODO: This isn't as good numerically as treating iS and iE as primary.  E.g. consider
1095        the case of low curvature (i.e. very large radius). */
1096
1097     Geom::Scale const ar(rx, ry);
1098     Geom::Rotate cb( angle + sang );
1099     if (wise) {
1100
1101         double const incr = -0.1;
1102         if ( sang < eang ) {
1103             sang += 2*M_PI;
1104         }
1105         Geom::Rotate const omega(incr);
1106         for (double b = sang + incr ; b > eang ; b += incr) {
1107             cb = omega * cb;
1108             AddPoint( cb.vector() * ar + dr );
1109         }
1110
1111     } else {
1112
1113         double const incr = 0.1;
1114         if ( sang > eang ) {
1115             sang -= 2*M_PI;
1116         }
1117         Geom::Rotate const omega(incr);
1118         for (double b = sang + incr ; b < eang ; b += incr) {
1119             cb = omega * cb;
1120             AddPoint( cb.vector() * ar + dr);
1121         }
1122     }
1123 }
1124
1125
1126 void Path::RecCubicTo( NR::Point const &iS, NR::Point const &isD,
1127                        NR::Point const &iE, NR::Point const &ieD,
1128                        double tresh, int lev, double maxL)
1129 {
1130     NR::Point se = iE - iS;
1131     const double dC = NR::L2(se);
1132     if ( dC < 0.01 ) {
1133
1134         const double sC = dot(isD,isD);
1135         const double eC = dot(ieD,ieD);
1136         if ( sC < tresh && eC < tresh ) {
1137             return;
1138         }
1139
1140     } else {
1141         const double sC = fabs(cross(se, isD)) / dC;
1142         const double eC = fabs(cross(se, ieD)) / dC;
1143         if ( sC < tresh && eC < tresh ) {
1144             // presque tt droit -> attention si on nous demande de bien subdiviser les petits segments
1145             if ( maxL > 0 && dC > maxL ) {
1146                 if ( lev <= 0 ) {
1147                     return;
1148                 }
1149                 NR::Point m = 0.5 * (iS + iE) + 0.125 * (isD - ieD);
1150                 NR::Point md = 0.75 * (iE - iS) - 0.125 * (isD + ieD);
1151
1152                 NR::Point hisD = 0.5 * isD;
1153                 NR::Point hieD = 0.5 * ieD;
1154
1155                 RecCubicTo(iS, hisD, m, md, tresh, lev - 1, maxL);
1156                 AddPoint(m);
1157                 RecCubicTo(m, md, iE, hieD, tresh, lev - 1,maxL);
1158             }
1159             return;
1160         }
1161     }
1162
1163     if ( lev <= 0 ) {
1164         return;
1165     }
1166
1167     {
1168         NR::Point m = 0.5 * (iS + iE) + 0.125 * (isD - ieD);
1169         NR::Point md = 0.75 * (iE - iS) - 0.125 * (isD + ieD);
1170
1171         NR::Point hisD = 0.5 * isD;
1172         NR::Point hieD = 0.5 * ieD;
1173
1174         RecCubicTo(iS, hisD, m, md, tresh, lev - 1, maxL);
1175         AddPoint(m);
1176         RecCubicTo(m, md, iE, hieD, tresh, lev - 1,maxL);
1177     }
1178 }
1179
1180
1181
1182 void Path::RecBezierTo(const NR::Point &iP,
1183                        const NR::Point &iS,
1184                        const NR::Point &iE,
1185                        double tresh, int lev, double maxL)
1186 {
1187     if ( lev <= 0 ) {
1188         return;
1189     }
1190
1191     NR::Point ps = iS - iP;
1192     NR::Point pe = iE - iP;
1193     NR::Point se = iE - iS;
1194     double s = fabs(cross(pe, ps));
1195     if ( s < tresh ) {
1196         const double l = L2(se);
1197         if ( maxL > 0 && l > maxL ) {
1198             const NR::Point m = 0.25 * (iS + iE + 2 * iP);
1199             NR::Point md = 0.5 * (iS + iP);
1200             RecBezierTo(md, iS, m, tresh, lev - 1, maxL);
1201             AddPoint(m);
1202             md = 0.5 * (iP + iE);
1203             RecBezierTo(md, m, iE, tresh, lev - 1, maxL);
1204         }
1205         return;
1206     }
1207
1208     {
1209         const NR::Point m = 0.25 * (iS + iE + 2 * iP);
1210         NR::Point md = 0.5 * (iS + iP);
1211         RecBezierTo(md, iS, m, tresh, lev - 1, maxL);
1212         AddPoint(m);
1213         md = 0.5 * (iP + iE);
1214         RecBezierTo(md, m, iE, tresh, lev - 1, maxL);
1215     }
1216 }
1217
1218
1219 void Path::DoArc(NR::Point const &iS, NR::Point const &iE,
1220                  double const rx, double const ry, double const angle,
1221                  bool const large, bool const wise, double const /*tresh*/, int const piece)
1222 {
1223     /* TODO: Check that our behaviour is standards-conformant if iS and iE are (much) further
1224        apart than the diameter.  Also check that we do the right thing for negative radius.
1225        (Same for the other DoArc functions in this file.) */
1226     if ( rx <= 0.0001 || ry <= 0.0001 ) {
1227         return;
1228         // We always add a lineto afterwards, so this is fine.
1229         // [on ajoute toujours un lineto apres, donc c bon]
1230     }
1231
1232     double sang;
1233     double eang;
1234     NR::Point dr_temp;
1235     ArcAnglesAndCenter(iS, iE, rx, ry, angle, large, wise, sang, eang, dr_temp);
1236     Geom::Point dr = dr_temp;
1237     /* TODO: This isn't as good numerically as treating iS and iE as primary.  E.g. consider
1238        the case of low curvature (i.e. very large radius). */
1239
1240     Geom::Scale const ar(rx, ry);
1241     Geom::Rotate cb(angle + sang);
1242     if (wise) {
1243
1244         double const incr = -0.1;
1245         if ( sang < eang ) {
1246             sang += 2*M_PI;
1247         }
1248         Geom::Rotate const omega(incr);
1249         for (double b = sang + incr; b > eang; b += incr) {
1250             cb = omega * cb;
1251             AddPoint(cb.vector() * ar + dr, piece, (sang - b) / (sang - eang));
1252         }
1253
1254     } else {
1255
1256         double const incr = 0.1;
1257         if ( sang > eang ) {
1258             sang -= 2 * M_PI;
1259         }
1260         Geom::Rotate const omega(incr);
1261         for (double b = sang + incr ; b < eang ; b += incr) {
1262             cb = omega * cb;
1263             AddPoint(cb.vector() * ar + dr, piece, (b - sang) / (eang - sang));
1264         }
1265     }
1266 }
1267
1268 void Path::RecCubicTo(NR::Point const &iS, NR::Point const &isD,
1269                       NR::Point const &iE, NR::Point const &ieD,
1270                       double tresh, int lev, double st, double et, int piece)
1271 {
1272     const NR::Point se = iE - iS;
1273     const double dC = NR::L2(se);
1274     if ( dC < 0.01 ) {
1275         const double sC = dot(isD, isD);
1276         const double eC = dot(ieD, ieD);
1277         if ( sC < tresh && eC < tresh ) {
1278             return;
1279         }
1280     } else {
1281         const double sC = fabs(cross(se, isD)) / dC;
1282         const double eC = fabs(cross(se, ieD)) / dC;
1283         if ( sC < tresh && eC < tresh ) {
1284             return;
1285         }
1286     }
1287
1288     if ( lev <= 0 ) {
1289         return;
1290     }
1291
1292     NR::Point m = 0.5 * (iS + iE) + 0.125 * (isD - ieD);
1293     NR::Point md = 0.75 * (iE - iS) - 0.125 * (isD + ieD);
1294     double mt = (st + et) / 2;
1295
1296     NR::Point hisD = 0.5 * isD;
1297     NR::Point hieD = 0.5 * ieD;
1298
1299     RecCubicTo(iS, hisD, m, md, tresh, lev - 1, st, mt, piece);
1300     AddPoint(m, piece, mt);
1301     RecCubicTo(m, md, iE, hieD, tresh, lev - 1, mt, et, piece);
1302
1303 }
1304
1305
1306
1307 void Path::RecBezierTo(NR::Point const &iP,
1308                        NR::Point const &iS,
1309                        NR::Point const &iE,
1310                        double tresh, int lev, double st, double et, int piece)
1311 {
1312     if ( lev <= 0 ) {
1313         return;
1314     }
1315
1316     NR::Point ps = iS - iP;
1317     NR::Point pe = iE - iP;
1318     const double s = fabs(cross(pe, ps));
1319     if ( s < tresh ) {
1320         return;
1321     }
1322
1323     {
1324         const double mt = (st + et) / 2;
1325         const NR::Point m = 0.25 * (iS + iE + 2 * iP);
1326         RecBezierTo(0.5 * (iS + iP), iS, m, tresh, lev - 1, st, mt, piece);
1327         AddPoint(m, piece, mt);
1328         RecBezierTo(0.5 * (iP + iE), m, iE, tresh, lev - 1, mt, et, piece);
1329     }
1330 }
1331
1332
1333
1334 void Path::DoArc(NR::Point const &iS, NR::Point const &iE,
1335                  double const rx, double const ry, double const angle,
1336                  bool const large, bool const wise, double const /*tresh*/,
1337                  int const piece, offset_orig &/*orig*/)
1338 {
1339     // Will never arrive here, as offsets are made of cubics.
1340     // [on n'arrivera jamais ici, puisque les offsets sont fait de cubiques]
1341     /* TODO: Check that our behaviour is standards-conformant if iS and iE are (much) further
1342        apart than the diameter.  Also check that we do the right thing for negative radius.
1343        (Same for the other DoArc functions in this file.) */
1344     if ( rx <= 0.0001 || ry <= 0.0001 ) {
1345         return;
1346         // We always add a lineto afterwards, so this is fine.
1347         // [on ajoute toujours un lineto apres, donc c bon]
1348     }
1349
1350     double sang;
1351     double eang;
1352     NR::Point dr_temp;
1353     ArcAnglesAndCenter(iS, iE, rx, ry, angle, large, wise, sang, eang, dr_temp);
1354     Geom::Point dr = dr_temp;
1355     /* TODO: This isn't as good numerically as treating iS and iE as primary.  E.g. consider
1356        the case of low curvature (i.e. very large radius). */
1357
1358     Geom::Scale const ar(rx, ry);
1359     Geom::Rotate cb(angle + sang);
1360     if (wise) {
1361
1362         double const incr = -0.1;
1363         if ( sang < eang ) {
1364             sang += 2*M_PI;
1365         }
1366         Geom::Rotate const omega(incr);
1367         for (double b = sang + incr; b > eang ;b += incr) {
1368             cb = omega * cb;
1369             AddPoint(cb.vector() * ar + dr, piece, (sang - b) / (sang - eang));
1370         }
1371
1372     } else {
1373         double const incr = 0.1;
1374         if ( sang > eang ) {
1375             sang -= 2*M_PI;
1376         }
1377         Geom::Rotate const omega(incr);
1378         for (double b = sang + incr ; b < eang ; b += incr) {
1379             cb = omega * cb;
1380             AddPoint(cb.vector() * ar + dr, piece, (b - sang) / (eang - sang));
1381         }
1382     }
1383 }
1384
1385
1386 void Path::RecCubicTo(NR::Point const &iS, NR::Point const &isD,
1387                       NR::Point const &iE, NR::Point const &ieD,
1388                       double tresh, int lev, double st, double et,
1389                       int piece, offset_orig &orig)
1390 {
1391     const NR::Point se = iE - iS;
1392     const double dC = NR::L2(se);
1393     bool doneSub = false;
1394     if ( dC < 0.01 ) {
1395         const double sC = dot(isD, isD);
1396         const double eC = dot(ieD, ieD);
1397         if ( sC < tresh && eC < tresh ) {
1398             return;
1399         }
1400     } else {
1401         const double sC = fabs(cross(se, isD)) / dC;
1402         const double eC = fabs(cross(se, ieD)) / dC;
1403         if ( sC < tresh && eC < tresh ) {
1404             doneSub = true;
1405         }
1406     }
1407
1408     if ( lev <= 0 ) {
1409         doneSub = true;
1410     }
1411
1412     // test des inversions
1413     bool stInv = false;
1414     bool enInv = false;
1415     {
1416         NR::Point os_pos;
1417         NR::Point os_tgt;
1418         NR::Point oe_pos;
1419         NR::Point oe_tgt;
1420
1421         orig.orig->PointAndTangentAt(orig.piece, orig.tSt * (1 - st) + orig.tEn * st, os_pos, os_tgt);
1422         orig.orig->PointAndTangentAt(orig.piece, orig.tSt * (1 - et) + orig.tEn * et, oe_pos, oe_tgt);
1423
1424
1425         NR::Point n_tgt = isD;
1426         double si = dot(n_tgt, os_tgt);
1427         if ( si < 0 ) {
1428             stInv = true;
1429         }
1430         n_tgt = ieD;
1431         si = dot(n_tgt, oe_tgt);
1432         if ( si < 0 ) {
1433             enInv = true;
1434         }
1435         if ( stInv && enInv ) {
1436
1437             AddPoint(os_pos, -1, 0.0);
1438             AddPoint(iE, piece, et);
1439             AddPoint(iS, piece, st);
1440             AddPoint(oe_pos, -1, 0.0);
1441             return;
1442
1443         } else if ( ( stInv && !enInv ) || ( !stInv && enInv ) ) {
1444             return;
1445         }
1446
1447     }
1448
1449     if ( ( !stInv && !enInv && doneSub ) || lev <= 0 ) {
1450         return;
1451     }
1452
1453     {
1454         const NR::Point m = 0.5 * (iS+iE) + 0.125 * (isD - ieD);
1455         const NR::Point md = 0.75 * (iE - iS) - 0.125 * (isD + ieD);
1456         const double mt = (st + et) / 2;
1457         const NR::Point hisD = 0.5 * isD;
1458         const NR::Point hieD = 0.5 * ieD;
1459
1460         RecCubicTo(iS, hisD, m, md, tresh, lev - 1, st, mt, piece, orig);
1461         AddPoint(m, piece, mt);
1462         RecCubicTo(m, md, iE, hieD, tresh, lev - 1, mt, et, piece, orig);
1463     }
1464 }
1465
1466
1467
1468 void Path::RecBezierTo(NR::Point const &iP, NR::Point const &iS,NR::Point const &iE,
1469                        double tresh, int lev, double st, double et,
1470                        int piece, offset_orig& orig)
1471 {
1472     bool doneSub = false;
1473     if ( lev <= 0 ) {
1474         return;
1475     }
1476
1477     const NR::Point ps = iS - iP;
1478     const NR::Point pe = iE - iP;
1479     const double s = fabs(cross(pe, ps));
1480     if ( s < tresh ) {
1481         doneSub = true ;
1482     }
1483
1484     // test des inversions
1485     bool stInv = false;
1486     bool enInv = false;
1487     {
1488         NR::Point os_pos;
1489         NR::Point os_tgt;
1490         NR::Point oe_pos;
1491         NR::Point oe_tgt;
1492         NR::Point n_tgt;
1493         NR::Point n_pos;
1494
1495         double n_len;
1496         double n_rad;
1497         PathDescrIntermBezierTo mid(iP);
1498         PathDescrBezierTo fin(iE, 1);
1499
1500         TangentOnBezAt(0.0, iS, mid, fin, false, n_pos, n_tgt, n_len, n_rad);
1501         orig.orig->PointAndTangentAt(orig.piece, orig.tSt * (1 - st) + orig.tEn * st, os_pos, os_tgt);
1502         double si = dot(n_tgt, os_tgt);
1503         if ( si < 0 ) {
1504             stInv = true;
1505         }
1506
1507         TangentOnBezAt(1.0, iS, mid, fin, false, n_pos, n_tgt, n_len, n_rad);
1508         orig.orig->PointAndTangentAt(orig.piece, orig.tSt * (1 - et) + orig.tEn * et, oe_pos, oe_tgt);
1509         si = dot(n_tgt, oe_tgt);
1510         if ( si < 0 ) {
1511             enInv = true;
1512         }
1513
1514         if ( stInv && enInv ) {
1515             AddPoint(os_pos, -1, 0.0);
1516             AddPoint(iE, piece, et);
1517             AddPoint(iS, piece, st);
1518             AddPoint(oe_pos, -1, 0.0);
1519             return;
1520         }
1521     }
1522
1523     if ( !stInv && !enInv && doneSub ) {
1524         return;
1525     }
1526
1527     {
1528         double mt = (st + et) / 2;
1529         NR::Point m = 0.25 * (iS + iE + 2 * iP);
1530         NR::Point md = 0.5 * (iS + iP);
1531         RecBezierTo(md, iS, m, tresh, lev - 1, st, mt, piece, orig);
1532         AddPoint(m, piece, mt);
1533         md = 0.5 * (iP + iE);
1534         RecBezierTo(md, m, iE, tresh, lev - 1, mt, et, piece, orig);
1535     }
1536 }
1537
1538
1539 /*
1540  * put a polyline in a Shape instance, for further fun
1541  * pathID is the ID you want this Path instance to be associated with, for when you're going to recompose the polyline
1542  * in a path description ( you need to have prepared the back data for that, of course)
1543  */
1544
1545 void Path::Fill(Shape* dest, int pathID, bool justAdd, bool closeIfNeeded, bool invert)
1546 {
1547     if ( dest == NULL ) {
1548         return;
1549     }
1550
1551     if ( justAdd == false ) {
1552         dest->Reset(pts.size(), pts.size());
1553     }
1554
1555     if ( pts.size() <= 1 ) {
1556         return;
1557     }
1558
1559     int first = dest->numberOfPoints();
1560
1561     if ( back ) {
1562         dest->MakeBackData(true);
1563     }
1564
1565     if ( invert ) {
1566         if ( back ) {
1567             {
1568                 // invert && back && !weighted
1569                 for (int i = 0; i < int(pts.size()); i++) {
1570                     dest->AddPoint(pts[i].p);
1571                 }
1572                 int lastM = 0;
1573                 int curP = 1;
1574                 int pathEnd = 0;
1575                 bool closed = false;
1576                 int lEdge = -1;
1577
1578                 while ( curP < int(pts.size()) ) {
1579                     int sbp = curP;
1580                     int lm = lastM;
1581                     int prp = pathEnd;
1582
1583                     if ( pts[sbp].isMoveTo == polyline_moveto ) {
1584
1585                         if ( closeIfNeeded ) {
1586                             if ( closed && lEdge >= 0 ) {
1587                                 dest->DisconnectStart(lEdge);
1588                                 dest->ConnectStart(first + lastM, lEdge);
1589                             } else {
1590                                 lEdge = dest->AddEdge(first + lastM, first+pathEnd);
1591                                 if ( lEdge >= 0 ) {
1592                                     dest->ebData[lEdge].pathID = pathID;
1593                                     dest->ebData[lEdge].pieceID = pts[lm].piece;
1594                                     dest->ebData[lEdge].tSt = 1.0;
1595                                     dest->ebData[lEdge].tEn = 0.0;
1596                                 }
1597                             }
1598                         }
1599
1600                         lastM = curP;
1601                         pathEnd = curP;
1602                         closed = false;
1603                         lEdge = -1;
1604
1605                     } else {
1606
1607                         if ( Geom::LInfty(pts[sbp].p - pts[prp].p) >= 0.00001 ) {
1608                             lEdge = dest->AddEdge(first + curP, first + pathEnd);
1609                             if ( lEdge >= 0 ) {
1610                                 dest->ebData[lEdge].pathID = pathID;
1611                                 dest->ebData[lEdge].pieceID = pts[sbp].piece;
1612                                 if ( pts[sbp].piece == pts[prp].piece ) {
1613                                     dest->ebData[lEdge].tSt = pts[sbp].t;
1614                                     dest->ebData[lEdge].tEn = pts[prp].t;
1615                                 } else {
1616                                     dest->ebData[lEdge].tSt = pts[sbp].t;
1617                                     dest->ebData[lEdge].tEn = 0.0;
1618                                 }
1619                             }
1620                             pathEnd = curP;
1621                             if ( Geom::LInfty(pts[sbp].p - pts[lm].p) < 0.00001 ) {
1622                                 closed = true;
1623                             } else {
1624                                 closed = false;
1625                             }
1626                         }
1627                     }
1628
1629                     curP++;
1630                 }
1631
1632                 if ( closeIfNeeded ) {
1633                     if ( closed && lEdge >= 0 ) {
1634                         dest->DisconnectStart(lEdge);
1635                         dest->ConnectStart(first + lastM, lEdge);
1636                     } else {
1637                         int lm = lastM;
1638                         lEdge = dest->AddEdge(first + lastM, first + pathEnd);
1639                         if ( lEdge >= 0 ) {
1640                             dest->ebData[lEdge].pathID = pathID;
1641                             dest->ebData[lEdge].pieceID = pts[lm].piece;
1642                             dest->ebData[lEdge].tSt = 1.0;
1643                             dest->ebData[lEdge].tEn = 0.0;
1644                         }
1645                     }
1646                 }
1647             }
1648
1649         } else {
1650
1651             {
1652                 // invert && !back && !weighted
1653                 for (int i = 0; i < int(pts.size()); i++) {
1654                     dest->AddPoint(pts[i].p);
1655                 }
1656                 int lastM = 0;
1657                 int curP = 1;
1658                 int pathEnd = 0;
1659                 bool closed = false;
1660                 int lEdge = -1;
1661                 while ( curP < int(pts.size()) ) {
1662                     int sbp = curP;
1663                     int lm = lastM;
1664                     int prp = pathEnd;
1665                     if ( pts[sbp].isMoveTo == polyline_moveto ) {
1666                         if ( closeIfNeeded ) {
1667                             if ( closed && lEdge >= 0 ) {
1668                                 dest->DisconnectStart(lEdge);
1669                                 dest->ConnectStart(first + lastM, lEdge);
1670                             } else {
1671                                 dest->AddEdge(first + lastM, first + pathEnd);
1672                             }
1673                         }
1674                         lastM = curP;
1675                         pathEnd = curP;
1676                         closed = false;
1677                         lEdge = -1;
1678                     } else {
1679                         if ( Geom::LInfty(pts[sbp].p - pts[prp].p) >= 0.00001 ) {
1680                             lEdge = dest->AddEdge(first+curP, first+pathEnd);
1681                             pathEnd = curP;
1682                             if ( Geom::LInfty(pts[sbp].p - pts[lm].p) < 0.00001 ) {
1683                                 closed = true;
1684                             } else {
1685                                 closed = false;
1686                             }
1687                         }
1688                     }
1689                     curP++;
1690                 }
1691
1692                 if ( closeIfNeeded ) {
1693                     if ( closed && lEdge >= 0 ) {
1694                         dest->DisconnectStart(lEdge);
1695                         dest->ConnectStart(first + lastM, lEdge);
1696                     } else {
1697                         dest->AddEdge(first + lastM, first + pathEnd);
1698                     }
1699                 }
1700
1701             }
1702         }
1703
1704     } else {
1705
1706         if ( back ) {
1707             {
1708                 // !invert && back && !weighted
1709                 for (int i = 0; i < int(pts.size()); i++) {
1710                     dest->AddPoint(pts[i].p);
1711                 }
1712
1713                 int lastM = 0;
1714                 int curP = 1;
1715                 int pathEnd = 0;
1716                 bool closed = false;
1717                 int lEdge = -1;
1718                 while ( curP < int(pts.size()) ) {
1719                     int sbp = curP;
1720                     int lm = lastM;
1721                     int prp = pathEnd;
1722                     if ( pts[sbp].isMoveTo == polyline_moveto ) {
1723                         if ( closeIfNeeded ) {
1724                             if ( closed && lEdge >= 0 ) {
1725                                 dest->DisconnectEnd(lEdge);
1726                                 dest->ConnectEnd(first + lastM, lEdge);
1727                             } else {
1728                                 lEdge = dest->AddEdge(first + pathEnd, first+lastM);
1729                                 if ( lEdge >= 0 ) {
1730                                     dest->ebData[lEdge].pathID = pathID;
1731                                     dest->ebData[lEdge].pieceID = pts[lm].piece;
1732                                     dest->ebData[lEdge].tSt = 0.0;
1733                                     dest->ebData[lEdge].tEn = 1.0;
1734                                 }
1735                             }
1736                         }
1737                         lastM = curP;
1738                         pathEnd = curP;
1739                         closed = false;
1740                         lEdge = -1;
1741                     } else {
1742                         if ( Geom::LInfty(pts[sbp].p - pts[prp].p) >= 0.00001 ) {
1743                             lEdge = dest->AddEdge(first + pathEnd, first + curP);
1744                             dest->ebData[lEdge].pathID = pathID;
1745                             dest->ebData[lEdge].pieceID = pts[sbp].piece;
1746                             if ( pts[sbp].piece == pts[prp].piece ) {
1747                                 dest->ebData[lEdge].tSt = pts[prp].t;
1748                                 dest->ebData[lEdge].tEn = pts[sbp].t;
1749                             } else {
1750                                 dest->ebData[lEdge].tSt = 0.0;
1751                                 dest->ebData[lEdge].tEn = pts[sbp].t;
1752                             }
1753                             pathEnd = curP;
1754                             if ( Geom::LInfty(pts[sbp].p - pts[lm].p) < 0.00001 ) {
1755                                 closed = true;
1756                             } else {
1757                                 closed = false;
1758                             }
1759                         }
1760                     }
1761                     curP++;
1762                 }
1763
1764                 if ( closeIfNeeded ) {
1765                     if ( closed && lEdge >= 0 ) {
1766                         dest->DisconnectEnd(lEdge);
1767                         dest->ConnectEnd(first + lastM, lEdge);
1768                     } else {
1769                         int lm = lastM;
1770                         lEdge = dest->AddEdge(first + pathEnd, first + lastM);
1771                         if ( lEdge >= 0 ) {
1772                             dest->ebData[lEdge].pathID = pathID;
1773                             dest->ebData[lEdge].pieceID = pts[lm].piece;
1774                             dest->ebData[lEdge].tSt = 0.0;
1775                             dest->ebData[lEdge].tEn = 1.0;
1776                         }
1777                     }
1778                 }
1779             }
1780
1781         } else {
1782             {
1783                 // !invert && !back && !weighted
1784                 for (int i = 0;i < int(pts.size()); i++) {
1785                     dest->AddPoint(pts[i].p);
1786                 }
1787
1788                 int lastM = 0;
1789                 int curP = 1;
1790                 int pathEnd = 0;
1791                 bool closed = false;
1792                 int lEdge = -1;
1793                 while ( curP < int(pts.size()) ) {
1794                     int sbp = curP;
1795                     int lm = lastM;
1796                     int prp = pathEnd;
1797                     if ( pts[sbp].isMoveTo == polyline_moveto ) {
1798                         if ( closeIfNeeded ) {
1799                             if ( closed && lEdge >= 0 ) {
1800                                 dest->DisconnectEnd(lEdge);
1801                                 dest->ConnectEnd(first + lastM, lEdge);
1802                             } else {
1803                                 dest->AddEdge(first + pathEnd, first + lastM);
1804                             }
1805                         }
1806                         lastM = curP;
1807                         pathEnd = curP;
1808                         closed = false;
1809                         lEdge = -1;
1810                     } else {
1811                         if ( Geom::LInfty(pts[sbp].p - pts[prp].p) >= 0.00001 ) {
1812                             lEdge = dest->AddEdge(first+pathEnd, first+curP);
1813                             pathEnd = curP;
1814                             if ( Geom::LInfty(pts[sbp].p - pts[lm].p) < 0.00001 ) {
1815                                 closed = true;
1816                             } else {
1817                                 closed = false;
1818                             }
1819                         }
1820                     }
1821                     curP++;
1822                 }
1823
1824                 if ( closeIfNeeded ) {
1825                     if ( closed && lEdge >= 0 ) {
1826                         dest->DisconnectEnd(lEdge);
1827                         dest->ConnectEnd(first + lastM, lEdge);
1828                     } else {
1829                         dest->AddEdge(first + pathEnd, first + lastM);
1830                     }
1831                 }
1832
1833             }
1834         }
1835     }
1836 }
1837
1838 /*
1839   Local Variables:
1840   mode:c++
1841   c-file-style:"stroustrup"
1842   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1843   indent-tabs-mode:nil
1844   fill-column:99
1845   End:
1846 */
1847 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :