File indexing completed on 2024-06-09 13:46:43

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