1 /****************************************************************************
2 **
3 ** Copyright (C) 2015 The Qt Company Ltd.
4 ** Contact: http://www.qt.io/licensing/
5 **
6 ** This file is part of the Qt3Support module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and The Qt Company. For licensing terms
14 ** and conditions see http://www.qt.io/terms-conditions. For further
15 ** information use the contact form at http://www.qt.io/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 or version 3 as published by the Free
20 ** Software Foundation and appearing in the file LICENSE.LGPLv21 and
21 ** LICENSE.LGPLv3 included in the packaging of this file. Please review the
22 ** following information to ensure the GNU Lesser General Public License
23 ** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
24 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
25 **
26 ** As a special exception, The Qt Company gives you certain additional
27 ** rights. These rights are described in The Qt Company LGPL Exception
28 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
29 **
30 ** GNU General Public License Usage
31 ** Alternatively, this file may be used under the terms of the GNU
32 ** General Public License version 3.0 as published by the Free Software
33 ** Foundation and appearing in the file LICENSE.GPL included in the
34 ** packaging of this file. Please review the following information to
35 ** ensure the GNU General Public License version 3.0 requirements will be
36 ** met: http://www.gnu.org/copyleft/gpl.html.
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41
42 #include "q3polygonscanner.h"
43 #include "q3pointarray.h"
44 #include <stdlib.h>
45
46 QT_BEGIN_NAMESPACE
47
48 // Based on Xserver code miFillGeneralPoly...
49 /*
50 *
51 * Written by Brian Kelleher; Oct. 1985
52 *
53 * Routine to fill a polygon. Two fill rules are
54 * supported: frWINDING and frEVENODD.
55 *
56 * See fillpoly.h for a complete description of the algorithm.
57 */
58
59 /*
60 * These are the data structures needed to scan
61 * convert regions. Two different scan conversion
62 * methods are available -- the even-odd method, and
63 * the winding number method.
64 * The even-odd rule states that a point is inside
65 * the polygon if a ray drawn from that point in any
66 * direction will pass through an odd number of
67 * path segments.
68 * By the winding number rule, a point is decided
69 * to be inside the polygon if a ray drawn from that
70 * point in any direction passes through a different
71 * number of clockwise and counterclockwise path
72 * segments.
73 *
74 * These data structures are adapted somewhat from
75 * the algorithm in (Foley/Van Dam) for scan converting
76 * polygons.
77 * The basic algorithm is to start at the top (smallest y)
78 * of the polygon, stepping down to the bottom of
79 * the polygon by incrementing the y coordinate. We
80 * keep a list of edges which the current scanline crosses,
81 * sorted by x. This list is called the Active Edge Table (AET)
82 * As we change the y-coordinate, we update each entry in
83 * in the active edge table to reflect the edges new xcoord.
84 * This list must be sorted at each scanline in case
85 * two edges intersect.
86 * We also keep a data structure known as the Edge Table (ET),
87 * which keeps track of all the edges which the current
88 * scanline has not yet reached. The ET is basically a
89 * list of ScanLineList structures containing a list of
90 * edges which are entered at a given scanline. There is one
91 * ScanLineList per scanline at which an edge is entered.
92 * When we enter a new edge, we move it from the ET to the AET.
93 *
94 * From the AET, we can implement the even-odd rule as in
95 * (Foley/Van Dam).
96 * The winding number rule is a little trickier. We also
97 * keep the EdgeTableEntries in the AET linked by the
98 * nextWETE (winding EdgeTableEntry) link. This allows
99 * the edges to be linked just as before for updating
100 * purposes, but only uses the edges linked by the nextWETE
101 * link as edges representing spans of the polygon to
102 * drawn (as with the even-odd rule).
103 */
104
105 /* $XConsortium: miscanfill.h,v 1.5 94/04/17 20:27:50 dpw Exp $ */
106 /*
107
108 Copyright (c) 1987 X Consortium
109
110 Permission is hereby granted, free of charge, to any person obtaining
111 a copy of this software and associated documentation files (the
112 "Software"), to deal in the Software without restriction, including
113 without limitation the rights to use, copy, modify, merge, publish,
114 distribute, sublicense, and/or sell copies of the Software, and to
115 permit persons to whom the Software is furnished to do so, subject to
116 the following conditions:
117
118 The above copyright notice and this permission notice shall be included
119 in all copies or substantial portions of the Software.
120
121 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
122 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
123 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
124 IN NO EVENT SHALL THE X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR
125 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
126 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
127 OTHER DEALINGS IN THE SOFTWARE.
128
129 Except as contained in this notice, the name of the X Consortium shall
130 not be used in advertising or otherwise to promote the sale, use or
131 other dealings in this Software without prior written authorization
132 from the X Consortium.
133
134 */
135
136
137 /*
138 * scanfill.h
139 *
140 * Written by Brian Kelleher; Jan 1985
141 *
142 * This file contains a few macros to help track
143 * the edge of a filled object. The object is assumed
144 * to be filled in scanline order, and thus the
145 * algorithm used is an extension of Bresenham's line
146 * drawing algorithm which assumes that y is always the
147 * major axis.
148 * Since these pieces of code are the same for any filled shape,
149 * it is more convenient to gather the library in one
150 * place, but since these pieces of code are also in
151 * the inner loops of output primitives, procedure call
152 * overhead is out of the question.
153 * See the author for a derivation if needed.
154 */
155
156 /*
157 * In scan converting polygons, we want to choose those pixels
158 * which are inside the polygon. Thus, we add .5 to the starting
159 * x coordinate for both left and right edges. Now we choose the
160 * first pixel which is inside the pgon for the left edge and the
161 * first pixel which is outside the pgon for the right edge.
162 * Draw the left pixel, but not the right.
163 *
164 * How to add .5 to the starting x coordinate:
165 * If the edge is moving to the right, then subtract dy from the
166 * error term from the general form of the algorithm.
167 * If the edge is moving to the left, then add dy to the error term.
168 *
169 * The reason for the difference between edges moving to the left
170 * and edges moving to the right is simple: If an edge is moving
171 * to the right, then we want the algorithm to flip immediately.
172 * If it is moving to the left, then we don't want it to flip until
173 * we traverse an entire pixel.
174 */
175 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
176 int dx; /* local storage */ \
177 \
178 /* \
179 * if the edge is horizontal, then it is ignored \
180 * and assumed not to be processed. Otherwise, do this stuff. \
181 */ \
182 if ((dy) != 0) { \
183 xStart = (x1); \
184 dx = (x2) - xStart; \
185 if (dx < 0) { \
186 m = dx / (dy); \
187 m1 = m - 1; \
188 incr1 = -2 * dx + 2 * (dy) * m1; \
189 incr2 = -2 * dx + 2 * (dy) * m; \
190 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
191 } else { \
192 m = dx / (dy); \
193 m1 = m + 1; \
194 incr1 = 2 * dx - 2 * (dy) * m1; \
195 incr2 = 2 * dx - 2 * (dy) * m; \
196 d = -2 * m * (dy) + 2 * dx; \
197 } \
198 } \
199 }
200
201 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
202 if (m1 > 0) { \
203 if (d > 0) { \
204 minval += m1; \
205 d += incr1; \
206 } \
207 else { \
208 minval += m; \
209 d += incr2; \
210 } \
211 } else {\
212 if (d >= 0) { \
213 minval += m1; \
214 d += incr1; \
215 } \
216 else { \
217 minval += m; \
218 d += incr2; \
219 } \
220 } \
221 }
222
223
224 /*
225 * This structure contains all of the information needed
226 * to run the bresenham algorithm.
227 * The variables may be hardcoded into the declarations
228 * instead of using this structure to make use of
229 * register declarations.
230 */
231 typedef struct {
232 int minor; /* minor axis */
233 int d; /* decision variable */
234 int m, m1; /* slope and slope+1 */
235 int incr1, incr2; /* error increments */
236 } BRESINFO;
237
238
239 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
240 BRESINITPGON(dmaj, min1, min2, bres.minor, bres.d, \
241 bres.m, bres.m1, bres.incr1, bres.incr2)
242
243 #define BRESINCRPGONSTRUCT(bres) \
244 BRESINCRPGON(bres.d, bres.minor, bres.m, bres.m1, bres.incr1, bres.incr2)
245
246
247 typedef struct _EdgeTableEntry {
248 int ymax; /* ycoord at which we exit this edge. */
249 BRESINFO bres; /* Bresenham info to run the edge */
250 struct _EdgeTableEntry *next; /* next in the list */
251 struct _EdgeTableEntry *back; /* for insertion sort */
252 struct _EdgeTableEntry *nextWETE; /* for winding num rule */
253 int ClockWise; /* flag for winding number rule */
254 } EdgeTableEntry;
255
256
257 typedef struct _ScanLineList{
258 int scanline; /* the scanline represented */
259 EdgeTableEntry *edgelist; /* header node */
260 struct _ScanLineList *next; /* next in the list */
261 } ScanLineList;
262
263
264 typedef struct {
265 int ymax; /* ymax for the polygon */
266 int ymin; /* ymin for the polygon */
267 ScanLineList scanlines; /* header node */
268 } EdgeTable;
269
270
271 /*
272 * Here is a struct to help with storage allocation
273 * so we can allocate a big chunk at a time, and then take
274 * pieces from this heap when we need to.
275 */
276 #define SLLSPERBLOCK 25
277
278 typedef struct _ScanLineListBlock {
279 ScanLineList SLLs[SLLSPERBLOCK];
280 struct _ScanLineListBlock *next;
281 } ScanLineListBlock;
282
283 /*
284 * number of points to buffer before sending them off
285 * to scanlines() : Must be an even number
286 */
287 #define NUMPTSTOBUFFER 200
288
289 /*
290 *
291 * a few macros for the inner loops of the fill code where
292 * performance considerations don't allow a procedure call.
293 *
294 * Evaluate the given edge at the given scanline.
295 * If the edge has expired, then we leave it and fix up
296 * the active edge table; otherwise, we increment the
297 * x value to be ready for the next scanline.
298 * The winding number rule is in effect, so we must notify
299 * the caller when the edge has been removed so he
300 * can reorder the Winding Active Edge Table.
301 */
302 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
303 if (pAET->ymax == y) { /* leaving this edge */ \
304 pPrevAET->next = pAET->next; \
305 pAET = pPrevAET->next; \
306 fixWAET = 1; \
307 if (pAET) \
308 pAET->back = pPrevAET; \
309 } \
310 else { \
311 BRESINCRPGONSTRUCT(pAET->bres); \
312 pPrevAET = pAET; \
313 pAET = pAET->next; \
314 } \
315 }
316
317
318 /*
319 * Evaluate the given edge at the given scanline.
320 * If the edge has expired, then we leave it and fix up
321 * the active edge table; otherwise, we increment the
322 * x value to be ready for the next scanline.
323 * The even-odd rule is in effect.
324 */
325 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
326 if (pAET->ymax == y) { /* leaving this edge */ \
327 pPrevAET->next = pAET->next; \
328 pAET = pPrevAET->next; \
329 if (pAET) \
330 pAET->back = pPrevAET; \
331 } \
332 else { \
333 BRESINCRPGONSTRUCT(pAET->bres) \
334 pPrevAET = pAET; \
335 pAET = pAET->next; \
336 } \
337 }
338
339 /***********************************************************
340
341 Copyright (c) 1987 X Consortium
342
343 Permission is hereby granted, free of charge, to any person obtaining a copy
344 of this software and associated documentation files (the "Software"), to deal
345 in the Software without restriction, including without limitation the rights
346 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
347 copies of the Software, and to permit persons to whom the Software is
348 furnished to do so, subject to the following conditions:
349
350 The above copyright notice and this permission notice shall be included in
351 all copies or substantial portions of the Software.
352
353 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
354 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
355 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
356 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
357 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
358 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
359
360 Except as contained in this notice, the name of the X Consortium shall not be
361 used in advertising or otherwise to promote the sale, use or other dealings
362 in this Software without prior written authorization from the X Consortium.
363
364
365 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
366
367 All Rights Reserved
368
369 Permission to use, copy, modify, and distribute this software and its
370 documentation for any purpose and without fee is hereby granted,
371 provided that the above copyright notice appear in all copies and that
372 both that copyright notice and this permission notice appear in
373 supporting documentation, and that the name of Digital not be
374 used in advertising or publicity pertaining to distribution of the
375 software without specific, written prior permission.
376
377 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
378 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
379 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
380 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
381 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
382 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
383 SOFTWARE.
384
385 ******************************************************************/
386
387 #define MAXINT 0x7fffffff
388 #define MININT -MAXINT
389
390 /*
391 * fillUtils.c
392 *
393 * Written by Brian Kelleher; Oct. 1985
394 *
395 * This module contains all of the utility functions
396 * needed to scan convert a polygon.
397 *
398 */
399 /*
400 * InsertEdgeInET
401 *
402 * Insert the given edge into the edge table.
403 * First we must find the correct bucket in the
404 * Edge table, then find the right slot in the
405 * bucket. Finally, we can insert it.
406 *
407 */
408 static bool
miInsertEdgeInET(EdgeTable * ET,EdgeTableEntry * ETE,int scanline,ScanLineListBlock ** SLLBlock,int * iSLLBlock)409 miInsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
410 int scanline, ScanLineListBlock **SLLBlock, int *iSLLBlock)
411 {
412 register EdgeTableEntry *start, *prev;
413 register ScanLineList *pSLL, *pPrevSLL;
414 ScanLineListBlock *tmpSLLBlock;
415
416 /*
417 * find the right bucket to put the edge into
418 */
419 pPrevSLL = &ET->scanlines;
420 pSLL = pPrevSLL->next;
421 while (pSLL && (pSLL->scanline < scanline))
422 {
423 pPrevSLL = pSLL;
424 pSLL = pSLL->next;
425 }
426
427 /*
428 * reassign pSLL (pointer to ScanLineList) if necessary
429 */
430 if ((!pSLL) || (pSLL->scanline > scanline))
431 {
432 if (*iSLLBlock > SLLSPERBLOCK-1)
433 {
434 tmpSLLBlock =
435 (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock));
436 if (!tmpSLLBlock)
437 return false;
438 (*SLLBlock)->next = tmpSLLBlock;
439 tmpSLLBlock->next = 0;
440 *SLLBlock = tmpSLLBlock;
441 *iSLLBlock = 0;
442 }
443 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
444
445 pSLL->next = pPrevSLL->next;
446 pSLL->edgelist = 0;
447 pPrevSLL->next = pSLL;
448 }
449 pSLL->scanline = scanline;
450
451 /*
452 * now insert the edge in the right bucket
453 */
454 prev = 0;
455 start = pSLL->edgelist;
456 while (start && (start->bres.minor < ETE->bres.minor))
457 {
458 prev = start;
459 start = start->next;
460 }
461 ETE->next = start;
462
463 if (prev)
464 prev->next = ETE;
465 else
466 pSLL->edgelist = ETE;
467 return true;
468 }
469
470 /*
471 * CreateEdgeTable
472 *
473 * This routine creates the edge table for
474 * scan converting polygons.
475 * The Edge Table (ET) looks like:
476 *
477 * EdgeTable
478 * --------
479 * | ymax | ScanLineLists
480 * |scanline|-->------------>-------------->...
481 * -------- |scanline| |scanline|
482 * |edgelist| |edgelist|
483 * --------- ---------
484 * | |
485 * | |
486 * V V
487 * list of ETEs list of ETEs
488 *
489 * where ETE is an EdgeTableEntry data structure,
490 * and there is one ScanLineList per scanline at
491 * which an edge is initially entered.
492 *
493 */
494
495 typedef struct {
496 #if defined(Q_OS_MAC)
497 int y, x;
498 #else
499 int x, y;
500 #endif
501
502 } DDXPointRec, *DDXPointPtr;
503
504 /*
505 * Clean up our act.
506 */
507 static void
miFreeStorage(ScanLineListBlock * pSLLBlock)508 miFreeStorage(ScanLineListBlock *pSLLBlock)
509 {
510 register ScanLineListBlock *tmpSLLBlock;
511
512 while (pSLLBlock)
513 {
514 tmpSLLBlock = pSLLBlock->next;
515 free(pSLLBlock);
516 pSLLBlock = tmpSLLBlock;
517 }
518 }
519
520 static bool
miCreateETandAET(int count,DDXPointPtr pts,EdgeTable * ET,EdgeTableEntry * AET,EdgeTableEntry * pETEs,ScanLineListBlock * pSLLBlock)521 miCreateETandAET(int count, DDXPointPtr pts, EdgeTable *ET,
522 EdgeTableEntry *AET, EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
523 {
524 register DDXPointPtr top, bottom;
525 register DDXPointPtr PrevPt, CurrPt;
526 int iSLLBlock = 0;
527
528 int dy;
529
530 if (count < 2) return true;
531
532 /*
533 * initialize the Active Edge Table
534 */
535 AET->next = 0;
536 AET->back = 0;
537 AET->nextWETE = 0;
538 AET->bres.minor = MININT;
539
540 /*
541 * initialize the Edge Table.
542 */
543 ET->scanlines.next = 0;
544 ET->ymax = MININT;
545 ET->ymin = MAXINT;
546 pSLLBlock->next = 0;
547
548 PrevPt = &pts[count-1];
549
550 /*
551 * for each vertex in the array of points.
552 * In this loop we are dealing with two vertices at
553 * a time -- these make up one edge of the polygon.
554 */
555 while (count--)
556 {
557 CurrPt = pts++;
558
559 /*
560 * find out which point is above and which is below.
561 */
562 if (PrevPt->y > CurrPt->y)
563 {
564 bottom = PrevPt, top = CurrPt;
565 pETEs->ClockWise = 0;
566 }
567 else
568 {
569 bottom = CurrPt, top = PrevPt;
570 pETEs->ClockWise = 1;
571 }
572
573 /*
574 * don't add horizontal edges to the Edge table.
575 */
576 if (bottom->y != top->y)
577 {
578 pETEs->ymax = bottom->y-1; /* -1 so we don't get last scanline */
579
580 /*
581 * initialize integer edge algorithm
582 */
583 dy = bottom->y - top->y;
584 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres)
585
586 if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock))
587 {
588 miFreeStorage(pSLLBlock->next);
589 return false;
590 }
591
592 ET->ymax = qMax(ET->ymax, PrevPt->y);
593 ET->ymin = qMin(ET->ymin, PrevPt->y);
594 pETEs++;
595 }
596
597 PrevPt = CurrPt;
598 }
599 return true;
600 }
601
602 /*
603 * loadAET
604 *
605 * This routine moves EdgeTableEntries from the
606 * EdgeTable into the Active Edge Table,
607 * leaving them sorted by smaller x coordinate.
608 *
609 */
610
611 static void
miloadAET(EdgeTableEntry * AET,EdgeTableEntry * ETEs)612 miloadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
613 {
614 register EdgeTableEntry *pPrevAET;
615 register EdgeTableEntry *tmp;
616
617 pPrevAET = AET;
618 AET = AET->next;
619 while (ETEs)
620 {
621 while (AET && (AET->bres.minor < ETEs->bres.minor))
622 {
623 pPrevAET = AET;
624 AET = AET->next;
625 }
626 tmp = ETEs->next;
627 ETEs->next = AET;
628 if (AET)
629 AET->back = ETEs;
630 ETEs->back = pPrevAET;
631 pPrevAET->next = ETEs;
632 pPrevAET = ETEs;
633
634 ETEs = tmp;
635 }
636 }
637
638 /*
639 * computeWAET
640 *
641 * This routine links the AET by the
642 * nextWETE (winding EdgeTableEntry) link for
643 * use by the winding number rule. The final
644 * Active Edge Table (AET) might look something
645 * like:
646 *
647 * AET
648 * ---------- --------- ---------
649 * |ymax | |ymax | |ymax |
650 * | ... | |... | |... |
651 * |next |->|next |->|next |->...
652 * |nextWETE| |nextWETE| |nextWETE|
653 * --------- --------- ^--------
654 * | | |
655 * V-------------------> V---> ...
656 *
657 */
658 static void
micomputeWAET(EdgeTableEntry * AET)659 micomputeWAET(EdgeTableEntry *AET)
660 {
661 register EdgeTableEntry *pWETE;
662 register int inside = 1;
663 register int isInside = 0;
664
665 AET->nextWETE = 0;
666 pWETE = AET;
667 AET = AET->next;
668 while (AET)
669 {
670 if (AET->ClockWise)
671 isInside++;
672 else
673 isInside--;
674
675 if ((!inside && !isInside) ||
676 (inside && isInside))
677 {
678 pWETE->nextWETE = AET;
679 pWETE = AET;
680 inside = !inside;
681 }
682 AET = AET->next;
683 }
684 pWETE->nextWETE = 0;
685 }
686
687 /*
688 * InsertionSort
689 *
690 * Just a simple insertion sort using
691 * pointers and back pointers to sort the Active
692 * Edge Table.
693 *
694 */
695
696 static int
miInsertionSort(EdgeTableEntry * AET)697 miInsertionSort(EdgeTableEntry *AET)
698 {
699 register EdgeTableEntry *pETEchase;
700 register EdgeTableEntry *pETEinsert;
701 register EdgeTableEntry *pETEchaseBackTMP;
702 register int changed = 0;
703
704 AET = AET->next;
705 while (AET)
706 {
707 pETEinsert = AET;
708 pETEchase = AET;
709 while (pETEchase->back->bres.minor > AET->bres.minor)
710 pETEchase = pETEchase->back;
711
712 AET = AET->next;
713 if (pETEchase != pETEinsert)
714 {
715 pETEchaseBackTMP = pETEchase->back;
716 pETEinsert->back->next = AET;
717 if (AET)
718 AET->back = pETEinsert->back;
719 pETEinsert->next = pETEchase;
720 pETEchase->back->next = pETEinsert;
721 pETEchase->back = pETEinsert;
722 pETEinsert->back = pETEchaseBackTMP;
723 changed = 1;
724 }
725 }
726 return changed;
727 }
728
729 /*!
730 \overload
731 */
scan(const Q3PointArray & pa,bool winding,int index,int npoints)732 void Q3PolygonScanner::scan(const Q3PointArray& pa, bool winding, int index, int npoints)
733 {
734 scan(pa, winding, index, npoints, true);
735 }
736
737 /*!
738 \overload
739
740 If \a stitchable is false, the right and bottom edges of the
741 polygon are included. This causes adjacent polygons to overlap.
742 */
scan(const Q3PointArray & pa,bool winding,int index,int npoints,bool stitchable)743 void Q3PolygonScanner::scan(const Q3PointArray& pa, bool winding, int index, int npoints, bool stitchable)
744 {
745 scan(pa, winding, index, npoints,
746 stitchable ? Edge(Left+Top) : Edge(Left+Right+Top+Bottom));
747 }
748
749 /*!
750 Calls processSpans() for all scanlines of the polygon defined by
751 \a npoints starting at \a index in \a pa.
752
753 If \a winding is true, the Winding algorithm rather than the
754 Odd-Even rule is used.
755
756 The \a edges is any bitwise combination of:
757 \list
758 \i Q3PolygonScanner::Left
759 \i Q3PolygonScanner::Right
760 \i Q3PolygonScanner::Top
761 \i Q3PolygonScanner::Bottom
762 \endlist
763 \a edges determines which edges are included.
764
765 \warning The edges feature does not work properly.
766
767 */
scan(const Q3PointArray & pa,bool winding,int index,int npoints,Edge edges)768 void Q3PolygonScanner::scan(const Q3PointArray& pa, bool winding, int index, int npoints, Edge edges)
769 {
770
771
772 DDXPointPtr ptsIn = (DDXPointPtr)pa.data();
773 ptsIn += index;
774 register EdgeTableEntry *pAET; /* the Active Edge Table */
775 register int y; /* the current scanline */
776 register int nPts = 0; /* number of pts in buffer */
777 register EdgeTableEntry *pWETE; /* Winding Edge Table */
778 register ScanLineList *pSLL; /* Current ScanLineList */
779 register DDXPointPtr ptsOut; /* ptr to output buffers */
780 int *width;
781 DDXPointRec FirstPoint[NUMPTSTOBUFFER]; /* the output buffers */
782 int FirstWidth[NUMPTSTOBUFFER];
783 EdgeTableEntry *pPrevAET; /* previous AET entry */
784 EdgeTable ET; /* Edge Table header node */
785 EdgeTableEntry AET; /* Active ET header node */
786 EdgeTableEntry *pETEs; /* Edge Table Entries buff */
787 ScanLineListBlock SLLBlock; /* header for ScanLineList */
788 int fixWAET = 0;
789 int edge_l = (edges & Left) ? 1 : 0;
790 int edge_r = (edges & Right) ? 1 : 0;
791 int edge_t = 1; //#### (edges & Top) ? 1 : 0;
792 int edge_b = (edges & Bottom) ? 1 : 0;
793
794 if (npoints == -1)
795 npoints = pa.size();
796
797 if (npoints < 3)
798 return;
799
800 if(!(pETEs = (EdgeTableEntry *)
801 malloc(sizeof(EdgeTableEntry) * npoints)))
802 return;
803 ptsOut = FirstPoint;
804 width = FirstWidth;
805 if (!miCreateETandAET(npoints, ptsIn, &ET, &AET, pETEs, &SLLBlock))
806 {
807 free(pETEs);
808 return;
809 }
810 pSLL = ET.scanlines.next;
811
812 if (!winding)
813 {
814 /*
815 * for each scanline
816 */
817 for (y = ET.ymin+1-edge_t; y < ET.ymax+edge_b; y++)
818 {
819 /*
820 * Add a new edge to the active edge table when we
821 * get to the next edge.
822 */
823 if (pSLL && y == pSLL->scanline)
824 {
825 miloadAET(&AET, pSLL->edgelist);
826 pSLL = pSLL->next;
827 }
828 pPrevAET = &AET;
829 pAET = AET.next;
830
831 /*
832 * for each active edge
833 */
834 while (pAET)
835 {
836 ptsOut->x = pAET->bres.minor + 1 - edge_l;
837 ptsOut++->y = y;
838 *width++ = pAET->next->bres.minor - pAET->bres.minor
839 - 1 + edge_l + edge_r;
840 nPts++;
841
842 /*
843 * send out the buffer when its full
844 */
845 if (nPts == NUMPTSTOBUFFER)
846 {
847 processSpans(nPts, (QPoint*)FirstPoint, FirstWidth);
848 ptsOut = FirstPoint;
849 width = FirstWidth;
850 nPts = 0;
851 }
852 EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
853 EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
854 }
855 miInsertionSort(&AET);
856 }
857 }
858 else /* default to WindingNumber */
859 {
860 /*
861 * for each scanline
862 */
863 for (y = ET.ymin+1-edge_t; y < ET.ymax+edge_b; y++)
864 {
865 /*
866 * Add a new edge to the active edge table when we
867 * get to the next edge.
868 */
869 if (pSLL && y == pSLL->scanline)
870 {
871 miloadAET(&AET, pSLL->edgelist);
872 micomputeWAET(&AET);
873 pSLL = pSLL->next;
874 }
875 pPrevAET = &AET;
876 pAET = AET.next;
877 pWETE = pAET;
878
879 /*
880 * for each active edge
881 */
882 while (pAET)
883 {
884 /*
885 * if the next edge in the active edge table is
886 * also the next edge in the winding active edge
887 * table.
888 */
889 if (pWETE == pAET)
890 {
891 ptsOut->x = pAET->bres.minor + 1 - edge_l;
892 ptsOut++->y = y;
893 *width++ = pAET->nextWETE->bres.minor - pAET->bres.minor - 1 + edge_l + edge_r;
894 nPts++;
895
896 /*
897 * send out the buffer
898 */
899 if (nPts == NUMPTSTOBUFFER)
900 {
901 processSpans(nPts, (QPoint*)FirstPoint, FirstWidth);
902 ptsOut = FirstPoint;
903 width = FirstWidth;
904 nPts = 0;
905 }
906
907 pWETE = pWETE->nextWETE;
908 while (pWETE != pAET) {
909 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
910 }
911 pWETE = pWETE->nextWETE;
912 }
913 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
914 }
915
916 /*
917 * reevaluate the Winding active edge table if we
918 * just had to resort it or if we just exited an edge.
919 */
920 if (miInsertionSort(&AET) || fixWAET)
921 {
922 micomputeWAET(&AET);
923 fixWAET = 0;
924 }
925 }
926 }
927
928 /*
929 * Get any spans that we missed by buffering
930 */
931
932
933 processSpans(nPts, (QPoint*)FirstPoint, FirstWidth);
934 free(pETEs);
935 miFreeStorage(SLLBlock.next);
936 }
937 /***** END OF X11-based CODE *****/
938
939 QT_END_NAMESPACE
940