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 start_elimination = false;
 427     bool replace = false;
 428
 429     // le moveto
 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     // et le reste, 1 par 1
 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                 if (curent_point_relation > 0 && curent_point_relation == last_point_relation) {
 491                     if (!start_elimination) {
 492                         start_elimination = true;
 493                     } else {
 494                         replace = true;
 495                         descr_cmd[curP]->associated = ReplacePoint(nextX);
 496                     }
 497                 } else {
 498                     start_elimination = false;
 499                 }
 500
 501                 if (!replace) {
 502                     descr_cmd[curP]->associated = AddPoint(nextX, false);
 503                 }
 504
 505                 if ( descr_cmd[curP]->associated < 0 ) {
 506                     if ( curP == 0 ) {
 507                         descr_cmd[curP]->associated = 0;
 508                     } else {
 509                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 510                     }
 511                 }
 512                 last_point_relation = curent_point_relation;
 513                 curP++;
 514                 break;
 515             }
 516
 517             case descr_cubicto: {
 518                 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[curP]);
 519                 nextX = nData->p;
 520
 521                 curent_point_relation = POINT_RELATION_TO_AREA(nextX, area);
 522                 replace = false;
 523                 if (curent_point_relation > 0 && curent_point_relation == last_point_relation &&
 524                     curent_point_relation == POINT_RELATION_TO_AREA(curX + (nData->start), area) &&
 525                     curent_point_relation == POINT_RELATION_TO_AREA(nextX + (nData->end), area))
 526                 {
 527                     if (!start_elimination) {
 528                         start_elimination = true;
 529                     } else {
 530                         replace = true;
 531                         descr_cmd[curP]->associated = ReplacePoint(nextX);
 532                     }
 533                 } else {
 534                     start_elimination = false;
 535                 }
 536
 537                 if (!replace) {
 538                     RecCubicTo(curX, nData->start, nextX, nData->end, treshhold, 8);
 539                     descr_cmd[curP]->associated = AddPoint(nextX,false);
 540                 }
 541
 542                 if ( descr_cmd[curP]->associated < 0 ) {
 543                     if ( curP == 0 ) {
 544                         descr_cmd[curP]->associated = 0;
 545                     } else {
 546                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 547                     }
 548                 }
 549                 last_point_relation = curent_point_relation;
 550                 curP++;
 551                 break;
 552             }
 553
 554             case descr_arcto: {
 555                 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[curP]);
 556                 nextX = nData->p;
 557                 DoArc(curX, nextX, nData->rx, nData->ry, nData->angle, nData->large, nData->clockwise, treshhold);
 558                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 559                 if ( descr_cmd[curP]->associated < 0 ) {
 560                     if ( curP == 0 ) {
 561                         descr_cmd[curP]->associated = 0;
 562                     } else {
 563                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 564                     }
 565                 }
 566                 last_point_relation = 0;
 567
 568                 curP++;
 569                 break;
 570             }
 571
 572             case descr_bezierto: {
 573                 PathDescrBezierTo *nBData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[curP]);
 574                 int nbInterm = nBData->nb;
 575                 nextX = nBData->p;
 576                 int curBD = curP;
 577
 578                 curP++;
 579                 int ip = curP;
 580                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 581
 582                 if ( nbInterm == 1 ) {
 583                     NR::Point const midX = nData->p;
 584                     RecBezierTo(midX, curX, nextX, treshhold, 8);
 585                 } else if ( nbInterm > 1 ) {
 586                     NR::Point bx = curX;
 587                     NR::Point cx = curX;
 588                     NR::Point dx = curX;
 589
 590                     dx = nData->p;
 591                     ip++;
 592                     nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 593
 594                     cx = 2 * bx - dx;
 595
 596                     for (int k = 0; k < nbInterm - 1; k++) {
 597                         bx = cx;
 598                         cx = dx;
 599
 600                         dx = nData->p;
 601                         ip++;
 602                         nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 603
 604                         NR::Point stx = (bx + cx) / 2;
 605                         if ( k > 0 ) {
 606                             descr_cmd[ip - 2]->associated = AddPoint(stx, false);
 607                             if ( descr_cmd[ip - 2]->associated < 0 ) {
 608                                 if ( curP == 0 ) {
 609                                     descr_cmd[ip - 2]->associated = 0;
 610                                 } else {
 611                                     descr_cmd[ip - 2]->associated = descr_cmd[ip - 3]->associated;
 612                                 }
 613                             }
 614                         }
 615
 616                         {
 617                             NR::Point const mx = (cx + dx) / 2;
 618                             RecBezierTo(cx, stx, mx, treshhold, 8);
 619                         }
 620                     }
 621
 622                     {
 623                         bx = cx;
 624                         cx = dx;
 625
 626                         dx = nextX;
 627                         dx = 2 * dx - cx;
 628
 629                         NR::Point stx = (bx + cx) / 2;
 630
 631                         descr_cmd[ip - 1]->associated = AddPoint(stx, false);
 632                         if ( descr_cmd[ip - 1]->associated < 0 ) {
 633                             if ( curP == 0 ) {
 634                                 descr_cmd[ip - 1]->associated = 0;
 635                             } else {
 636                                 descr_cmd[ip - 1]->associated = descr_cmd[ip - 2]->associated;
 637                             }
 638                         }
 639
 640                         {
 641                             NR::Point mx = (cx + dx) / 2;
 642                             RecBezierTo(cx, stx, mx, treshhold, 8);
 643                         }
 644                     }
 645                 }
 646
 647                 descr_cmd[curBD]->associated = AddPoint(nextX, false);
 648                 if ( descr_cmd[curBD]->associated < 0 ) {
 649                     if ( curP == 0 ) {
 650                         descr_cmd[curBD]->associated = 0;
 651                     } else {
 652                         descr_cmd[curBD]->associated = descr_cmd[curBD - 1]->associated;
 653                     }
 654                 }
 655
 656                 last_point_relation = 0;
 657
 658                 curP += nbInterm;
 659                 break;
 660             }
 661         }
 662
 663         curX = nextX;
 664     }
 665 }
 666
 667
 668 void Path::ConvertEvenLines(double treshhold)
 669 {
 670     if ( descr_flags & descr_adding_bezier ) {
 671         CancelBezier();
 672     }
 673
 674     if ( descr_flags & descr_doing_subpath ) {
 675         CloseSubpath();
 676     }
 677
 678     SetBackData(false);
 679     ResetPoints();
 680     if ( descr_cmd.empty() ) {
 681         return;
 682     }
 683
 684     NR::Point curX;
 685     int curP = 1;
 686     int lastMoveTo = 0;
 687
 688     // le moveto
 689     {
 690         int const firstTyp = descr_cmd[0]->getType();
 691         if ( firstTyp == descr_moveto ) {
 692             curX = dynamic_cast<PathDescrMoveTo *>(descr_cmd[0])->p;
 693         } else {
 694             curP = 0;
 695             curX[0] = curX[1] = 0;
 696         }
 697         lastMoveTo = AddPoint(curX, true);
 698     }
 699     descr_cmd[0]->associated = lastMoveTo;
 700
 701     // et le reste, 1 par 1
 702     while ( curP < int(descr_cmd.size()) ) {
 703
 704         int const nType = descr_cmd[curP]->getType();
 705         NR::Point nextX;
 706
 707         switch (nType) {
 708             case descr_forced: {
 709                 descr_cmd[curP]->associated = AddForcedPoint(curX);
 710                 curP++;
 711                 break;
 712             }
 713
 714             case descr_moveto: {
 715                 PathDescrMoveTo* nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[curP]);
 716                 nextX = nData->p;
 717                 lastMoveTo = AddPoint(nextX,true);
 718                 descr_cmd[curP]->associated = lastMoveTo;
 719
 720                 // et on avance
 721                 curP++;
 722                 break;
 723             }
 724
 725             case descr_close: {
 726                 nextX = pts[lastMoveTo].p;
 727                 {
 728                     NR::Point nexcur;
 729                     nexcur = nextX - curX;
 730                     const double segL = NR::L2(nexcur);
 731                     if ( segL > treshhold ) {
 732                         for (double i = treshhold; i < segL; i += treshhold) {
 733                             NR::Point nX;
 734                             nX = (segL - i) * curX + i * nextX;
 735                             nX /= segL;
 736                             AddPoint(nX);
 737                         }
 738                     }
 739                 }
 740
 741                 descr_cmd[curP]->associated = AddPoint(nextX,false);
 742                 if ( descr_cmd[curP]->associated < 0 ) {
 743                     if ( curP == 0 ) {
 744                         descr_cmd[curP]->associated = 0;
 745                     } else {
 746                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 747                     }
 748                 }
 749
 750                 curP++;
 751                 break;
 752             }
 753
 754             case descr_lineto: {
 755                 PathDescrLineTo* nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[curP]);
 756                 nextX = nData->p;
 757                 NR::Point nexcur = nextX - curX;
 758                 const double segL = L2(nexcur);
 759                 if ( segL > treshhold ) {
 760                     for (double i = treshhold; i < segL; i += treshhold) {
 761                         NR::Point nX = ((segL - i) * curX + i * nextX) / segL;
 762                         AddPoint(nX);
 763                     }
 764                 }
 765
 766                 descr_cmd[curP]->associated = AddPoint(nextX,false);
 767                 if ( descr_cmd[curP]->associated < 0 ) {
 768                     if ( curP == 0 ) {
 769                         descr_cmd[curP]->associated = 0;
 770                     } else {
 771                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 772                     }
 773                 }
 774                 // et on avance
 775                 curP++;
 776                 break;
 777             }
 778
 779             case descr_cubicto: {
 780                 PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[curP]);
 781                 nextX = nData->p;
 782                 RecCubicTo(curX, nData->start, nextX, nData->end, treshhold, 8, 4 * treshhold);
 783                 descr_cmd[curP]->associated = AddPoint(nextX, false);
 784                 if ( descr_cmd[curP]->associated < 0 ) {
 785                     if ( curP == 0 ) {
 786                         descr_cmd[curP]->associated = 0;
 787                     } else {
 788                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 789                     }
 790                 }
 791                 // et on avance
 792                 curP++;
 793                 break;
 794             }
 795
 796             case descr_arcto: {
 797                 PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[curP]);
 798                 nextX = nData->p;
 799                 DoArc(curX, nextX, nData->rx, nData->ry, nData->angle, nData->large, nData->clockwise, treshhold);
 800                 descr_cmd[curP]->associated =AddPoint(nextX, false);
 801                 if ( descr_cmd[curP]->associated < 0 ) {
 802                     if ( curP == 0 ) {
 803                         descr_cmd[curP]->associated = 0;
 804                     } else {
 805                         descr_cmd[curP]->associated = descr_cmd[curP - 1]->associated;
 806                     }
 807                 }
 808
 809                 // et on avance
 810                 curP++;
 811                 break;
 812             }
 813
 814             case descr_bezierto: {
 815                 PathDescrBezierTo *nBData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[curP]);
 816                 int nbInterm = nBData->nb;
 817                 nextX = nBData->p;
 818                 int curBD = curP;
 819
 820                 curP++;
 821                 int ip = curP;
 822                 PathDescrIntermBezierTo *nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 823
 824                 if ( nbInterm == 1 ) {
 825                     NR::Point const midX = nData->p;
 826                     RecBezierTo(midX, curX, nextX, treshhold, 8, 4 * treshhold);
 827                 } else if ( nbInterm > 1 ) {
 828                     NR::Point bx = curX;
 829                     NR::Point cx = curX;
 830                     NR::Point dx = curX;
 831
 832                     dx = nData->p;
 833                     ip++;
 834                     nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 835
 836                     cx = 2 * bx - dx;
 837
 838                     for (int k = 0; k < nbInterm - 1; k++) {
 839                         bx = cx;
 840                         cx = dx;
 841                         dx = nData->p;
 842
 843                         ip++;
 844                         nData = dynamic_cast<PathDescrIntermBezierTo *>(descr_cmd[ip]);
 845
 846                         NR::Point stx = (bx+cx) / 2;
 847                         if ( k > 0 ) {
 848                             descr_cmd[ip - 2]->associated = AddPoint(stx, false);
 849                             if ( descr_cmd[ip - 2]->associated < 0 ) {
 850                                 if ( curP == 0 ) {
 851                                     descr_cmd[ip- 2]->associated = 0;
 852                                 } else {
 853                                     descr_cmd[ip - 2]->associated = descr_cmd[ip - 3]->associated;
 854                                 }
 855                             }
 856                         }
 857
 858                         {
 859                             NR::Point const mx = (cx + dx) / 2;
 860                             RecBezierTo(cx, stx, mx, treshhold, 8, 4 * treshhold);
 861                         }
 862                     }
 863
 864                     {
 865                         bx = cx;
 866                         cx = dx;
 867
 868                         dx = nextX;
 869                         dx = 2 * dx - cx;
 870
 871                         NR::Point const stx = (bx + cx) / 2;
 872
 873                         descr_cmd[ip - 1]->associated = AddPoint(stx, false);
 874                         if ( descr_cmd[ip - 1]->associated < 0 ) {
 875                             if ( curP == 0 ) {
 876                                 descr_cmd[ip - 1]->associated = 0;
 877                             } else {
 878                                 descr_cmd[ip - 1]->associated = descr_cmd[ip - 2]->associated;
 879                             }
 880                         }
 881
 882                         {
 883                             NR::Point const mx = (cx + dx) / 2;
 884                             RecBezierTo(cx, stx, mx, treshhold, 8, 4 * treshhold);
 885                         }
 886                     }
 887                 }
 888
 889                 descr_cmd[curBD]->associated = AddPoint(nextX, false);
 890                 if ( descr_cmd[curBD]->associated < 0 ) {
 891                     if ( curP == 0 ) {
 892                         descr_cmd[curBD]->associated = 0;
 893                     } else {
 894                         descr_cmd[curBD]->associated = descr_cmd[curBD - 1]->associated;
 895                     }
 896                 }
 897
 898                 // et on avance
 899                 curP += nbInterm;
 900                 break;
 901             }
 902         }
 903         if ( NR::LInfty(curX - nextX) > 0.00001 ) {
 904             curX = nextX;
 905         }
 906     }
 907 }
 908
 909 const NR::Point Path::PrevPoint(int i) const
 910 {
 911     /* TODO: I suspect this should assert `(unsigned) i < descr_nb'.  We can probably change
 912        the argument to unsigned.  descr_nb should probably be changed to unsigned too. */
 913     g_assert( i >= 0 );
 914     switch ( descr_cmd[i]->getType() ) {
 915         case descr_moveto: {
 916             PathDescrMoveTo *nData = dynamic_cast<PathDescrMoveTo *>(descr_cmd[i]);
 917             return nData->p;
 918         }
 919         case descr_lineto: {
 920             PathDescrLineTo *nData = dynamic_cast<PathDescrLineTo *>(descr_cmd[i]);
 921             return nData->p;
 922         }
 923         case descr_arcto: {
 924             PathDescrArcTo *nData = dynamic_cast<PathDescrArcTo *>(descr_cmd[i]);
 925             return nData->p;
 926         }
 927         case descr_cubicto: {
 928             PathDescrCubicTo *nData = dynamic_cast<PathDescrCubicTo *>(descr_cmd[i]);
 929             return nData->p;
 930         }
 931         case descr_bezierto: {
 932             PathDescrBezierTo *nData = dynamic_cast<PathDescrBezierTo *>(descr_cmd[i]);
 933             return nData->p;
 934         }
 935         case descr_interm_bezier:
 936         case descr_close:
 937         case descr_forced:
 938             return PrevPoint(i - 1);
 939         default:
 940             g_assert_not_reached();
 941             return NR::Point(0, 0);
 942     }
 943 }
 944
 945 // utilitaries: given a quadratic bezier curve (start point, control point, end point, ie that's a clamped curve),
 946 // and an abcissis on it, get the point with that abcissis.
 947 // 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"
 948 void Path::QuadraticPoint(double t, NR::Point &oPt,
 949                           const NR::Point &iS, const NR::Point &iM, const NR::Point &iE)
 950 {
 951     NR::Point const ax = iE - 2 * iM + iS;
 952     NR::Point const bx = 2 * iM - 2 * iS;
 953     NR::Point const cx = iS;
 954
 955     oPt = t * t * ax + t * bx + cx;
 956 }
 957 // idem for cubic bezier patch
 958 void Path::CubicTangent(double t, NR::Point &oPt, const NR::Point &iS, const NR::Point &isD,
 959                         const NR::Point &iE, const NR::Point &ieD)
 960 {
 961     NR::Point const ax = ieD - 2 * iE + 2 * iS + isD;
 962     NR::Point const bx = 3 * iE - ieD - 2 * isD - 3 * iS;
 963     NR::Point const cx = isD;
 964
 965     oPt = 3 * t * t * ax + 2 * t * bx + cx;
 966 }
 967
 968 // extract interesting info of a SVG arc description
 969 static void ArcAnglesAndCenter(NR::Point const &iS, NR::Point const &iE,
 970                                double rx, double ry, double angle,
 971                                bool large, bool wise,
 972                                double &sang, double &eang, NR::Point &dr);
 973
 974 void Path::ArcAngles(const NR::Point &iS, const NR::Point &iE,
 975                      double rx, double ry, double angle, bool large, bool wise, double &sang, double &eang)
 976 {
 977     NR::Point dr;
 978     ArcAnglesAndCenter(iS, iE, rx, ry, angle, large, wise, sang, eang, dr);
 979 }
 980
 981 /* N.B. If iS == iE then sang,eang,dr each become NaN.  Probably a bug. */
 982 static void ArcAnglesAndCenter(NR::Point const &iS, NR::Point const &iE,
 983                                double rx, double ry, double angle,
 984                                bool large, bool wise,
 985                                double &sang, double &eang, NR::Point &dr)
 986 {
 987     NR::Point se = iE - iS;
 988     NR::Point ca(cos(angle), sin(angle));
 989     NR::Point cse(dot(se, ca), cross(se, ca));
 990     cse[0] /= rx;
 991     cse[1] /= ry;
 992     double const lensq = dot(cse,cse);
 993     NR::Point csd = ( ( lensq < 4
 994                         ? sqrt( 1/lensq - .25 )
 995                         : 0.0 )
 996                       * cse.ccw() );
 997
 998     NR::Point ra = -csd - 0.5 * cse;
 999     if ( ra[0] <= -1 ) {
1000         sang = M_PI;
1001     } else if ( ra[0] >= 1 ) {
1002         sang = 0;
1003     } else {
1004         sang = acos(ra[0]);
1005         if ( ra[1] < 0 ) {
1006             sang = 2 * M_PI - sang;
1007         }
1008     }
1009
1010     ra = -csd + 0.5 * cse;
1011     if ( ra[0] <= -1 ) {
1012         eang = M_PI;
1013     } else if ( ra[0] >= 1 ) {
1014         eang = 0;
1015     } else {
1016         eang = acos(ra[0]);
1017         if ( ra[1] < 0 ) {
1018             eang = 2 * M_PI - eang;
1019         }
1020     }
1021
1022     csd[0] *= rx;
1023     csd[1] *= ry;
1024     ca[1] = -ca[1]; // because it's the inverse rotation
1025
1026     dr[0] = dot(csd, ca);
1027     dr[1] = cross(csd, ca);
1028
1029     ca[1] = -ca[1];
1030
1031     if ( wise ) {
1032
1033         if (large) {
1034             dr = -dr;
1035             double swap = eang;
1036             eang = sang;
1037             sang = swap;
1038             eang += M_PI;
1039             sang += M_PI;
1040             if ( eang >= 2*M_PI ) {
1041                 eang -= 2*M_PI;
1042             }
1043             if ( sang >= 2*M_PI ) {
1044                 sang -= 2*M_PI;
1045             }
1046         }
1047
1048     } else {
1049         if (!large) {
1050             dr = -dr;
1051             double swap = eang;
1052             eang = sang;
1053             sang = swap;
1054             eang += M_PI;
1055             sang += M_PI;
1056             if ( eang >= 2*M_PI ) {
1057                 eang -= 2 * M_PI;
1058             }
1059             if ( sang >= 2*M_PI ) {
1060                 sang -= 2 * M_PI;
1061             }
1062         }
1063     }
1064
1065     dr += 0.5 * (iS + iE);
1066 }
1067
1068
1069
1070 void Path::DoArc(NR::Point const &iS, NR::Point const &iE,
1071                  double const rx, double const ry, double const angle,
1072                  bool const large, bool const wise, double const /*tresh*/)
1073 {
1074     /* TODO: Check that our behaviour is standards-conformant if iS and iE are (much) further
1075        apart than the diameter.  Also check that we do the right thing for negative radius.
1076        (Same for the other DoArc functions in this file.) */
1077     if ( rx <= 0.0001 || ry <= 0.0001 ) {
1078         return;
1079         // We always add a lineto afterwards, so this is fine.
1080         // [on ajoute toujours un lineto apres, donc c bon]
1081     }
1082
1083     double sang;
1084     double eang;
1085     NR::Point dr;
1086     ArcAnglesAndCenter(iS, iE, rx, ry, angle, large, wise, sang, eang, dr);
1087     /* TODO: This isn't as good numerically as treating iS and iE as primary.  E.g. consider
1088        the case of low curvature (i.e. very large radius). */
1089
1090     NR::scale const ar(rx, ry);
1091     NR::rotate cb( angle + sang );
1092     if (wise) {
1093
1094         double const incr = -0.1;
1095         if ( sang < eang ) {
1096             sang += 2*M_PI;
1097         }
1098         NR::rotate const omega(incr);
1099         for (double b = sang + incr ; b > eang ; b += incr) {
1100             cb = omega * cb;
1101             AddPoint( cb.vec * ar + dr );
1102         }
1103
1104     } else {
1105
1106         double const incr = 0.1;
1107         if ( sang > eang ) {
1108             sang -= 2*M_PI;
1109         }
1110         NR::rotate const omega(incr);
1111         for (double b = sang + incr ; b < eang ; b += incr) {
1112             cb = omega * cb;
1113             AddPoint( cb.vec * ar + dr);
1114         }
1115     }
1116 }
1117
1118
1119 void Path::RecCubicTo( NR::Point const &iS, NR::Point const &isD,
1120                        NR::Point const &iE, NR::Point const &ieD,
1121                        double tresh, int lev, double maxL)
1122 {
1123     NR::Point se = iE - iS;
1124     const double dC = NR::L2(se);
1125     if ( dC < 0.01 ) {
1126
1127         const double sC = dot(isD,isD);
1128         const double eC = dot(ieD,ieD);
1129         if ( sC < tresh && eC < tresh ) {
1130             return;
1131         }
1132
1133     } else {
1134         const double sC = fabs(cross(se, isD)) / dC;
1135         const double eC = fabs(cross(se, ieD)) / dC;
1136         if ( sC < tresh && eC < tresh ) {
1137             // presque tt droit -> attention si on nous demande de bien subdiviser les petits segments
1138             if ( maxL > 0 && dC > maxL ) {
1139                 if ( lev <= 0 ) {
1140                     return;
1141                 }
1142                 NR::Point m = 0.5 * (iS + iE) + 0.125 * (isD - ieD);
1143                 NR::Point md = 0.75 * (iE - iS) - 0.125 * (isD + ieD);
1144
1145                 NR::Point hisD = 0.5 * isD;
1146                 NR::Point hieD = 0.5 * ieD;
1147
1148                 RecCubicTo(iS, hisD, m, md, tresh, lev - 1, maxL);
1149                 AddPoint(m);
1150                 RecCubicTo(m, md, iE, hieD, tresh, lev - 1,maxL);
1151             }
1152             return;
1153         }
1154     }
1155
1156     if ( lev <= 0 ) {
1157         return;
1158     }
1159
1160     {
1161         NR::Point m = 0.5 * (iS + iE) + 0.125 * (isD - ieD);
1162         NR::Point md = 0.75 * (iE - iS) - 0.125 * (isD + ieD);
1163
1164         NR::Point hisD = 0.5 * isD;
1165         NR::Point hieD = 0.5 * ieD;
1166
1167         RecCubicTo(iS, hisD, m, md, tresh, lev - 1, maxL);
1168         AddPoint(m);
1169         RecCubicTo(m, md, iE, hieD, tresh, lev - 1,maxL);
1170     }
1171 }
1172
1173
1174
1175 void Path::RecBezierTo(const NR::Point &iP,
1176                        const NR::Point &iS,
1177                        const NR::Point &iE,
1178                        double tresh, int lev, double maxL)
1179 {
1180     if ( lev <= 0 ) {
1181         return;
1182     }
1183
1184     NR::Point ps = iS - iP;
1185     NR::Point pe = iE - iP;
1186     NR::Point se = iE - iS;
1187     double s = fabs(cross(pe, ps));
1188     if ( s < tresh ) {
1189         const double l = L2(se);
1190         if ( maxL > 0 && l > maxL ) {
1191             const NR::Point m = 0.25 * (iS + iE + 2 * iP);
1192             NR::Point md = 0.5 * (iS + iP);
1193             RecBezierTo(md, iS, m, tresh, lev - 1, maxL);
1194             AddPoint(m);
1195             md = 0.5 * (iP + iE);
1196             RecBezierTo(md, m, iE, tresh, lev - 1, maxL);
1197         }
1198         return;
1199     }
1200
1201     {
1202         const NR::Point m = 0.25 * (iS + iE + 2 * iP);
1203         NR::Point md = 0.5 * (iS + iP);
1204         RecBezierTo(md, iS, m, tresh, lev - 1, maxL);
1205         AddPoint(m);
1206         md = 0.5 * (iP + iE);
1207         RecBezierTo(md, m, iE, tresh, lev - 1, maxL);
1208     }
1209 }
1210
1211
1212 void Path::DoArc(NR::Point const &iS, NR::Point const &iE,
1213                  double const rx, double const ry, double const angle,
1214                  bool const large, bool const wise, double const /*tresh*/, int const piece)
1215 {
1216     /* TODO: Check that our behaviour is standards-conformant if iS and iE are (much) further
1217        apart than the diameter.  Also check that we do the right thing for negative radius.
1218        (Same for the other DoArc functions in this file.) */
1219     if ( rx <= 0.0001 || ry <= 0.0001 ) {
1220         return;
1221         // We always add a lineto afterwards, so this is fine.
1222         // [on ajoute toujours un lineto apres, donc c bon]
1223     }
1224
1225     double sang;
1226     double eang;
1227     NR::Point dr;
1228     ArcAnglesAndCenter(iS, iE, rx, ry, angle, large, wise, sang, eang, dr);
1229     /* TODO: This isn't as good numerically as treating iS and iE as primary.  E.g. consider
1230        the case of low curvature (i.e. very large radius). */
1231
1232     NR::scale const ar(rx, ry);
1233     NR::rotate cb(angle + sang);
1234     if (wise) {
1235
1236         double const incr = -0.1;
1237         if ( sang < eang ) {
1238             sang += 2*M_PI;
1239         }
1240         NR::rotate const omega(incr);
1241         for (double b = sang + incr; b > eang; b += incr) {
1242             cb = omega * cb;
1243             AddPoint(cb.vec * ar + dr, piece, (sang - b) / (sang - eang));
1244         }
1245
1246     } else {
1247
1248         double const incr = 0.1;
1249         if ( sang > eang ) {
1250             sang -= 2 * M_PI;
1251         }
1252         NR::rotate const omega(incr);
1253         for (double b = sang + incr ; b < eang ; b += incr) {
1254             cb = omega * cb;
1255             AddPoint(cb.vec * ar + dr, piece, (b - sang) / (eang - sang));
1256         }
1257     }
1258 }
1259
1260 void Path::RecCubicTo(NR::Point const &iS, NR::Point const &isD,
1261                       NR::Point const &iE, NR::Point const &ieD,
1262                       double tresh, int lev, double st, double et, int piece)
1263 {
1264     const NR::Point se = iE - iS;
1265     const double dC = NR::L2(se);
1266     if ( dC < 0.01 ) {
1267         const double sC = dot(isD, isD);
1268         const double eC = dot(ieD, ieD);
1269         if ( sC < tresh && eC < tresh ) {
1270             return;
1271         }
1272     } else {
1273         const double sC = fabs(cross(se, isD)) / dC;
1274         const double eC = fabs(cross(se, ieD)) / dC;
1275         if ( sC < tresh && eC < tresh ) {
1276             return;
1277         }
1278     }
1279
1280     if ( lev <= 0 ) {
1281         return;
1282     }
1283
1284     NR::Point m = 0.5 * (iS + iE) + 0.125 * (isD - ieD);
1285     NR::Point md = 0.75 * (iE - iS) - 0.125 * (isD + ieD);
1286     double mt = (st + et) / 2;
1287
1288     NR::Point hisD = 0.5 * isD;
1289     NR::Point hieD = 0.5 * ieD;
1290
1291     RecCubicTo(iS, hisD, m, md, tresh, lev - 1, st, mt, piece);
1292     AddPoint(m, piece, mt);
1293     RecCubicTo(m, md, iE, hieD, tresh, lev - 1, mt, et, piece);
1294
1295 }
1296
1297
1298
1299 void Path::RecBezierTo(NR::Point const &iP,
1300                        NR::Point const &iS,
1301                        NR::Point const &iE,
1302                        double tresh, int lev, double st, double et, int piece)
1303 {
1304     if ( lev <= 0 ) {
1305         return;
1306     }
1307
1308     NR::Point ps = iS - iP;
1309     NR::Point pe = iE - iP;
1310     const double s = fabs(cross(pe, ps));
1311     if ( s < tresh ) {
1312         return;
1313     }
1314
1315     {
1316         const double mt = (st + et) / 2;
1317         const NR::Point m = 0.25 * (iS + iE + 2 * iP);
1318         RecBezierTo(0.5 * (iS + iP), iS, m, tresh, lev - 1, st, mt, piece);
1319         AddPoint(m, piece, mt);
1320         RecBezierTo(0.5 * (iP + iE), m, iE, tresh, lev - 1, mt, et, piece);
1321     }
1322 }
1323
1324
1325
1326 void Path::DoArc(NR::Point const &iS, NR::Point const &iE,
1327                  double const rx, double const ry, double const angle,
1328                  bool const large, bool const wise, double const /*tresh*/,
1329                  int const piece, offset_orig &/*orig*/)
1330 {
1331     // Will never arrive here, as offsets are made of cubics.
1332     // [on n'arrivera jamais ici, puisque les offsets sont fait de cubiques]
1333     /* TODO: Check that our behaviour is standards-conformant if iS and iE are (much) further
1334        apart than the diameter.  Also check that we do the right thing for negative radius.
1335        (Same for the other DoArc functions in this file.) */
1336     if ( rx <= 0.0001 || ry <= 0.0001 ) {
1337         return;
1338         // We always add a lineto afterwards, so this is fine.
1339         // [on ajoute toujours un lineto apres, donc c bon]
1340     }
1341
1342     double sang;
1343     double eang;
1344     NR::Point dr;
1345     ArcAnglesAndCenter(iS, iE, rx, ry, angle, large, wise, sang, eang, dr);
1346     /* TODO: This isn't as good numerically as treating iS and iE as primary.  E.g. consider
1347        the case of low curvature (i.e. very large radius). */
1348
1349     NR::scale const ar(rx, ry);
1350     NR::rotate cb(angle + sang);
1351     if (wise) {
1352
1353         double const incr = -0.1;
1354         if ( sang < eang ) {
1355             sang += 2*M_PI;
1356         }
1357         NR::rotate const omega(incr);
1358         for (double b = sang + incr; b > eang ;b += incr) {
1359             cb = omega * cb;
1360             AddPoint(cb.vec * ar + dr, piece, (sang - b) / (sang - eang));
1361         }
1362
1363     } else {
1364         double const incr = 0.1;
1365         if ( sang > eang ) {
1366             sang -= 2*M_PI;
1367         }
1368         NR::rotate const omega(incr);
1369         for (double b = sang + incr ; b < eang ; b += incr) {
1370             cb = omega * cb;
1371             AddPoint(cb.vec * ar + dr, piece, (b - sang) / (eang - sang));
1372         }
1373     }
1374 }
1375
1376
1377 void Path::RecCubicTo(NR::Point const &iS, NR::Point const &isD,
1378                       NR::Point const &iE, NR::Point const &ieD,
1379                       double tresh, int lev, double st, double et,
1380                       int piece, offset_orig &orig)
1381 {
1382     const NR::Point se = iE - iS;
1383     const double dC = NR::L2(se);
1384     bool doneSub = false;
1385     if ( dC < 0.01 ) {
1386         const double sC = dot(isD, isD);
1387         const double eC = dot(ieD, ieD);
1388         if ( sC < tresh && eC < tresh ) {
1389             return;
1390         }
1391     } else {
1392         const double sC = fabs(cross(se, isD)) / dC;
1393         const double eC = fabs(cross(se, ieD)) / dC;
1394         if ( sC < tresh && eC < tresh ) {
1395             doneSub = true;
1396         }
1397     }
1398
1399     if ( lev <= 0 ) {
1400         doneSub = true;
1401     }
1402
1403     // test des inversions
1404     bool stInv = false;
1405     bool enInv = false;
1406     {
1407         NR::Point os_pos;
1408         NR::Point os_tgt;
1409         NR::Point oe_pos;
1410         NR::Point oe_tgt;
1411
1412         orig.orig->PointAndTangentAt(orig.piece, orig.tSt * (1 - st) + orig.tEn * st, os_pos, os_tgt);
1413         orig.orig->PointAndTangentAt(orig.piece, orig.tSt * (1 - et) + orig.tEn * et, oe_pos, oe_tgt);
1414
1415
1416         NR::Point n_tgt = isD;
1417         double si = dot(n_tgt, os_tgt);
1418         if ( si < 0 ) {
1419             stInv = true;
1420         }
1421         n_tgt = ieD;
1422         si = dot(n_tgt, oe_tgt);
1423         if ( si < 0 ) {
1424             enInv = true;
1425         }
1426         if ( stInv && enInv ) {
1427
1428             AddPoint(os_pos, -1, 0.0);
1429             AddPoint(iE, piece, et);
1430             AddPoint(iS, piece, st);
1431             AddPoint(oe_pos, -1, 0.0);
1432             return;
1433
1434         } else if ( ( stInv && !enInv ) || ( !stInv && enInv ) ) {
1435             return;
1436         }
1437
1438     }
1439
1440     if ( ( !stInv && !enInv && doneSub ) || lev <= 0 ) {
1441         return;
1442     }
1443
1444     {
1445         const NR::Point m = 0.5 * (iS+iE) + 0.125 * (isD - ieD);
1446         const NR::Point md = 0.75 * (iE - iS) - 0.125 * (isD + ieD);
1447         const double mt = (st + et) / 2;
1448         const NR::Point hisD = 0.5 * isD;
1449         const NR::Point hieD = 0.5 * ieD;
1450
1451         RecCubicTo(iS, hisD, m, md, tresh, lev - 1, st, mt, piece, orig);
1452         AddPoint(m, piece, mt);
1453         RecCubicTo(m, md, iE, hieD, tresh, lev - 1, mt, et, piece, orig);
1454     }
1455 }
1456
1457
1458
1459 void Path::RecBezierTo(NR::Point const &iP, NR::Point const &iS,NR::Point const &iE,
1460                        double tresh, int lev, double st, double et,
1461                        int piece, offset_orig& orig)
1462 {
1463     bool doneSub = false;
1464     if ( lev <= 0 ) {
1465         return;
1466     }
1467
1468     const NR::Point ps = iS - iP;
1469     const NR::Point pe = iE - iP;
1470     const double s = fabs(cross(pe, ps));
1471     if ( s < tresh ) {
1472         doneSub = true ;
1473     }
1474
1475     // test des inversions
1476     bool stInv = false;
1477     bool enInv = false;
1478     {
1479         NR::Point os_pos;
1480         NR::Point os_tgt;
1481         NR::Point oe_pos;
1482         NR::Point oe_tgt;
1483         NR::Point n_tgt;
1484         NR::Point n_pos;
1485
1486         double n_len;
1487         double n_rad;
1488         PathDescrIntermBezierTo mid(iP);
1489         PathDescrBezierTo fin(iE, 1);
1490
1491         TangentOnBezAt(0.0, iS, mid, fin, false, n_pos, n_tgt, n_len, n_rad);
1492         orig.orig->PointAndTangentAt(orig.piece, orig.tSt * (1 - st) + orig.tEn * st, os_pos, os_tgt);
1493         double si = dot(n_tgt, os_tgt);
1494         if ( si < 0 ) {
1495             stInv = true;
1496         }
1497
1498         TangentOnBezAt(1.0, iS, mid, fin, false, n_pos, n_tgt, n_len, n_rad);
1499         orig.orig->PointAndTangentAt(orig.piece, orig.tSt * (1 - et) + orig.tEn * et, oe_pos, oe_tgt);
1500         si = dot(n_tgt, oe_tgt);
1501         if ( si < 0 ) {
1502             enInv = true;
1503         }
1504
1505         if ( stInv && enInv ) {
1506             AddPoint(os_pos, -1, 0.0);
1507             AddPoint(iE, piece, et);
1508             AddPoint(iS, piece, st);
1509             AddPoint(oe_pos, -1, 0.0);
1510             return;
1511         }
1512     }
1513
1514     if ( !stInv && !enInv && doneSub ) {
1515         return;
1516     }
1517
1518     {
1519         double mt = (st + et) / 2;
1520         NR::Point m = 0.25 * (iS + iE + 2 * iP);
1521         NR::Point md = 0.5 * (iS + iP);
1522         RecBezierTo(md, iS, m, tresh, lev - 1, st, mt, piece, orig);
1523         AddPoint(m, piece, mt);
1524         md = 0.5 * (iP + iE);
1525         RecBezierTo(md, m, iE, tresh, lev - 1, mt, et, piece, orig);
1526     }
1527 }
1528
1529
1530 /*
1531  * put a polyline in a Shape instance, for further fun
1532  * pathID is the ID you want this Path instance to be associated with, for when you're going to recompose the polyline
1533  * in a path description ( you need to have prepared the back data for that, of course)
1534  */
1535
1536 void Path::Fill(Shape* dest, int pathID, bool justAdd, bool closeIfNeeded, bool invert)
1537 {
1538     if ( dest == NULL ) {
1539         return;
1540     }
1541
1542     if ( justAdd == false ) {
1543         dest->Reset(pts.size(), pts.size());
1544     }
1545
1546     if ( pts.size() <= 1 ) {
1547         return;
1548     }
1549
1550     int first = dest->numberOfPoints();
1551
1552     if ( back ) {
1553         dest->MakeBackData(true);
1554     }
1555
1556     if ( invert ) {
1557         if ( back ) {
1558             {
1559                 // invert && back && !weighted
1560                 for (int i = 0; i < int(pts.size()); i++) {
1561                     dest->AddPoint(pts[i].p);
1562                 }
1563                 int lastM = 0;
1564                 int curP = 1;
1565                 int pathEnd = 0;
1566                 bool closed = false;
1567                 int lEdge = -1;
1568
1569                 while ( curP < int(pts.size()) ) {
1570                     int sbp = curP;
1571                     int lm = lastM;
1572                     int prp = pathEnd;
1573
1574                     if ( pts[sbp].isMoveTo == polyline_moveto ) {
1575
1576                         if ( closeIfNeeded ) {
1577                             if ( closed && lEdge >= 0 ) {
1578                                 dest->DisconnectStart(lEdge);
1579                                 dest->ConnectStart(first + lastM, lEdge);
1580                             } else {
1581                                 lEdge = dest->AddEdge(first + lastM, first+pathEnd);
1582                                 if ( lEdge >= 0 ) {
1583                                     dest->ebData[lEdge].pathID = pathID;
1584                                     dest->ebData[lEdge].pieceID = pts[lm].piece;
1585                                     dest->ebData[lEdge].tSt = 1.0;
1586                                     dest->ebData[lEdge].tEn = 0.0;
1587                                 }
1588                             }
1589                         }
1590
1591                         lastM = curP;
1592                         pathEnd = curP;
1593                         closed = false;
1594                         lEdge = -1;
1595
1596                     } else {
1597
1598                         if ( NR::LInfty(pts[sbp].p - pts[prp].p) >= 0.00001 ) {
1599                             lEdge = dest->AddEdge(first + curP, first + pathEnd);
1600                             if ( lEdge >= 0 ) {
1601                                 dest->ebData[lEdge].pathID = pathID;
1602                                 dest->ebData[lEdge].pieceID = pts[sbp].piece;
1603                                 if ( pts[sbp].piece == pts[prp].piece ) {
1604                                     dest->ebData[lEdge].tSt = pts[sbp].t;
1605                                     dest->ebData[lEdge].tEn = pts[prp].t;
1606                                 } else {
1607                                     dest->ebData[lEdge].tSt = pts[sbp].t;
1608                                     dest->ebData[lEdge].tEn = 0.0;
1609                                 }
1610                             }
1611                             pathEnd = curP;
1612                             if ( NR::LInfty(pts[sbp].p - pts[lm].p) < 0.00001 ) {
1613                                 closed = true;
1614                             } else {
1615                                 closed = false;
1616                             }
1617                         }
1618                     }
1619
1620                     curP++;
1621                 }
1622
1623                 if ( closeIfNeeded ) {
1624                     if ( closed && lEdge >= 0 ) {
1625                         dest->DisconnectStart(lEdge);
1626                         dest->ConnectStart(first + lastM, lEdge);
1627                     } else {
1628                         int lm = lastM;
1629                         lEdge = dest->AddEdge(first + lastM, first + pathEnd);
1630                         if ( lEdge >= 0 ) {
1631                             dest->ebData[lEdge].pathID = pathID;
1632                             dest->ebData[lEdge].pieceID = pts[lm].piece;
1633                             dest->ebData[lEdge].tSt = 1.0;
1634                             dest->ebData[lEdge].tEn = 0.0;
1635                         }
1636                     }
1637                 }
1638             }
1639
1640         } else {
1641
1642             {
1643                 // invert && !back && !weighted
1644                 for (int i = 0; i < int(pts.size()); i++) {
1645                     dest->AddPoint(pts[i].p);
1646                 }
1647                 int lastM = 0;
1648                 int curP = 1;
1649                 int pathEnd = 0;
1650                 bool closed = false;
1651                 int lEdge = -1;
1652                 while ( curP < int(pts.size()) ) {
1653                     int sbp = curP;
1654                     int lm = lastM;
1655                     int prp = pathEnd;
1656                     if ( pts[sbp].isMoveTo == polyline_moveto ) {
1657                         if ( closeIfNeeded ) {
1658                             if ( closed && lEdge >= 0 ) {
1659                                 dest->DisconnectStart(lEdge);
1660                                 dest->ConnectStart(first + lastM, lEdge);
1661                             } else {
1662                                 dest->AddEdge(first + lastM, first + pathEnd);
1663                             }
1664                         }
1665                         lastM = curP;
1666                         pathEnd = curP;
1667                         closed = false;
1668                         lEdge = -1;
1669                     } else {
1670                         if ( NR::LInfty(pts[sbp].p - pts[prp].p) >= 0.00001 ) {
1671                             lEdge = dest->AddEdge(first+curP, first+pathEnd);
1672                             pathEnd = curP;
1673                             if ( NR::LInfty(pts[sbp].p - pts[lm].p) < 0.00001 ) {
1674                                 closed = true;
1675                             } else {
1676                                 closed = false;
1677                             }
1678                         }
1679                     }
1680                     curP++;
1681                 }
1682
1683                 if ( closeIfNeeded ) {
1684                     if ( closed && lEdge >= 0 ) {
1685                         dest->DisconnectStart(lEdge);
1686                         dest->ConnectStart(first + lastM, lEdge);
1687                     } else {
1688                         dest->AddEdge(first + lastM, first + pathEnd);
1689                     }
1690                 }
1691
1692             }
1693         }
1694
1695     } else {
1696
1697         if ( back ) {
1698             {
1699                 // !invert && back && !weighted
1700                 for (int i = 0; i < int(pts.size()); i++) {
1701                     dest->AddPoint(pts[i].p);
1702                 }
1703
1704                 int lastM = 0;
1705                 int curP = 1;
1706                 int pathEnd = 0;
1707                 bool closed = false;
1708                 int lEdge = -1;
1709                 while ( curP < int(pts.size()) ) {
1710                     int sbp = curP;
1711                     int lm = lastM;
1712                     int prp = pathEnd;
1713                     if ( pts[sbp].isMoveTo == polyline_moveto ) {
1714                         if ( closeIfNeeded ) {
1715                             if ( closed && lEdge >= 0 ) {
1716                                 dest->DisconnectEnd(lEdge);
1717                                 dest->ConnectEnd(first + lastM, lEdge);
1718                             } else {
1719                                 lEdge = dest->AddEdge(first + pathEnd, first+lastM);
1720                                 if ( lEdge >= 0 ) {
1721                                     dest->ebData[lEdge].pathID = pathID;
1722                                     dest->ebData[lEdge].pieceID = pts[lm].piece;
1723                                     dest->ebData[lEdge].tSt = 0.0;
1724                                     dest->ebData[lEdge].tEn = 1.0;
1725                                 }
1726                             }
1727                         }
1728                         lastM = curP;
1729                         pathEnd = curP;
1730                         closed = false;
1731                         lEdge = -1;
1732                     } else {
1733                         if ( NR::LInfty(pts[sbp].p - pts[prp].p) >= 0.00001 ) {
1734                             lEdge = dest->AddEdge(first + pathEnd, first + curP);
1735                             dest->ebData[lEdge].pathID = pathID;
1736                             dest->ebData[lEdge].pieceID = pts[sbp].piece;
1737                             if ( pts[sbp].piece == pts[prp].piece ) {
1738                                 dest->ebData[lEdge].tSt = pts[prp].t;
1739                                 dest->ebData[lEdge].tEn = pts[sbp].t;
1740                             } else {
1741                                 dest->ebData[lEdge].tSt = 0.0;
1742                                 dest->ebData[lEdge].tEn = pts[sbp].t;
1743                             }
1744                             pathEnd = curP;
1745                             if ( NR::LInfty(pts[sbp].p - pts[lm].p) < 0.00001 ) {
1746                                 closed = true;
1747                             } else {
1748                                 closed = false;
1749                             }
1750                         }
1751                     }
1752                     curP++;
1753                 }
1754
1755                 if ( closeIfNeeded ) {
1756                     if ( closed && lEdge >= 0 ) {
1757                         dest->DisconnectEnd(lEdge);
1758                         dest->ConnectEnd(first + lastM, lEdge);
1759                     } else {
1760                         int lm = lastM;
1761                         lEdge = dest->AddEdge(first + pathEnd, first + lastM);
1762                         if ( lEdge >= 0 ) {
1763                             dest->ebData[lEdge].pathID = pathID;
1764                             dest->ebData[lEdge].pieceID = pts[lm].piece;
1765                             dest->ebData[lEdge].tSt = 0.0;
1766                             dest->ebData[lEdge].tEn = 1.0;
1767                         }
1768                     }
1769                 }
1770             }
1771
1772         } else {
1773             {
1774                 // !invert && !back && !weighted
1775                 for (int i = 0;i < int(pts.size()); i++) {
1776                     dest->AddPoint(pts[i].p);
1777                 }
1778
1779                 int lastM = 0;
1780                 int curP = 1;
1781                 int pathEnd = 0;
1782                 bool closed = false;
1783                 int lEdge = -1;
1784                 while ( curP < int(pts.size()) ) {
1785                     int sbp = curP;
1786                     int lm = lastM;
1787                     int prp = pathEnd;
1788                     if ( pts[sbp].isMoveTo == polyline_moveto ) {
1789                         if ( closeIfNeeded ) {
1790                             if ( closed && lEdge >= 0 ) {
1791                                 dest->DisconnectEnd(lEdge);
1792                                 dest->ConnectEnd(first + lastM, lEdge);
1793                             } else {
1794                                 dest->AddEdge(first + pathEnd, first + lastM);
1795                             }
1796                         }
1797                         lastM = curP;
1798                         pathEnd = curP;
1799                         closed = false;
1800                         lEdge = -1;
1801                     } else {
1802                         if ( NR::LInfty(pts[sbp].p - pts[prp].p) >= 0.00001 ) {
1803                             lEdge = dest->AddEdge(first+pathEnd, first+curP);
1804                             pathEnd = curP;
1805                             if ( NR::LInfty(pts[sbp].p - pts[lm].p) < 0.00001 ) {
1806                                 closed = true;
1807                             } else {
1808                                 closed = false;
1809                             }
1810                         }
1811                     }
1812                     curP++;
1813                 }
1814
1815                 if ( closeIfNeeded ) {
1816                     if ( closed && lEdge >= 0 ) {
1817                         dest->DisconnectEnd(lEdge);
1818                         dest->ConnectEnd(first + lastM, lEdge);
1819                     } else {
1820                         dest->AddEdge(first + pathEnd, first + lastM);
1821                     }
1822                 }
1823
1824             }
1825         }
1826     }
1827 }
1828
1829 /*
1830   Local Variables:
1831   mode:c++
1832   c-file-style:"stroustrup"
1833   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1834   indent-tabs-mode:nil
1835   fill-column:99
1836   End:
1837 */
1838 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :