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