File indexing completed on 2024-04-21 05:43:44
0001 /**************************************************************************** 0002 ** 0003 ** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). 0004 ** Contact: http://www.qt-project.org/legal 0005 ** 0006 ** This file is part of the Qt3Support module of the Qt Toolkit. 0007 ** 0008 ** $QT_BEGIN_LICENSE:LGPL$ 0009 ** Commercial License Usage 0010 ** Licensees holding valid commercial Qt licenses may use this file in 0011 ** accordance with the commercial license agreement provided with the 0012 ** Software or, alternatively, in accordance with the terms contained in 0013 ** a written agreement between you and Digia. For licensing terms and 0014 ** conditions see http://qt.digia.com/licensing. For further information 0015 ** use the contact form at http://qt.digia.com/contact-us. 0016 ** 0017 ** GNU Lesser General Public License Usage 0018 ** Alternatively, this file may be used under the terms of the GNU Lesser 0019 ** General Public License version 2.1 as published by the Free Software 0020 ** Foundation and appearing in the file LICENSE.LGPL included in the 0021 ** packaging of this file. Please review the following information to 0022 ** ensure the GNU Lesser General Public License version 2.1 requirements 0023 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. 0024 ** 0025 ** In addition, as a special exception, Digia gives you certain additional 0026 ** rights. These rights are described in the Digia Qt LGPL Exception 0027 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. 0028 ** 0029 ** GNU General Public License Usage 0030 ** Alternatively, this file may be used under the terms of the GNU 0031 ** General Public License version 3.0 as published by the Free Software 0032 ** Foundation and appearing in the file LICENSE.GPL included in the 0033 ** packaging of this file. Please review the following information to 0034 ** ensure the GNU General Public License version 3.0 requirements will be 0035 ** met: http://www.gnu.org/copyleft/gpl.html. 0036 ** 0037 ** 0038 ** $QT_END_LICENSE$ 0039 ** 0040 ****************************************************************************/ 0041 0042 #include "ktlq3polygonscanner.h" 0043 0044 #include <QPolygon> 0045 #include <limits> 0046 #include <stdlib.h> 0047 0048 QT_BEGIN_NAMESPACE 0049 0050 // Based on Xserver code miFillGeneralPoly... 0051 /* 0052 * 0053 * Written by Brian Kelleher; Oct. 1985 0054 * 0055 * Routine to fill a polygon. Two fill rules are 0056 * supported: frWINDING and frEVENODD. 0057 * 0058 * See fillpoly.h for a complete description of the algorithm. 0059 */ 0060 0061 /* 0062 * These are the data structures needed to scan 0063 * convert regions. Two different scan conversion 0064 * methods are available -- the even-odd method, and 0065 * the winding number method. 0066 * The even-odd rule states that a point is inside 0067 * the polygon if a ray drawn from that point in any 0068 * direction will pass through an odd number of 0069 * path segments. 0070 * By the winding number rule, a point is decided 0071 * to be inside the polygon if a ray drawn from that 0072 * point in any direction passes through a different 0073 * number of clockwise and counterclockwise path 0074 * segments. 0075 * 0076 * These data structures are adapted somewhat from 0077 * the algorithm in (Foley/Van Dam) for scan converting 0078 * polygons. 0079 * The basic algorithm is to start at the top (smallest y) 0080 * of the polygon, stepping down to the bottom of 0081 * the polygon by incrementing the y coordinate. We 0082 * keep a list of edges which the current scanline crosses, 0083 * sorted by x. This list is called the Active Edge Table (AET) 0084 * As we change the y-coordinate, we update each entry in 0085 * in the active edge table to reflect the edges new xcoord. 0086 * This list must be sorted at each scanline in case 0087 * two edges intersect. 0088 * We also keep a data structure known as the Edge Table (ET), 0089 * which keeps track of all the edges which the current 0090 * scanline has not yet reached. The ET is basically a 0091 * list of ScanLineList structures containing a list of 0092 * edges which are entered at a given scanline. There is one 0093 * ScanLineList per scanline at which an edge is entered. 0094 * When we enter a new edge, we move it from the ET to the AET. 0095 * 0096 * From the AET, we can implement the even-odd rule as in 0097 * (Foley/Van Dam). 0098 * The winding number rule is a little trickier. We also 0099 * keep the EdgeTableEntries in the AET linked by the 0100 * nextWETE (winding EdgeTableEntry) link. This allows 0101 * the edges to be linked just as before for updating 0102 * purposes, but only uses the edges linked by the nextWETE 0103 * link as edges representing spans of the polygon to 0104 * drawn (as with the even-odd rule). 0105 */ 0106 0107 /* $XConsortium: miscanfill.h,v 1.5 94/04/17 20:27:50 dpw Exp $ */ 0108 /* 0109 0110 Copyright (c) 1987 X Consortium 0111 0112 Permission is hereby granted, free of charge, to any person obtaining 0113 a copy of this software and associated documentation files (the 0114 "Software"), to deal in the Software without restriction, including 0115 without limitation the rights to use, copy, modify, merge, publish, 0116 distribute, sublicense, and/or sell copies of the Software, and to 0117 permit persons to whom the Software is furnished to do so, subject to 0118 the following conditions: 0119 0120 The above copyright notice and this permission notice shall be included 0121 in all copies or substantial portions of the Software. 0122 0123 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 0124 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 0125 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 0126 IN NO EVENT SHALL THE X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR 0127 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 0128 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 0129 OTHER DEALINGS IN THE SOFTWARE. 0130 0131 Except as contained in this notice, the name of the X Consortium shall 0132 not be used in advertising or otherwise to promote the sale, use or 0133 other dealings in this Software without prior written authorization 0134 from the X Consortium. 0135 0136 */ 0137 0138 /* 0139 * scanfill.h 0140 * 0141 * Written by Brian Kelleher; Jan 1985 0142 * 0143 * This file contains a few macros to help track 0144 * the edge of a filled object. The object is assumed 0145 * to be filled in scanline order, and thus the 0146 * algorithm used is an extension of Bresenham's line 0147 * drawing algorithm which assumes that y is always the 0148 * major axis. 0149 * Since these pieces of code are the same for any filled shape, 0150 * it is more convenient to gather the library in one 0151 * place, but since these pieces of code are also in 0152 * the inner loops of output primitives, procedure call 0153 * overhead is out of the question. 0154 * See the author for a derivation if needed. 0155 */ 0156 0157 /* 0158 * In scan converting polygons, we want to choose those pixels 0159 * which are inside the polygon. Thus, we add .5 to the starting 0160 * x coordinate for both left and right edges. Now we choose the 0161 * first pixel which is inside the pgon for the left edge and the 0162 * first pixel which is outside the pgon for the right edge. 0163 * Draw the left pixel, but not the right. 0164 * 0165 * How to add .5 to the starting x coordinate: 0166 * If the edge is moving to the right, then subtract dy from the 0167 * error term from the general form of the algorithm. 0168 * If the edge is moving to the left, then add dy to the error term. 0169 * 0170 * The reason for the difference between edges moving to the left 0171 * and edges moving to the right is simple: If an edge is moving 0172 * to the right, then we want the algorithm to flip immediately. 0173 * If it is moving to the left, then we don't want it to flip until 0174 * we traverse an entire pixel. 0175 */ 0176 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) \ 0177 { \ 0178 int dx; /* local storage */ \ 0179 \ 0180 /* \ 0181 * if the edge is horizontal, then it is ignored \ 0182 * and assumed not to be processed. Otherwise, do this stuff. \ 0183 */ \ 0184 if ((dy) != 0) { \ 0185 xStart = (x1); \ 0186 dx = (x2)-xStart; \ 0187 if (dx < 0) { \ 0188 m = dx / (dy); \ 0189 m1 = m - 1; \ 0190 incr1 = -2 * dx + 2 * (dy)*m1; \ 0191 incr2 = -2 * dx + 2 * (dy)*m; \ 0192 d = 2 * m * (dy)-2 * dx - 2 * (dy); \ 0193 } else { \ 0194 m = dx / (dy); \ 0195 m1 = m + 1; \ 0196 incr1 = 2 * dx - 2 * (dy)*m1; \ 0197 incr2 = 2 * dx - 2 * (dy)*m; \ 0198 d = -2 * m * (dy) + 2 * dx; \ 0199 } \ 0200 } \ 0201 } 0202 0203 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) \ 0204 { \ 0205 if (m1 > 0) { \ 0206 if (d > 0) { \ 0207 minval += m1; \ 0208 d += incr1; \ 0209 } else { \ 0210 minval += m; \ 0211 d += incr2; \ 0212 } \ 0213 } else { \ 0214 if (d >= 0) { \ 0215 minval += m1; \ 0216 d += incr1; \ 0217 } else { \ 0218 minval += m; \ 0219 d += incr2; \ 0220 } \ 0221 } \ 0222 } 0223 0224 /* 0225 * This structure contains all of the information needed 0226 * to run the bresenham algorithm. 0227 * The variables may be hardcoded into the declarations 0228 * instead of using this structure to make use of 0229 * register declarations. 0230 */ 0231 typedef struct { 0232 int minor; /* minor axis */ 0233 int d; /* decision variable */ 0234 int m, m1; /* slope and slope+1 */ 0235 int incr1, incr2; /* error increments */ 0236 } BRESINFO; 0237 0238 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) BRESINITPGON(dmaj, min1, min2, bres.minor, bres.d, bres.m, bres.m1, bres.incr1, bres.incr2) 0239 0240 #define BRESINCRPGONSTRUCT(bres) BRESINCRPGON(bres.d, bres.minor, bres.m, bres.m1, bres.incr1, bres.incr2) 0241 0242 typedef struct _EdgeTableEntry { 0243 int ymax; /* ycoord at which we exit this edge. */ 0244 BRESINFO bres; /* Bresenham info to run the edge */ 0245 struct _EdgeTableEntry *next; /* next in the list */ 0246 struct _EdgeTableEntry *back; /* for insertion sort */ 0247 struct _EdgeTableEntry *nextWETE; /* for winding num rule */ 0248 int ClockWise; /* flag for winding number rule */ 0249 } EdgeTableEntry; 0250 0251 typedef struct _ScanLineList { 0252 int scanline; /* the scanline represented */ 0253 EdgeTableEntry *edgelist; /* header node */ 0254 struct _ScanLineList *next; /* next in the list */ 0255 } ScanLineList; 0256 0257 typedef struct { 0258 int ymax; /* ymax for the polygon */ 0259 int ymin; /* ymin for the polygon */ 0260 ScanLineList scanlines; /* header node */ 0261 } EdgeTable; 0262 0263 /* 0264 * Here is a struct to help with storage allocation 0265 * so we can allocate a big chunk at a time, and then take 0266 * pieces from this heap when we need to. 0267 */ 0268 #define SLLSPERBLOCK 25 0269 0270 typedef struct _ScanLineListBlock { 0271 ScanLineList SLLs[SLLSPERBLOCK]; 0272 struct _ScanLineListBlock *next; 0273 } ScanLineListBlock; 0274 0275 /* 0276 * number of points to buffer before sending them off 0277 * to scanlines() : Must be an even number 0278 */ 0279 #define NUMPTSTOBUFFER 200 0280 0281 /* 0282 * 0283 * a few macros for the inner loops of the fill code where 0284 * performance considerations don't allow a procedure call. 0285 * 0286 * Evaluate the given edge at the given scanline. 0287 * If the edge has expired, then we leave it and fix up 0288 * the active edge table; otherwise, we increment the 0289 * x value to be ready for the next scanline. 0290 * The winding number rule is in effect, so we must notify 0291 * the caller when the edge has been removed so he 0292 * can reorder the Winding Active Edge Table. 0293 */ 0294 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) \ 0295 { \ 0296 if (pAET->ymax == y) { /* leaving this edge */ \ 0297 pPrevAET->next = pAET->next; \ 0298 pAET = pPrevAET->next; \ 0299 fixWAET = 1; \ 0300 if (pAET) \ 0301 pAET->back = pPrevAET; \ 0302 } else { \ 0303 BRESINCRPGONSTRUCT(pAET->bres); \ 0304 pPrevAET = pAET; \ 0305 pAET = pAET->next; \ 0306 } \ 0307 } 0308 0309 /* 0310 * Evaluate the given edge at the given scanline. 0311 * If the edge has expired, then we leave it and fix up 0312 * the active edge table; otherwise, we increment the 0313 * x value to be ready for the next scanline. 0314 * The even-odd rule is in effect. 0315 */ 0316 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) \ 0317 { \ 0318 if (pAET->ymax == y) { /* leaving this edge */ \ 0319 pPrevAET->next = pAET->next; \ 0320 pAET = pPrevAET->next; \ 0321 if (pAET) \ 0322 pAET->back = pPrevAET; \ 0323 } else { \ 0324 BRESINCRPGONSTRUCT(pAET->bres) \ 0325 pPrevAET = pAET; \ 0326 pAET = pAET->next; \ 0327 } \ 0328 } 0329 0330 /*********************************************************** 0331 0332 Copyright (c) 1987 X Consortium 0333 0334 Permission is hereby granted, free of charge, to any person obtaining a copy 0335 of this software and associated documentation files (the "Software"), to deal 0336 in the Software without restriction, including without limitation the rights 0337 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 0338 copies of the Software, and to permit persons to whom the Software is 0339 furnished to do so, subject to the following conditions: 0340 0341 The above copyright notice and this permission notice shall be included in 0342 all copies or substantial portions of the Software. 0343 0344 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 0345 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 0346 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 0347 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 0348 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 0349 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 0350 0351 Except as contained in this notice, the name of the X Consortium shall not be 0352 used in advertising or otherwise to promote the sale, use or other dealings 0353 in this Software without prior written authorization from the X Consortium. 0354 0355 0356 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. 0357 0358 All Rights Reserved 0359 0360 Permission to use, copy, modify, and distribute this software and its 0361 documentation for any purpose and without fee is hereby granted, 0362 provided that the above copyright notice appear in all copies and that 0363 both that copyright notice and this permission notice appear in 0364 supporting documentation, and that the name of Digital not be 0365 used in advertising or publicity pertaining to distribution of the 0366 software without specific, written prior permission. 0367 0368 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING 0369 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL 0370 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR 0371 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, 0372 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, 0373 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 0374 SOFTWARE. 0375 0376 ******************************************************************/ 0377 0378 /* 0379 * fillUtils.c 0380 * 0381 * Written by Brian Kelleher; Oct. 1985 0382 * 0383 * This module contains all of the utility functions 0384 * needed to scan convert a polygon. 0385 * 0386 */ 0387 /* 0388 * InsertEdgeInET 0389 * 0390 * Insert the given edge into the edge table. 0391 * First we must find the correct bucket in the 0392 * Edge table, then find the right slot in the 0393 * bucket. Finally, we can insert it. 0394 * 0395 */ 0396 static bool miInsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline, ScanLineListBlock **SLLBlock, int *iSLLBlock) 0397 { 0398 EdgeTableEntry *start, *prev; 0399 ScanLineList *pSLL, *pPrevSLL; 0400 ScanLineListBlock *tmpSLLBlock; 0401 0402 /* 0403 * find the right bucket to put the edge into 0404 */ 0405 pPrevSLL = &ET->scanlines; 0406 pSLL = pPrevSLL->next; 0407 while (pSLL && (pSLL->scanline < scanline)) { 0408 pPrevSLL = pSLL; 0409 pSLL = pSLL->next; 0410 } 0411 0412 /* 0413 * reassign pSLL (pointer to ScanLineList) if necessary 0414 */ 0415 if ((!pSLL) || (pSLL->scanline > scanline)) { 0416 if (*iSLLBlock > SLLSPERBLOCK - 1) { 0417 tmpSLLBlock = static_cast<ScanLineListBlock *>(malloc(sizeof(ScanLineListBlock))); 0418 if (!tmpSLLBlock) 0419 return false; 0420 (*SLLBlock)->next = tmpSLLBlock; 0421 tmpSLLBlock->next = nullptr; 0422 *SLLBlock = tmpSLLBlock; 0423 *iSLLBlock = 0; 0424 } 0425 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]); 0426 0427 pSLL->next = pPrevSLL->next; 0428 pSLL->edgelist = nullptr; 0429 pPrevSLL->next = pSLL; 0430 } 0431 pSLL->scanline = scanline; 0432 0433 /* 0434 * now insert the edge in the right bucket 0435 */ 0436 prev = nullptr; 0437 start = pSLL->edgelist; 0438 while (start && (start->bres.minor < ETE->bres.minor)) { 0439 prev = start; 0440 start = start->next; 0441 } 0442 ETE->next = start; 0443 0444 if (prev) 0445 prev->next = ETE; 0446 else 0447 pSLL->edgelist = ETE; 0448 return true; 0449 } 0450 0451 /* 0452 * CreateEdgeTable 0453 * 0454 * This routine creates the edge table for 0455 * scan converting polygons. 0456 * The Edge Table (ET) looks like: 0457 * 0458 * EdgeTable 0459 * -------- 0460 * | ymax | ScanLineLists 0461 * |scanline|-->------------>-------------->... 0462 * -------- |scanline| |scanline| 0463 * |edgelist| |edgelist| 0464 * --------- --------- 0465 * | | 0466 * | | 0467 * V V 0468 * list of ETEs list of ETEs 0469 * 0470 * where ETE is an EdgeTableEntry data structure, 0471 * and there is one ScanLineList per scanline at 0472 * which an edge is initially entered. 0473 * 0474 */ 0475 0476 namespace { // anonymous namespace, don't export 0477 typedef struct { 0478 int x, y; 0479 } DDXPointRec, *DDXPointPtr; 0480 } 0481 0482 /* 0483 * Clean up our act. 0484 */ 0485 static void miFreeStorage(ScanLineListBlock *pSLLBlock) 0486 { 0487 ScanLineListBlock *tmpSLLBlock; 0488 0489 while (pSLLBlock) { 0490 tmpSLLBlock = pSLLBlock->next; 0491 free(pSLLBlock); 0492 pSLLBlock = tmpSLLBlock; 0493 } 0494 } 0495 0496 static bool miCreateETandAET(int count, DDXPointPtr pts, EdgeTable *ET, EdgeTableEntry *AET, EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock) 0497 { 0498 DDXPointPtr top, bottom; 0499 DDXPointPtr PrevPt, CurrPt; 0500 int iSLLBlock = 0; 0501 0502 int dy; 0503 0504 if (count < 2) 0505 return true; 0506 0507 /* 0508 * initialize the Active Edge Table 0509 */ 0510 AET->next = nullptr; 0511 AET->back = nullptr; 0512 AET->nextWETE = nullptr; 0513 AET->bres.minor = std::numeric_limits<decltype(AET->bres.minor)>::min(); 0514 0515 /* 0516 * initialize the Edge Table. 0517 */ 0518 ET->scanlines.next = nullptr; 0519 ET->ymax = std::numeric_limits<decltype(ET->ymax)>::min(); 0520 ET->ymin = std::numeric_limits<decltype(ET->ymin)>::max(); 0521 pSLLBlock->next = nullptr; 0522 0523 PrevPt = &pts[count - 1]; 0524 0525 /* 0526 * for each vertex in the array of points. 0527 * In this loop we are dealing with two vertices at 0528 * a time -- these make up one edge of the polygon. 0529 */ 0530 while (count--) { 0531 CurrPt = pts++; 0532 0533 /* 0534 * find out which point is above and which is below. 0535 */ 0536 if (PrevPt->y > CurrPt->y) { 0537 bottom = PrevPt, top = CurrPt; 0538 pETEs->ClockWise = 0; 0539 } else { 0540 bottom = CurrPt, top = PrevPt; 0541 pETEs->ClockWise = 1; 0542 } 0543 0544 /* 0545 * don't add horizontal edges to the Edge table. 0546 */ 0547 if (bottom->y != top->y) { 0548 pETEs->ymax = bottom->y - 1; /* -1 so we don't get last scanline */ 0549 0550 /* 0551 * initialize integer edge algorithm 0552 */ 0553 dy = bottom->y - top->y; 0554 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres) 0555 0556 if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock)) { 0557 miFreeStorage(pSLLBlock->next); 0558 return false; 0559 } 0560 0561 ET->ymax = qMax(ET->ymax, PrevPt->y); 0562 ET->ymin = qMin(ET->ymin, PrevPt->y); 0563 pETEs++; 0564 } 0565 0566 PrevPt = CurrPt; 0567 } 0568 return true; 0569 } 0570 0571 /* 0572 * loadAET 0573 * 0574 * This routine moves EdgeTableEntries from the 0575 * EdgeTable into the Active Edge Table, 0576 * leaving them sorted by smaller x coordinate. 0577 * 0578 */ 0579 0580 static void miloadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs) 0581 { 0582 EdgeTableEntry *pPrevAET; 0583 EdgeTableEntry *tmp; 0584 0585 pPrevAET = AET; 0586 AET = AET->next; 0587 while (ETEs) { 0588 while (AET && (AET->bres.minor < ETEs->bres.minor)) { 0589 pPrevAET = AET; 0590 AET = AET->next; 0591 } 0592 tmp = ETEs->next; 0593 ETEs->next = AET; 0594 if (AET) 0595 AET->back = ETEs; 0596 ETEs->back = pPrevAET; 0597 pPrevAET->next = ETEs; 0598 pPrevAET = ETEs; 0599 0600 ETEs = tmp; 0601 } 0602 } 0603 0604 /* 0605 * computeWAET 0606 * 0607 * This routine links the AET by the 0608 * nextWETE (winding EdgeTableEntry) link for 0609 * use by the winding number rule. The final 0610 * Active Edge Table (AET) might look something 0611 * like: 0612 * 0613 * AET 0614 * ---------- --------- --------- 0615 * |ymax | |ymax | |ymax | 0616 * | ... | |... | |... | 0617 * |next |->|next |->|next |->... 0618 * |nextWETE| |nextWETE| |nextWETE| 0619 * --------- --------- ^-------- 0620 * | | | 0621 * V-------------------> V---> ... 0622 * 0623 */ 0624 static void micomputeWAET(EdgeTableEntry *AET) 0625 { 0626 EdgeTableEntry *pWETE; 0627 int inside = 1; 0628 int isInside = 0; 0629 0630 AET->nextWETE = nullptr; 0631 pWETE = AET; 0632 AET = AET->next; 0633 while (AET) { 0634 if (AET->ClockWise) 0635 isInside++; 0636 else 0637 isInside--; 0638 0639 if ((!inside && !isInside) || (inside && isInside)) { 0640 pWETE->nextWETE = AET; 0641 pWETE = AET; 0642 inside = !inside; 0643 } 0644 AET = AET->next; 0645 } 0646 pWETE->nextWETE = nullptr; 0647 } 0648 0649 /* 0650 * InsertionSort 0651 * 0652 * Just a simple insertion sort using 0653 * pointers and back pointers to sort the Active 0654 * Edge Table. 0655 * 0656 */ 0657 0658 static int miInsertionSort(EdgeTableEntry *AET) 0659 { 0660 EdgeTableEntry *pETEchase; 0661 EdgeTableEntry *pETEinsert; 0662 EdgeTableEntry *pETEchaseBackTMP; 0663 int changed = 0; 0664 0665 AET = AET->next; 0666 while (AET) { 0667 pETEinsert = AET; 0668 pETEchase = AET; 0669 while (pETEchase->back->bres.minor > AET->bres.minor) 0670 pETEchase = pETEchase->back; 0671 0672 AET = AET->next; 0673 if (pETEchase != pETEinsert) { 0674 pETEchaseBackTMP = pETEchase->back; 0675 pETEinsert->back->next = AET; 0676 if (AET) 0677 AET->back = pETEinsert->back; 0678 pETEinsert->next = pETEchase; 0679 pETEchase->back->next = pETEinsert; 0680 pETEchase->back = pETEinsert; 0681 pETEinsert->back = pETEchaseBackTMP; 0682 changed = 1; 0683 } 0684 } 0685 return changed; 0686 } 0687 0688 /*! 0689 \overload 0690 */ 0691 void KtlQ3PolygonScanner::scan(const QPolygon &pa, bool winding, int index, int npoints) 0692 { 0693 scan(pa, winding, index, npoints, true); 0694 } 0695 0696 /*! 0697 \overload 0698 0699 If \a stitchable is false, the right and bottom edges of the 0700 polygon are included. This causes adjacent polygons to overlap. 0701 */ 0702 void KtlQ3PolygonScanner::scan(const QPolygon &pa, bool winding, int index, int npoints, bool stitchable) 0703 { 0704 scan(pa, winding, index, npoints, stitchable ? Edge(Left + Top) : Edge(Left + Right + Top + Bottom)); 0705 } 0706 0707 /*! 0708 Calls processSpans() for all scanlines of the polygon defined by 0709 \a npoints starting at \a index in \a pa. 0710 0711 If \a winding is true, the Winding algorithm rather than the 0712 Odd-Even rule is used. 0713 0714 The \a edges is any bitwise combination of: 0715 \list 0716 \i KtlQ3PolygonScanner::Left 0717 \i KtlQ3PolygonScanner::Right 0718 \i KtlQ3PolygonScanner::Top 0719 \i KtlQ3PolygonScanner::Bottom 0720 \endlist 0721 \a edges determines which edges are included. 0722 0723 \warning The edges feature does not work properly. 0724 0725 */ 0726 void KtlQ3PolygonScanner::scan(const QPolygon &pa, bool winding, int index, int npoints, Edge edges) 0727 { 0728 DDXPointPtr ptsIn = reinterpret_cast<DDXPointPtr>( const_cast<QPoint*>(pa.data())); 0729 ptsIn += index; 0730 EdgeTableEntry *pAET; /* the Active Edge Table */ 0731 int y; /* the current scanline */ 0732 int nPts = 0; /* number of pts in buffer */ 0733 EdgeTableEntry *pWETE; /* Winding Edge Table */ 0734 ScanLineList *pSLL; /* Current ScanLineList */ 0735 DDXPointPtr ptsOut; /* ptr to output buffers */ 0736 int *width; 0737 DDXPointRec FirstPoint[NUMPTSTOBUFFER]; /* the output buffers */ 0738 int FirstWidth[NUMPTSTOBUFFER]; 0739 EdgeTableEntry *pPrevAET; /* previous AET entry */ 0740 EdgeTable ET; /* Edge Table header node */ 0741 EdgeTableEntry AET; /* Active ET header node */ 0742 EdgeTableEntry *pETEs; /* Edge Table Entries buff */ 0743 ScanLineListBlock SLLBlock; /* header for ScanLineList */ 0744 int fixWAET = 0; 0745 int edge_l = (edges & Left) ? 1 : 0; 0746 int edge_r = (edges & Right) ? 1 : 0; 0747 int edge_t = 1; //#### (edges & Top) ? 1 : 0; 0748 int edge_b = (edges & Bottom) ? 1 : 0; 0749 0750 if (npoints == -1) 0751 npoints = pa.size(); 0752 0753 if (npoints < 3) 0754 return; 0755 0756 if (!(pETEs = static_cast<EdgeTableEntry *>(malloc(sizeof(EdgeTableEntry) * npoints)))) 0757 return; 0758 ptsOut = FirstPoint; 0759 width = FirstWidth; 0760 if (!miCreateETandAET(npoints, ptsIn, &ET, &AET, pETEs, &SLLBlock)) { 0761 free(pETEs); 0762 return; 0763 } 0764 pSLL = ET.scanlines.next; 0765 0766 if (!winding) { 0767 /* 0768 * for each scanline 0769 */ 0770 for (y = ET.ymin + 1 - edge_t; y < ET.ymax + edge_b; y++) { 0771 /* 0772 * Add a new edge to the active edge table when we 0773 * get to the next edge. 0774 */ 0775 if (pSLL && y == pSLL->scanline) { 0776 miloadAET(&AET, pSLL->edgelist); 0777 pSLL = pSLL->next; 0778 } 0779 pPrevAET = &AET; 0780 pAET = AET.next; 0781 0782 /* 0783 * for each active edge 0784 */ 0785 while (pAET) { 0786 ptsOut->x = pAET->bres.minor + 1 - edge_l; 0787 ptsOut++->y = y; 0788 *width++ = pAET->next->bres.minor - pAET->bres.minor - 1 + edge_l + edge_r; 0789 nPts++; 0790 0791 /* 0792 * send out the buffer when its full 0793 */ 0794 if (nPts == NUMPTSTOBUFFER) { 0795 processSpans(nPts, reinterpret_cast<QPoint *>(FirstPoint), FirstWidth); 0796 ptsOut = FirstPoint; 0797 width = FirstWidth; 0798 nPts = 0; 0799 } 0800 EVALUATEEDGEEVENODD(pAET, pPrevAET, y) 0801 EVALUATEEDGEEVENODD(pAET, pPrevAET, y) 0802 } 0803 miInsertionSort(&AET); 0804 } 0805 } else /* default to WindingNumber */ 0806 { 0807 /* 0808 * for each scanline 0809 */ 0810 for (y = ET.ymin + 1 - edge_t; y < ET.ymax + edge_b; y++) { 0811 /* 0812 * Add a new edge to the active edge table when we 0813 * get to the next edge. 0814 */ 0815 if (pSLL && y == pSLL->scanline) { 0816 miloadAET(&AET, pSLL->edgelist); 0817 micomputeWAET(&AET); 0818 pSLL = pSLL->next; 0819 } 0820 pPrevAET = &AET; 0821 pAET = AET.next; 0822 pWETE = pAET; 0823 0824 /* 0825 * for each active edge 0826 */ 0827 while (pAET) { 0828 /* 0829 * if the next edge in the active edge table is 0830 * also the next edge in the winding active edge 0831 * table. 0832 */ 0833 if (pWETE == pAET) { 0834 ptsOut->x = pAET->bres.minor + 1 - edge_l; 0835 ptsOut++->y = y; 0836 *width++ = pAET->nextWETE->bres.minor - pAET->bres.minor - 1 + edge_l + edge_r; 0837 nPts++; 0838 0839 /* 0840 * send out the buffer 0841 */ 0842 if (nPts == NUMPTSTOBUFFER) { 0843 processSpans(nPts, reinterpret_cast<QPoint *>(FirstPoint), FirstWidth); 0844 ptsOut = FirstPoint; 0845 width = FirstWidth; 0846 nPts = 0; 0847 } 0848 0849 pWETE = pWETE->nextWETE; 0850 while (pWETE != pAET) { 0851 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) 0852 } 0853 pWETE = pWETE->nextWETE; 0854 } 0855 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) 0856 } 0857 0858 /* 0859 * reevaluate the Winding active edge table if we 0860 * just had to resort it or if we just exited an edge. 0861 */ 0862 if (miInsertionSort(&AET) || fixWAET) { 0863 micomputeWAET(&AET); 0864 fixWAET = 0; 0865 } 0866 } 0867 } 0868 0869 /* 0870 * Get any spans that we missed by buffering 0871 */ 0872 0873 processSpans(nPts, reinterpret_cast<QPoint *>(FirstPoint), FirstWidth); 0874 free(pETEs); 0875 miFreeStorage(SLLBlock.next); 0876 } 0877 /***** END OF X11-based CODE *****/ 0878 0879 QT_END_NAMESPACE