← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/qt3support/other/q3polygonscanner.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

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