summaryrefslogtreecommitdiffstats
path: root/src/livarot/ShapeRaster.cpp
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/livarot/ShapeRaster.cpp2014
1 files changed, 2014 insertions, 0 deletions
diff --git a/src/livarot/ShapeRaster.cpp b/src/livarot/ShapeRaster.cpp
new file mode 100644
index 0000000..7aa300e
--- /dev/null
+++ b/src/livarot/ShapeRaster.cpp
@@ -0,0 +1,2014 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+/*
+ * ShapeRaster.cpp
+ * nlivarot
+ *
+ * Created by fred on Sat Jul 19 2003.
+ *
+ */
+
+#include "Shape.h"
+
+#include "livarot/float-line.h"
+#include "AlphaLigne.h"
+#include "BitLigne.h"
+
+#include "livarot/sweep-event-queue.h"
+#include "livarot/sweep-tree-list.h"
+#include "livarot/sweep-tree.h"
+
+/*
+ * polygon rasterization: the sweepline algorithm in all its glory
+ * nothing unusual in this implementation, so nothing special to say
+ * the *Quick*() functions are not useful. forget about them
+ */
+
+void Shape::BeginRaster(float &pos, int &curPt)
+{
+ if ( numberOfPoints() <= 1 || numberOfEdges() <= 1 ) {
+ curPt = 0;
+ pos = 0;
+ return;
+ }
+
+ MakeRasterData(true);
+ MakePointData(true);
+ MakeEdgeData(true);
+
+ if (sTree == nullptr) {
+ sTree = new SweepTreeList(numberOfEdges());
+ }
+ if (sEvts == nullptr) {
+ sEvts = new SweepEventQueue(numberOfEdges());
+ }
+
+ SortPoints();
+
+ curPt = 0;
+ pos = getPoint(0).x[1] - 1.0;
+
+ for (int i = 0; i < numberOfPoints(); i++) {
+ pData[i].pending = 0;
+ pData[i].edgeOnLeft = -1;
+ pData[i].nextLinkedPoint = -1;
+ pData[i].rx[0] = /*Round(*/getPoint(i).x[0]/*)*/;
+ pData[i].rx[1] = /*Round(*/getPoint(i).x[1]/*)*/;
+ }
+
+ for (int i = 0;i < numberOfEdges(); i++) {
+ swrData[i].misc = nullptr;
+ eData[i].rdx=pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
+ }
+}
+
+
+void Shape::EndRaster()
+{
+ delete sTree;
+ sTree = nullptr;
+ delete sEvts;
+ sEvts = nullptr;
+
+ MakePointData(false);
+ MakeEdgeData(false);
+ MakeRasterData(false);
+}
+
+
+void Shape::BeginQuickRaster(float &pos, int &curPt)
+{
+ if ( numberOfPoints() <= 1 || numberOfEdges() <= 1 ) {
+ curPt = 0;
+ pos = 0;
+ return;
+ }
+
+ MakeRasterData(true);
+ MakeQuickRasterData(true);
+ nbQRas = 0;
+ firstQRas = lastQRas = -1;
+ MakePointData(true);
+ MakeEdgeData(true);
+
+ curPt = 0;
+ pos = getPoint(0).x[1] - 1.0;
+
+ initialisePointData();
+
+ for (int i=0;i<numberOfEdges();i++) {
+ swrData[i].misc = nullptr;
+ qrsData[i].ind = -1;
+ eData[i].rdx = pData[getEdge(i).en].rx - pData[getEdge(i).st].rx;
+ }
+
+ SortPoints();
+// SortPointsRounded();
+}
+
+
+void Shape::EndQuickRaster()
+{
+ MakePointData(false);
+ MakeEdgeData(false);
+ MakeRasterData(false);
+ MakeQuickRasterData(false);
+}
+
+
+// 2 versions of the Scan() series to move the scanline to a given position withou actually computing coverages
+void Shape::Scan(float &pos, int &curP, float to, float step)
+{
+ if ( numberOfEdges() <= 1 ) {
+ return;
+ }
+
+ if ( pos == to ) {
+ return;
+ }
+
+ enum Direction {
+ DOWNWARDS,
+ UPWARDS
+ };
+
+ Direction const d = (pos < to) ? DOWNWARDS : UPWARDS;
+
+ // points of the polygon are sorted top-down, so we take them in order, starting with the one at index curP,
+ // until we reach the wanted position to.
+ // don't forget to update curP and pos when we're done
+ int curPt = curP;
+ while ( ( d == DOWNWARDS && curPt < numberOfPoints() && getPoint(curPt).x[1] <= to) ||
+ ( d == UPWARDS && curPt > 0 && getPoint(curPt - 1).x[1] >= to) )
+ {
+ int nPt = (d == DOWNWARDS) ? curPt++ : --curPt;
+
+ // treat a new point: remove and add edges incident to it
+ int nbUp;
+ int nbDn;
+ int upNo;
+ int dnNo;
+ _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+
+ if ( d == DOWNWARDS ) {
+ if ( nbDn <= 0 ) {
+ upNo = -1;
+ }
+ if ( upNo >= 0 && swrData[upNo].misc == nullptr ) {
+ upNo = -1;
+ }
+ } else {
+ if ( nbUp <= 0 ) {
+ dnNo = -1;
+ }
+ if ( dnNo >= 0 && swrData[dnNo].misc == nullptr ) {
+ dnNo = -1;
+ }
+ }
+
+ if ( ( d == DOWNWARDS && nbUp > 0 ) || ( d == UPWARDS && nbDn > 0 ) ) {
+ // first remove edges coming from above or below, as appropriate
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( (d == DOWNWARDS && nPt == std::max(e.st, e.en)) ||
+ (d == UPWARDS && nPt == std::min(e.st, e.en)) )
+ {
+ if ( ( d == DOWNWARDS && cb != upNo ) || ( d == UPWARDS && cb != dnNo ) ) {
+ // we salvage the edge upNo to plug the edges we'll be addingat its place
+ // but the other edge don't have this chance
+ SweepTree *node = swrData[cb].misc;
+ if ( node ) {
+ swrData[cb].misc = nullptr;
+ node->Remove(*sTree, *sEvts, true);
+ }
+ }
+ }
+ cb = NextAt(nPt, cb);
+ }
+ }
+
+ // if there is one edge going down and one edge coming from above, we don't Insert() the new edge,
+ // but replace the upNo edge by the new one (faster)
+ SweepTree* insertionNode = nullptr;
+ if ( dnNo >= 0 ) {
+ if ( upNo >= 0 ) {
+ int rmNo=(d == DOWNWARDS) ? upNo:dnNo;
+ int neNo=(d == DOWNWARDS) ? dnNo:upNo;
+ SweepTree* node = swrData[rmNo].misc;
+ swrData[rmNo].misc = nullptr;
+
+ int const P = (d == DOWNWARDS) ? nPt : Other(nPt, neNo);
+ node->ConvertTo(this, neNo, 1, P);
+
+ swrData[neNo].misc = node;
+ insertionNode = node;
+ CreateEdge(neNo, to, step);
+ } else {
+ // always DOWNWARDS
+ SweepTree* node = sTree->add(this, dnNo, 1, nPt, this);
+ swrData[dnNo].misc = node;
+ node->Insert(*sTree, *sEvts, this, nPt, true);
+ //if (d == UPWARDS) {
+ // node->startPoint = Other(nPt, dnNo);
+ //}
+ insertionNode = node;
+ CreateEdge(dnNo,to,step);
+ }
+ } else {
+ if ( upNo >= 0 ) {
+ // always UPWARDS
+ SweepTree* node = sTree->add(this, upNo, 1, nPt, this);
+ swrData[upNo].misc = node;
+ node->Insert(*sTree, *sEvts, this, nPt, true);
+ //if (d == UPWARDS) {
+ node->startPoint = Other(nPt, upNo);
+ //}
+ insertionNode = node;
+ CreateEdge(upNo,to,step);
+ }
+ }
+
+ // add the remaining edges
+ if ( ( d == DOWNWARDS && nbDn > 1 ) || ( d == UPWARDS && nbUp > 1 ) ) {
+ // si nbDn == 1 , alors dnNo a deja ete traite
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::min(e.st, e.en) ) {
+ if ( cb != dnNo && cb != upNo ) {
+ SweepTree *node = sTree->add(this, cb, 1, nPt, this);
+ swrData[cb].misc = node;
+ node->InsertAt(*sTree, *sEvts, this, insertionNode, nPt, true);
+ if (d == UPWARDS) {
+ node->startPoint = Other(nPt, cb);
+ }
+ CreateEdge(cb, to, step);
+ }
+ }
+ cb = NextAt(nPt,cb);
+ }
+ }
+ }
+
+ curP = curPt;
+ if ( curPt > 0 ) {
+ pos = getPoint(curPt - 1).x[1];
+ } else {
+ pos = to;
+ }
+
+ // the final touch: edges intersecting the sweepline must be update so that their intersection with
+ // said sweepline is correct.
+ pos = to;
+ if ( sTree->racine ) {
+ SweepTree* curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
+ while ( curS ) {
+ int cb = curS->bord;
+ AvanceEdge(cb, to, true, step);
+ curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
+ }
+ }
+}
+
+
+
+void Shape::QuickScan(float &pos,int &curP, float to, bool /*doSort*/, float step)
+{
+ if ( numberOfEdges() <= 1 ) {
+ return;
+ }
+
+ if ( pos == to ) {
+ return;
+ }
+
+ enum Direction {
+ DOWNWARDS,
+ UPWARDS
+ };
+
+ Direction const d = (pos < to) ? DOWNWARDS : UPWARDS;
+
+ int curPt = curP;
+ while ( (d == DOWNWARDS && curPt < numberOfPoints() && getPoint(curPt ).x[1] <= to) ||
+ (d == UPWARDS && curPt > 0 && getPoint(curPt - 1).x[1] >= to) )
+ {
+ int nPt = (d == DOWNWARDS) ? curPt++ : --curPt;
+
+ int nbUp;
+ int nbDn;
+ int upNo;
+ int dnNo;
+ _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+
+ if ( nbDn <= 0 ) {
+ upNo = -1;
+ }
+ if ( upNo >= 0 && swrData[upNo].misc == nullptr ) {
+ upNo = -1;
+ }
+
+ if ( nbUp > 0 ) {
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( (d == DOWNWARDS && nPt == std::max(e.st, e.en)) ||
+ (d == UPWARDS && nPt == std::min(e.st, e.en)) )
+ {
+ if ( cb != upNo ) {
+ QuickRasterSubEdge(cb);
+ }
+ }
+ cb = NextAt(nPt,cb);
+ }
+ }
+
+ // traitement du "upNo devient dnNo"
+ int ins_guess = -1;
+ if ( dnNo >= 0 ) {
+ if ( upNo >= 0 ) {
+ ins_guess = QuickRasterChgEdge(upNo, dnNo, getPoint(nPt).x[0]);
+ } else {
+ ins_guess = QuickRasterAddEdge(dnNo, getPoint(nPt).x[0], ins_guess);
+ }
+ CreateEdge(dnNo, to, step);
+ }
+
+ if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( (d == DOWNWARDS && nPt == std::min(e.st, e.en)) ||
+ (d == UPWARDS && nPt == std::max(e.st, e.en)) )
+ {
+ if ( cb != dnNo ) {
+ ins_guess = QuickRasterAddEdge(cb, getPoint(nPt).x[0], ins_guess);
+ CreateEdge(cb, to, step);
+ }
+ }
+ cb = NextAt(nPt,cb);
+ }
+ }
+
+
+ curP = curPt;
+ if ( curPt > 0 ) {
+ pos = getPoint(curPt-1).x[1];
+ } else {
+ pos = to;
+ }
+ }
+
+ pos = to;
+
+ for (int i=0; i < nbQRas; i++) {
+ int cb = qrsData[i].bord;
+ AvanceEdge(cb, to, true, step);
+ qrsData[i].x=swrData[cb].curX;
+ }
+
+ QuickRasterSort();
+}
+
+
+
+int Shape::QuickRasterChgEdge(int oBord, int nBord, double x)
+{
+ if ( oBord == nBord ) {
+ return -1;
+ }
+
+ int no = qrsData[oBord].ind;
+ if ( no >= 0 ) {
+ qrsData[no].bord = nBord;
+ qrsData[no].x = x;
+ qrsData[oBord].ind = -1;
+ qrsData[nBord].ind = no;
+ }
+
+ return no;
+}
+
+
+
+int Shape::QuickRasterAddEdge(int bord, double x, int guess)
+{
+ int no = nbQRas++;
+ qrsData[no].bord = bord;
+ qrsData[no].x = x;
+ qrsData[bord].ind = no;
+ qrsData[no].prev = -1;
+ qrsData[no].next = -1;
+
+ if ( no < 0 || no >= nbQRas ) {
+ return -1;
+ }
+
+ if ( firstQRas < 0 ) {
+ firstQRas = lastQRas = no;
+ qrsData[no].prev = -1;
+ qrsData[no].next = -1;
+ return no;
+ }
+
+ if ( guess < 0 || guess >= nbQRas ) {
+
+ int c = firstQRas;
+ while ( c >= 0 && c < nbQRas && CmpQRs(qrsData[c],qrsData[no]) < 0 ) {
+ c = qrsData[c].next;
+ }
+
+ if ( c < 0 || c >= nbQRas ) {
+ qrsData[no].prev = lastQRas;
+ qrsData[lastQRas].next = no;
+ lastQRas = no;
+ } else {
+ qrsData[no].prev = qrsData[c].prev;
+ if ( qrsData[no].prev >= 0 ) {
+ qrsData[qrsData[no].prev].next=no;
+ } else {
+ firstQRas = no;
+ }
+
+ qrsData[no].next = c;
+ qrsData[c].prev = no;
+ }
+
+ } else {
+ int c = guess;
+ int stTst = CmpQRs(qrsData[c],qrsData[no]);
+ if ( stTst == 0 ) {
+
+ qrsData[no].prev = qrsData[c].prev;
+ if ( qrsData[no].prev >= 0 ) {
+ qrsData[qrsData[no].prev].next = no;
+ } else {
+ firstQRas = no;
+ }
+
+ qrsData[no].next = c;
+ qrsData[c].prev = no;
+
+ } else if ( stTst > 0 ) {
+
+ while ( c >= 0 && c < nbQRas && CmpQRs(qrsData[c],qrsData[no]) > 0 ) {
+ c = qrsData[c].prev;
+ }
+
+ if ( c < 0 || c >= nbQRas ) {
+ qrsData[no].next = firstQRas;
+ qrsData[firstQRas].prev = no; // firstQRas != -1
+ firstQRas = no;
+ } else {
+ qrsData[no].next = qrsData[c].next;
+ if ( qrsData[no].next >= 0 ) {
+ qrsData[qrsData[no].next].prev = no;
+ } else {
+ lastQRas = no;
+ }
+ qrsData[no].prev = c;
+ qrsData[c].next = no;
+ }
+
+ } else {
+
+ while ( c >= 0 && c < nbQRas && CmpQRs(qrsData[c],qrsData[no]) < 0 ) {
+ c = qrsData[c].next;
+ }
+
+ if ( c < 0 || c >= nbQRas ) {
+ qrsData[no].prev = lastQRas;
+ qrsData[lastQRas].next = no;
+ lastQRas = no;
+ } else {
+ qrsData[no].prev = qrsData[c].prev;
+ if ( qrsData[no].prev >= 0 ) {
+ qrsData[qrsData[no].prev].next = no;
+ } else {
+ firstQRas = no;
+ }
+
+ qrsData[no].next = c;
+ qrsData[c].prev = no;
+ }
+ }
+ }
+
+ return no;
+}
+
+
+
+void Shape::QuickRasterSubEdge(int bord)
+{
+ int no = qrsData[bord].ind;
+ if ( no < 0 || no >= nbQRas ) {
+ return; // euuhHHH
+ }
+
+ if ( qrsData[no].prev >= 0 ) {
+ qrsData[qrsData[no].prev].next=qrsData[no].next;
+ }
+
+ if ( qrsData[no].next >= 0 ) {
+ qrsData[qrsData[no].next].prev = qrsData[no].prev;
+ }
+
+ if ( no == firstQRas ) {
+ firstQRas = qrsData[no].next;
+ }
+
+ if ( no == lastQRas ) {
+ lastQRas = qrsData[no].prev;
+ }
+
+ qrsData[no].prev = qrsData[no].next = -1;
+
+ int savInd = qrsData[no].ind;
+ qrsData[no] = qrsData[--nbQRas];
+ qrsData[no].ind = savInd;
+ qrsData[qrsData[no].bord].ind = no;
+ qrsData[bord].ind = -1;
+
+ if ( nbQRas > 0 ) {
+ if ( firstQRas == nbQRas ) {
+ firstQRas = no;
+ }
+ if ( lastQRas == nbQRas ) {
+ lastQRas = no;
+ }
+ if ( qrsData[no].prev >= 0 ) {
+ qrsData[qrsData[no].prev].next = no;
+ }
+ if ( qrsData[no].next >= 0 ) {
+ qrsData[qrsData[no].next].prev = no;
+ }
+ }
+}
+
+
+
+void Shape::QuickRasterSwapEdge(int a, int b)
+{
+ if ( a == b ) {
+ return;
+ }
+
+ int na = qrsData[a].ind;
+ int nb = qrsData[b].ind;
+ if ( na < 0 || na >= nbQRas || nb < 0 || nb >= nbQRas ) {
+ return; // errrm
+ }
+
+ qrsData[na].bord = b;
+ qrsData[nb].bord = a;
+ qrsData[a].ind = nb;
+ qrsData[b].ind = na;
+
+ double swd = qrsData[na].x;
+ qrsData[na].x = qrsData[nb].x;
+ qrsData[nb].x = swd;
+}
+
+
+void Shape::QuickRasterSort()
+{
+ if ( nbQRas <= 1 ) {
+ return;
+ }
+
+ int cb = qrsData[firstQRas].bord;
+
+ while ( cb >= 0 ) {
+ int bI = qrsData[cb].ind;
+ int nI = qrsData[bI].next;
+
+ if ( nI < 0 ) {
+ break;
+ }
+
+ int ncb = qrsData[nI].bord;
+ if ( CmpQRs(qrsData[nI], qrsData[bI]) < 0 ) {
+ QuickRasterSwapEdge(cb, ncb);
+ int pI = qrsData[bI].prev; // ca reste bI, puisqu'on a juste echange les contenus
+ if ( pI < 0 ) {
+ cb = ncb; // en fait inutile; mais bon...
+ } else {
+ int pcb = qrsData[pI].bord;
+ cb = pcb;
+ }
+ } else {
+ cb = ncb;
+ }
+ }
+}
+
+
+// direct scan to a given position. goes through the edge list to keep only the ones intersecting the target sweepline
+// good for initial setup of scanline algo, bad for incremental changes
+void Shape::DirectScan(float &pos, int &curP, float to, float step)
+{
+ if ( numberOfEdges() <= 1 ) {
+ return;
+ }
+
+ if ( pos == to ) {
+ return;
+ }
+
+ if ( pos < to ) {
+ // we're moving downwards
+ // points of the polygon are sorted top-down, so we take them in order, starting with the one at index curP,
+ // until we reach the wanted position to.
+ // don't forget to update curP and pos when we're done
+ int curPt = curP;
+ while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
+ curPt++;
+ }
+
+ for (int i=0;i<numberOfEdges();i++) {
+ if ( swrData[i].misc ) {
+ SweepTree* node = swrData[i].misc;
+ swrData[i].misc = nullptr;
+ node->Remove(*sTree, *sEvts, true);
+ }
+ }
+
+ for (int i=0; i < numberOfEdges(); i++) {
+ Shape::dg_arete const &e = getEdge(i);
+ if ( ( e.st < curPt && e.en >= curPt ) || ( e.en < curPt && e.st >= curPt )) {
+ // crosses sweepline
+ int nPt = (e.st < curPt) ? e.st : e.en;
+ SweepTree* node = sTree->add(this, i, 1, nPt, this);
+ swrData[i].misc = node;
+ node->Insert(*sTree, *sEvts, this, nPt, true);
+ CreateEdge(i, to, step);
+ }
+ }
+
+ curP = curPt;
+ if ( curPt > 0 ) {
+ pos = getPoint(curPt - 1).x[1];
+ } else {
+ pos = to;
+ }
+
+ } else {
+
+ // same thing, but going up. so the sweepSens is inverted for the Find() function
+ int curPt=curP;
+ while ( curPt > 0 && getPoint(curPt-1).x[1] >= to ) {
+ curPt--;
+ }
+
+ for (int i = 0; i < numberOfEdges(); i++) {
+ if ( swrData[i].misc ) {
+ SweepTree* node = swrData[i].misc;
+ swrData[i].misc = nullptr;
+ node->Remove(*sTree, *sEvts, true);
+ }
+ }
+
+ for (int i=0;i<numberOfEdges();i++) {
+ Shape::dg_arete const &e = getEdge(i);
+ if ( ( e.st > curPt - 1 && e.en <= curPt - 1 ) || ( e.en > curPt - 1 && e.st <= curPt - 1 )) {
+ // crosses sweepline
+ int nPt = (e.st > curPt) ? e.st : e.en;
+ SweepTree* node = sTree->add(this, i, 1, nPt, this);
+ swrData[i].misc = node;
+ node->Insert(*sTree, *sEvts, this, nPt, false);
+ node->startPoint = Other(nPt, i);
+ CreateEdge(i, to, step);
+ }
+ }
+
+ curP = curPt;
+ if ( curPt > 0 ) {
+ pos = getPoint(curPt - 1).x[1];
+ } else {
+ pos = to;
+ }
+ }
+
+ // the final touch: edges intersecting the sweepline must be update so that their intersection with
+ // said sweepline is correct.
+ pos = to;
+ if ( sTree->racine ) {
+ SweepTree* curS=static_cast<SweepTree*>(sTree->racine->Leftmost());
+ while ( curS ) {
+ int cb = curS->bord;
+ AvanceEdge(cb, to, true, step);
+ curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
+ }
+ }
+}
+
+
+
+void Shape::DirectQuickScan(float &pos, int &curP, float to, bool /*doSort*/, float step)
+{
+ if ( numberOfEdges() <= 1 ) {
+ return;
+ }
+
+ if ( pos == to ) {
+ return;
+ }
+
+ if ( pos < to ) {
+ // we're moving downwards
+ // points of the polygon are sorted top-down, so we take them in order, starting with the one at index curP,
+ // until we reach the wanted position to.
+ // don't forget to update curP and pos when we're done
+ int curPt=curP;
+ while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
+ curPt++;
+ }
+
+ for (int i = 0; i < numberOfEdges(); i++) {
+ if ( qrsData[i].ind < 0 ) {
+ QuickRasterSubEdge(i);
+ }
+ }
+
+ for (int i = 0; i < numberOfEdges(); i++) {
+ Shape::dg_arete const &e = getEdge(i);
+ if ( ( e.st < curPt && e.en >= curPt ) || ( e.en < curPt && e.st >= curPt )) {
+ // crosses sweepline
+ int nPt = (e.st < e.en) ? e.st : e.en;
+ QuickRasterAddEdge(i, getPoint(nPt).x[0], -1);
+ CreateEdge(i, to, step);
+ }
+ }
+
+ curP = curPt;
+ if ( curPt > 0 ) {
+ pos=getPoint(curPt-1).x[1];
+ } else {
+ pos = to;
+ }
+
+ } else {
+
+ // same thing, but going up. so the sweepSens is inverted for the Find() function
+ int curPt=curP;
+ while ( curPt > 0 && getPoint(curPt-1).x[1] >= to ) {
+ curPt--;
+ }
+
+ for (int i = 0; i < numberOfEdges(); i++) {
+ if ( qrsData[i].ind < 0 ) {
+ QuickRasterSubEdge(i);
+ }
+ }
+
+ for (int i=0;i<numberOfEdges();i++) {
+ Shape::dg_arete const &e = getEdge(i);
+ if ( ( e.st < curPt-1 && e.en >= curPt-1 ) || ( e.en < curPt-1 && e.st >= curPt-1 )) {
+ // crosses sweepline
+ int nPt = (e.st > e.en) ? e.st : e.en;
+ QuickRasterAddEdge(i, getPoint(nPt).x[0], -1);
+ CreateEdge(i, to, step);
+ }
+ }
+
+ curP = curPt;
+ if ( curPt > 0 ) {
+ pos = getPoint(curPt-1).x[1];
+ } else {
+ pos = to;
+ }
+
+ }
+
+ pos = to;
+ for (int i = 0; i < nbQRas; i++) {
+ int cb = qrsData[i].bord;
+ AvanceEdge(cb, to, true, step);
+ qrsData[i].x = swrData[cb].curX;
+ }
+
+ QuickRasterSort();
+}
+
+
+// scan and compute coverage, FloatLigne version coverage of the line is bult in 2 parts: first a
+// set of rectangles of height the height of the line (here: "step") one rectangle for each portion
+// of the sweepline that is in the polygon at the beginning of the scan. then a set ot trapezoids
+// are added or removed to these rectangles, one trapezoid for each edge destroyed or edge crossing
+// the entire line. think of it as a refinement of the coverage by rectangles
+
+void Shape::Scan(float &pos, int &curP, float to, FloatLigne *line, bool exact, float step)
+{
+ if ( numberOfEdges() <= 1 ) {
+ return;
+ }
+
+ if ( pos >= to ) {
+ return;
+ }
+
+ // first step: the rectangles since we read the sweepline left to right, we know the
+ // boundaries of the rectangles are appended in a list, hence the AppendBord(). we salvage
+ // the guess value for the trapezoids the edges will induce
+
+ if ( sTree->racine ) {
+ SweepTree *curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
+ while ( curS ) {
+
+ int lastGuess = -1;
+ int cb = curS->bord;
+
+ if ( swrData[cb].sens == false && curS->elem[LEFT] ) {
+
+ int lb = (static_cast<SweepTree*>(curS->elem[LEFT]))->bord;
+
+ lastGuess = line->AppendBord(swrData[lb].curX,
+ to - swrData[lb].curY,
+ swrData[cb].curX,
+ to - swrData[cb].curY,0.0);
+
+ swrData[lb].guess = lastGuess - 1;
+ swrData[cb].guess = lastGuess;
+ } else {
+ int lb = curS->bord;
+ swrData[lb].guess = -1;
+ }
+
+ curS=static_cast <SweepTree*> (curS->elem[RIGHT]);
+ }
+ }
+
+ int curPt = curP;
+ while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
+
+ int nPt = curPt++;
+
+ // same thing as the usual Scan(), just with a hardcoded "indegree+outdegree=2" case, since
+ // it's the most common one
+
+ int nbUp;
+ int nbDn;
+ int upNo;
+ int dnNo;
+ if ( getPoint(nPt).totalDegree() == 2 ) {
+ _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+ } else {
+ _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+ }
+
+ if ( nbDn <= 0 ) {
+ upNo = -1;
+ }
+ if ( upNo >= 0 && swrData[upNo].misc == nullptr ) {
+ upNo = -1;
+ }
+
+ if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::max(e.st, e.en) ) {
+ if ( cb != upNo ) {
+ SweepTree* node = swrData[cb].misc;
+ if ( node ) {
+ _updateIntersection(cb, nPt);
+ // create trapezoid for the chunk of edge intersecting with the line
+ DestroyEdge(cb, to, line);
+ node->Remove(*sTree, *sEvts, true);
+ }
+ }
+ }
+
+ cb = NextAt(nPt,cb);
+ }
+ }
+
+ // traitement du "upNo devient dnNo"
+ SweepTree *insertionNode = nullptr;
+ if ( dnNo >= 0 ) {
+ if ( upNo >= 0 ) {
+ SweepTree* node = swrData[upNo].misc;
+ _updateIntersection(upNo, nPt);
+ DestroyEdge(upNo, to, line);
+
+ node->ConvertTo(this, dnNo, 1, nPt);
+
+ swrData[dnNo].misc = node;
+ insertionNode = node;
+ CreateEdge(dnNo, to, step);
+ swrData[dnNo].guess = swrData[upNo].guess;
+ } else {
+ SweepTree *node = sTree->add(this, dnNo, 1, nPt, this);
+ swrData[dnNo].misc = node;
+ node->Insert(*sTree, *sEvts, this, nPt, true);
+ insertionNode = node;
+ CreateEdge(dnNo, to, step);
+ }
+ }
+
+ if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::min(e.st, e.en) ) {
+ if ( cb != dnNo ) {
+ SweepTree *node = sTree->add(this, cb, 1, nPt, this);
+ swrData[cb].misc = node;
+ node->InsertAt(*sTree, *sEvts, this, insertionNode, nPt, true);
+ CreateEdge(cb, to, step);
+ }
+ }
+ cb = NextAt(nPt,cb);
+ }
+ }
+ }
+
+ curP = curPt;
+ if ( curPt > 0 ) {
+ pos = getPoint(curPt - 1).x[1];
+ } else {
+ pos = to;
+ }
+
+ // update intersections with the sweepline, and add trapezoids for edges crossing the line
+ pos = to;
+ if ( sTree->racine ) {
+ SweepTree* curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
+ while ( curS ) {
+ int cb = curS->bord;
+ AvanceEdge(cb, to, line, exact, step);
+ curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
+ }
+ }
+}
+
+
+
+
+void Shape::Scan(float &pos, int &curP, float to, FillRule directed, BitLigne *line, bool exact, float step)
+{
+ if ( numberOfEdges() <= 1 ) {
+ return;
+ }
+
+ if ( pos >= to ) {
+ return;
+ }
+
+ if ( sTree->racine ) {
+ int curW = 0;
+ float lastX = 0;
+ SweepTree* curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
+
+ if ( directed == fill_oddEven ) {
+
+ while ( curS ) {
+ int cb = curS->bord;
+ curW++;
+ curW &= 0x00000001;
+ if ( curW == 0 ) {
+ line->AddBord(lastX,swrData[cb].curX,true);
+ } else {
+ lastX = swrData[cb].curX;
+ }
+ curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
+ }
+
+ } else if ( directed == fill_positive ) {
+
+ // doesn't behave correctly; no way i know to do this without a ConvertToShape()
+ while ( curS ) {
+ int cb = curS->bord;
+ int oW = curW;
+ if ( swrData[cb].sens ) {
+ curW++;
+ } else {
+ curW--;
+ }
+
+ if ( curW <= 0 && oW > 0) {
+ line->AddBord(lastX, swrData[cb].curX, true);
+ } else if ( curW > 0 && oW <= 0 ) {
+ lastX = swrData[cb].curX;
+ }
+
+ curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
+ }
+
+ } else if ( directed == fill_nonZero ) {
+
+ while ( curS ) {
+ int cb = curS->bord;
+ int oW = curW;
+ if ( swrData[cb].sens ) {
+ curW++;
+ } else {
+ curW--;
+ }
+
+ if ( curW == 0 && oW != 0) {
+ line->AddBord(lastX,swrData[cb].curX,true);
+ } else if ( curW != 0 && oW == 0 ) {
+ lastX=swrData[cb].curX;
+ }
+ curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
+ }
+ }
+
+ }
+
+ int curPt = curP;
+ while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
+ int nPt = curPt++;
+
+ int cb;
+ int nbUp;
+ int nbDn;
+ int upNo;
+ int dnNo;
+
+ if ( getPoint(nPt).totalDegree() == 2 ) {
+ _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+ } else {
+ _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+ }
+
+ if ( nbDn <= 0 ) {
+ upNo = -1;
+ }
+ if ( upNo >= 0 && swrData[upNo].misc == nullptr ) {
+ upNo = -1;
+ }
+
+ if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::max(e.st, e.en) ) {
+ if ( cb != upNo ) {
+ SweepTree* node=swrData[cb].misc;
+ if ( node ) {
+ _updateIntersection(cb, nPt);
+ DestroyEdge(cb, line);
+ node->Remove(*sTree,*sEvts,true);
+ }
+ }
+ }
+ cb = NextAt(nPt,cb);
+ }
+ }
+
+ // traitement du "upNo devient dnNo"
+ SweepTree* insertionNode = nullptr;
+ if ( dnNo >= 0 ) {
+ if ( upNo >= 0 ) {
+ SweepTree* node = swrData[upNo].misc;
+ _updateIntersection(upNo, nPt);
+ DestroyEdge(upNo, line);
+
+ node->ConvertTo(this, dnNo, 1, nPt);
+
+ swrData[dnNo].misc = node;
+ insertionNode = node;
+ CreateEdge(dnNo, to, step);
+
+ } else {
+
+ SweepTree* node = sTree->add(this,dnNo,1,nPt,this);
+ swrData[dnNo].misc = node;
+ node->Insert(*sTree, *sEvts, this, nPt, true);
+ insertionNode = node;
+ CreateEdge(dnNo, to, step);
+ }
+ }
+
+ if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
+ cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::min(e.st, e.en) ) {
+ if ( cb != dnNo ) {
+ SweepTree* node = sTree->add(this, cb, 1, nPt, this);
+ swrData[cb].misc = node;
+ node->InsertAt(*sTree, *sEvts, this, insertionNode, nPt, true);
+ CreateEdge(cb, to, step);
+ }
+ }
+ cb = NextAt(nPt, cb);
+ }
+ }
+ }
+
+ curP = curPt;
+ if ( curPt > 0 ) {
+ pos = getPoint(curPt - 1).x[1];
+ } else {
+ pos = to;
+ }
+
+ pos = to;
+ if ( sTree->racine ) {
+ SweepTree* curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
+ while ( curS ) {
+ int cb = curS->bord;
+ AvanceEdge(cb, to, line, exact, step);
+ curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
+ }
+ }
+}
+
+
+void Shape::Scan(float &pos, int &curP, float to, AlphaLigne *line, bool exact, float step)
+{
+ if ( numberOfEdges() <= 1 ) {
+ return;
+ }
+
+ if ( pos >= to ) {
+ return;
+ }
+
+ int curPt = curP;
+ while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
+ int nPt = curPt++;
+
+ int nbUp;
+ int nbDn;
+ int upNo;
+ int dnNo;
+ if ( getPoint(nPt).totalDegree() == 2 ) {
+ _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+ } else {
+ _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+ }
+
+ if ( nbDn <= 0 ) {
+ upNo=-1;
+ }
+ if ( upNo >= 0 && swrData[upNo].misc == nullptr ) {
+ upNo=-1;
+ }
+
+ if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::max(e.st, e.en) ) {
+ if ( cb != upNo ) {
+ SweepTree* node = swrData[cb].misc;
+ if ( node ) {
+ _updateIntersection(cb, nPt);
+ DestroyEdge(cb, line);
+ node->Remove(*sTree, *sEvts, true);
+ }
+ }
+ }
+
+ cb = NextAt(nPt,cb);
+ }
+ }
+
+ // traitement du "upNo devient dnNo"
+ SweepTree* insertionNode = nullptr;
+ if ( dnNo >= 0 ) {
+ if ( upNo >= 0 ) {
+ SweepTree* node = swrData[upNo].misc;
+ _updateIntersection(upNo, nPt);
+ DestroyEdge(upNo, line);
+
+ node->ConvertTo(this, dnNo, 1, nPt);
+
+ swrData[dnNo].misc = node;
+ insertionNode = node;
+ CreateEdge(dnNo, to, step);
+ swrData[dnNo].guess = swrData[upNo].guess;
+ } else {
+ SweepTree* node = sTree->add(this, dnNo, 1, nPt, this);
+ swrData[dnNo].misc = node;
+ node->Insert(*sTree, *sEvts, this, nPt, true);
+ insertionNode = node;
+ CreateEdge(dnNo, to, step);
+ }
+ }
+
+ if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::min(e.st, e.en) ) {
+ if ( cb != dnNo ) {
+ SweepTree* node = sTree->add(this, cb, 1, nPt, this);
+ swrData[cb].misc = node;
+ node->InsertAt(*sTree, *sEvts, this, insertionNode, nPt, true);
+ CreateEdge(cb, to, step);
+ }
+ }
+ cb = NextAt(nPt,cb);
+ }
+ }
+ }
+
+ curP = curPt;
+ if ( curPt > 0 ) {
+ pos = getPoint(curPt - 1).x[1];
+ } else {
+ pos = to;
+ }
+
+ pos = to;
+ if ( sTree->racine ) {
+ SweepTree* curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
+ while ( curS ) {
+ int cb = curS->bord;
+ AvanceEdge(cb, to, line, exact, step);
+ curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
+ }
+ }
+}
+
+
+
+void Shape::QuickScan(float &pos, int &curP, float to, FloatLigne* line, float step)
+{
+ if ( numberOfEdges() <= 1 ) {
+ return;
+ }
+
+ if ( pos >= to ) {
+ return;
+ }
+
+ if ( nbQRas > 1 ) {
+ int curW = 0;
+ // float lastX = 0;
+ // float lastY = 0;
+ int lastGuess = -1;
+ int lastB = -1;
+
+ for (int i = firstQRas; i >= 0 && i < nbQRas; i = qrsData[i].next) {
+ int cb = qrsData[i].bord;
+ int oW = curW;
+ if ( swrData[cb].sens ) {
+ curW++;
+ } else {
+ curW--;
+ }
+
+ if ( curW % 2 == 0 && oW % 2 != 0) {
+
+ lastGuess = line->AppendBord(swrData[lastB].curX,
+ to - swrData[lastB].curY,
+ swrData[cb].curX,
+ to - swrData[cb].curY,
+ 0.0);
+
+ swrData[cb].guess = lastGuess;
+ if ( lastB >= 0 ) {
+ swrData[lastB].guess = lastGuess - 1;
+ }
+
+ } else if ( curW%2 != 0 && oW%2 == 0 ) {
+
+ // lastX = swrData[cb].curX;
+ // lastY = swrData[cb].curY;
+ lastB = cb;
+ swrData[cb].guess = -1;
+
+ } else {
+ swrData[cb].guess = -1;
+ }
+ }
+ }
+
+ int curPt = curP;
+ while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
+ int nPt = curPt++;
+
+ int nbUp;
+ int nbDn;
+ int upNo;
+ int dnNo;
+ if ( getPoint(nPt).totalDegree() == 2 ) {
+ _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+ } else {
+ _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+ }
+
+ if ( nbDn <= 0 ) {
+ upNo = -1;
+ }
+ if ( upNo >= 0 && swrData[upNo].misc == nullptr ) {
+ upNo = -1;
+ }
+
+ if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::max(e.st, e.en) ) {
+ if ( cb != upNo ) {
+ QuickRasterSubEdge(cb);
+ _updateIntersection(cb, nPt);
+ DestroyEdge(cb, to, line);
+ }
+ }
+ cb = NextAt(nPt, cb);
+ }
+ }
+
+ // traitement du "upNo devient dnNo"
+ int ins_guess=-1;
+ if ( dnNo >= 0 ) {
+ if ( upNo >= 0 ) {
+ ins_guess = QuickRasterChgEdge(upNo ,dnNo, getPoint(nPt).x[0]);
+ _updateIntersection(upNo, nPt);
+ DestroyEdge(upNo, to, line);
+
+ CreateEdge(dnNo, to, step);
+ swrData[dnNo].guess = swrData[upNo].guess;
+ } else {
+ ins_guess = QuickRasterAddEdge(dnNo, getPoint(nPt).x[0], ins_guess);
+ CreateEdge(dnNo, to, step);
+ }
+ }
+
+ if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::min(e.st, e.en) ) {
+ if ( cb != dnNo ) {
+ ins_guess = QuickRasterAddEdge(cb, getPoint(nPt).x[0], ins_guess);
+ CreateEdge(cb, to, step);
+ }
+ }
+ cb = NextAt(nPt, cb);
+ }
+ }
+ }
+
+ curP = curPt;
+ if ( curPt > 0 ) {
+ pos = getPoint(curPt-1).x[1];
+ } else {
+ pos=to;
+ }
+
+ pos = to;
+ for (int i=0; i < nbQRas; i++) {
+ int cb = qrsData[i].bord;
+ AvanceEdge(cb, to, line, true, step);
+ qrsData[i].x = swrData[cb].curX;
+ }
+
+ QuickRasterSort();
+}
+
+
+
+
+void Shape::QuickScan(float &pos, int &curP, float to, FillRule directed, BitLigne* line, float step)
+{
+ if ( numberOfEdges() <= 1 ) {
+ return;
+ }
+
+ if ( pos >= to ) {
+ return;
+ }
+
+ if ( nbQRas > 1 ) {
+ int curW = 0;
+ float lastX = 0;
+
+ if ( directed == fill_oddEven ) {
+
+ for (int i = firstQRas; i >= 0 && i < nbQRas; i = qrsData[i].next) {
+ int cb = qrsData[i].bord;
+ curW++;
+ curW &= 1;
+ if ( curW == 0 ) {
+ line->AddBord(lastX, swrData[cb].curX, true);
+ } else {
+ lastX = swrData[cb].curX;
+ }
+ }
+
+ } else if ( directed == fill_positive ) {
+ // doesn't behave correctly; no way i know to do this without a ConvertToShape()
+ for (int i = firstQRas; i >= 0 && i < nbQRas; i = qrsData[i].next) {
+ int cb = qrsData[i].bord;
+ int oW = curW;
+ if ( swrData[cb].sens ) {
+ curW++;
+ } else {
+ curW--;
+ }
+
+ if ( curW <= 0 && oW > 0) {
+ line->AddBord(lastX, swrData[cb].curX, true);
+ } else if ( curW > 0 && oW <= 0 ) {
+ lastX = swrData[cb].curX;
+ }
+ }
+
+ } else if ( directed == fill_nonZero ) {
+ for (int i = firstQRas; i >= 0 && i < nbQRas; i = qrsData[i].next) {
+ int cb = qrsData[i].bord;
+ int oW = curW;
+ if ( swrData[cb].sens ) {
+ curW++;
+ } else {
+ curW--;
+ }
+
+ if ( curW == 0 && oW != 0) {
+ line->AddBord(lastX, swrData[cb].curX, true);
+ } else if ( curW != 0 && oW == 0 ) {
+ lastX = swrData[cb].curX;
+ }
+ }
+ }
+ }
+
+ int curPt = curP;
+ while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
+ int nPt = curPt++;
+
+ int nbUp;
+ int nbDn;
+ int upNo;
+ int dnNo;
+ if ( getPoint(nPt).totalDegree() == 2 ) {
+ _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+ } else {
+ _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+ }
+
+ if ( nbDn <= 0 ) {
+ upNo = -1;
+ }
+
+ if ( upNo >= 0 && swrData[upNo].misc == nullptr ) {
+ upNo = -1;
+ }
+
+ if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::max(e.st, e.en) ) {
+ if ( cb != upNo ) {
+ QuickRasterSubEdge(cb);
+ _updateIntersection(cb, nPt);
+ DestroyEdge(cb, line);
+ }
+ }
+ cb = NextAt(nPt, cb);
+ }
+ }
+
+ // traitement du "upNo devient dnNo"
+ int ins_guess = -1;
+ if ( dnNo >= 0 ) {
+ if ( upNo >= 0 ) {
+ ins_guess = QuickRasterChgEdge(upNo, dnNo, getPoint(nPt).x[0]);
+ _updateIntersection(upNo, nPt);
+ DestroyEdge(upNo, line);
+
+ CreateEdge(dnNo, to, step);
+ } else {
+ ins_guess = QuickRasterAddEdge(dnNo, getPoint(nPt).x[0], ins_guess);
+ CreateEdge(dnNo, to, step);
+ }
+ }
+
+ if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::min(e.st, e.en) ) {
+ if ( cb != dnNo ) {
+ ins_guess = QuickRasterAddEdge(cb, getPoint(nPt).x[0], ins_guess);
+ CreateEdge(cb, to, step);
+ }
+ }
+ cb = NextAt(nPt,cb);
+ }
+ }
+ }
+
+ curP = curPt;
+ if ( curPt > 0 ) {
+ pos=getPoint(curPt - 1).x[1];
+ } else {
+ pos = to;
+ }
+
+ pos = to;
+ for (int i = 0; i < nbQRas; i++) {
+ int cb = qrsData[i].bord;
+ AvanceEdge(cb, to, line, true, step);
+ qrsData[i].x = swrData[cb].curX;
+ }
+
+ QuickRasterSort();
+}
+
+
+
+void Shape::QuickScan(float &pos, int &curP, float to, AlphaLigne* line, float step)
+{
+ if ( numberOfEdges() <= 1 ) {
+ return;
+ }
+ if ( pos >= to ) {
+ return;
+ }
+
+ int curPt = curP;
+ while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
+ int nPt = curPt++;
+
+ int nbUp;
+ int nbDn;
+ int upNo;
+ int dnNo;
+ if ( getPoint(nPt).totalDegree() == 2 ) {
+ _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+ } else {
+ _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
+ }
+
+ if ( nbDn <= 0 ) {
+ upNo = -1;
+ }
+ if ( upNo >= 0 && swrData[upNo].misc == nullptr ) {
+ upNo = -1;
+ }
+
+ if ( nbUp > 1 || ( nbUp == 1 && upNo < 0 ) ) {
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::max(e.st, e.en) ) {
+ if ( cb != upNo ) {
+ QuickRasterSubEdge(cb);
+ _updateIntersection(cb, nPt);
+ DestroyEdge(cb, line);
+ }
+ }
+ cb = NextAt(nPt,cb);
+ }
+ }
+
+ // traitement du "upNo devient dnNo"
+ int ins_guess = -1;
+ if ( dnNo >= 0 ) {
+ if ( upNo >= 0 ) {
+ ins_guess = QuickRasterChgEdge(upNo, dnNo, getPoint(nPt).x[0]);
+ _updateIntersection(upNo, nPt);
+ DestroyEdge(upNo, line);
+
+ CreateEdge(dnNo, to, step);
+ swrData[dnNo].guess = swrData[upNo].guess;
+ } else {
+ ins_guess = QuickRasterAddEdge(dnNo, getPoint(nPt).x[0], ins_guess);
+ CreateEdge(dnNo, to, step);
+ }
+ }
+
+ if ( nbDn > 1 ) { // si nbDn == 1 , alors dnNo a deja ete traite
+ int cb = getPoint(nPt).incidentEdge[FIRST];
+ while ( cb >= 0 && cb < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(cb);
+ if ( nPt == std::min(e.st, e.en) ) {
+ if ( cb != dnNo ) {
+ ins_guess = QuickRasterAddEdge(cb,getPoint(nPt).x[0], ins_guess);
+ CreateEdge(cb, to, step);
+ }
+ }
+ cb = NextAt(nPt,cb);
+ }
+ }
+ }
+
+ curP = curPt;
+ if ( curPt > 0 ) {
+ pos = getPoint(curPt-1).x[1];
+ } else {
+ pos = to;
+ }
+
+ pos = to;
+ for (int i = 0; i < nbQRas; i++) {
+ int cb = qrsData[i].bord;
+ AvanceEdge(cb, to, line, true, step);
+ qrsData[i].x = swrData[cb].curX;
+ }
+
+ QuickRasterSort();
+}
+
+
+/*
+ * operations de bases pour la rasterization
+ *
+ */
+void Shape::CreateEdge(int no, float to, float step)
+{
+ int cPt;
+ Geom::Point dir;
+ if ( getEdge(no).st < getEdge(no).en ) {
+ cPt = getEdge(no).st;
+ swrData[no].sens = true;
+ dir = getEdge(no).dx;
+ } else {
+ cPt = getEdge(no).en;
+ swrData[no].sens = false;
+ dir = -getEdge(no).dx;
+ }
+
+ swrData[no].lastX = swrData[no].curX = getPoint(cPt).x[0];
+ swrData[no].lastY = swrData[no].curY = getPoint(cPt).x[1];
+
+ if ( fabs(dir[1]) < 0.000001 ) {
+ swrData[no].dxdy = 0;
+ } else {
+ swrData[no].dxdy = dir[0]/dir[1];
+ }
+
+ if ( fabs(dir[0]) < 0.000001 ) {
+ swrData[no].dydx = 0;
+ } else {
+ swrData[no].dydx = dir[1]/dir[0];
+ }
+
+ swrData[no].calcX = swrData[no].curX + (to - step - swrData[no].curY) * swrData[no].dxdy;
+ swrData[no].guess = -1;
+}
+
+
+void Shape::AvanceEdge(int no, float to, bool exact, float step)
+{
+ if ( exact ) {
+ Geom::Point dir;
+ Geom::Point stp;
+ if ( swrData[no].sens ) {
+ stp = getPoint(getEdge(no).st).x;
+ dir = getEdge(no).dx;
+ } else {
+ stp = getPoint(getEdge(no).en).x;
+ dir = -getEdge(no).dx;
+ }
+
+ if ( fabs(dir[1]) < 0.000001 ) {
+ swrData[no].calcX = stp[0] + dir[0];
+ } else {
+ swrData[no].calcX = stp[0] + ((to - stp[1]) * dir[0]) / dir[1];
+ }
+ } else {
+ swrData[no].calcX += step * swrData[no].dxdy;
+ }
+
+ swrData[no].lastX = swrData[no].curX;
+ swrData[no].lastY = swrData[no].curY;
+ swrData[no].curX = swrData[no].calcX;
+ swrData[no].curY = to;
+}
+
+/*
+ * specialisation par type de structure utilise
+ */
+
+void Shape::DestroyEdge(int no, float to, FloatLigne* line)
+{
+ if ( swrData[no].sens ) {
+
+ if ( swrData[no].curX < swrData[no].lastX ) {
+
+ swrData[no].guess = line->AddBordR(swrData[no].curX,
+ to - swrData[no].curY,
+ swrData[no].lastX,
+ to - swrData[no].lastY,
+ -swrData[no].dydx,
+ swrData[no].guess);
+
+ } else if ( swrData[no].curX > swrData[no].lastX ) {
+
+ swrData[no].guess = line->AddBord(swrData[no].lastX,
+ -(to - swrData[no].lastY),
+ swrData[no].curX,
+ -(to - swrData[no].curY),
+ swrData[no].dydx,
+ swrData[no].guess);
+ }
+
+ } else {
+
+ if ( swrData[no].curX < swrData[no].lastX ) {
+
+ swrData[no].guess = line->AddBordR(swrData[no].curX,
+ -(to - swrData[no].curY),
+ swrData[no].lastX,
+ -(to - swrData[no].lastY),
+ swrData[no].dydx,
+ swrData[no].guess);
+
+ } else if ( swrData[no].curX > swrData[no].lastX ) {
+
+ swrData[no].guess = line->AddBord(swrData[no].lastX,
+ to - swrData[no].lastY,
+ swrData[no].curX,
+ to - swrData[no].curY,
+ -swrData[no].dydx,
+ swrData[no].guess);
+ }
+ }
+}
+
+
+
+void Shape::AvanceEdge(int no, float to, FloatLigne *line, bool exact, float step)
+{
+ AvanceEdge(no,to,exact,step);
+
+ if ( swrData[no].sens ) {
+
+ if ( swrData[no].curX < swrData[no].lastX ) {
+
+ swrData[no].guess = line->AddBordR(swrData[no].curX,
+ to - swrData[no].curY,
+ swrData[no].lastX,
+ to - swrData[no].lastY,
+ -swrData[no].dydx,
+ swrData[no].guess);
+
+ } else if ( swrData[no].curX > swrData[no].lastX ) {
+
+ swrData[no].guess = line->AddBord(swrData[no].lastX,
+ -(to - swrData[no].lastY),
+ swrData[no].curX,
+ -(to - swrData[no].curY),
+ swrData[no].dydx,
+ swrData[no].guess);
+ }
+
+ } else {
+
+ if ( swrData[no].curX < swrData[no].lastX ) {
+
+ swrData[no].guess = line->AddBordR(swrData[no].curX,
+ -(to - swrData[no].curY),
+ swrData[no].lastX,
+ -(to - swrData[no].lastY),
+ swrData[no].dydx,
+ swrData[no].guess);
+
+ } else if ( swrData[no].curX > swrData[no].lastX ) {
+
+ swrData[no].guess = line->AddBord(swrData[no].lastX,
+ to - swrData[no].lastY,
+ swrData[no].curX,
+ to - swrData[no].curY,
+ -swrData[no].dydx,
+ swrData[no].guess);
+ }
+ }
+}
+
+
+void Shape::DestroyEdge(int no, BitLigne *line)
+{
+ if ( swrData[no].sens ) {
+
+ if ( swrData[no].curX < swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].curX, swrData[no].lastX, false);
+
+ } else if ( swrData[no].curX > swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].lastX,swrData[no].curX,false);
+ }
+
+ } else {
+
+ if ( swrData[no].curX < swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].curX, swrData[no].lastX, false);
+
+ } else if ( swrData[no].curX > swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].lastX, swrData[no].curX, false);
+
+ }
+ }
+}
+
+
+void Shape::AvanceEdge(int no, float to, BitLigne *line, bool exact, float step)
+{
+ AvanceEdge(no, to, exact, step);
+
+ if ( swrData[no].sens ) {
+
+ if ( swrData[no].curX < swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].curX, swrData[no].lastX, false);
+
+ } else if ( swrData[no].curX > swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].lastX, swrData[no].curX, false);
+ }
+
+ } else {
+
+ if ( swrData[no].curX < swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].curX, swrData[no].lastX, false);
+
+ } else if ( swrData[no].curX > swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].lastX, swrData[no].curX, false);
+ }
+ }
+}
+
+
+void Shape::DestroyEdge(int no, AlphaLigne* line)
+{
+ if ( swrData[no].sens ) {
+
+ if ( swrData[no].curX <= swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].curX,
+ 0,
+ swrData[no].lastX,
+ swrData[no].curY - swrData[no].lastY,
+ -swrData[no].dydx);
+
+ } else if ( swrData[no].curX > swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].lastX,
+ 0,
+ swrData[no].curX,
+ swrData[no].curY - swrData[no].lastY,
+ swrData[no].dydx);
+ }
+
+ } else {
+
+ if ( swrData[no].curX <= swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].curX,
+ 0,
+ swrData[no].lastX,
+ swrData[no].lastY - swrData[no].curY,
+ swrData[no].dydx);
+
+ } else if ( swrData[no].curX > swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].lastX,
+ 0,
+ swrData[no].curX,
+ swrData[no].lastY - swrData[no].curY,
+ -swrData[no].dydx);
+ }
+ }
+}
+
+
+void Shape::AvanceEdge(int no, float to, AlphaLigne *line, bool exact, float step)
+{
+ AvanceEdge(no,to,exact,step);
+
+ if ( swrData[no].sens ) {
+
+ if ( swrData[no].curX <= swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].curX,
+ 0,
+ swrData[no].lastX,
+ swrData[no].curY - swrData[no].lastY,
+ -swrData[no].dydx);
+
+ } else if ( swrData[no].curX > swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].lastX,
+ 0,
+ swrData[no].curX,
+ swrData[no].curY - swrData[no].lastY,
+ swrData[no].dydx);
+ }
+
+ } else {
+
+ if ( swrData[no].curX <= swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].curX,
+ 0,
+ swrData[no].lastX,
+ swrData[no].lastY - swrData[no].curY,
+ swrData[no].dydx);
+
+ } else if ( swrData[no].curX > swrData[no].lastX ) {
+
+ line->AddBord(swrData[no].lastX,
+ 0,
+ swrData[no].curX,
+ swrData[no].lastY - swrData[no].curY,
+ -swrData[no].dydx);
+ }
+ }
+}
+
+/**
+ * \param P point index.
+ * \param numberUp Filled in with the number of edges coming into P from above.
+ * \param numberDown Filled in with the number of edges coming exiting P to go below.
+ * \param upEdge One of the numberUp edges, or -1.
+ * \param downEdge One of the numberDown edges, or -1.
+ */
+
+void Shape::_countUpDown(int P, int *numberUp, int *numberDown, int *upEdge, int *downEdge) const
+{
+ *numberUp = 0;
+ *numberDown = 0;
+ *upEdge = -1;
+ *downEdge = -1;
+
+ int i = getPoint(P).incidentEdge[FIRST];
+
+ while ( i >= 0 && i < numberOfEdges() ) {
+ Shape::dg_arete const &e = getEdge(i);
+ if ( P == std::max(e.st, e.en) ) {
+ *upEdge = i;
+ (*numberUp)++;
+ }
+ if ( P == std::min(e.st, e.en) ) {
+ *downEdge = i;
+ (*numberDown)++;
+ }
+ i = NextAt(P, i);
+ }
+
+}
+
+
+
+/**
+ * Version of Shape::_countUpDown optimised for the case when getPoint(P).totalDegree() == 2.
+ */
+
+void Shape::_countUpDownTotalDegree2(int P,
+ int *numberUp, int *numberDown, int *upEdge, int *downEdge) const
+{
+ *numberUp = 0;
+ *numberDown = 0;
+ *upEdge = -1;
+ *downEdge = -1;
+
+ for (int j : getPoint(P).incidentEdge) {
+ Shape::dg_arete const &e = getEdge(j);
+ if ( P == std::max(e.st, e.en) ) {
+ *upEdge = j;
+ (*numberUp)++;
+ }
+ if ( P == std::min(e.st, e.en) ) {
+ *downEdge = j;
+ (*numberDown)++;
+ }
+ }
+}
+
+
+void Shape::_updateIntersection(int e, int p)
+{
+ swrData[e].lastX = swrData[e].curX;
+ swrData[e].lastY = swrData[e].curY;
+ swrData[e].curX = getPoint(p).x[0];
+ swrData[e].curY = getPoint(p).x[1];
+ swrData[e].misc = nullptr;
+}
+
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-06 19:00:26 +0000