1
/****************************************************************************
3
** Copyright (C) 1992-2005 Trolltech AS. All rights reserved.
5
** This file is part of the painting module of the Qt Toolkit.
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.
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.
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.
21
** Contact info@trolltech.com if any conditions of this licensing are
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.
27
****************************************************************************/
30
#include "qpainterpath.h"
41
struct QRegionPrivate {
46
inline QRegionPrivate() : numRects(0) {}
47
inline QRegionPrivate(const QRect &r) : rects(1) {
53
inline QRegionPrivate(const QRegionPrivate &r) {
55
numRects = r.numRects;
59
inline QRegionPrivate &operator=(const QRegionPrivate &r) {
61
numRects = r.numRects;
68
# include "qregion_x11.cpp"
69
#elif defined(Q_WS_MAC)
70
# include "qregion_mac.cpp"
71
#elif defined(Q_WS_QWS)
72
static QRegionPrivate qrp;
73
QRegion::QRegionData QRegion::shared_empty = {Q_ATOMIC_INIT(1), &qrp};
76
static bool isEmpty(QRegionPrivate *preg)
78
return !preg || preg->numRects == 0;
81
typedef void (*OverlapFunc)(register QRegionPrivate &dest, register QRect *r1, QRect *r1End,
82
register QRect *r2, QRect *r2End, register int y1, register int y2);
83
typedef void (*NonOverlapFunc)(register QRegionPrivate &dest, register QRect *r, QRect *rEnd,
84
register int y1, register int y2);
86
static void UnionRegion(QRegionPrivate *reg1, QRegionPrivate *reg2, QRegionPrivate &dest);
87
static void IntersectRegion(QRegionPrivate *reg1, QRegionPrivate *reg2,
88
register QRegionPrivate &dest);
89
static void miRegionOp(register QRegionPrivate &dest, QRegionPrivate *reg1, QRegionPrivate *reg2,
90
OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
91
NonOverlapFunc nonOverlap2Func);
93
#define RectangleOut 0
95
#define RectanglePart 2
99
// START OF region.h extract
100
/* $XConsortium: region.h,v 11.14 94/04/17 20:22:20 rws Exp $ */
101
/************************************************************************
103
Copyright (c) 1987 X Consortium
105
Permission is hereby granted, free of charge, to any person obtaining a copy
106
of this software and associated documentation files (the "Software"), to deal
107
in the Software without restriction, including without limitation the rights
108
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
109
copies of the Software, and to permit persons to whom the Software is
110
furnished to do so, subject to the following conditions:
112
The above copyright notice and this permission notice shall be included in
113
all copies or substantial portions of the Software.
115
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
116
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
117
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
118
X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
119
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
120
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
122
Except as contained in this notice, the name of the X Consortium shall not be
123
used in advertising or otherwise to promote the sale, use or other dealings
124
in this Software without prior written authorization from the X Consortium.
127
Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
131
Permission to use, copy, modify, and distribute this software and its
132
documentation for any purpose and without fee is hereby granted,
133
provided that the above copyright notice appear in all copies and that
134
both that copyright notice and this permission notice appear in
135
supporting documentation, and that the name of Digital not be
136
used in advertising or publicity pertaining to distribution of the
137
software without specific, written prior permission.
139
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
140
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
141
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
142
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
143
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
144
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
147
************************************************************************/
154
/* 1 if two BOXs overlap.
155
* 0 if two BOXs do not overlap.
156
* Remember, x2 and y2 are not in the region
158
#define EXTENTCHECK(r1, r2) \
159
((r1)->right() >= (r2)->left() && \
160
(r1)->left() <= (r2)->right() && \
161
(r1)->bottom() >= (r2)->top() && \
162
(r1)->top() <= (r2)->bottom())
165
* update region extents
167
#define EXTENTS(r,idRect){\
168
if((r)->left() < (idRect)->extents.left())\
169
(idRect)->extents.setLeft((r)->left());\
170
if((r)->top() < (idRect)->extents.top())\
171
(idRect)->extents.setTop((r)->top());\
172
if((r)->right() > (idRect)->extents.right())\
173
(idRect)->extents.setRight((r)->right());\
174
if((r)->bottom() > (idRect)->extents.bottom())\
175
(idRect)->extents.setBottom((r)->bottom());\
179
* Check to see if there is enough memory in the present region.
181
#define MEMCHECK(dest, rect, firstrect){\
182
if ((dest).numRects >= ((dest).rects.size()-1)){\
183
firstrect.resize(firstrect.size() * 2); \
184
(rect) = (firstrect).data() + (dest).numRects;\
190
* number of points to buffer before sending them off
191
* to scanlines(): Must be an even number
193
#define NUMPTSTOBUFFER 200
196
* used to allocate buffers for points and link
197
* the buffers together
199
typedef struct _POINTBLOCK {
200
QPoint pts[NUMPTSTOBUFFER];
201
struct _POINTBLOCK *next;
205
// END OF region.h extract
207
// START OF Region.c extract
208
/* $XConsortium: Region.c /main/30 1996/10/22 14:21:24 kaleb $ */
209
/************************************************************************
211
Copyright (c) 1987, 1988 X Consortium
213
Permission is hereby granted, free of charge, to any person obtaining a copy
214
of this software and associated documentation files (the "Software"), to deal
215
in the Software without restriction, including without limitation the rights
216
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
217
copies of the Software, and to permit persons to whom the Software is
218
furnished to do so, subject to the following conditions:
220
The above copyright notice and this permission notice shall be included in
221
all copies or substantial portions of the Software.
223
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
224
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
225
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
226
X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
227
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
228
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
230
Except as contained in this notice, the name of the X Consortium shall not be
231
used in advertising or otherwise to promote the sale, use or other dealings
232
in this Software without prior written authorization from the X Consortium.
235
Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
239
Permission to use, copy, modify, and distribute this software and its
240
documentation for any purpose and without fee is hereby granted,
241
provided that the above copyright notice appear in all copies and that
242
both that copyright notice and this permission notice appear in
243
supporting documentation, and that the name of Digital not be
244
used in advertising or publicity pertaining to distribution of the
245
software without specific, written prior permission.
247
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
248
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
249
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
250
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
251
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
252
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
255
************************************************************************/
257
* The functions in this file implement the Region abstraction, similar to one
258
* used in the X11 sample server. A Region is simply an area, as the name
259
* implies, and is implemented as a "y-x-banded" array of rectangles. To
260
* explain: Each Region is made up of a certain number of rectangles sorted
261
* by y coordinate first, and then by x coordinate.
263
* Furthermore, the rectangles are banded such that every rectangle with a
264
* given upper-left y coordinate (y1) will have the same lower-right y
265
* coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
266
* will span the entire vertical distance of the band. This means that some
267
* areas that could be merged into a taller rectangle will be represented as
268
* several shorter rectangles to account for shorter rectangles to its left
269
* or right but within its "vertical scope".
271
* An added constraint on the rectangles is that they must cover as much
272
* horizontal area as possible. E.g. no two rectangles in a band are allowed
275
* Whenever possible, bands will be merged together to cover a greater vertical
276
* distance (and thus reduce the number of rectangles). Two bands can be merged
277
* only if the bottom of one touches the top of the other and they have
278
* rectangles in the same places (of the same width, of course). This maintains
279
* the y-x-banding that's so nice to have...
281
/* $XFree86: xc/lib/X11/Region.c,v 1.1.1.2.2.2 1998/10/04 15:22:50 hohndel Exp $ */
283
static void UnionRectWithRegion(register const QRect *rect, QRegionPrivate *source,
284
QRegionPrivate &dest)
286
QRegionPrivate region;
288
if (!rect->width() || !rect->height())
290
region.rects.resize(1);
292
region.rects[0] = *rect;
293
region.extents = *rect;
295
UnionRegion(®ion, source, dest);
300
*-----------------------------------------------------------------------
302
* Reset the extents of a region to what they should be. Called by
303
* miSubtract and miIntersect b/c they can't figure it out along the
304
* way or do so easily, as miUnion can.
310
* The region's 'extents' structure is overwritten.
312
*-----------------------------------------------------------------------
314
static void miSetExtents(QRegionPrivate &dest)
316
register const QRect *pBox,
318
register QRect *pExtents;
320
if (dest.numRects == 0) {
321
dest.extents.setCoords(0, 0, 0, 0);
325
pExtents = &dest.extents;
326
pBox = dest.rects.constData();
327
pBoxEnd = &pBox[dest.numRects - 1];
330
* Since pBox is the first rectangle in the region, it must have the
331
* smallest y1 and since pBoxEnd is the last rectangle in the region,
332
* it must have the largest y2, because of banding. Initialize x1 and
333
* x2 from pBox and pBoxEnd, resp., as good things to initialize them
336
pExtents->setLeft(pBox->left());
337
pExtents->setTop(pBox->top());
338
pExtents->setRight(pBoxEnd->right());
339
pExtents->setBottom(pBoxEnd->bottom());
341
Q_ASSERT(pExtents->top() <= pExtents->bottom());
342
while (pBox <= pBoxEnd) {
343
if (pBox->left() < pExtents->left())
344
pExtents->setLeft(pBox->left());
345
if (pBox->right() > pExtents->right())
346
pExtents->setRight(pBox->right());
349
Q_ASSERT(pExtents->left() <= pExtents->right());
353
/* TranslateRegion(pRegion, x, y)
358
static void OffsetRegion(register QRegionPrivate ®ion, register int x, register int y)
361
register QRect *pbox;
363
pbox = region.rects.data();
364
nbox = region.numRects;
367
pbox->translate(x, y);
370
region.extents.translate(x, y);
373
/*======================================================================
374
* Region Intersection
375
*====================================================================*/
377
*-----------------------------------------------------------------------
379
* Handle an overlapping band for miIntersect.
385
* Rectangles may be added to the region.
387
*-----------------------------------------------------------------------
389
static void miIntersectO(register QRegionPrivate &dest, register QRect *r1, QRect *r1End,
390
register QRect *r2, QRect *r2End, int y1, int y2)
394
register QRect *pNextRect;
396
pNextRect = dest.rects.data() + dest.numRects;
398
while (r1 != r1End && r2 != r2End) {
399
x1 = qMax(r1->left(), r2->left());
400
x2 = qMin(r1->right(), r2->right());
403
* If there's any overlap between the two rectangles, add that
404
* overlap to the new region.
405
* There's no need to check for subsumption because the only way
406
* such a need could arise is if some region has two rectangles
407
* right next to each other. Since that should never happen...
411
MEMCHECK(dest, pNextRect, dest.rects)
412
pNextRect->setCoords(x1, y1, x2, y2);
418
* Need to advance the pointers. Shift the one that extends
419
* to the right the least, since the other still has a chance to
420
* overlap with that region's next rectangle, if you see what I mean.
422
if (r1->right() < r2->right()) {
424
} else if (r2->right() < r1->right()) {
433
static void IntersectRegion(QRegionPrivate *reg1, QRegionPrivate *reg2,
434
register QRegionPrivate &dest)
436
if (isEmpty(reg1) || isEmpty(reg2) || !EXTENTCHECK(®1->extents, ®2->extents))
439
miRegionOp(dest, reg1, reg2, miIntersectO, 0, 0);
442
* Can't alter dest's extents before we call miRegionOp because
443
* it might be one of the source regions and miRegionOp depends
444
* on the extents of those regions being the same. Besides, this
445
* way there's no checking against rectangles that will be nuked
446
* due to coalescing, so we have to examine fewer rectangles.
451
/*======================================================================
452
* Generic Region Operator
453
*====================================================================*/
456
*-----------------------------------------------------------------------
458
* Attempt to merge the boxes in the current band with those in the
459
* previous one. Used only by miRegionOp.
462
* The new index for the previous band.
465
* If coalescing takes place:
466
* - rectangles in the previous band will have their y2 fields
468
* - dest.numRects will be decreased.
470
*-----------------------------------------------------------------------
472
static int miCoalesce(register QRegionPrivate &dest, int prevStart, int curStart)
474
register QRect *pPrevBox; /* Current box in previous band */
475
register QRect *pCurBox; /* Current box in current band */
476
register QRect *pRegEnd; /* End of region */
477
int curNumRects; /* Number of rectangles in current band */
478
int prevNumRects; /* Number of rectangles in previous band */
479
int bandY1; /* Y1 coordinate for current band */
481
pRegEnd = dest.rects.data() + dest.numRects;
483
pPrevBox = dest.rects.data() + prevStart;
484
prevNumRects = curStart - prevStart;
487
* Figure out how many rectangles are in the current band. Have to do
488
* this because multiple bands could have been added in miRegionOp
489
* at the end when one region has been exhausted.
491
pCurBox = dest.rects.data() + curStart;
492
bandY1 = pCurBox->top();
493
for (curNumRects = 0; pCurBox != pRegEnd && pCurBox->top() == bandY1; ++curNumRects) {
497
if (pCurBox != pRegEnd) {
499
* If more than one band was added, we have to find the start
500
* of the last band added so the next coalescing job can start
501
* at the right place... (given when multiple bands are added,
502
* this may be pointless -- see above).
505
while ((pRegEnd - 1)->top() == pRegEnd->top())
507
curStart = pRegEnd - dest.rects.data();
508
pRegEnd = dest.rects.data() + dest.numRects;
511
if (curNumRects == prevNumRects && curNumRects != 0) {
512
pCurBox -= curNumRects;
514
* The bands may only be coalesced if the bottom of the previous
515
* matches the top scanline of the current.
517
if (pPrevBox->bottom() == pCurBox->top() - 1) {
519
* Make sure the bands have boxes in the same places. This
520
* assumes that boxes have been added in such a way that they
521
* cover the most area possible. I.e. two boxes in a band must
522
* have some horizontal space between them.
525
if (pPrevBox->left() != pCurBox->left() || pPrevBox->right() != pCurBox->right()) {
526
// The bands don't line up so they can't be coalesced.
532
} while (prevNumRects != 0);
534
dest.numRects -= curNumRects;
535
pCurBox -= curNumRects;
536
pPrevBox -= curNumRects;
539
* The bands may be merged, so set the bottom y of each box
540
* in the previous band to that of the corresponding box in
544
pPrevBox->setBottom(pCurBox->bottom());
548
} while (curNumRects != 0);
551
* If only one band was added to the region, we have to backup
552
* curStart to the start of the previous band.
554
* If more than one band was added to the region, copy the
555
* other bands down. The assumption here is that the other bands
556
* came from the same region as the current one and no further
557
* coalescing can be done on them since it's all been done
558
* already... curStart is already in the right place.
560
if (pCurBox == pRegEnd) {
561
curStart = prevStart;
564
*pPrevBox++ = *pCurBox++;
565
} while (pCurBox != pRegEnd);
573
*-----------------------------------------------------------------------
575
* Apply an operation to two regions. Called by miUnion, miInverse,
576
* miSubtract, miIntersect...
582
* The new region is overwritten.
585
* The idea behind this function is to view the two regions as sets.
586
* Together they cover a rectangle of area that this function divides
587
* into horizontal bands where points are covered only by one region
588
* or by both. For the first case, the nonOverlapFunc is called with
589
* each the band and the band's upper and lower extents. For the
590
* second, the overlapFunc is called to process the entire band. It
591
* is responsible for clipping the rectangles in the band, though
592
* this function provides the boundaries.
593
* At the end of each band, the new region is coalesced, if possible,
594
* to reduce the number of rectangles in the region.
596
*-----------------------------------------------------------------------
598
static void miRegionOp(register QRegionPrivate &dest, QRegionPrivate *reg1, QRegionPrivate *reg2,
599
OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
600
NonOverlapFunc nonOverlap2Func)
602
register QRect *r1; // Pointer into first region
603
register QRect *r2; // Pointer into 2d region
604
QRect *r1End; // End of 1st region
605
QRect *r2End; // End of 2d region
606
register int ybot; // Bottom of intersection
607
register int ytop; // Top of intersection
608
int prevBand; // Index of start of previous band in dest
609
int curBand; // Index of start of current band in dest
610
register QRect *r1BandEnd; // End of current band in r1
611
register QRect *r2BandEnd; // End of current band in r2
612
int top; // Top of non-overlapping band
613
int bot; // Bottom of non-overlapping band
617
* set r1, r2, r1End and r2End appropriately, preserve the important
618
* parts of the destination region until the end in case it's one of
619
* the two source regions, then mark the "new" region empty, allocating
620
* another array of rectangles for it to use.
622
r1 = reg1->rects.data();
623
r2 = reg2->rects.data();
624
r1End = r1 + reg1->numRects;
625
r2End = r2 + reg2->numRects;
627
QVector<QRect> oldRects = dest.rects;
632
* Allocate a reasonable number of rectangles for the new region. The idea
633
* is to allocate enough so the individual functions don't need to
634
* reallocate and copy the array, which is time consuming, yet we don't
635
* have to worry about using too much memory. I hope to be able to
636
* nuke the realloc() at the end of this function eventually.
638
dest.rects.resize(qMax(reg1->numRects,reg2->numRects) * 2);
641
* Initialize ybot and ytop.
642
* In the upcoming loop, ybot and ytop serve different functions depending
643
* on whether the band being handled is an overlapping or non-overlapping
645
* In the case of a non-overlapping band (only one of the regions
646
* has points in the band), ybot is the bottom of the most recent
647
* intersection and thus clips the top of the rectangles in that band.
648
* ytop is the top of the next intersection between the two regions and
649
* serves to clip the bottom of the rectangles in the current band.
650
* For an overlapping band (where the two regions intersect), ytop clips
651
* the top of the rectangles of both regions and ybot clips the bottoms.
653
if (reg1->extents.top() < reg2->extents.top())
654
ybot = reg1->extents.top() - 1;
656
ybot = reg2->extents.top() - 1;
659
* prevBand serves to mark the start of the previous band so rectangles
660
* can be coalesced into larger rectangles. qv. miCoalesce, above.
661
* In the beginning, there is no previous band, so prevBand == curBand
662
* (curBand is set later on, of course, but the first band will always
663
* start at index 0). prevBand and curBand must be indices because of
664
* the possible expansion, and resultant moving, of the new region's
665
* array of rectangles.
670
curBand = dest.numRects;
673
* This algorithm proceeds one source-band (as opposed to a
674
* destination band, which is determined by where the two regions
675
* intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
676
* rectangle after the last one in the current band for their
677
* respective regions.
680
while (r1BandEnd != r1End && r1BandEnd->top() == r1->top())
684
while (r2BandEnd != r2End && r2BandEnd->top() == r2->top())
688
* First handle the band that doesn't intersect, if any.
690
* Note that attention is restricted to one band in the
691
* non-intersecting region at once, so if a region has n
692
* bands between the current position and the next place it overlaps
693
* the other, this entire loop will be passed through n times.
695
if (r1->top() < r2->top()) {
696
top = qMax(r1->top(), ybot + 1);
697
bot = qMin(r1->bottom(), r2->top() - 1);
699
if (nonOverlap1Func != 0 && bot >= top)
700
(*nonOverlap1Func)(dest, r1, r1BandEnd, top, bot);
702
} else if (r2->top() < r1->top()) {
703
top = qMax(r2->top(), ybot + 1);
704
bot = qMin(r2->bottom(), r1->top() - 1);
706
if (nonOverlap2Func != 0 && bot >= top)
707
(*nonOverlap2Func)(dest, r2, r2BandEnd, top, bot);
714
* If any rectangles got added to the region, try and coalesce them
715
* with rectangles from the previous band. Note we could just do
716
* this test in miCoalesce, but some machines incur a not
717
* inconsiderable cost for function calls, so...
719
if (dest.numRects != curBand)
720
prevBand = miCoalesce(dest, prevBand, curBand);
723
* Now see if we've hit an intersecting band. The two bands only
724
* intersect if ybot >= ytop
726
ybot = qMin(r1->bottom(), r2->bottom());
727
curBand = dest.numRects;
729
(*overlapFunc)(dest, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
731
if (dest.numRects != curBand)
732
prevBand = miCoalesce(dest, prevBand, curBand);
735
* If we've finished with a band (y2 == ybot) we skip forward
736
* in the region to the next band.
738
if (r1->bottom() == ybot)
740
if (r2->bottom() == ybot)
742
} while (r1 != r1End && r2 != r2End);
745
* Deal with whichever region still has rectangles left.
747
curBand = dest.numRects;
749
if (nonOverlap1Func != 0) {
752
while (r1BandEnd < r1End && r1BandEnd->top() == r1->top())
754
(*nonOverlap1Func)(dest, r1, r1BandEnd, qMax(r1->top(), ybot + 1), r1->bottom());
756
} while (r1 != r1End);
758
} else if ((r2 != r2End) && (nonOverlap2Func != 0)) {
761
while (r2BandEnd < r2End && r2BandEnd->top() == r2->top())
763
(*nonOverlap2Func)(dest, r2, r2BandEnd, qMax(r2->top(), ybot + 1), r2->bottom());
765
} while (r2 != r2End);
768
if (dest.numRects != curBand)
769
(void)miCoalesce(dest, prevBand, curBand);
772
* A bit of cleanup. To keep regions from growing without bound,
773
* we shrink the array of rectangles to match the new number of
774
* rectangles in the region.
776
* Only do this stuff if the number of rectangles allocated is more than
777
* twice the number of rectangles in the region (a simple optimization).
779
if (dest.numRects < (dest.rects.size() >> 1))
780
dest.rects.resize(dest.numRects);
783
/*======================================================================
785
*====================================================================*/
788
*-----------------------------------------------------------------------
790
* Handle a non-overlapping band for the union operation. Just
791
* Adds the rectangles into the region. Doesn't have to check for
792
* subsumption or anything.
798
* dest.numRects is incremented and the final rectangles overwritten
799
* with the rectangles we're passed.
801
*-----------------------------------------------------------------------
804
static void miUnionNonO(register QRegionPrivate &dest, register QRect *r, QRect *rEnd,
805
register int y1, register int y2)
807
register QRect *pNextRect;
809
pNextRect = dest.rects.data() + dest.numRects;
814
Q_ASSERT(r->left() <= r->right());
815
MEMCHECK(dest, pNextRect, dest.rects)
816
pNextRect->setCoords(r->left(), y1, r->right(), y2);
825
*-----------------------------------------------------------------------
827
* Handle an overlapping band for the union operation. Picks the
828
* left-most rectangle each time and merges it into the region.
834
* Rectangles are overwritten in dest.rects and dest.numRects will
837
*-----------------------------------------------------------------------
840
static void miUnionO(register QRegionPrivate &dest, register QRect *r1, QRect *r1End,
841
register QRect *r2, QRect *r2End, register int y1, register int y2)
843
register QRect *pNextRect;
845
pNextRect = dest.rects.data() + dest.numRects;
847
#define MERGERECT(r) \
848
if ((dest.numRects != 0) && \
849
(pNextRect[-1].top() == y1) && \
850
(pNextRect[-1].bottom() == y2) && \
851
(pNextRect[-1].right() >= r->left()-1)) { \
852
if (pNextRect[-1].right() < r->right()) { \
853
pNextRect[-1].setRight(r->right()); \
854
Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
857
MEMCHECK(dest, pNextRect, dest.rects) \
858
pNextRect->setCoords(r->left(), y1, r->right(), y2); \
865
while (r1 != r1End && r2 != r2End) {
866
if (r1->left() < r2->left()) {
876
} while (r1 != r1End);
878
while (r2 != r2End) {
884
static void UnionRegion(QRegionPrivate *reg1, QRegionPrivate *reg2, QRegionPrivate &dest)
887
Region 1 is empty or is equal to region 2.
889
if (reg1 == reg2 || isEmpty(reg1)) {
896
Region 2 is empty (and region 1 isn't).
904
Region 1 completely subsumes region 2.
906
if (reg1->numRects == 1 && reg1->extents.left() <= reg2->extents.left()
907
&& reg1->extents.top() <= reg2->extents.top()
908
&& reg1->extents.right() >= reg2->extents.right()
909
&& reg1->extents.bottom() >= reg2->extents.bottom()) {
915
Region 2 completely subsumes region 1.
917
if (reg2->numRects == 1 && reg2->extents.left() <= reg1->extents.left()
918
&& reg2->extents.top() <= reg1->extents.top()
919
&& reg2->extents.right() >= reg1->extents.right()
920
&& reg2->extents.bottom() >= reg1->extents.bottom()) {
925
miRegionOp(dest, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO);
927
dest.extents.setCoords(qMin(reg1->extents.left(), reg2->extents.left()),
928
qMin(reg1->extents.top(), reg2->extents.top()),
929
qMax(reg1->extents.right(), reg2->extents.right()),
930
qMax(reg1->extents.bottom(), reg2->extents.bottom()));
933
/*======================================================================
935
*====================================================================*/
938
*-----------------------------------------------------------------------
940
* Deal with non-overlapping band for subtraction. Any parts from
941
* region 2 we discard. Anything from region 1 we add to the region.
947
* dest may be affected.
949
*-----------------------------------------------------------------------
952
static void miSubtractNonO1(register QRegionPrivate &dest, register QRect *r,
953
QRect *rEnd, register int y1, register int y2)
955
register QRect *pNextRect;
957
pNextRect = dest.rects.data() + dest.numRects;
962
Q_ASSERT(r->left() <= r->right());
963
MEMCHECK(dest, pNextRect, dest.rects)
964
pNextRect->setCoords(r->left(), y1, r->right(), y2);
972
*-----------------------------------------------------------------------
974
* Overlapping band subtraction. x1 is the left-most point not yet
981
* dest may have rectangles added to it.
983
*-----------------------------------------------------------------------
986
static void miSubtractO(register QRegionPrivate &dest, register QRect *r1, QRect *r1End,
987
register QRect *r2, QRect *r2End, register int y1, register int y2)
989
register QRect *pNextRect;
995
pNextRect = dest.rects.data() + dest.numRects;
997
while (r1 != r1End && r2 != r2End) {
998
if (r2->right() < x1) {
1000
* Subtrahend missed the boat: go to next subtrahend.
1003
} else if (r2->left() <= x1) {
1005
* Subtrahend precedes minuend: nuke left edge of minuend.
1007
x1 = r2->right() + 1;
1008
if (x1 > r1->right()) {
1010
* Minuend completely covered: advance to next minuend and
1011
* reset left fence to edge of new minuend.
1017
// Subtrahend now used up since it doesn't extend beyond minuend
1020
} else if (r2->left() <= r1->right()) {
1022
* Left part of subtrahend covers part of minuend: add uncovered
1023
* part of minuend to region and skip to next subtrahend.
1025
Q_ASSERT(x1 < r2->left());
1026
MEMCHECK(dest, pNextRect, dest.rects)
1027
pNextRect->setCoords(x1, y1, r2->left() - 1, y2);
1031
x1 = r2->right() + 1;
1032
if (x1 > r1->right()) {
1034
* Minuend used up: advance to new...
1040
// Subtrahend used up
1045
* Minuend used up: add any remaining piece before advancing.
1047
if (r1->right() >= x1) {
1048
MEMCHECK(dest, pNextRect, dest.rects)
1049
pNextRect->setCoords(x1, y1, r1->right(), y2);
1060
* Add remaining minuend rectangles to region.
1062
while (r1 != r1End) {
1063
Q_ASSERT(x1 <= r1->right());
1064
MEMCHECK(dest, pNextRect, dest.rects)
1065
pNextRect->setCoords(x1, y1, r1->right(), y2);
1076
*-----------------------------------------------------------------------
1078
* Subtract regS from regM and leave the result in regD.
1079
* S stands for subtrahend, M for minuend and D for difference.
1082
* regD is overwritten.
1084
*-----------------------------------------------------------------------
1087
static void SubtractRegion(QRegionPrivate *regM, QRegionPrivate *regS,
1088
register QRegionPrivate &dest)
1090
/* check for trivial reject */
1094
if (isEmpty(regS) || !EXTENTCHECK(®M->extents, ®S->extents)) {
1098
miRegionOp(dest, regM, regS, miSubtractO, miSubtractNonO1, 0);
1101
* Can't alter dest's extents before we call miRegionOp because
1102
* it might be one of the source regions and miRegionOp depends
1103
* on the extents of those regions being the unaltered. Besides, this
1104
* way there's no checking against rectangles that will be nuked
1105
* due to coalescing, so we have to examine fewer rectangles.
1110
static void XorRegion(QRegionPrivate *sra, QRegionPrivate *srb, QRegionPrivate &dest)
1112
QRegionPrivate tra, trb;
1114
SubtractRegion(sra, srb, tra);
1115
SubtractRegion(srb, sra, trb);
1116
UnionRegion(&tra, &trb, dest);
1120
* Check to see if two regions are equal
1122
static bool EqualRegion(QRegionPrivate *r1, QRegionPrivate *r2)
1124
if (r1->numRects != r2->numRects) {
1126
} else if (r1->numRects == 0) {
1128
} else if (r1->extents != r2->extents) {
1131
const QRect *rr1 = r1->rects.constData();
1132
const QRect *rr2 = r2->rects.constData();
1133
for (int i = 0; i < r1->numRects; ++i, ++rr1, ++rr2) {
1141
static bool PointInRegion(QRegionPrivate *pRegion, int x, int y)
1145
if (isEmpty(pRegion))
1147
if (!pRegion->extents.contains(x, y))
1149
for (i = 0; i < pRegion->numRects; ++i) {
1150
if (pRegion->rects[i].contains(x, y))
1156
static bool RectInRegion(register QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight)
1158
register const QRect *pbox;
1159
register const QRect *pboxEnd;
1160
QRect rect(rx, ry, rwidth, rheight);
1161
register QRect *prect = ▭
1162
int partIn, partOut;
1164
if (region->numRects == 0 || !EXTENTCHECK(®ion->extents, prect))
1165
return RectangleOut;
1170
/* can stop when both partOut and partIn are true, or we reach prect->y2 */
1171
for (pbox = region->rects.constData(), pboxEnd = pbox + region->numRects;
1172
pbox < pboxEnd; ++pbox) {
1173
if (pbox->bottom() < ry)
1176
if (pbox->top() > ry) {
1178
if (partIn || pbox->top() > prect->bottom())
1183
if (pbox->right() < rx)
1184
continue; /* not far enough over yet */
1186
if (pbox->left() > rx) {
1187
partOut = true; /* missed part of rectangle to left */
1192
if (pbox->left() <= prect->right()) {
1193
partIn = true; /* definitely overlap */
1198
if (pbox->right() >= prect->right()) {
1199
ry = pbox->bottom() + 1; /* finished with this band */
1200
if (ry > prect->bottom())
1202
rx = prect->left(); /* reset x out to left again */
1205
* Because boxes in a band are maximal width, if the first box
1206
* to overlap the rectangle doesn't completely cover it in that
1207
* band, the rectangle must be partially out, since some of it
1208
* will be uncovered in that band. partIn will have been set true
1214
return partIn ? ((ry <= prect->bottom()) ? RectanglePart : RectangleIn) : RectangleOut;
1216
// END OF Region.c extract
1217
// START OF poly.h extract
1218
/* $XConsortium: poly.h,v 1.4 94/04/17 20:22:19 rws Exp $ */
1219
/************************************************************************
1221
Copyright (c) 1987 X Consortium
1223
Permission is hereby granted, free of charge, to any person obtaining a copy
1224
of this software and associated documentation files (the "Software"), to deal
1225
in the Software without restriction, including without limitation the rights
1226
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1227
copies of the Software, and to permit persons to whom the Software is
1228
furnished to do so, subject to the following conditions:
1230
The above copyright notice and this permission notice shall be included in
1231
all copies or substantial portions of the Software.
1233
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1234
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1235
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1236
X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1237
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1238
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1240
Except as contained in this notice, the name of the X Consortium shall not be
1241
used in advertising or otherwise to promote the sale, use or other dealings
1242
in this Software without prior written authorization from the X Consortium.
1245
Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
1249
Permission to use, copy, modify, and distribute this software and its
1250
documentation for any purpose and without fee is hereby granted,
1251
provided that the above copyright notice appear in all copies and that
1252
both that copyright notice and this permission notice appear in
1253
supporting documentation, and that the name of Digital not be
1254
used in advertising or publicity pertaining to distribution of the
1255
software without specific, written prior permission.
1257
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1258
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1259
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1260
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1261
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1262
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1265
************************************************************************/
1268
* This file contains a few macros to help track
1269
* the edge of a filled object. The object is assumed
1270
* to be filled in scanline order, and thus the
1271
* algorithm used is an extension of Bresenham's line
1272
* drawing algorithm which assumes that y is always the
1274
* Since these pieces of code are the same for any filled shape,
1275
* it is more convenient to gather the library in one
1276
* place, but since these pieces of code are also in
1277
* the inner loops of output primitives, procedure call
1278
* overhead is out of the question.
1279
* See the author for a derivation if needed.
1284
* In scan converting polygons, we want to choose those pixels
1285
* which are inside the polygon. Thus, we add .5 to the starting
1286
* x coordinate for both left and right edges. Now we choose the
1287
* first pixel which is inside the pgon for the left edge and the
1288
* first pixel which is outside the pgon for the right edge.
1289
* Draw the left pixel, but not the right.
1291
* How to add .5 to the starting x coordinate:
1292
* If the edge is moving to the right, then subtract dy from the
1293
* error term from the general form of the algorithm.
1294
* If the edge is moving to the left, then add dy to the error term.
1296
* The reason for the difference between edges moving to the left
1297
* and edges moving to the right is simple: If an edge is moving
1298
* to the right, then we want the algorithm to flip immediately.
1299
* If it is moving to the left, then we don't want it to flip until
1300
* we traverse an entire pixel.
1302
#define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
1303
int dx; /* local storage */ \
1306
* if the edge is horizontal, then it is ignored \
1307
* and assumed not to be processed. Otherwise, do this stuff. \
1311
dx = (x2) - xStart; \
1315
incr1 = -2 * dx + 2 * (dy) * m1; \
1316
incr2 = -2 * dx + 2 * (dy) * m; \
1317
d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
1321
incr1 = 2 * dx - 2 * (dy) * m1; \
1322
incr2 = 2 * dx - 2 * (dy) * m; \
1323
d = -2 * m * (dy) + 2 * dx; \
1328
#define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
1352
* This structure contains all of the information needed
1353
* to run the bresenham algorithm.
1354
* The variables may be hardcoded into the declarations
1355
* instead of using this structure to make use of
1356
* register declarations.
1359
int minor_axis; /* minor axis */
1360
int d; /* decision variable */
1361
int m, m1; /* slope and slope+1 */
1362
int incr1, incr2; /* error increments */
1366
#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
1367
BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
1368
bres.m, bres.m1, bres.incr1, bres.incr2)
1370
#define BRESINCRPGONSTRUCT(bres) \
1371
BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
1376
* These are the data structures needed to scan
1377
* convert regions. Two different scan conversion
1378
* methods are available -- the even-odd method, and
1379
* the winding number method.
1380
* The even-odd rule states that a point is inside
1381
* the polygon if a ray drawn from that point in any
1382
* direction will pass through an odd number of
1384
* By the winding number rule, a point is decided
1385
* to be inside the polygon if a ray drawn from that
1386
* point in any direction passes through a different
1387
* number of clockwise and counter-clockwise path
1390
* These data structures are adapted somewhat from
1391
* the algorithm in (Foley/Van Dam) for scan converting
1393
* The basic algorithm is to start at the top (smallest y)
1394
* of the polygon, stepping down to the bottom of
1395
* the polygon by incrementing the y coordinate. We
1396
* keep a list of edges which the current scanline crosses,
1397
* sorted by x. This list is called the Active Edge Table (AET)
1398
* As we change the y-coordinate, we update each entry in
1399
* in the active edge table to reflect the edges new xcoord.
1400
* This list must be sorted at each scanline in case
1401
* two edges intersect.
1402
* We also keep a data structure known as the Edge Table (ET),
1403
* which keeps track of all the edges which the current
1404
* scanline has not yet reached. The ET is basically a
1405
* list of ScanLineList structures containing a list of
1406
* edges which are entered at a given scanline. There is one
1407
* ScanLineList per scanline at which an edge is entered.
1408
* When we enter a new edge, we move it from the ET to the AET.
1410
* From the AET, we can implement the even-odd rule as in
1412
* The winding number rule is a little trickier. We also
1413
* keep the EdgeTableEntries in the AET linked by the
1414
* nextWETE (winding EdgeTableEntry) link. This allows
1415
* the edges to be linked just as before for updating
1416
* purposes, but only uses the edges linked by the nextWETE
1417
* link as edges representing spans of the polygon to
1418
* drawn (as with the even-odd rule).
1422
* for the winding number rule
1425
#define COUNTERCLOCKWISE -1
1427
typedef struct _EdgeTableEntry {
1428
int ymax; /* ycoord at which we exit this edge. */
1429
BRESINFO bres; /* Bresenham info to run the edge */
1430
struct _EdgeTableEntry *next; /* next in the list */
1431
struct _EdgeTableEntry *back; /* for insertion sort */
1432
struct _EdgeTableEntry *nextWETE; /* for winding num rule */
1433
int ClockWise; /* flag for winding number rule */
1437
typedef struct _ScanLineList{
1438
int scanline; /* the scanline represented */
1439
EdgeTableEntry *edgelist; /* header node */
1440
struct _ScanLineList *next; /* next in the list */
1445
int ymax; /* ymax for the polygon */
1446
int ymin; /* ymin for the polygon */
1447
ScanLineList scanlines; /* header node */
1452
* Here is a struct to help with storage allocation
1453
* so we can allocate a big chunk at a time, and then take
1454
* pieces from this heap when we need to.
1456
#define SLLSPERBLOCK 25
1458
typedef struct _ScanLineListBlock {
1459
ScanLineList SLLs[SLLSPERBLOCK];
1460
struct _ScanLineListBlock *next;
1461
} ScanLineListBlock;
1467
* a few macros for the inner loops of the fill code where
1468
* performance considerations don't allow a procedure call.
1470
* Evaluate the given edge at the given scanline.
1471
* If the edge has expired, then we leave it and fix up
1472
* the active edge table; otherwise, we increment the
1473
* x value to be ready for the next scanline.
1474
* The winding number rule is in effect, so we must notify
1475
* the caller when the edge has been removed so he
1476
* can reorder the Winding Active Edge Table.
1478
#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
1479
if (pAET->ymax == y) { /* leaving this edge */ \
1480
pPrevAET->next = pAET->next; \
1481
pAET = pPrevAET->next; \
1484
pAET->back = pPrevAET; \
1487
BRESINCRPGONSTRUCT(pAET->bres) \
1489
pAET = pAET->next; \
1495
* Evaluate the given edge at the given scanline.
1496
* If the edge has expired, then we leave it and fix up
1497
* the active edge table; otherwise, we increment the
1498
* x value to be ready for the next scanline.
1499
* The even-odd rule is in effect.
1501
#define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
1502
if (pAET->ymax == y) { /* leaving this edge */ \
1503
pPrevAET->next = pAET->next; \
1504
pAET = pPrevAET->next; \
1506
pAET->back = pPrevAET; \
1509
BRESINCRPGONSTRUCT(pAET->bres) \
1511
pAET = pAET->next; \
1514
// END OF poly.h extract
1515
// START OF PolyReg.c extract
1516
/* $XConsortium: PolyReg.c,v 11.23 94/11/17 21:59:37 converse Exp $ */
1517
/************************************************************************
1519
Copyright (c) 1987 X Consortium
1521
Permission is hereby granted, free of charge, to any person obtaining a copy
1522
of this software and associated documentation files (the "Software"), to deal
1523
in the Software without restriction, including without limitation the rights
1524
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1525
copies of the Software, and to permit persons to whom the Software is
1526
furnished to do so, subject to the following conditions:
1528
The above copyright notice and this permission notice shall be included in
1529
all copies or substantial portions of the Software.
1531
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1532
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1533
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1534
X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1535
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1536
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1538
Except as contained in this notice, the name of the X Consortium shall not be
1539
used in advertising or otherwise to promote the sale, use or other dealings
1540
in this Software without prior written authorization from the X Consortium.
1543
Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
1547
Permission to use, copy, modify, and distribute this software and its
1548
documentation for any purpose and without fee is hereby granted,
1549
provided that the above copyright notice appear in all copies and that
1550
both that copyright notice and this permission notice appear in
1551
supporting documentation, and that the name of Digital not be
1552
used in advertising or publicity pertaining to distribution of the
1553
software without specific, written prior permission.
1555
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1556
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1557
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1558
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1559
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1560
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1563
************************************************************************/
1564
/* $XFree86: xc/lib/X11/PolyReg.c,v 1.1.1.2.8.2 1998/10/04 15:22:49 hohndel Exp $ */
1566
#define LARGE_COORDINATE 1000000
1567
#define SMALL_COORDINATE -LARGE_COORDINATE
1572
* Insert the given edge into the edge table.
1573
* First we must find the correct bucket in the
1574
* Edge table, then find the right slot in the
1575
* bucket. Finally, we can insert it.
1578
static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline,
1579
ScanLineListBlock **SLLBlock, int *iSLLBlock)
1581
register EdgeTableEntry *start, *prev;
1582
register ScanLineList *pSLL, *pPrevSLL;
1583
ScanLineListBlock *tmpSLLBlock;
1586
* find the right bucket to put the edge into
1588
pPrevSLL = &ET->scanlines;
1589
pSLL = pPrevSLL->next;
1590
while (pSLL && (pSLL->scanline < scanline)) {
1596
* reassign pSLL (pointer to ScanLineList) if necessary
1598
if ((!pSLL) || (pSLL->scanline > scanline)) {
1599
if (*iSLLBlock > SLLSPERBLOCK-1)
1602
(ScanLineListBlock *)malloc(sizeof(ScanLineListBlock));
1603
(*SLLBlock)->next = tmpSLLBlock;
1604
tmpSLLBlock->next = (ScanLineListBlock *)NULL;
1605
*SLLBlock = tmpSLLBlock;
1608
pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
1610
pSLL->next = pPrevSLL->next;
1611
pSLL->edgelist = (EdgeTableEntry *)NULL;
1612
pPrevSLL->next = pSLL;
1614
pSLL->scanline = scanline;
1617
* now insert the edge in the right bucket
1620
start = pSLL->edgelist;
1621
while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) {
1623
start = start->next;
1630
pSLL->edgelist = ETE;
1636
* This routine creates the edge table for
1637
* scan converting polygons.
1638
* The Edge Table (ET) looks like:
1642
* | ymax | ScanLineLists
1643
* |scanline|-->------------>-------------->...
1644
* -------- |scanline| |scanline|
1645
* |edgelist| |edgelist|
1646
* --------- ---------
1650
* list of ETEs list of ETEs
1652
* where ETE is an EdgeTableEntry data structure,
1653
* and there is one ScanLineList per scanline at
1654
* which an edge is initially entered.
1658
static void CreateETandAET(register int count, register const QPoint *pts,
1659
EdgeTable *ET, EdgeTableEntry *AET, register EdgeTableEntry *pETEs,
1660
ScanLineListBlock *pSLLBlock)
1662
register const QPoint *top,
1673
* initialize the Active Edge Table
1678
AET->bres.minor_axis = SMALL_COORDINATE;
1681
* initialize the Edge Table.
1683
ET->scanlines.next = 0;
1684
ET->ymax = SMALL_COORDINATE;
1685
ET->ymin = LARGE_COORDINATE;
1686
pSLLBlock->next = 0;
1688
PrevPt = &pts[count - 1];
1691
* for each vertex in the array of points.
1692
* In this loop we are dealing with two vertices at
1693
* a time -- these make up one edge of the polygon.
1699
* find out which point is above and which is below.
1701
if (PrevPt->y() > CurrPt->y()) {
1704
pETEs->ClockWise = 0;
1708
pETEs->ClockWise = 1;
1712
* don't add horizontal edges to the Edge table.
1714
if (bottom->y() != top->y()) {
1715
pETEs->ymax = bottom->y() - 1; /* -1 so we don't get last scanline */
1718
* initialize integer edge algorithm
1720
dy = bottom->y() - top->y();
1721
BRESINITPGONSTRUCT(dy, top->x(), bottom->x(), pETEs->bres)
1723
InsertEdgeInET(ET, pETEs, top->y(), &pSLLBlock, &iSLLBlock);
1725
if (PrevPt->y() > ET->ymax)
1726
ET->ymax = PrevPt->y();
1727
if (PrevPt->y() < ET->ymin)
1728
ET->ymin = PrevPt->y();
1739
* This routine moves EdgeTableEntries from the
1740
* EdgeTable into the Active Edge Table,
1741
* leaving them sorted by smaller x coordinate.
1745
static void loadAET(register EdgeTableEntry *AET, register EdgeTableEntry *ETEs)
1747
register EdgeTableEntry *pPrevAET;
1748
register EdgeTableEntry *tmp;
1753
while (AET && AET->bres.minor_axis < ETEs->bres.minor_axis) {
1761
ETEs->back = pPrevAET;
1762
pPrevAET->next = ETEs;
1772
* This routine links the AET by the
1773
* nextWETE (winding EdgeTableEntry) link for
1774
* use by the winding number rule. The final
1775
* Active Edge Table (AET) might look something
1779
* ---------- --------- ---------
1780
* |ymax | |ymax | |ymax |
1781
* | ... | |... | |... |
1782
* |next |->|next |->|next |->...
1783
* |nextWETE| |nextWETE| |nextWETE|
1784
* --------- --------- ^--------
1786
* V-------------------> V---> ...
1789
static void computeWAET(register EdgeTableEntry *AET)
1791
register EdgeTableEntry *pWETE;
1792
register int inside = 1;
1793
register int isInside = 0;
1804
if (!inside && !isInside || inside && isInside) {
1805
pWETE->nextWETE = AET;
1811
pWETE->nextWETE = 0;
1817
* Just a simple insertion sort using
1818
* pointers and back pointers to sort the Active
1823
static int InsertionSort(register EdgeTableEntry *AET)
1825
register EdgeTableEntry *pETEchase;
1826
register EdgeTableEntry *pETEinsert;
1827
register EdgeTableEntry *pETEchaseBackTMP;
1828
register int changed = 0;
1834
while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
1835
pETEchase = pETEchase->back;
1838
if (pETEchase != pETEinsert) {
1839
pETEchaseBackTMP = pETEchase->back;
1840
pETEinsert->back->next = AET;
1842
AET->back = pETEinsert->back;
1843
pETEinsert->next = pETEchase;
1844
pETEchase->back->next = pETEinsert;
1845
pETEchase->back = pETEinsert;
1846
pETEinsert->back = pETEchaseBackTMP;
1856
static void FreeStorage(register ScanLineListBlock *pSLLBlock)
1858
register ScanLineListBlock *tmpSLLBlock;
1861
tmpSLLBlock = pSLLBlock->next;
1863
pSLLBlock = tmpSLLBlock;
1868
* Create an array of rectangles from a list of points.
1869
* If indeed these things (POINTS, RECTS) are the same,
1870
* then this proc is still needed, because it allocates
1871
* storage for the array, which was allocated on the
1872
* stack by the calling procedure.
1875
static void PtsToRegion(register int numFullPtBlocks, register int iCurPtBlock,
1876
POINTBLOCK *FirstPtBlock, QRegionPrivate *reg)
1878
register QRect *rects;
1879
register QPoint *pts;
1880
register POINTBLOCK *CurPtBlock;
1882
register QRect *extents;
1883
register int numRects;
1885
extents = ®->extents;
1887
numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
1889
reg->rects.resize(numRects);
1891
CurPtBlock = FirstPtBlock;
1892
rects = reg->rects.data() - 1;
1894
extents->setLeft(INT_MAX);
1895
extents->setRight(INT_MIN);
1897
for (; numFullPtBlocks >= 0; --numFullPtBlocks) {
1898
/* the loop uses 2 points per iteration */
1899
i = NUMPTSTOBUFFER >> 1;
1900
if (!numFullPtBlocks)
1901
i = iCurPtBlock >> 1;
1903
for (pts = CurPtBlock->pts; i--; pts += 2) {
1904
if (pts->x() == pts[1].x())
1906
if (numRects && pts->x() == rects->left() && pts->y() == rects->bottom() + 1
1907
&& pts[1].x() == rects->right()
1908
&& (numRects == 1 || rects[-1].top() != rects->top())
1909
&& (i && pts[2].y() > pts[1].y())) {
1910
rects->setBottom(pts[1].y());
1915
rects->setCoords(pts->x(), pts->y(), pts[1].x() - 1, pts[1].y());
1916
if (rects->left() < extents->left())
1917
extents->setLeft(rects->left());
1918
if (rects->right() > extents->right())
1919
extents->setRight(rects->right());
1922
CurPtBlock = CurPtBlock->next;
1926
extents->setTop(reg->rects[0].top());
1927
extents->setBottom(rects->bottom());
1929
extents->setCoords(0, 0, 0, 0);
1931
reg->numRects = numRects;
1937
* Scan converts a polygon by returning a run-length
1938
* encoding of the resultant bitmap -- the run-length
1939
* encoding is in the form of an array of rectangles.
1941
static QRegionPrivate *PolygonRegion(const QPoint *Pts, int Count, int rule)
1942
//Point *Pts; /* the pts */
1943
//int Count; /* number of pts */
1944
//int rule; /* winding rule */
1946
QRegionPrivate *region;
1947
register EdgeTableEntry *pAET; /* Active Edge Table */
1948
register int y; /* current scanline */
1949
register int iPts = 0; /* number of pts in buffer */
1950
register EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
1951
register ScanLineList *pSLL; /* current scanLineList */
1952
register QPoint *pts; /* output buffer */
1953
EdgeTableEntry *pPrevAET; /* ptr to previous AET */
1954
EdgeTable ET; /* header node for ET */
1955
EdgeTableEntry AET; /* header node for AET */
1956
EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
1957
ScanLineListBlock SLLBlock; /* header for scanlinelist */
1958
int fixWAET = false;
1959
POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
1960
POINTBLOCK *tmpPtBlock;
1961
int numFullPtBlocks = 0;
1963
if (!(region = new QRegionPrivate))
1966
/* special case a rectangle */
1967
if (((Count == 4) ||
1968
((Count == 5) && (Pts[4].x() == Pts[0].x()) && (Pts[4].y() == Pts[0].y())))
1969
&& (((Pts[0].y() == Pts[1].y()) && (Pts[1].x() == Pts[2].x()) && (Pts[2].y() == Pts[3].y())
1970
&& (Pts[3].x() == Pts[0].x())) || ((Pts[0].x() == Pts[1].x())
1971
&& (Pts[1].y() == Pts[2].y()) && (Pts[2].x() == Pts[3].x())
1972
&& (Pts[3].y() == Pts[0].y())))) {
1973
int x = qMin(Pts[0].x(), Pts[2].x());
1974
region->extents.setLeft(x);
1975
int y = qMin(Pts[0].y(), Pts[2].y());
1976
region->extents.setTop(y);
1977
region->extents.setWidth(qMax(Pts[0].x(), Pts[2].x()) - x);
1978
region->extents.setHeight(qMax(Pts[0].y(), Pts[2].y()) - y);
1979
if ((region->extents.left() <= region->extents.right()) &&
1980
(region->extents.top() <= region->extents.bottom())) {
1981
region->numRects = 1;
1982
region->rects.resize(1);
1983
region->rects[0] = region->extents;
1988
if (!(pETEs = static_cast<EdgeTableEntry *>(malloc(sizeof(EdgeTableEntry) * Count))))
1991
pts = FirstPtBlock.pts;
1992
CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
1993
pSLL = ET.scanlines.next;
1994
curPtBlock = &FirstPtBlock;
1996
if (rule == EvenOddRule) {
2000
for (y = ET.ymin; y < ET.ymax; ++y) {
2002
* Add a new edge to the active edge table when we
2003
* get to the next edge.
2005
if (pSLL && y == pSLL->scanline) {
2006
loadAET(&AET, pSLL->edgelist);
2013
* for each active edge
2016
pts->setX(pAET->bres.minor_axis);
2022
* send out the buffer
2024
if (iPts == NUMPTSTOBUFFER) {
2025
tmpPtBlock = (POINTBLOCK *)malloc(sizeof(POINTBLOCK));
2026
curPtBlock->next = tmpPtBlock;
2027
curPtBlock = tmpPtBlock;
2028
pts = curPtBlock->pts;
2032
EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
2034
InsertionSort(&AET);
2040
for (y = ET.ymin; y < ET.ymax; ++y) {
2042
* Add a new edge to the active edge table when we
2043
* get to the next edge.
2045
if (pSLL && y == pSLL->scanline) {
2046
loadAET(&AET, pSLL->edgelist);
2055
* for each active edge
2059
* add to the buffer only those edges that
2060
* are in the Winding active edge table.
2062
if (pWETE == pAET) {
2063
pts->setX(pAET->bres.minor_axis);
2069
* send out the buffer
2071
if (iPts == NUMPTSTOBUFFER) {
2072
tmpPtBlock = static_cast<POINTBLOCK *>(malloc(sizeof(POINTBLOCK)));
2073
curPtBlock->next = tmpPtBlock;
2074
curPtBlock = tmpPtBlock;
2075
pts = curPtBlock->pts;
2079
pWETE = pWETE->nextWETE;
2081
EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
2085
* recompute the winding active edge table if
2086
* we just resorted or have exited an edge.
2088
if (InsertionSort(&AET) || fixWAET) {
2094
FreeStorage(SLLBlock.next);
2095
PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
2096
for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
2097
tmpPtBlock = curPtBlock->next;
2099
curPtBlock = tmpPtBlock;
2104
// END OF PolyReg.c extract
2106
QRegionPrivate *qt_bitmapToRegion(const QBitmap& bitmap)
2108
QImage image = bitmap.toImage();
2110
QRegionPrivate *region = new QRegionPrivate;
2115
xr.setCoords(prev1, y, x-1, y); \
2116
UnionRectWithRegion(&xr, region, *region); \
2119
const uint zero = 0;
2120
bool little = image.format() == QImage::Format_MonoLSB;
2124
for (y = 0; y < image.height(); ++y) {
2125
uchar *line = image.scanLine(y);
2126
int w = image.width();
2129
for (x = 0; x < w;) {
2130
uchar byte = line[x / 8];
2131
if (x > w - 8 || byte!=all) {
2133
for (int b = 8; b > 0 && x < w; --b) {
2134
if (!(byte & 0x01) == !all) {
2150
for (int b = 8; b > 0 && x < w; --b) {
2151
if (!(byte & 0x80) == !all) {
2181
Constructs an empty region.
2195
Create a region based on the rectange \a r with region type \a t.
2197
If the rectangle is invalid a null region will be created.
2199
\sa QRegion::RegionType
2202
QRegion::QRegion(const QRect &r, RegionType t)
2208
d = new QRegionData;
2210
#if defined(Q_WS_X11)
2213
#elif defined(Q_WS_MAC)
2216
if (t == Rectangle) {
2217
d->qt_rgn = new QRegionPrivate(r);
2218
} else if (t == Ellipse) {
2220
path.addEllipse(r.x(), r.y(), r.width(), r.height());
2221
QPolygon a = path.toSubpathPolygons().at(0).toPolygon();
2222
d->qt_rgn = PolygonRegion(a.constData(), a.size(), EvenOddRule);
2228
Constructs a polygon region from the point array \a a with the fill rule
2229
specified by \a fillRule.
2231
If \a fillRule is \l{Qt::WindingFill}, the polygon region is defined
2232
using the winding algorithm; if it is \l{Qt::OddEvenFill}, the odd-even fill
2235
\warning This constructor can be used to create complex regions that will
2236
slow down painting when used.
2239
QRegion::QRegion(const QPolygon &a, Qt::FillRule fillRule)
2241
if (a.count() > 2) {
2242
d = new QRegionData;
2244
#if defined(Q_WS_X11)
2247
#elif defined(Q_WS_MAC)
2250
d->qt_rgn = PolygonRegion(a.constData(), a.size(),
2251
fillRule == Qt::WindingFill ? WindingRule : EvenOddRule);
2260
Constructs a new region which is equal to region \a r.
2263
QRegion::QRegion(const QRegion &r)
2271
Constructs a region from the bitmap \a bm.
2273
The resulting region consists of the pixels in bitmap \a bm that
2274
are \c Qt::color1, as if each pixel was a 1 by 1 rectangle.
2276
This constructor may create complex regions that will slow down
2277
painting when used. Note that drawing masked pixmaps can be done
2278
much faster using QPixmap::setMask().
2280
QRegion::QRegion(const QBitmap &bm)
2286
d = new QRegionData;
2288
#if defined(Q_WS_X11)
2291
#elif defined(Q_WS_MAC)
2294
d->qt_rgn = qt_bitmapToRegion(bm);
2298
void QRegion::cleanUp(QRegion::QRegionData *x)
2301
#if defined(Q_WS_X11)
2303
XDestroyRegion(x->rgn);
2305
free(x->xrectangles);
2306
#elif defined(Q_WS_MAC)
2308
qt_mac_dispose_rgn(x->rgn);
2314
Destroys the region.
2319
if (!d->ref.deref())
2325
Assigns \a r to this region and returns a reference to the region.
2328
QRegion &QRegion::operator=(const QRegion &r)
2330
QRegionData *x = r.d;
2332
x = qAtomicSetPtr(&d, x);
2333
if (!x->ref.deref())
2340
Returns a \link shclass.html deep copy\endlink of the region.
2345
QRegion QRegion::copy() const
2348
QRegionData *x = new QRegionData;
2350
#if defined(Q_WS_X11)
2353
#elif defined(Q_WS_MAC)
2357
x->qt_rgn = new QRegionPrivate(*d->qt_rgn);
2359
x->qt_rgn = new QRegionPrivate;
2360
x = qAtomicSetPtr(&r.d, x);
2361
if (!x->ref.deref())
2367
Returns true if the region is empty; otherwise returns false. An
2368
empty region is a region that contains no points.
2372
QRegion r1(10, 10, 20, 20);
2373
QRegion r2(40, 40, 20, 20);
2375
r1.isNull(); // false
2376
r1.isEmpty(); // false
2377
r3.isNull(); // true
2378
r3.isEmpty(); // true
2379
r3 = r1.intersect(r2); // r3 = intersection of r1 and r2
2380
r3.isNull(); // false
2381
r3.isEmpty(); // true
2382
r3 = r1.unite(r2); // r3 = union of r1 and r2
2383
r3.isNull(); // false
2384
r3.isEmpty(); // false
2388
bool QRegion::isEmpty() const
2390
return d == &shared_empty || d->qt_rgn->numRects == 0;
2395
Returns true if the region contains the point \a p; otherwise
2399
bool QRegion::contains(const QPoint &p) const
2401
return PointInRegion(d->qt_rgn, p.x(), p.y());
2407
Returns true if the region overlaps the rectangle \a r; otherwise
2411
bool QRegion::contains(const QRect &r) const
2413
return RectInRegion(d->qt_rgn, r.left(), r.top(), r.width(), r.height()) != RectangleOut;
2419
Translates (moves) the region \a dx along the X axis and \a dy
2423
void QRegion::translate(int dx, int dy)
2426
OffsetRegion(*d->qt_rgn, dx, dy);
2427
#if defined(Q_WS_X11)
2428
if (d->xrectangles) {
2429
free(d->xrectangles);
2432
#elif defined(Q_WS_MAC)
2434
qt_mac_dispose_rgn(d->rgn);
2442
Returns a region which is the union of this region and \a r.
2444
\img runion.png Region Union
2446
The figure shows the union of two elliptical regions.
2449
QRegion QRegion::unite(const QRegion &r) const
2453
UnionRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
2458
Returns a region which is the intersection of this region and \a r.
2460
\img rintersect.png Region Intersection
2462
The figure shows the intersection of two elliptical regions.
2465
QRegion QRegion::intersect(const QRegion &r) const
2469
IntersectRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
2474
Returns a region which is \a r subtracted from this region.
2476
\img rsubtract.png Region Subtraction
2478
The figure shows the result when the ellipse on the right is
2479
subtracted from the ellipse on the left. (\c left-right)
2482
QRegion QRegion::subtract(const QRegion &r) const
2486
SubtractRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
2491
Returns a region which is the exclusive or (XOR) of this region
2494
\img rxor.png Region XORed
2496
The figure shows the exclusive or of two elliptical regions.
2499
QRegion QRegion::eor(const QRegion &r) const
2503
XorRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
2508
Returns the bounding rectangle of this region. An empty region
2509
gives a rectangle that is QRect::isNull().
2512
QRect QRegion::boundingRect() const
2516
return d->qt_rgn->extents;
2521
Returns an array of non-overlapping rectangles that make up the
2524
The union of all the rectangles is equal to the original region.
2526
QVector<QRect> QRegion::rects() const
2529
d->qt_rgn->rects.resize(d->qt_rgn->numRects);
2530
return d->qt_rgn->rects;
2532
return QVector<QRect>();
2537
Sets the region to be the given set of rectangles. The rectangles
2538
\e must be optimal Y-X sorted bands as follows:
2540
<li> The rectangles must not intersect
2541
<li> All rectangles with a given top coordinate must have the same height.
2542
<li> No two rectangles may abut horizontally (they should be combined
2543
into a single wider rectangle in that case).
2544
<li> The rectangles must be sorted ascendingly by Y as the major sort key
2545
and X as the minor sort key.
2548
Only some platforms have that restriction (QWS and X11 and Mac OS X).
2550
void QRegion::setRects(const QRect *rects, int num)
2554
if (!rects || (num == 1 && rects->isEmpty()))
2557
d->qt_rgn->rects.resize(num);
2558
d->qt_rgn->numRects = num;
2560
d->qt_rgn->extents = QRect();
2566
for (int i = 0; i < num; ++i) {
2567
const QRect &rect = rects[i];
2568
d->qt_rgn->rects[i] = rect;
2569
left = qMin(rect.left(), left);
2570
right = qMax(rect.right(), right);
2571
top = qMin(rect.top(), top);
2572
bottom = qMax(rect.bottom(), bottom);
2574
d->qt_rgn->extents = QRect(QPoint(left, top), QPoint(right, bottom));
2579
Returns true if the region is equal to \a r; otherwise returns
2583
bool QRegion::operator==(const QRegion &r) const
2585
if (!d->qt_rgn || !r.d->qt_rgn)
2586
return r.d->qt_rgn == d->qt_rgn;
2591
return EqualRegion(d->qt_rgn, r.d->qt_rgn);
added
removed
src/gui/painting/qregion_unix.cpp
