1 /*
2 * ShapeRaster.cpp
3 * nlivarot
4 *
5 * Created by fred on Sat Jul 19 2003.
6 *
7 */
9 #include "Shape.h"
11 #include "livarot/float-line.h"
12 #include "AlphaLigne.h"
13 #include "BitLigne.h"
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"
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 */
26 void Shape::BeginRaster(float &pos, int &curPt)
27 {
28 if ( numberOfPoints() <= 1 || numberOfEdges() <= 1 ) {
29 curPt = 0;
30 pos = 0;
31 return;
32 }
34 MakeRasterData(true);
35 MakePointData(true);
36 MakeEdgeData(true);
38 if (sTree == NULL) {
39 sTree = new SweepTreeList(numberOfEdges());
40 }
41 if (sEvts == NULL) {
42 sEvts = new SweepEventQueue(numberOfEdges());
43 }
45 SortPoints();
47 curPt = 0;
48 pos = getPoint(0).x[1] - 1.0;
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 }
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 }
65 void Shape::EndRaster()
66 {
67 delete sTree;
68 sTree = NULL;
69 delete sEvts;
70 sEvts = NULL;
72 MakePointData(false);
73 MakeEdgeData(false);
74 MakeRasterData(false);
75 }
78 void Shape::BeginQuickRaster(float &pos, int &curPt)
79 {
80 if ( numberOfPoints() <= 1 || numberOfEdges() <= 1 ) {
81 curPt = 0;
82 pos = 0;
83 return;
84 }
86 MakeRasterData(true);
87 MakeQuickRasterData(true);
88 nbQRas = 0;
89 firstQRas = lastQRas = -1;
90 MakePointData(true);
91 MakeEdgeData(true);
93 curPt = 0;
94 pos = getPoint(0).x[1] - 1.0;
96 initialisePointData();
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 }
104 SortPoints();
105 // SortPointsRounded();
106 }
109 void Shape::EndQuickRaster()
110 {
111 MakePointData(false);
112 MakeEdgeData(false);
113 MakeRasterData(false);
114 MakeQuickRasterData(false);
115 }
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 }
125 if ( pos == to ) {
126 return;
127 }
129 enum Direction {
130 DOWNWARDS,
131 UPWARDS
132 };
134 Direction const d = (pos < to) ? DOWNWARDS : UPWARDS;
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;
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);
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 }
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() ) {
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 }
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;
201 int const P = (d == DOWNWARDS) ? nPt : Other(nPt, neNo);
202 node->ConvertTo(this, neNo, 1, P);
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 }
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 }
254 curP = curPt;
255 if ( curPt > 0 ) {
256 pos = getPoint(curPt - 1).x[1];
257 } else {
258 pos = to;
259 }
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 }
276 void Shape::QuickScan(float &pos,int &curP, float to, bool doSort, float step)
277 {
278 if ( numberOfEdges() <= 1 ) {
279 return;
280 }
282 if ( pos == to ) {
283 return;
284 }
286 enum Direction {
287 DOWNWARDS,
288 UPWARDS
289 };
291 Direction const d = (pos < to) ? DOWNWARDS : UPWARDS;
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;
299 int nbUp;
300 int nbDn;
301 int upNo;
302 int dnNo;
303 _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
305 if ( nbDn <= 0 ) {
306 upNo = -1;
307 }
308 if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
309 upNo = -1;
310 }
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 }
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 }
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 }
355 curP = curPt;
356 if ( curPt > 0 ) {
357 pos = getPoint(curPt-1).x[1];
358 } else {
359 pos = to;
360 }
361 }
363 pos = to;
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 }
371 QuickRasterSort();
372 }
376 int Shape::QuickRasterChgEdge(int oBord, int nBord, double x)
377 {
378 if ( oBord == nBord ) {
379 return -1;
380 }
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 }
390 return no;
391 }
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;
404 if ( no < 0 || no >= nbQRas ) {
405 return -1;
406 }
408 if ( firstQRas < 0 ) {
409 firstQRas = lastQRas = no;
410 qrsData[no].prev = -1;
411 qrsData[no].next = -1;
412 return no;
413 }
415 if ( guess < 0 || guess >= nbQRas ) {
417 int c = firstQRas;
418 while ( c >= 0 && c < nbQRas && CmpQRs(qrsData[c],qrsData[no]) < 0 ) {
419 c = qrsData[c].next;
420 }
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 }
434 qrsData[no].next = c;
435 qrsData[c].prev = no;
436 }
438 } else {
439 int c = guess;
440 int stTst = CmpQRs(qrsData[c],qrsData[no]);
441 if ( stTst == 0 ) {
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 }
450 qrsData[no].next = c;
451 qrsData[c].prev = no;
453 } else if ( stTst > 0 ) {
455 while ( c >= 0 && c < nbQRas && CmpQRs(qrsData[c],qrsData[no]) > 0 ) {
456 c = qrsData[c].prev;
457 }
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 }
474 } else {
476 while ( c >= 0 && c < nbQRas && CmpQRs(qrsData[c],qrsData[no]) < 0 ) {
477 c = qrsData[c].next;
478 }
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 }
492 qrsData[no].next = c;
493 qrsData[c].prev = no;
494 }
495 }
496 }
498 return no;
499 }
503 void Shape::QuickRasterSubEdge(int bord)
504 {
505 int no = qrsData[bord].ind;
506 if ( no < 0 || no >= nbQRas ) {
507 return; // euuhHHH
508 }
510 if ( qrsData[no].prev >= 0 ) {
511 qrsData[qrsData[no].prev].next=qrsData[no].next;
512 }
514 if ( qrsData[no].next >= 0 ) {
515 qrsData[qrsData[no].next].prev = qrsData[no].prev;
516 }
518 if ( no == firstQRas ) {
519 firstQRas = qrsData[no].next;
520 }
522 if ( no == lastQRas ) {
523 lastQRas = qrsData[no].prev;
524 }
526 qrsData[no].prev = qrsData[no].next = -1;
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;
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 }
552 void Shape::QuickRasterSwapEdge(int a, int b)
553 {
554 if ( a == b ) {
555 return;
556 }
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 }
564 qrsData[na].bord = b;
565 qrsData[nb].bord = a;
566 qrsData[a].ind = nb;
567 qrsData[b].ind = na;
569 double swd = qrsData[na].x;
570 qrsData[na].x = qrsData[nb].x;
571 qrsData[nb].x = swd;
572 }
575 void Shape::QuickRasterSort()
576 {
577 if ( nbQRas <= 1 ) {
578 return;
579 }
581 int cb = qrsData[firstQRas].bord;
583 while ( cb >= 0 ) {
584 int bI = qrsData[cb].ind;
585 int nI = qrsData[bI].next;
587 if ( nI < 0 ) {
588 break;
589 }
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 }
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 }
616 if ( pos == to ) {
617 return;
618 }
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 }
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 }
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 }
650 curP = curPt;
651 if ( curPt > 0 ) {
652 pos = getPoint(curPt - 1).x[1];
653 } else {
654 pos = to;
655 }
657 } else {
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 }
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 }
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 }
686 curP = curPt;
687 if ( curPt > 0 ) {
688 pos = getPoint(curPt - 1).x[1];
689 } else {
690 pos = to;
691 }
692 }
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 }
709 void Shape::DirectQuickScan(float &pos, int &curP, float to, bool doSort, float step)
710 {
711 if ( numberOfEdges() <= 1 ) {
712 return;
713 }
715 if ( pos == to ) {
716 return;
717 }
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 }
729 for (int i = 0; i < numberOfEdges(); i++) {
730 if ( qrsData[i].ind < 0 ) {
731 QuickRasterSubEdge(i);
732 }
733 }
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 }
745 curP = curPt;
746 if ( curPt > 0 ) {
747 pos=getPoint(curPt-1).x[1];
748 } else {
749 pos = to;
750 }
752 } else {
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 }
760 for (int i = 0; i < numberOfEdges(); i++) {
761 if ( qrsData[i].ind < 0 ) {
762 QuickRasterSubEdge(i);
763 }
764 }
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 }
776 curP = curPt;
777 if ( curPt > 0 ) {
778 pos = getPoint(curPt-1).x[1];
779 } else {
780 pos = to;
781 }
783 }
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 }
792 QuickRasterSort();
793 }
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
802 void Shape::Scan(float &pos, int &curP, float to, FloatLigne *line, bool exact, float step)
803 {
804 if ( numberOfEdges() <= 1 ) {
805 return;
806 }
808 if ( pos >= to ) {
809 return;
810 }
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
816 if ( sTree->racine ) {
817 SweepTree *curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
818 while ( curS ) {
820 int lastGuess = -1;
821 int cb = curS->bord;
823 if ( swrData[cb].sens == false && curS->elem[LEFT] ) {
825 int lb = (static_cast<SweepTree*>(curS->elem[LEFT]))->bord;
827 lastGuess = line->AppendBord(swrData[lb].curX,
828 to - swrData[lb].curY,
829 swrData[cb].curX,
830 to - swrData[cb].curY,0.0);
832 swrData[lb].guess = lastGuess - 1;
833 swrData[cb].guess = lastGuess;
834 } else {
835 int lb = curS->bord;
836 swrData[lb].guess = -1;
837 }
839 curS=static_cast <SweepTree*> (curS->elem[RIGHT]);
840 }
841 }
843 int curPt = curP;
844 while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
846 int nPt = curPt++;
848 // same thing as the usual Scan(), just with a hardcoded "indegree+outdegree=2" case, since
849 // it's the most common one
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 }
861 if ( nbDn <= 0 ) {
862 upNo = -1;
863 }
864 if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
865 upNo = -1;
866 }
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 }
884 cb = NextAt(nPt,cb);
885 }
886 }
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);
896 node->ConvertTo(this, dnNo, 1, nPt);
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 }
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 }
928 curP = curPt;
929 if ( curPt > 0 ) {
930 pos = getPoint(curPt - 1).x[1];
931 } else {
932 pos = to;
933 }
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 }
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 }
956 if ( pos >= to ) {
957 return;
958 }
960 if ( sTree->racine ) {
961 int curW = 0;
962 float lastX = 0;
963 SweepTree* curS = static_cast<SweepTree*>(sTree->racine->Leftmost());
965 if ( directed == fill_oddEven ) {
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 }
979 } else if ( directed == fill_positive ) {
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 }
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 }
997 curS = static_cast<SweepTree*>(curS->elem[RIGHT]);
998 }
1000 } else if ( directed == fill_nonZero ) {
1002 while ( curS ) {
1003 int cb = curS->bord;
1004 int oW = curW;
1005 if ( swrData[cb].sens ) {
1006 curW++;
1007 } else {
1008 curW--;
1009 }
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 }
1020 }
1022 int curPt = curP;
1023 while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
1024 int nPt = curPt++;
1026 int cb;
1027 int nbUp;
1028 int nbDn;
1029 int upNo;
1030 int dnNo;
1032 if ( getPoint(nPt).totalDegree() == 2 ) {
1033 _countUpDownTotalDegree2(nPt, &nbUp, &nbDn, &upNo, &dnNo);
1034 } else {
1035 _countUpDown(nPt, &nbUp, &nbDn, &upNo, &dnNo);
1036 }
1038 if ( nbDn <= 0 ) {
1039 upNo = -1;
1040 }
1041 if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
1042 upNo = -1;
1043 }
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 }
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);
1071 node->ConvertTo(this, dnNo, 1, nPt);
1073 swrData[dnNo].misc = node;
1074 insertionNode = node;
1075 CreateEdge(dnNo, to, step);
1077 } else {
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 }
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 }
1104 curP = curPt;
1105 if ( curPt > 0 ) {
1106 pos = getPoint(curPt - 1).x[1];
1107 } else {
1108 pos = to;
1109 }
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 }
1123 void Shape::Scan(float &pos, int &curP, float to, AlphaLigne *line, bool exact, float step)
1124 {
1125 if ( numberOfEdges() <= 1 ) {
1126 return;
1127 }
1129 if ( pos >= to ) {
1130 return;
1131 }
1133 int curPt = curP;
1134 while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
1135 int nPt = -1;
1136 nPt = curPt++;
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 }
1148 if ( nbDn <= 0 ) {
1149 upNo=-1;
1150 }
1151 if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
1152 upNo=-1;
1153 }
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 }
1170 cb = NextAt(nPt,cb);
1171 }
1172 }
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);
1182 node->ConvertTo(this, dnNo, 1, nPt);
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 }
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 }
1214 curP = curPt;
1215 if ( curPt > 0 ) {
1216 pos = getPoint(curPt - 1).x[1];
1217 } else {
1218 pos = to;
1219 }
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 }
1234 void Shape::QuickScan(float &pos, int &curP, float to, FloatLigne* line, float step)
1235 {
1236 if ( numberOfEdges() <= 1 ) {
1237 return;
1238 }
1240 if ( pos >= to ) {
1241 return;
1242 }
1244 if ( nbQRas > 1 ) {
1245 int curW = 0;
1246 float lastX = 0;
1247 float lastY = 0;
1248 int lastGuess = -1;
1249 int lastB = -1;
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 }
1260 if ( curW % 2 == 0 && oW % 2 != 0) {
1262 lastGuess = line->AppendBord(swrData[lastB].curX,
1263 to - swrData[lastB].curY,
1264 swrData[cb].curX,
1265 to - swrData[cb].curY,
1266 0.0);
1268 swrData[cb].guess = lastGuess;
1269 if ( lastB >= 0 ) {
1270 swrData[lastB].guess = lastGuess - 1;
1271 }
1273 } else if ( curW%2 != 0 && oW%2 == 0 ) {
1275 lastX = swrData[cb].curX;
1276 lastY = swrData[cb].curY;
1277 lastB = cb;
1278 swrData[cb].guess = -1;
1280 } else {
1281 swrData[cb].guess = -1;
1282 }
1283 }
1284 }
1286 int curPt = curP;
1287 while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
1288 int nPt = curPt++;
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 }
1300 if ( nbDn <= 0 ) {
1301 upNo = -1;
1302 }
1303 if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
1304 upNo = -1;
1305 }
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 }
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);
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 }
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 }
1353 curP = curPt;
1354 if ( curPt > 0 ) {
1355 pos = getPoint(curPt-1).x[1];
1356 } else {
1357 pos=to;
1358 }
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 }
1367 QuickRasterSort();
1368 }
1373 void Shape::QuickScan(float &pos, int &curP, float to, FillRule directed, BitLigne* line, float step)
1374 {
1375 if ( numberOfEdges() <= 1 ) {
1376 return;
1377 }
1379 if ( pos >= to ) {
1380 return;
1381 }
1383 if ( nbQRas > 1 ) {
1384 int curW = 0;
1385 float lastX = 0;
1387 if ( directed == fill_oddEven ) {
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 }
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 }
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 }
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 }
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 }
1437 int curPt = curP;
1438 while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
1439 int nPt = -1;
1440 nPt = curPt++;
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 }
1452 if ( nbDn <= 0 ) {
1453 upNo = -1;
1454 }
1456 if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
1457 upNo = -1;
1458 }
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 }
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);
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 }
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 }
1505 curP = curPt;
1506 if ( curPt > 0 ) {
1507 pos=getPoint(curPt - 1).x[1];
1508 } else {
1509 pos = to;
1510 }
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 }
1519 QuickRasterSort();
1520 }
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 }
1533 int curPt = curP;
1534 while ( curPt < numberOfPoints() && getPoint(curPt).x[1] <= to ) {
1535 int nPt = curPt++;
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 }
1547 if ( nbDn <= 0 ) {
1548 upNo = -1;
1549 }
1550 if ( upNo >= 0 && swrData[upNo].misc == NULL ) {
1551 upNo = -1;
1552 }
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 }
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);
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 }
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 }
1600 curP = curPt;
1601 if ( curPt > 0 ) {
1602 pos = getPoint(curPt-1).x[1];
1603 } else {
1604 pos = to;
1605 }
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 }
1614 QuickRasterSort();
1615 }
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 NR::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 }
1636 swrData[no].lastX = swrData[no].curX = getPoint(cPt).x[0];
1637 swrData[no].lastY = swrData[no].curY = getPoint(cPt).x[1];
1639 if ( fabs(dir[1]) < 0.000001 ) {
1640 swrData[no].dxdy = 0;
1641 } else {
1642 swrData[no].dxdy = dir[0]/dir[1];
1643 }
1645 if ( fabs(dir[0]) < 0.000001 ) {
1646 swrData[no].dydx = 0;
1647 } else {
1648 swrData[no].dydx = dir[1]/dir[0];
1649 }
1651 swrData[no].calcX = swrData[no].curX + (to - step - swrData[no].curY) * swrData[no].dxdy;
1652 swrData[no].guess = -1;
1653 }
1656 void Shape::AvanceEdge(int no, float to, bool exact, float step)
1657 {
1658 if ( exact ) {
1659 NR::Point dir;
1660 NR::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 }
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 }
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 }
1684 /*
1685 * specialisation par type de structure utilise
1686 */
1688 void Shape::DestroyEdge(int no, float to, FloatLigne* line)
1689 {
1690 if ( swrData[no].sens ) {
1692 if ( swrData[no].curX < swrData[no].lastX ) {
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);
1701 } else if ( swrData[no].curX > swrData[no].lastX ) {
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 }
1711 } else {
1713 if ( swrData[no].curX < swrData[no].lastX ) {
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);
1722 } else if ( swrData[no].curX > swrData[no].lastX ) {
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 }
1736 void Shape::AvanceEdge(int no, float to, FloatLigne *line, bool exact, float step)
1737 {
1738 AvanceEdge(no,to,exact,step);
1740 if ( swrData[no].sens ) {
1742 if ( swrData[no].curX < swrData[no].lastX ) {
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);
1751 } else if ( swrData[no].curX > swrData[no].lastX ) {
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 }
1761 } else {
1763 if ( swrData[no].curX < swrData[no].lastX ) {
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);
1772 } else if ( swrData[no].curX > swrData[no].lastX ) {
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 }
1785 void Shape::DestroyEdge(int no, BitLigne *line)
1786 {
1787 if ( swrData[no].sens ) {
1789 if ( swrData[no].curX < swrData[no].lastX ) {
1791 line->AddBord(swrData[no].curX, swrData[no].lastX, false);
1793 } else if ( swrData[no].curX > swrData[no].lastX ) {
1795 line->AddBord(swrData[no].lastX,swrData[no].curX,false);
1796 }
1798 } else {
1800 if ( swrData[no].curX < swrData[no].lastX ) {
1802 line->AddBord(swrData[no].curX, swrData[no].lastX, false);
1804 } else if ( swrData[no].curX > swrData[no].lastX ) {
1806 line->AddBord(swrData[no].lastX, swrData[no].curX, false);
1808 }
1809 }
1810 }
1813 void Shape::AvanceEdge(int no, float to, BitLigne *line, bool exact, float step)
1814 {
1815 AvanceEdge(no, to, exact, step);
1817 if ( swrData[no].sens ) {
1819 if ( swrData[no].curX < swrData[no].lastX ) {
1821 line->AddBord(swrData[no].curX, swrData[no].lastX, false);
1823 } else if ( swrData[no].curX > swrData[no].lastX ) {
1825 line->AddBord(swrData[no].lastX, swrData[no].curX, false);
1826 }
1828 } else {
1830 if ( swrData[no].curX < swrData[no].lastX ) {
1832 line->AddBord(swrData[no].curX, swrData[no].lastX, false);
1834 } else if ( swrData[no].curX > swrData[no].lastX ) {
1836 line->AddBord(swrData[no].lastX, swrData[no].curX, false);
1837 }
1838 }
1839 }
1842 void Shape::DestroyEdge(int no, AlphaLigne* line)
1843 {
1844 if ( swrData[no].sens ) {
1846 if ( swrData[no].curX <= swrData[no].lastX ) {
1848 line->AddBord(swrData[no].curX,
1849 0,
1850 swrData[no].lastX,
1851 swrData[no].curY - swrData[no].lastY,
1852 -swrData[no].dydx);
1854 } else if ( swrData[no].curX > swrData[no].lastX ) {
1856 line->AddBord(swrData[no].lastX,
1857 0,
1858 swrData[no].curX,
1859 swrData[no].curY - swrData[no].lastY,
1860 swrData[no].dydx);
1861 }
1863 } else {
1865 if ( swrData[no].curX <= swrData[no].lastX ) {
1867 line->AddBord(swrData[no].curX,
1868 0,
1869 swrData[no].lastX,
1870 swrData[no].lastY - swrData[no].curY,
1871 swrData[no].dydx);
1873 } else if ( swrData[no].curX > swrData[no].lastX ) {
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 }
1885 void Shape::AvanceEdge(int no, float to, AlphaLigne *line, bool exact, float step)
1886 {
1887 AvanceEdge(no,to,exact,step);
1889 if ( swrData[no].sens ) {
1891 if ( swrData[no].curX <= swrData[no].lastX ) {
1893 line->AddBord(swrData[no].curX,
1894 0,
1895 swrData[no].lastX,
1896 swrData[no].curY - swrData[no].lastY,
1897 -swrData[no].dydx);
1899 } else if ( swrData[no].curX > swrData[no].lastX ) {
1901 line->AddBord(swrData[no].lastX,
1902 0,
1903 swrData[no].curX,
1904 swrData[no].curY - swrData[no].lastY,
1905 swrData[no].dydx);
1906 }
1908 } else {
1910 if ( swrData[no].curX <= swrData[no].lastX ) {
1912 line->AddBord(swrData[no].curX,
1913 0,
1914 swrData[no].lastX,
1915 swrData[no].lastY - swrData[no].curY,
1916 swrData[no].dydx);
1918 } else if ( swrData[no].curX > swrData[no].lastX ) {
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 }
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 */
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;
1944 int i = getPoint(P).incidentEdge[FIRST];
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 }
1959 }
1963 /**
1964 * Version of Shape::_countUpDown optimised for the case when getPoint(P).totalDegree() == 2.
1965 */
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;
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 }
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 }
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 :