src/livarot/ShapeRaster.cpp

   1 /*
   2  *  ShapeRaster.cpp
   3  *  nlivarot
   4  *
   5  *  Created by fred on Sat Jul 19 2003.
   6  *
   7  */
   8
   9 #include "Shape.h"
  10
  11 #include "livarot/float-line.h"
  12 #include "AlphaLigne.h"
  13 #include "BitLigne.h"
  14
  15 #include <libnr/nr-point-fns.h>
  16 #include "livarot/sweep-event-queue.h"
  17 #include "livarot/sweep-tree-list.h"
  18 #include "livarot/sweep-tree.h"
  19
  20 /*
  21  * polygon rasterization: the sweepline algorithm in all its glory
  22  * nothing unusual in this implementation, so nothing special to say
  23  * the *Quick*() functions are not useful. forget about them
  24  */
  25
  26 void Shape::BeginRaster(float &pos, int &curPt)
  27 {
  28     if ( numberOfPoints() <= 1 || numberOfEdges() <= 1 ) {
  29         curPt = 0;
  30         pos = 0;
  31         return;
  32     }
  33
  34     MakeRasterData(true);
  35     MakePointData(true);
  36     MakeEdgeData(true);
  37
  38     if (sTree == NULL) {
  39         sTree = new SweepTreeList(numberOfEdges());
  40     }
  41     if (sEvts == NULL) {
  42         sEvts = new SweepEventQueue(numberOfEdges());
  43     }
  44
  45     SortPoints();
  46
  47     curPt = 0;
  48     pos = getPoint(0).x[1] - 1.0;
  49
  50     for (int i = 0; i < numberOfPoints(); i++) {
  51         pData[i].pending = 0;
  52         pData[i].edgeOnLeft = -1;
  53         pData[i].nextLinkedPoint = -1;
  54         pData[i].rx[0] = /*Round(*/getPoint(i).x[0]/*)*/;
  55         pData[i].rx[1] = /*Round(*/getPoint(i).x[1]/*)*/;
  56     }
  57
  58     for (int i = 0;i < numberOfEdges(); i++) {
  59         swrData[i].misc = NULL;
  60         eData[i].rdx=pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
  61     }
  62 }
  63
  64
  65 void Shape::EndRaster()
  66 {
  67     delete sTree;
  68     sTree = NULL;
  69     delete sEvts;
  70     sEvts = NULL;
  71
  72     MakePointData(false);
  73     MakeEdgeData(false);
  74     MakeRasterData(false);
  75 }
  76
  77
  78 void Shape::BeginQuickRaster(float &pos, int &curPt)
  79 {
  80     if ( numberOfPoints() <= 1 || numberOfEdges() <= 1 ) {
  81         curPt = 0;
  82         pos = 0;
  83         return;
  84     }
  85
  86     MakeRasterData(true);
  87     MakeQuickRasterData(true);
  88     nbQRas = 0;
  89     firstQRas = lastQRas = -1;
  90     MakePointData(true);
  91     MakeEdgeData(true);
  92
  93     curPt = 0;
  94     pos = getPoint(0).x[1] - 1.0;
  95
  96     initialisePointData();
  97
  98     for (int i=0;i<numberOfEdges();i++) {
  99         swrData[i].misc = NULL;
 100         qrsData[i].ind = -1;
 101         eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
 102     }
 103
 104     SortPoints();
 105 //      SortPointsRounded();
 106 }
 107
 108
 109 void Shape::EndQuickRaster()
 110 {
 111     MakePointData(false);
 112     MakeEdgeData(false);
 113     MakeRasterData(false);
 114     MakeQuickRasterData(false);
 115 }
 116
 117
 118 // 2 versions of the Scan() series to move the scanline to a given position withou actually computing coverages
 119 void Shape::Scan(float &pos, int &curP, float to, float step)
 120 {
 121     if ( numberOfEdges() <= 1 ) {
 122         return;
 123     }
 124
 125     if ( pos == to ) {
 126         return;
 127     }
 128
 129     enum Direction {
 130         DOWNWARDS,
 131         UPWARDS
 132     };
 133
 134     Direction const d = (pos < to) ? DOWNWARDS : UPWARDS;
 135
 136     // points of the polygon are sorted top-down, so we take them in order, starting with the one at index curP,
 137     // until we reach the wanted position to.
 138     // don't forget to update curP and pos when we're done
 139     int curPt = curP;
 140     while ( ( d == DOWNWARDS && curPt < numberOfPoints() && getPoint(curPt).x[1]     <= to) ||
 141             ( d == UPWARDS   && curPt > 0                && getPoint(curPt - 1).x[1] >= to) )
 142     {
 143         int nPt = (d == DOWNWARDS) ? curPt++ : --curPt;
 144
 145         // treat a new point: remove and add edges incident to it
 146         int nbUp;
 147         int nbDn;
 148         int upNo;
 149         int dnNo;
 150         _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
 151
 152                                 if ( d == DOWNWARDS ) {
 153                                         if ( nbDn <= 0 ) {
 154             upNo = -1;
 155                                         }
 156                                         if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
 157             upNo = -1;
 158                                         }
 159                                 } else {
 160                                         if ( nbUp <= 0 ) {
 161             dnNo = -1;
 162                                         }
 163                                         if ( dnNo >= 0 && swrData[dnNo].misc == NULL ) {
 164             dnNo = -1;
 165                                         }
 166                                 }
 167
 168         if ( ( d == DOWNWARDS && nbUp > 0 ) || ( d == UPWARDS && nbDn > 0 ) ) {
 169             // first remove edges coming from above or below, as appropriate
 170             int cb = getPoint(nPt).incidentEdge[FIRST];
 171             while ( cb >= 0 && cb < numberOfEdges() ) {
 172
 173                 Shape::dg_arete const &e = getEdge(cb);
 174                 if ( (d == DOWNWARDS && nPt == std::max(e.st, e.en)) ||
 175                      (d == UPWARDS   && nPt == std::min(e.st, e.en)) )
 176                 {
 177                     if ( ( d == DOWNWARDS && cb != upNo ) || ( d == UPWARDS && cb != dnNo ) ) {
 178                         // we salvage the edge upNo to plug the edges we'll be addingat its place
 179                         // but the other edge don't have this chance
 180                         SweepTree *node = swrData[cb].misc;
 181                         if ( node ) {
 182                             swrData[cb].misc = NULL;
 183                             node->Remove(*sTree, *sEvts, true);
 184                         }
 185                     }
 186                 }
 187                 cb = NextAt(nPt, cb);
 188             }
 189                                 }
 190
 191         // if there is one edge going down and one edge coming from above, we don't Insert() the new edge,
 192         // but replace the upNo edge by the new one (faster)
 193         SweepTree* insertionNode = NULL;
 194         if ( dnNo >= 0 ) {
 195             if ( upNo >= 0 ) {
 196                                                         int    rmNo=(d == DOWNWARDS) ? upNo:dnNo;
 197                                                         int    neNo=(d == DOWNWARDS) ? dnNo:upNo;
 198                                                           SweepTree* node = swrData[rmNo].misc;
 199                 swrData[rmNo].misc = NULL;
 200
 201                 int const P = (d == DOWNWARDS) ? nPt : Other(nPt, neNo);
 202                 node->ConvertTo(this, neNo, 1, P);
 203
 204                 swrData[neNo].misc = node;
 205                 insertionNode = node;
 206                 CreateEdge(neNo, to, step);
 207             } else {
 208                                                         // always DOWNWARDS
 209                 SweepTree* node = sTree->add(this, dnNo, 1, nPt, this);
 210                 swrData[dnNo].misc = node;
 211                 node->Insert(*sTree, *sEvts, this, nPt, true);
 212                 //if (d == UPWARDS) {
 213                 //    node->startPoint = Other(nPt, dnNo);
 214                 //}
 215                 insertionNode = node;
 216                 CreateEdge(dnNo,to,step);
 217             }
 218         } else {
 219                                         if ( upNo >= 0 ) {
 220                                                 // always UPWARDS
 221                                                 SweepTree* node = sTree->add(this, upNo, 1, nPt, this);
 222                                                 swrData[upNo].misc = node;
 223                                                 node->Insert(*sTree, *sEvts, this, nPt, true);
 224                                                 //if (d == UPWARDS) {
 225                                                         node->startPoint = Other(nPt, upNo);
 226                                                 //}
 227                                                 insertionNode = node;
 228                                                 CreateEdge(upNo,to,step);
 229                                         }
 230                                 }
 231
 232         // add the remaining edges
 233         if ( ( d == DOWNWARDS && nbDn > 1 ) || ( d == UPWARDS && nbUp > 1 ) ) {
 234             // si nbDn == 1 , alors dnNo a deja ete traite
 235             int cb = getPoint(nPt).incidentEdge[FIRST];
 236             while ( cb >= 0 && cb < numberOfEdges() ) {
 237                 Shape::dg_arete const &e = getEdge(cb);
 238                 if ( nPt == std::min(e.st, e.en) ) {
 239                     if ( cb != dnNo && cb != upNo ) {
 240                         SweepTree *node = sTree->add(this, cb, 1, nPt, this);
 241                         swrData[cb].misc = node;
 242                         node->InsertAt(*sTree, *sEvts, this, insertionNode, nPt, true);
 243                         if (d == UPWARDS) {
 244                             node->startPoint = Other(nPt, cb);
 245                         }
 246                         CreateEdge(cb, to, step);
 247                     }
 248                 }
 249                 cb = NextAt(nPt,cb);
 250             }
 251         }
 252     }
 253
 254     curP = curPt;
 255     if ( curPt > 0 ) {
 256         pos = getPoint(curPt - 1).x[1];
 257     } else {
 258         pos = to;
 259     }
 260
 261     // the final touch: edges intersecting the sweepline must be update so that their intersection with
 262     // said sweepline is correct.
 263     pos = to;
 264     if ( sTree->racine ) {
 265         SweepTree* curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
 266         while ( curS ) {
 267             int cb = curS->bord;
 268             AvanceEdge(cb, to, true, step);
 269             curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
 270         }
 271     }
 272 }
 273
 274
 275
 276 void Shape::QuickScan(float &pos,int &curP, float to, bool /*doSort*/, float step)
 277 {
 278     if ( numberOfEdges() <= 1 ) {
 279         return;
 280     }
 281
 282     if ( pos == to ) {
 283         return;
 284     }
 285
 286     enum Direction {
 287         DOWNWARDS,
 288         UPWARDS
 289     };
 290
 291     Direction const d = (pos < to) ? DOWNWARDS : UPWARDS;
 292
 293     int curPt = curP;
 294     while ( (d == DOWNWARDS && curPt < numberOfPoints() && getPoint(curPt    ).x[1] <= to) ||
 295             (d == UPWARDS   && curPt > 0                && getPoint(curPt - 1).x[1] >= to) )
 296     {
 297         int nPt = (d == DOWNWARDS) ? curPt++ : --curPt;
 298
 299         int nbUp;
 300         int nbDn;
 301         int upNo;
 302         int dnNo;
 303         _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
 304
 305         if ( nbDn <= 0 ) {
 306             upNo = -1;
 307         }
 308         if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
 309             upNo = -1;
 310         }
 311
 312         if ( nbUp > 0 ) {
 313             int cb = getPoint(nPt).incidentEdge[FIRST];
 314             while ( cb >= 0 && cb < numberOfEdges() ) {
 315                 Shape::dg_arete const &e = getEdge(cb);
 316                 if ( (d == DOWNWARDS && nPt == std::max(e.st, e.en)) ||
 317                      (d == UPWARDS && nPt == std::min(e.st, e.en)) )
 318                 {
 319                     if ( cb != upNo ) {
 320                         QuickRasterSubEdge(cb);
 321                     }
 322                 }
 323                 cb = NextAt(nPt,cb);
 324             }
 325         }
 326
 327         // traitement du "upNo devient dnNo"
 328         int ins_guess = -1;
 329         if ( dnNo >= 0 ) {
 330             if ( upNo >= 0 ) {
 331                 ins_guess = QuickRasterChgEdge(upNo, dnNo, getPoint(nPt).x[0]);
 332             } else {
 333                 ins_guess = QuickRasterAddEdge(dnNo, getPoint(nPt).x[0], ins_guess);
 334             }
 335             CreateEdge(dnNo, to, step);
 336         }
 337
 338         if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
 339             int cb = getPoint(nPt).incidentEdge[FIRST];
 340             while ( cb >= 0 && cb < numberOfEdges() ) {
 341                 Shape::dg_arete const &e = getEdge(cb);
 342                 if ( (d == DOWNWARDS && nPt == std::min(e.st, e.en)) ||
 343                      (d == UPWARDS && nPt == std::max(e.st, e.en)) )
 344                 {
 345                     if ( cb != dnNo ) {
 346                         ins_guess = QuickRasterAddEdge(cb, getPoint(nPt).x[0], ins_guess);
 347                         CreateEdge(cb, to, step);
 348                     }
 349                 }
 350                 cb = NextAt(nPt,cb);
 351             }
 352         }
 353
 354
 355         curP = curPt;
 356         if ( curPt > 0 ) {
 357             pos = getPoint(curPt-1).x[1];
 358         } else {
 359             pos = to;
 360         }
 361     }
 362
 363     pos = to;
 364
 365     for (int i=0; i < nbQRas; i++) {
 366         int cb = qrsData[i].bord;
 367         AvanceEdge(cb, to, true, step);
 368         qrsData[i].x=swrData[cb].curX;
 369     }
 370
 371     QuickRasterSort();
 372 }
 373
 374
 375
 376 int Shape::QuickRasterChgEdge(int oBord, int nBord, double x)
 377 {
 378     if ( oBord == nBord ) {
 379         return -1;
 380     }
 381
 382     int no = qrsData[oBord].ind;
 383     if ( no >= 0 ) {
 384         qrsData[no].bord = nBord;
 385         qrsData[no].x = x;
 386         qrsData[oBord].ind = -1;
 387         qrsData[nBord].ind = no;
 388     }
 389
 390     return no;
 391 }
 392
 393
 394
 395 int Shape::QuickRasterAddEdge(int bord, double x, int guess)
 396 {
 397     int no = nbQRas++;
 398     qrsData[no].bord = bord;
 399     qrsData[no].x = x;
 400     qrsData[bord].ind = no;
 401     qrsData[no].prev = -1;
 402     qrsData[no].next = -1;
 403
 404     if ( no < 0 || no >= nbQRas ) {
 405         return -1;
 406     }
 407
 408     if ( firstQRas < 0 ) {
 409         firstQRas = lastQRas = no;
 410         qrsData[no].prev = -1;
 411         qrsData[no].next = -1;
 412         return no;
 413     }
 414
 415     if ( guess < 0 || guess >= nbQRas ) {
 416
 417         int c = firstQRas;
 418         while ( c >= 0 && c < nbQRas && CmpQRs(qrsData[c],qrsData[no]) < 0 ) {
 419             c = qrsData[c].next;
 420         }
 421
 422         if ( c < 0 || c >= nbQRas ) {
 423             qrsData[no].prev = lastQRas;
 424             qrsData[lastQRas].next = no;
 425             lastQRas = no;
 426         } else {
 427             qrsData[no].prev = qrsData[c].prev;
 428             if ( qrsData[no].prev >= 0 ) {
 429                 qrsData[qrsData[no].prev].next=no;
 430             } else {
 431                 firstQRas = no;
 432             }
 433
 434             qrsData[no].next = c;
 435             qrsData[c].prev = no;
 436         }
 437
 438     } else {
 439         int c = guess;
 440         int stTst = CmpQRs(qrsData[c],qrsData[no]);
 441         if ( stTst == 0 ) {
 442
 443             qrsData[no].prev = qrsData[c].prev;
 444             if ( qrsData[no].prev >= 0 ) {
 445                 qrsData[qrsData[no].prev].next = no;
 446             } else {
 447                 firstQRas = no;
 448             }
 449
 450             qrsData[no].next = c;
 451             qrsData[c].prev = no;
 452
 453         } else if ( stTst > 0 ) {
 454
 455             while ( c >= 0 && c < nbQRas && CmpQRs(qrsData[c],qrsData[no]) > 0 ) {
 456                 c = qrsData[c].prev;
 457             }
 458
 459             if ( c < 0 || c >= nbQRas ) {
 460                 qrsData[no].next = firstQRas;
 461                 qrsData[firstQRas].prev = no; // firstQRas != -1
 462                 firstQRas = no;
 463             } else {
 464                 qrsData[no].next = qrsData[c].next;
 465                 if ( qrsData[no].next >= 0 ) {
 466                     qrsData[qrsData[no].next].prev = no;
 467                 } else {
 468                     lastQRas = no;
 469                 }
 470                 qrsData[no].prev = c;
 471                 qrsData[c].next = no;
 472             }
 473
 474         } else {
 475
 476             while ( c >= 0 && c < nbQRas && CmpQRs(qrsData[c],qrsData[no]) < 0 ) {
 477                 c = qrsData[c].next;
 478             }
 479
 480             if ( c < 0 || c >= nbQRas ) {
 481                 qrsData[no].prev = lastQRas;
 482                 qrsData[lastQRas].next = no;
 483                 lastQRas = no;
 484             } else {
 485                 qrsData[no].prev = qrsData[c].prev;
 486                 if ( qrsData[no].prev >= 0 ) {
 487                     qrsData[qrsData[no].prev].next = no;
 488                 } else {
 489                     firstQRas = no;
 490                 }
 491
 492                 qrsData[no].next = c;
 493                 qrsData[c].prev = no;
 494             }
 495         }
 496     }
 497
 498     return no;
 499 }
 500
 501
 502
 503 void Shape::QuickRasterSubEdge(int bord)
 504 {
 505     int no = qrsData[bord].ind;
 506     if ( no < 0 || no >= nbQRas ) {
 507         return; // euuhHHH
 508     }
 509
 510     if ( qrsData[no].prev >= 0 ) {
 511         qrsData[qrsData[no].prev].next=qrsData[no].next;
 512     }
 513
 514     if ( qrsData[no].next >= 0 ) {
 515         qrsData[qrsData[no].next].prev = qrsData[no].prev;
 516     }
 517
 518     if ( no == firstQRas ) {
 519         firstQRas = qrsData[no].next;
 520     }
 521
 522     if ( no == lastQRas ) {
 523         lastQRas = qrsData[no].prev;
 524     }
 525
 526     qrsData[no].prev = qrsData[no].next = -1;
 527
 528     int savInd = qrsData[no].ind;
 529     qrsData[no] = qrsData[--nbQRas];
 530     qrsData[no].ind = savInd;
 531     qrsData[qrsData[no].bord].ind = no;
 532     qrsData[bord].ind = -1;
 533
 534     if ( nbQRas > 0 ) {
 535         if ( firstQRas == nbQRas ) {
 536             firstQRas = no;
 537         }
 538         if ( lastQRas == nbQRas ) {
 539             lastQRas = no;
 540         }
 541         if ( qrsData[no].prev >= 0 ) {
 542             qrsData[qrsData[no].prev].next = no;
 543         }
 544         if ( qrsData[no].next >= 0 ) {
 545             qrsData[qrsData[no].next].prev = no;
 546         }
 547     }
 548 }
 549
 550
 551
 552 void Shape::QuickRasterSwapEdge(int a, int b)
 553 {
 554     if ( a == b ) {
 555         return;
 556     }
 557
 558     int na = qrsData[a].ind;
 559     int nb = qrsData[b].ind;
 560     if ( na < 0 || na >= nbQRas || nb < 0 || nb >= nbQRas ) {
 561         return; // errrm
 562     }
 563
 564     qrsData[na].bord = b;
 565     qrsData[nb].bord = a;
 566     qrsData[a].ind = nb;
 567     qrsData[b].ind = na;
 568
 569     double swd = qrsData[na].x;
 570     qrsData[na].x = qrsData[nb].x;
 571     qrsData[nb].x = swd;
 572 }
 573
 574
 575 void Shape::QuickRasterSort()
 576 {
 577     if ( nbQRas <= 1 ) {
 578         return;
 579     }
 580
 581     int cb = qrsData[firstQRas].bord;
 582
 583     while ( cb >= 0 ) {
 584         int bI = qrsData[cb].ind;
 585         int nI = qrsData[bI].next;
 586
 587         if ( nI < 0 ) {
 588             break;
 589         }
 590
 591         int ncb = qrsData[nI].bord;
 592         if ( CmpQRs(qrsData[nI], qrsData[bI]) < 0 ) {
 593             QuickRasterSwapEdge(cb, ncb);
 594             int pI = qrsData[bI].prev; // ca reste bI, puisqu'on a juste echange les contenus
 595             if ( pI < 0 ) {
 596                 cb = ncb; // en fait inutile; mais bon...
 597             } else {
 598                 int pcb = qrsData[pI].bord;
 599                 cb = pcb;
 600             }
 601         } else {
 602             cb = ncb;
 603         }
 604     }
 605 }
 606
 607
 608 // direct scan to a given position. goes through the edge list to keep only the ones intersecting the target sweepline
 609 // good for initial setup of scanline algo, bad for incremental changes
 610 void Shape::DirectScan(float &pos, int &curP, float to, float step)
 611 {
 612     if ( numberOfEdges() <= 1 ) {
 613         return;
 614     }
 615
 616     if ( pos == to ) {
 617         return;
 618     }
 619
 620     if ( pos < to ) {
 621         // we're moving downwards
 622         // points of the polygon are sorted top-down, so we take them in order, starting with the one at index curP,
 623         // until we reach the wanted position to.
 624         // don't forget to update curP and pos when we're done
 625         int curPt = curP;
 626         while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
 627             curPt++;
 628         }
 629
 630         for (int i=0;i<numberOfEdges();i++) {
 631             if ( swrData[i].misc ) {
 632                 SweepTree* node = swrData[i].misc;
 633                 swrData[i].misc = NULL;
 634                 node->Remove(*sTree, *sEvts, true);
 635             }
 636         }
 637
 638         for (int i=0; i < numberOfEdges(); i++) {
 639             Shape::dg_arete const &e = getEdge(i);
 640             if ( ( e.st < curPt && e.en >= curPt ) || ( e.en < curPt && e.st >= curPt )) {
 641                 // crosses sweepline
 642                 int nPt = (e.st < curPt) ? e.st : e.en;
 643                 SweepTree* node = sTree->add(this, i, 1, nPt, this);
 644                 swrData[i].misc = node;
 645                 node->Insert(*sTree, *sEvts, this, nPt, true);
 646                 CreateEdge(i, to, step);
 647             }
 648         }
 649
 650         curP = curPt;
 651         if ( curPt > 0 ) {
 652             pos = getPoint(curPt - 1).x[1];
 653         } else {
 654             pos = to;
 655         }
 656
 657     } else {
 658
 659         // same thing, but going up. so the sweepSens is inverted for the Find() function
 660         int curPt=curP;
 661         while ( curPt > 0 && getPoint(curPt-1).x[1] >= to ) {
 662             curPt--;
 663         }
 664
 665         for (int i = 0; i < numberOfEdges(); i++) {
 666             if ( swrData[i].misc ) {
 667                 SweepTree* node = swrData[i].misc;
 668                 swrData[i].misc = NULL;
 669                 node->Remove(*sTree, *sEvts, true);
 670             }
 671         }
 672
 673         for (int i=0;i<numberOfEdges();i++) {
 674             Shape::dg_arete const &e = getEdge(i);
 675             if ( ( e.st > curPt - 1 && e.en <= curPt - 1 ) || ( e.en > curPt - 1 && e.st <= curPt - 1 )) {
 676                 // crosses sweepline
 677                 int nPt = (e.st > curPt) ? e.st : e.en;
 678                 SweepTree* node = sTree->add(this, i, 1, nPt, this);
 679                 swrData[i].misc = node;
 680                 node->Insert(*sTree, *sEvts, this, nPt, false);
 681                 node->startPoint = Other(nPt, i);
 682                 CreateEdge(i, to, step);
 683             }
 684         }
 685
 686         curP = curPt;
 687         if ( curPt > 0 ) {
 688             pos = getPoint(curPt - 1).x[1];
 689         } else {
 690             pos = to;
 691         }
 692     }
 693
 694     // the final touch: edges intersecting the sweepline must be update so that their intersection with
 695     // said sweepline is correct.
 696     pos = to;
 697     if ( sTree->racine ) {
 698         SweepTree* curS=static_cast<SweepTree*>(sTree->racine->Leftmost());
 699         while ( curS ) {
 700             int cb = curS->bord;
 701             AvanceEdge(cb, to, true, step);
 702             curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
 703         }
 704     }
 705 }
 706
 707
 708
 709 void Shape::DirectQuickScan(float &pos, int &curP, float to, bool /*doSort*/, float step)
 710 {
 711     if ( numberOfEdges() <= 1 ) {
 712         return;
 713     }
 714
 715     if ( pos == to ) {
 716         return;
 717     }
 718
 719     if ( pos < to ) {
 720         // we're moving downwards
 721         // points of the polygon are sorted top-down, so we take them in order, starting with the one at index curP,
 722         // until we reach the wanted position to.
 723         // don't forget to update curP and pos when we're done
 724         int curPt=curP;
 725         while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
 726             curPt++;
 727         }
 728
 729         for (int i = 0; i < numberOfEdges(); i++) {
 730             if ( qrsData[i].ind < 0 ) {
 731                 QuickRasterSubEdge(i);
 732             }
 733         }
 734
 735         for (int i = 0; i < numberOfEdges(); i++) {
 736             Shape::dg_arete const &e = getEdge(i);
 737             if ( ( e.st < curPt && e.en >= curPt ) || ( e.en < curPt && e.st >= curPt )) {
 738                 // crosses sweepline
 739                 int nPt = (e.st < e.en) ? e.st : e.en;
 740                 QuickRasterAddEdge(i, getPoint(nPt).x[0], -1);
 741                 CreateEdge(i, to, step);
 742             }
 743         }
 744
 745         curP = curPt;
 746         if ( curPt > 0 ) {
 747             pos=getPoint(curPt-1).x[1];
 748         } else {
 749             pos = to;
 750         }
 751
 752     } else {
 753
 754         // same thing, but going up. so the sweepSens is inverted for the Find() function
 755         int curPt=curP;
 756         while ( curPt > 0 && getPoint(curPt-1).x[1] >= to ) {
 757             curPt--;
 758         }
 759
 760         for (int i = 0; i < numberOfEdges(); i++) {
 761             if ( qrsData[i].ind < 0 ) {
 762                 QuickRasterSubEdge(i);
 763             }
 764         }
 765
 766         for (int i=0;i<numberOfEdges();i++) {
 767             Shape::dg_arete const &e = getEdge(i);
 768             if ( ( e.st < curPt-1 && e.en >= curPt-1 ) || ( e.en < curPt-1 && e.st >= curPt-1 )) {
 769                 // crosses sweepline
 770                 int nPt = (e.st > e.en) ? e.st : e.en;
 771                 QuickRasterAddEdge(i, getPoint(nPt).x[0], -1);
 772                 CreateEdge(i, to, step);
 773             }
 774         }
 775
 776         curP = curPt;
 777         if ( curPt > 0 ) {
 778             pos = getPoint(curPt-1).x[1];
 779         } else {
 780             pos = to;
 781         }
 782
 783     }
 784
 785     pos = to;
 786     for (int i = 0; i < nbQRas; i++) {
 787         int cb = qrsData[i].bord;
 788         AvanceEdge(cb, to, true, step);
 789         qrsData[i].x = swrData[cb].curX;
 790     }
 791
 792     QuickRasterSort();
 793 }
 794
 795
 796 // scan and compute coverage, FloatLigne version coverage of the line is bult in 2 parts: first a
 797 // set of rectangles of height the height of the line (here: "step") one rectangle for each portion
 798 // of the sweepline that is in the polygon at the beginning of the scan.  then a set ot trapezoids
 799 // are added or removed to these rectangles, one trapezoid for each edge destroyed or edge crossing
 800 // the entire line. think of it as a refinement of the coverage by rectangles
 801
 802 void Shape::Scan(float &pos, int &curP, float to, FloatLigne *line, bool exact, float step)
 803 {
 804     if ( numberOfEdges() <= 1 ) {
 805         return;
 806     }
 807
 808     if ( pos >= to ) {
 809         return;
 810     }
 811
 812     // first step: the rectangles since we read the sweepline left to right, we know the
 813     // boundaries of the rectangles are appended in a list, hence the AppendBord(). we salvage
 814     // the guess value for the trapezoids the edges will induce
 815
 816     if ( sTree->racine ) {
 817         SweepTree *curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
 818         while ( curS ) {
 819
 820             int lastGuess = -1;
 821             int cb = curS->bord;
 822
 823             if ( swrData[cb].sens == false && curS->elem[LEFT] ) {
 824
 825                 int lb = (static_cast<SweepTree*>(curS->elem[LEFT]))->bord;
 826
 827                 lastGuess = line->AppendBord(swrData[lb].curX,
 828                                              to - swrData[lb].curY,
 829                                              swrData[cb].curX,
 830                                              to - swrData[cb].curY,0.0);
 831
 832                 swrData[lb].guess = lastGuess - 1;
 833                 swrData[cb].guess = lastGuess;
 834             } else {
 835                 int lb = curS->bord;
 836                 swrData[lb].guess = -1;
 837             }
 838
 839             curS=static_cast <SweepTree*> (curS->elem[RIGHT]);
 840         }
 841     }
 842
 843     int curPt = curP;
 844     while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
 845
 846         int nPt = curPt++;
 847
 848         // same thing as the usual Scan(), just with a hardcoded "indegree+outdegree=2" case, since
 849         // it's the most common one
 850
 851         int nbUp;
 852         int nbDn;
 853         int upNo;
 854         int dnNo;
 855         if ( getPoint(nPt).totalDegree() == 2 ) {
 856             _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
 857         } else {
 858             _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
 859         }
 860
 861         if ( nbDn <= 0 ) {
 862             upNo = -1;
 863         }
 864         if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
 865             upNo = -1;
 866         }
 867
 868         if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
 869             int cb = getPoint(nPt).incidentEdge[FIRST];
 870             while ( cb >= 0 && cb < numberOfEdges() ) {
 871                 Shape::dg_arete const &e = getEdge(cb);
 872                 if ( nPt == std::max(e.st, e.en) ) {
 873                     if ( cb != upNo ) {
 874                         SweepTree* node = swrData[cb].misc;
 875                         if ( node ) {
 876                             _updateIntersection(cb, nPt);
 877                             // create trapezoid for the chunk of edge intersecting with the line
 878                             DestroyEdge(cb, to, line);
 879                             node->Remove(*sTree, *sEvts, true);
 880                         }
 881                     }
 882                 }
 883
 884                 cb = NextAt(nPt,cb);
 885             }
 886         }
 887
 888         // traitement du "upNo devient dnNo"
 889         SweepTree *insertionNode = NULL;
 890         if ( dnNo >= 0 ) {
 891             if ( upNo >= 0 ) {
 892                 SweepTree* node = swrData[upNo].misc;
 893                 _updateIntersection(upNo, nPt);
 894                 DestroyEdge(upNo, to, line);
 895
 896                 node->ConvertTo(this, dnNo, 1, nPt);
 897
 898                 swrData[dnNo].misc = node;
 899                 insertionNode = node;
 900                 CreateEdge(dnNo, to, step);
 901                 swrData[dnNo].guess = swrData[upNo].guess;
 902             } else {
 903                 SweepTree *node = sTree->add(this, dnNo, 1, nPt, this);
 904                 swrData[dnNo].misc = node;
 905                 node->Insert(*sTree, *sEvts, this, nPt, true);
 906                 insertionNode = node;
 907                 CreateEdge(dnNo, to, step);
 908             }
 909         }
 910
 911         if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
 912             int cb = getPoint(nPt).incidentEdge[FIRST];
 913             while ( cb >= 0 && cb < numberOfEdges() ) {
 914                 Shape::dg_arete const &e = getEdge(cb);
 915                 if ( nPt == std::min(e.st, e.en) ) {
 916                     if ( cb != dnNo ) {
 917                         SweepTree *node = sTree->add(this, cb, 1, nPt, this);
 918                         swrData[cb].misc = node;
 919                         node->InsertAt(*sTree, *sEvts, this, insertionNode, nPt, true);
 920                         CreateEdge(cb, to, step);
 921                     }
 922                 }
 923                 cb = NextAt(nPt,cb);
 924             }
 925         }
 926     }
 927
 928     curP = curPt;
 929     if ( curPt > 0 ) {
 930         pos = getPoint(curPt - 1).x[1];
 931     } else {
 932         pos = to;
 933     }
 934
 935     // update intersections with the sweepline, and add trapezoids for edges crossing the line
 936     pos = to;
 937     if ( sTree->racine ) {
 938         SweepTree* curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
 939         while ( curS ) {
 940             int cb = curS->bord;
 941             AvanceEdge(cb, to, line, exact, step);
 942             curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
 943         }
 944     }
 945 }
 946
 947
 948
 949
 950 void Shape::Scan(float &pos, int &curP, float to, FillRule directed, BitLigne *line, bool exact, float step)
 951 {
 952     if ( numberOfEdges() <= 1 ) {
 953         return;
 954     }
 955
 956     if ( pos >= to ) {
 957         return;
 958     }
 959
 960     if ( sTree->racine ) {
 961         int curW = 0;
 962         float lastX = 0;
 963         SweepTree* curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
 964
 965         if ( directed == fill_oddEven ) {
 966
 967             while ( curS ) {
 968                 int cb = curS->bord;
 969                 curW++;
 970                 curW &= 0x00000001;
 971                 if ( curW == 0 ) {
 972                     line->AddBord(lastX,swrData[cb].curX,true);
 973                 } else {
 974                     lastX = swrData[cb].curX;
 975                 }
 976                 curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
 977             }
 978
 979         } else if ( directed == fill_positive ) {
 980
 981             // doesn't behave correctly; no way i know to do this without a ConvertToShape()
 982             while ( curS ) {
 983                 int cb = curS->bord;
 984               int oW = curW;
 985               if ( swrData[cb].sens ) {
 986                   curW++;
 987               } else {
 988                   curW--;
 989               }
 990
 991               if ( curW <= 0 && oW > 0) {
 992                   line->AddBord(lastX, swrData[cb].curX, true);
 993               } else if ( curW > 0 && oW <= 0 ) {
 994                   lastX = swrData[cb].curX;
 995               }
 996
 997               curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
 998             }
 999
1000         } else if ( directed == fill_nonZero ) {
1001
1002             while ( curS ) {
1003                 int cb = curS->bord;
1004                 int oW = curW;
1005                 if ( swrData[cb].sens ) {
1006                     curW++;
1007                 } else {
1008                     curW--;
1009                 }
1010
1011                 if ( curW == 0 && oW != 0) {
1012                     line->AddBord(lastX,swrData[cb].curX,true);
1013                 } else if ( curW != 0 && oW == 0 ) {
1014                     lastX=swrData[cb].curX;
1015                 }
1016                 curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
1017             }
1018         }
1019
1020     }
1021
1022     int curPt = curP;
1023     while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
1024         int nPt = curPt++;
1025
1026         int cb;
1027         int nbUp;
1028         int nbDn;
1029         int upNo;
1030         int dnNo;
1031
1032         if ( getPoint(nPt).totalDegree() == 2 ) {
1033             _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
1034         } else {
1035             _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
1036         }
1037
1038         if ( nbDn <= 0 ) {
1039             upNo = -1;
1040         }
1041         if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
1042             upNo = -1;
1043         }
1044
1045         if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
1046             int cb = getPoint(nPt).incidentEdge[FIRST];
1047             while ( cb >= 0 && cb < numberOfEdges() ) {
1048                 Shape::dg_arete const &e = getEdge(cb);
1049                 if ( nPt == std::max(e.st, e.en) ) {
1050                     if ( cb != upNo ) {
1051                         SweepTree* node=swrData[cb].misc;
1052                         if ( node ) {
1053                             _updateIntersection(cb, nPt);
1054                             DestroyEdge(cb, line);
1055                             node->Remove(*sTree,*sEvts,true);
1056                         }
1057                     }
1058                 }
1059                 cb = NextAt(nPt,cb);
1060             }
1061         }
1062
1063         // traitement du "upNo devient dnNo"
1064         SweepTree* insertionNode = NULL;
1065         if ( dnNo >= 0 ) {
1066             if ( upNo >= 0 ) {
1067                 SweepTree* node = swrData[upNo].misc;
1068                 _updateIntersection(upNo, nPt);
1069                 DestroyEdge(upNo, line);
1070
1071                 node->ConvertTo(this, dnNo, 1, nPt);
1072
1073                 swrData[dnNo].misc = node;
1074                 insertionNode = node;
1075                 CreateEdge(dnNo, to, step);
1076
1077             } else {
1078
1079                 SweepTree* node = sTree->add(this,dnNo,1,nPt,this);
1080                 swrData[dnNo].misc = node;
1081                 node->Insert(*sTree, *sEvts, this, nPt, true);
1082                 insertionNode = node;
1083                 CreateEdge(dnNo, to, step);
1084             }
1085         }
1086
1087         if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
1088             cb = getPoint(nPt).incidentEdge[FIRST];
1089             while ( cb >= 0 && cb < numberOfEdges() ) {
1090                 Shape::dg_arete const &e = getEdge(cb);
1091                 if ( nPt == std::min(e.st, e.en) ) {
1092                     if ( cb != dnNo ) {
1093                         SweepTree* node = sTree->add(this, cb, 1, nPt, this);
1094                         swrData[cb].misc = node;
1095                         node->InsertAt(*sTree, *sEvts, this, insertionNode, nPt, true);
1096                         CreateEdge(cb, to, step);
1097                     }
1098                 }
1099                 cb = NextAt(nPt, cb);
1100             }
1101         }
1102     }
1103
1104     curP = curPt;
1105     if ( curPt > 0 ) {
1106         pos = getPoint(curPt - 1).x[1];
1107     } else {
1108         pos = to;
1109     }
1110
1111     pos = to;
1112     if ( sTree->racine ) {
1113         SweepTree* curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
1114         while ( curS ) {
1115             int cb = curS->bord;
1116             AvanceEdge(cb, to, line, exact, step);
1117             curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
1118         }
1119     }
1120 }
1121
1122
1123 void Shape::Scan(float &pos, int &curP, float to, AlphaLigne *line, bool exact, float step)
1124 {
1125     if ( numberOfEdges() <= 1 ) {
1126         return;
1127     }
1128
1129     if ( pos >= to ) {
1130         return;
1131     }
1132
1133     int curPt = curP;
1134     while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
1135         int nPt = -1;
1136         nPt = curPt++;
1137
1138         int nbUp;
1139         int nbDn;
1140         int upNo;
1141         int dnNo;
1142         if ( getPoint(nPt).totalDegree() == 2 ) {
1143             _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
1144         } else {
1145             _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
1146         }
1147
1148         if ( nbDn <= 0 ) {
1149             upNo=-1;
1150         }
1151         if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
1152             upNo=-1;
1153         }
1154
1155         if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
1156             int cb = getPoint(nPt).incidentEdge[FIRST];
1157             while ( cb >= 0 && cb < numberOfEdges() ) {
1158                 Shape::dg_arete const &e = getEdge(cb);
1159                 if ( nPt == std::max(e.st, e.en) ) {
1160                     if ( cb != upNo ) {
1161                         SweepTree* node = swrData[cb].misc;
1162                         if ( node ) {
1163                             _updateIntersection(cb, nPt);
1164                             DestroyEdge(cb, line);
1165                             node->Remove(*sTree, *sEvts, true);
1166                         }
1167                     }
1168                 }
1169
1170                 cb = NextAt(nPt,cb);
1171             }
1172         }
1173
1174         // traitement du "upNo devient dnNo"
1175         SweepTree* insertionNode = NULL;
1176         if ( dnNo >= 0 ) {
1177             if ( upNo >= 0 ) {
1178                 SweepTree* node = swrData[upNo].misc;
1179                 _updateIntersection(upNo, nPt);
1180                 DestroyEdge(upNo, line);
1181
1182                 node->ConvertTo(this, dnNo, 1, nPt);
1183
1184                 swrData[dnNo].misc = node;
1185                 insertionNode = node;
1186                 CreateEdge(dnNo, to, step);
1187                 swrData[dnNo].guess = swrData[upNo].guess;
1188             } else {
1189                 SweepTree* node = sTree->add(this, dnNo, 1, nPt, this);
1190                 swrData[dnNo].misc = node;
1191                 node->Insert(*sTree, *sEvts, this, nPt, true);
1192                 insertionNode = node;
1193                 CreateEdge(dnNo, to, step);
1194             }
1195         }
1196
1197         if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
1198             int cb = getPoint(nPt).incidentEdge[FIRST];
1199             while ( cb >= 0 && cb < numberOfEdges() ) {
1200                 Shape::dg_arete const &e = getEdge(cb);
1201                 if ( nPt == std::min(e.st, e.en) ) {
1202                     if ( cb != dnNo ) {
1203                         SweepTree* node = sTree->add(this, cb, 1, nPt, this);
1204                         swrData[cb].misc = node;
1205                         node->InsertAt(*sTree, *sEvts, this, insertionNode, nPt, true);
1206                         CreateEdge(cb, to, step);
1207                     }
1208                 }
1209                 cb = NextAt(nPt,cb);
1210             }
1211         }
1212     }
1213
1214     curP = curPt;
1215     if ( curPt > 0 ) {
1216         pos = getPoint(curPt - 1).x[1];
1217     } else {
1218         pos = to;
1219     }
1220
1221     pos = to;
1222     if ( sTree->racine ) {
1223         SweepTree* curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
1224         while ( curS ) {
1225             int cb = curS->bord;
1226             AvanceEdge(cb, to, line, exact, step);
1227             curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
1228         }
1229     }
1230 }
1231
1232
1233
1234 void Shape::QuickScan(float &pos, int &curP, float to, FloatLigne* line, float step)
1235 {
1236     if ( numberOfEdges() <= 1 ) {
1237         return;
1238     }
1239
1240     if ( pos >= to ) {
1241         return;
1242     }
1243
1244     if ( nbQRas > 1 ) {
1245         int curW = 0;
1246         float lastX = 0;
1247         float lastY = 0;
1248         int lastGuess = -1;
1249         int lastB = -1;
1250
1251         for (int i = firstQRas; i >= 0 && i < nbQRas; i = qrsData[i].next) {
1252             int cb = qrsData[i].bord;
1253             int oW = curW;
1254             if ( swrData[cb].sens ) {
1255                 curW++;
1256             } else {
1257                 curW--;
1258             }
1259
1260             if ( curW % 2 == 0 && oW % 2 != 0) {
1261
1262                 lastGuess = line->AppendBord(swrData[lastB].curX,
1263                                              to - swrData[lastB].curY,
1264                                              swrData[cb].curX,
1265                                              to - swrData[cb].curY,
1266                                              0.0);
1267
1268                 swrData[cb].guess = lastGuess;
1269                 if ( lastB >= 0 ) {
1270                     swrData[lastB].guess = lastGuess - 1;
1271                 }
1272
1273             } else if ( curW%2 != 0 && oW%2 == 0 ) {
1274
1275                 lastX = swrData[cb].curX;
1276                 lastY = swrData[cb].curY;
1277                 lastB = cb;
1278                 swrData[cb].guess = -1;
1279
1280             } else {
1281                 swrData[cb].guess = -1;
1282             }
1283         }
1284     }
1285
1286     int curPt = curP;
1287     while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
1288         int nPt = curPt++;
1289
1290         int nbUp;
1291         int nbDn;
1292         int upNo;
1293         int dnNo;
1294         if ( getPoint(nPt).totalDegree() == 2 ) {
1295             _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
1296         } else {
1297             _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
1298         }
1299
1300         if ( nbDn <= 0 ) {
1301             upNo = -1;
1302         }
1303         if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
1304             upNo = -1;
1305         }
1306
1307         if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
1308             int cb = getPoint(nPt).incidentEdge[FIRST];
1309             while ( cb >= 0 && cb < numberOfEdges() ) {
1310                 Shape::dg_arete const &e = getEdge(cb);
1311                 if ( nPt == std::max(e.st, e.en) ) {
1312                     if ( cb != upNo ) {
1313                         QuickRasterSubEdge(cb);
1314                         _updateIntersection(cb, nPt);
1315                         DestroyEdge(cb, to, line);
1316                     }
1317                 }
1318                 cb = NextAt(nPt, cb);
1319             }
1320         }
1321
1322         // traitement du "upNo devient dnNo"
1323         int ins_guess=-1;
1324         if ( dnNo >= 0 ) {
1325             if ( upNo >= 0 ) {
1326                 ins_guess = QuickRasterChgEdge(upNo ,dnNo, getPoint(nPt).x[0]);
1327                 _updateIntersection(upNo, nPt);
1328                 DestroyEdge(upNo, to, line);
1329
1330                 CreateEdge(dnNo, to, step);
1331                 swrData[dnNo].guess = swrData[upNo].guess;
1332             } else {
1333                 ins_guess = QuickRasterAddEdge(dnNo, getPoint(nPt).x[0], ins_guess);
1334                 CreateEdge(dnNo, to, step);
1335             }
1336         }
1337
1338         if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
1339             int cb = getPoint(nPt).incidentEdge[FIRST];
1340             while ( cb >= 0 && cb < numberOfEdges() ) {
1341                 Shape::dg_arete const &e = getEdge(cb);
1342                 if ( nPt == std::min(e.st, e.en) ) {
1343                     if ( cb != dnNo ) {
1344                         ins_guess = QuickRasterAddEdge(cb, getPoint(nPt).x[0], ins_guess);
1345                         CreateEdge(cb, to, step);
1346                     }
1347                 }
1348                 cb = NextAt(nPt, cb);
1349             }
1350         }
1351     }
1352
1353     curP = curPt;
1354     if ( curPt > 0 ) {
1355         pos = getPoint(curPt-1).x[1];
1356     } else {
1357         pos=to;
1358     }
1359
1360     pos = to;
1361     for (int i=0; i < nbQRas; i++) {
1362         int cb = qrsData[i].bord;
1363         AvanceEdge(cb, to, line, true, step);
1364         qrsData[i].x = swrData[cb].curX;
1365     }
1366
1367     QuickRasterSort();
1368 }
1369
1370
1371
1372
1373 void Shape::QuickScan(float &pos, int &curP, float to, FillRule directed, BitLigne* line, float step)
1374 {
1375     if ( numberOfEdges() <= 1 ) {
1376         return;
1377     }
1378
1379     if ( pos >= to ) {
1380         return;
1381     }
1382
1383     if ( nbQRas > 1 ) {
1384         int curW = 0;
1385         float lastX = 0;
1386
1387         if ( directed == fill_oddEven ) {
1388
1389             for (int i = firstQRas; i >= 0 && i < nbQRas; i = qrsData[i].next) {
1390                 int cb = qrsData[i].bord;
1391                 curW++;
1392                 curW &= 1;
1393                 if ( curW == 0 ) {
1394                     line->AddBord(lastX, swrData[cb].curX, true);
1395                 } else {
1396                     lastX = swrData[cb].curX;
1397                 }
1398             }
1399
1400         } else if ( directed == fill_positive ) {
1401             // doesn't behave correctly; no way i know to do this without a ConvertToShape()
1402             for (int i = firstQRas; i >= 0 && i < nbQRas; i = qrsData[i].next) {
1403                 int cb = qrsData[i].bord;
1404                 int oW = curW;
1405                 if ( swrData[cb].sens ) {
1406                     curW++;
1407                 } else {
1408                     curW--;
1409                 }
1410
1411                 if ( curW <= 0 && oW > 0) {
1412                     line->AddBord(lastX, swrData[cb].curX, true);
1413                 } else if ( curW > 0 && oW <= 0 ) {
1414                     lastX = swrData[cb].curX;
1415                 }
1416             }
1417
1418         } else if ( directed == fill_nonZero ) {
1419             for (int i = firstQRas; i >= 0 && i < nbQRas; i = qrsData[i].next) {
1420                 int cb = qrsData[i].bord;
1421                 int oW = curW;
1422                 if ( swrData[cb].sens ) {
1423                     curW++;
1424                 } else {
1425                     curW--;
1426                 }
1427
1428                 if ( curW == 0 && oW != 0) {
1429                     line->AddBord(lastX, swrData[cb].curX, true);
1430                 } else if ( curW != 0 && oW == 0 ) {
1431                     lastX = swrData[cb].curX;
1432                 }
1433             }
1434         }
1435     }
1436
1437     int curPt = curP;
1438     while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
1439         int nPt = -1;
1440         nPt = curPt++;
1441
1442         int nbUp;
1443         int nbDn;
1444         int upNo;
1445         int dnNo;
1446         if ( getPoint(nPt).totalDegree() == 2 ) {
1447             _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
1448         } else {
1449             _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
1450         }
1451
1452         if ( nbDn <= 0 ) {
1453             upNo = -1;
1454         }
1455
1456         if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
1457             upNo = -1;
1458         }
1459
1460         if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
1461             int cb = getPoint(nPt).incidentEdge[FIRST];
1462             while ( cb >= 0 && cb < numberOfEdges() ) {
1463                 Shape::dg_arete const &e = getEdge(cb);
1464                 if ( nPt == std::max(e.st, e.en) ) {
1465                     if ( cb != upNo ) {
1466                         QuickRasterSubEdge(cb);
1467                         _updateIntersection(cb, nPt);
1468                         DestroyEdge(cb, line);
1469                     }
1470                 }
1471                 cb = NextAt(nPt, cb);
1472             }
1473         }
1474
1475         // traitement du "upNo devient dnNo"
1476         int ins_guess = -1;
1477         if ( dnNo >= 0 ) {
1478             if ( upNo >= 0 ) {
1479                 ins_guess = QuickRasterChgEdge(upNo, dnNo, getPoint(nPt).x[0]);
1480                 _updateIntersection(upNo, nPt);
1481                 DestroyEdge(upNo, line);
1482
1483                 CreateEdge(dnNo, to, step);
1484             } else {
1485                 ins_guess = QuickRasterAddEdge(dnNo, getPoint(nPt).x[0], ins_guess);
1486                 CreateEdge(dnNo, to, step);
1487             }
1488         }
1489
1490         if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
1491             int cb = getPoint(nPt).incidentEdge[FIRST];
1492             while ( cb >= 0 && cb < numberOfEdges() ) {
1493                 Shape::dg_arete const &e = getEdge(cb);
1494                 if ( nPt == std::min(e.st, e.en) ) {
1495                     if ( cb != dnNo ) {
1496                         ins_guess = QuickRasterAddEdge(cb, getPoint(nPt).x[0], ins_guess);
1497                         CreateEdge(cb, to, step);
1498                     }
1499                 }
1500                 cb = NextAt(nPt,cb);
1501             }
1502         }
1503     }
1504
1505     curP = curPt;
1506     if ( curPt > 0 ) {
1507         pos=getPoint(curPt - 1).x[1];
1508     } else {
1509         pos = to;
1510     }
1511
1512     pos = to;
1513     for (int i = 0; i < nbQRas; i++) {
1514         int cb = qrsData[i].bord;
1515         AvanceEdge(cb, to, line, true, step);
1516         qrsData[i].x = swrData[cb].curX;
1517     }
1518
1519     QuickRasterSort();
1520 }
1521
1522
1523
1524 void Shape::QuickScan(float &pos, int &curP, float to, AlphaLigne* line, float step)
1525 {
1526     if ( numberOfEdges() <= 1 ) {
1527         return;
1528     }
1529     if ( pos >= to ) {
1530         return;
1531     }
1532
1533     int curPt = curP;
1534     while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
1535         int nPt = curPt++;
1536
1537         int nbUp;
1538         int nbDn;
1539         int upNo;
1540         int dnNo;
1541         if ( getPoint(nPt).totalDegree() == 2 ) {
1542             _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
1543         } else {
1544             _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
1545         }
1546
1547         if ( nbDn <= 0 ) {
1548             upNo = -1;
1549         }
1550         if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
1551             upNo = -1;
1552         }
1553
1554         if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
1555             int cb = getPoint(nPt).incidentEdge[FIRST];
1556             while ( cb >= 0 && cb < numberOfEdges() ) {
1557                 Shape::dg_arete const &e = getEdge(cb);
1558                 if ( nPt == std::max(e.st, e.en) ) {
1559                     if ( cb != upNo ) {
1560                         QuickRasterSubEdge(cb);
1561                         _updateIntersection(cb, nPt);
1562                         DestroyEdge(cb, line);
1563                     }
1564                 }
1565                 cb = NextAt(nPt,cb);
1566             }
1567         }
1568
1569         // traitement du "upNo devient dnNo"
1570         int ins_guess = -1;
1571         if ( dnNo >= 0 ) {
1572             if ( upNo >= 0 ) {
1573                 ins_guess = QuickRasterChgEdge(upNo, dnNo, getPoint(nPt).x[0]);
1574                 _updateIntersection(upNo, nPt);
1575                 DestroyEdge(upNo, line);
1576
1577                 CreateEdge(dnNo, to, step);
1578                 swrData[dnNo].guess = swrData[upNo].guess;
1579             } else {
1580                 ins_guess = QuickRasterAddEdge(dnNo, getPoint(nPt).x[0], ins_guess);
1581                 CreateEdge(dnNo, to, step);
1582             }
1583         }
1584
1585         if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
1586             int cb = getPoint(nPt).incidentEdge[FIRST];
1587             while ( cb >= 0 && cb < numberOfEdges() ) {
1588                 Shape::dg_arete const &e = getEdge(cb);
1589                 if ( nPt == std::min(e.st, e.en) ) {
1590                     if ( cb != dnNo ) {
1591                         ins_guess = QuickRasterAddEdge(cb,getPoint(nPt).x[0], ins_guess);
1592                         CreateEdge(cb, to, step);
1593                     }
1594                 }
1595                 cb = NextAt(nPt,cb);
1596             }
1597         }
1598     }
1599
1600     curP = curPt;
1601     if ( curPt > 0 ) {
1602         pos = getPoint(curPt-1).x[1];
1603     } else {
1604         pos = to;
1605     }
1606
1607     pos = to;
1608     for (int i = 0; i < nbQRas; i++) {
1609         int cb = qrsData[i].bord;
1610         AvanceEdge(cb, to, line, true, step);
1611         qrsData[i].x = swrData[cb].curX;
1612     }
1613
1614     QuickRasterSort();
1615 }
1616
1617
1618 /*
1619  * operations de bases pour la rasterization
1620  *
1621  */
1622 void Shape::CreateEdge(int no, float to, float step)
1623 {
1624     int cPt;
1625     Geom::Point dir;
1626     if ( getEdge(no).st < getEdge(no).en ) {
1627         cPt = getEdge(no).st;
1628         swrData[no].sens = true;
1629         dir = getEdge(no).dx;
1630     } else {
1631         cPt = getEdge(no).en;
1632         swrData[no].sens = false;
1633         dir = -getEdge(no).dx;
1634     }
1635
1636     swrData[no].lastX = swrData[no].curX = getPoint(cPt).x[0];
1637     swrData[no].lastY = swrData[no].curY = getPoint(cPt).x[1];
1638
1639     if ( fabs(dir[1]) < 0.000001 ) {
1640         swrData[no].dxdy = 0;
1641     } else {
1642         swrData[no].dxdy = dir[0]/dir[1];
1643     }
1644
1645     if ( fabs(dir[0]) < 0.000001 ) {
1646         swrData[no].dydx = 0;
1647     } else {
1648         swrData[no].dydx = dir[1]/dir[0];
1649     }
1650
1651     swrData[no].calcX = swrData[no].curX + (to - step - swrData[no].curY) * swrData[no].dxdy;
1652     swrData[no].guess = -1;
1653 }
1654
1655
1656 void Shape::AvanceEdge(int no, float to, bool exact, float step)
1657 {
1658     if ( exact ) {
1659         Geom::Point dir;
1660         Geom::Point stp;
1661         if ( swrData[no].sens ) {
1662             stp = getPoint(getEdge(no).st).x;
1663             dir = getEdge(no).dx;
1664         } else {
1665             stp = getPoint(getEdge(no).en).x;
1666             dir = -getEdge(no).dx;
1667         }
1668
1669         if ( fabs(dir[1]) < 0.000001 ) {
1670             swrData[no].calcX = stp[0] + dir[0];
1671         } else {
1672             swrData[no].calcX = stp[0] + ((to - stp[1]) * dir[0]) / dir[1];
1673         }
1674     } else {
1675         swrData[no].calcX += step * swrData[no].dxdy;
1676     }
1677
1678     swrData[no].lastX = swrData[no].curX;
1679     swrData[no].lastY = swrData[no].curY;
1680     swrData[no].curX = swrData[no].calcX;
1681     swrData[no].curY = to;
1682 }
1683
1684 /*
1685  * specialisation par type de structure utilise
1686  */
1687
1688 void Shape::DestroyEdge(int no, float to, FloatLigne* line)
1689 {
1690     if ( swrData[no].sens ) {
1691
1692         if ( swrData[no].curX < swrData[no].lastX ) {
1693
1694             swrData[no].guess = line->AddBordR(swrData[no].curX,
1695                                                to - swrData[no].curY,
1696                                                swrData[no].lastX,
1697                                                to - swrData[no].lastY,
1698                                                -swrData[no].dydx,
1699                                                swrData[no].guess);
1700
1701         } else if ( swrData[no].curX > swrData[no].lastX ) {
1702
1703             swrData[no].guess = line->AddBord(swrData[no].lastX,
1704                                               -(to - swrData[no].lastY),
1705                                               swrData[no].curX,
1706                                               -(to - swrData[no].curY),
1707                                               swrData[no].dydx,
1708                                               swrData[no].guess);
1709         }
1710
1711     } else {
1712
1713         if ( swrData[no].curX < swrData[no].lastX ) {
1714
1715             swrData[no].guess = line->AddBordR(swrData[no].curX,
1716                                                -(to - swrData[no].curY),
1717                                                swrData[no].lastX,
1718                                                -(to - swrData[no].lastY),
1719                                                swrData[no].dydx,
1720                                                swrData[no].guess);
1721
1722         } else if ( swrData[no].curX > swrData[no].lastX ) {
1723
1724             swrData[no].guess = line->AddBord(swrData[no].lastX,
1725                                               to - swrData[no].lastY,
1726                                               swrData[no].curX,
1727                                               to - swrData[no].curY,
1728                                               -swrData[no].dydx,
1729                                               swrData[no].guess);
1730         }
1731     }
1732 }
1733
1734
1735
1736 void Shape::AvanceEdge(int no, float to, FloatLigne *line, bool exact, float step)
1737 {
1738     AvanceEdge(no,to,exact,step);
1739
1740     if ( swrData[no].sens ) {
1741
1742         if ( swrData[no].curX < swrData[no].lastX ) {
1743
1744             swrData[no].guess = line->AddBordR(swrData[no].curX,
1745                                                to - swrData[no].curY,
1746                                                swrData[no].lastX,
1747                                                to - swrData[no].lastY,
1748                                                -swrData[no].dydx,
1749                                                swrData[no].guess);
1750
1751         } else if ( swrData[no].curX > swrData[no].lastX ) {
1752
1753             swrData[no].guess = line->AddBord(swrData[no].lastX,
1754                                               -(to - swrData[no].lastY),
1755                                               swrData[no].curX,
1756                                               -(to - swrData[no].curY),
1757                                               swrData[no].dydx,
1758                                               swrData[no].guess);
1759         }
1760
1761     } else {
1762
1763         if ( swrData[no].curX < swrData[no].lastX ) {
1764
1765             swrData[no].guess = line->AddBordR(swrData[no].curX,
1766                                                -(to - swrData[no].curY),
1767                                                swrData[no].lastX,
1768                                                -(to - swrData[no].lastY),
1769                                                swrData[no].dydx,
1770                                                swrData[no].guess);
1771
1772         } else if ( swrData[no].curX > swrData[no].lastX ) {
1773
1774             swrData[no].guess = line->AddBord(swrData[no].lastX,
1775                                               to - swrData[no].lastY,
1776                                               swrData[no].curX,
1777                                               to - swrData[no].curY,
1778                                               -swrData[no].dydx,
1779                                               swrData[no].guess);
1780         }
1781     }
1782 }
1783
1784
1785 void Shape::DestroyEdge(int no, BitLigne *line)
1786 {
1787     if ( swrData[no].sens ) {
1788
1789         if ( swrData[no].curX < swrData[no].lastX ) {
1790
1791             line->AddBord(swrData[no].curX, swrData[no].lastX, false);
1792
1793         } else if ( swrData[no].curX > swrData[no].lastX ) {
1794
1795             line->AddBord(swrData[no].lastX,swrData[no].curX,false);
1796         }
1797
1798     } else {
1799
1800         if ( swrData[no].curX < swrData[no].lastX ) {
1801
1802             line->AddBord(swrData[no].curX, swrData[no].lastX, false);
1803
1804         } else if ( swrData[no].curX > swrData[no].lastX ) {
1805
1806             line->AddBord(swrData[no].lastX, swrData[no].curX, false);
1807
1808         }
1809     }
1810 }
1811
1812
1813 void Shape::AvanceEdge(int no, float to, BitLigne *line, bool exact, float step)
1814 {
1815     AvanceEdge(no, to, exact, step);
1816
1817     if ( swrData[no].sens ) {
1818
1819         if ( swrData[no].curX < swrData[no].lastX ) {
1820
1821             line->AddBord(swrData[no].curX, swrData[no].lastX, false);
1822
1823         } else if ( swrData[no].curX > swrData[no].lastX ) {
1824
1825             line->AddBord(swrData[no].lastX, swrData[no].curX, false);
1826         }
1827
1828     } else {
1829
1830         if ( swrData[no].curX < swrData[no].lastX ) {
1831
1832             line->AddBord(swrData[no].curX, swrData[no].lastX, false);
1833
1834         } else if ( swrData[no].curX > swrData[no].lastX ) {
1835
1836             line->AddBord(swrData[no].lastX, swrData[no].curX, false);
1837         }
1838     }
1839 }
1840
1841
1842 void Shape::DestroyEdge(int no, AlphaLigne* line)
1843 {
1844     if ( swrData[no].sens ) {
1845
1846         if ( swrData[no].curX <= swrData[no].lastX ) {
1847
1848             line->AddBord(swrData[no].curX,
1849                           0,
1850                           swrData[no].lastX,
1851                           swrData[no].curY - swrData[no].lastY,
1852                           -swrData[no].dydx);
1853
1854         } else if ( swrData[no].curX > swrData[no].lastX ) {
1855
1856             line->AddBord(swrData[no].lastX,
1857                           0,
1858                           swrData[no].curX,
1859                           swrData[no].curY - swrData[no].lastY,
1860                           swrData[no].dydx);
1861         }
1862
1863     } else {
1864
1865         if ( swrData[no].curX <= swrData[no].lastX ) {
1866
1867             line->AddBord(swrData[no].curX,
1868                           0,
1869                           swrData[no].lastX,
1870                           swrData[no].lastY - swrData[no].curY,
1871                           swrData[no].dydx);
1872
1873         } else if ( swrData[no].curX > swrData[no].lastX ) {
1874
1875             line->AddBord(swrData[no].lastX,
1876                           0,
1877                           swrData[no].curX,
1878                           swrData[no].lastY - swrData[no].curY,
1879                           -swrData[no].dydx);
1880         }
1881     }
1882 }
1883
1884
1885 void Shape::AvanceEdge(int no, float to, AlphaLigne *line, bool exact, float step)
1886 {
1887     AvanceEdge(no,to,exact,step);
1888
1889     if ( swrData[no].sens ) {
1890
1891         if ( swrData[no].curX <= swrData[no].lastX ) {
1892
1893             line->AddBord(swrData[no].curX,
1894                           0,
1895                           swrData[no].lastX,
1896                           swrData[no].curY - swrData[no].lastY,
1897                           -swrData[no].dydx);
1898
1899         } else if ( swrData[no].curX > swrData[no].lastX ) {
1900
1901             line->AddBord(swrData[no].lastX,
1902                           0,
1903                           swrData[no].curX,
1904                           swrData[no].curY - swrData[no].lastY,
1905                           swrData[no].dydx);
1906         }
1907
1908     } else {
1909
1910         if ( swrData[no].curX <= swrData[no].lastX ) {
1911
1912             line->AddBord(swrData[no].curX,
1913                           0,
1914                           swrData[no].lastX,
1915                           swrData[no].lastY - swrData[no].curY,
1916                           swrData[no].dydx);
1917
1918         } else if ( swrData[no].curX > swrData[no].lastX ) {
1919
1920             line->AddBord(swrData[no].lastX,
1921                           0,
1922                           swrData[no].curX,
1923                           swrData[no].lastY - swrData[no].curY,
1924                           -swrData[no].dydx);
1925         }
1926     }
1927 }
1928
1929 /**
1930  *    \param P point index.
1931  *    \param numberUp Filled in with the number of edges coming into P from above.
1932  *    \param numberDown Filled in with the number of edges coming exiting P to go below.
1933  *    \param upEdge One of the numberUp edges, or -1.
1934  *    \param downEdge One of the numberDown edges, or -1.
1935  */
1936
1937 void Shape::_countUpDown(int P, int *numberUp, int *numberDown, int *upEdge, int *downEdge) const
1938 {
1939     *numberUp = 0;
1940     *numberDown = 0;
1941     *upEdge = -1;
1942     *downEdge = -1;
1943
1944     int i = getPoint(P).incidentEdge[FIRST];
1945
1946     while ( i >= 0 && i < numberOfEdges() ) {
1947         Shape::dg_arete const &e = getEdge(i);
1948         if ( P == std::max(e.st, e.en) ) {
1949             *upEdge = i;
1950             (*numberUp)++;
1951         }
1952         if ( P == std::min(e.st, e.en) ) {
1953             *downEdge = i;
1954             (*numberDown)++;
1955         }
1956         i = NextAt(P, i);
1957     }
1958
1959 }
1960
1961
1962
1963 /**
1964  *     Version of Shape::_countUpDown optimised for the case when getPoint(P).totalDegree() == 2.
1965  */
1966
1967 void Shape::_countUpDownTotalDegree2(int P,
1968                                      int *numberUp, int *numberDown, int *upEdge, int *downEdge) const
1969 {
1970     *numberUp = 0;
1971     *numberDown = 0;
1972     *upEdge = -1;
1973     *downEdge = -1;
1974
1975     for (int i = 0; i < 2; i++) {
1976         int const j = getPoint(P).incidentEdge[i];
1977         Shape::dg_arete const &e = getEdge(j);
1978         if ( P == std::max(e.st, e.en) ) {
1979             *upEdge = j;
1980             (*numberUp)++;
1981         }
1982         if ( P == std::min(e.st, e.en) ) {
1983             *downEdge = j;
1984             (*numberDown)++;
1985         }
1986     }
1987 }
1988
1989
1990 void Shape::_updateIntersection(int e, int p)
1991 {
1992     swrData[e].lastX = swrData[e].curX;
1993     swrData[e].lastY = swrData[e].curY;
1994     swrData[e].curX = getPoint(p).x[0];
1995     swrData[e].curY = getPoint(p).x[1];
1996     swrData[e].misc = NULL;
1997 }
1998
1999
2000 /*
2001   Local Variables:
2002   mode:c++
2003   c-file-style:"stroustrup"
2004   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
2005   indent-tabs-mode:nil
2006   fill-column:99
2007   End:
2008 */
2009 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :