00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include "qregion.h"
00025 #include "qpainterpath.h"
00026 #include "qpolygon.h"
00027 #include "qbuffer.h"
00028 #include "qimage.h"
00029 #include <qdebug.h>
00030 #include "qbitmap.h"
00031 #include <stdlib.h>
00032
00033
00034
00035
00036
00037 struct QRegionPrivate {
00038 int numRects;
00039 QVector<QRect> rects;
00040 QRect extents;
00041 #ifdef QT_EXPERIMENTAL_REGIONS
00042 QRect innerRect;
00043 int innerArea;
00044 #endif
00045
00046 inline QRegionPrivate() : numRects(0) {}
00047 inline QRegionPrivate(const QRect &r) : rects(1) {
00048 numRects = 1;
00049 rects[0] = r;
00050 extents = r;
00051 #ifdef QT_EXPERIMENTAL_REGIONS
00052 innerRect = r;
00053 innerArea = r.width() * r.height();
00054 #endif
00055 }
00056
00057 inline QRegionPrivate(const QRegionPrivate &r) {
00058 rects = r.rects;
00059 numRects = r.numRects;
00060 extents = r.extents;
00061 #ifdef QT_EXPERIMENTAL_REGIONS
00062 innerRect = r.innerRect;
00063 innerArea = r.innerArea;
00064 #endif
00065 }
00066
00067 inline QRegionPrivate &operator=(const QRegionPrivate &r) {
00068 rects = r.rects;
00069 numRects = r.numRects;
00070 extents = r.extents;
00071 #ifdef QT_EXPERIMENTAL_REGIONS
00072 innerRect = r.innerRect;
00073 innerArea = r.innerArea;
00074 #endif
00075 return *this;
00076 }
00077
00078 #ifdef QT_EXPERIMENTAL_REGIONS
00079
00080
00081
00082
00083 inline bool contains(const QRegionPrivate &r) const {
00084 const QRect &r1 = innerRect;
00085 const QRect &r2 = r.extents;
00086 return r2.left() >= r1.left() && r2.right() <= r1.right()
00087 && r2.top() >= r1.top() && r2.bottom() <= r1.bottom();
00088 }
00089
00090 inline void updateInnerRect(const QRect &rect) {
00091 const int area = rect.width() * rect.height();
00092 if (area > innerArea) {
00093 innerArea = area;
00094 innerRect = rect;
00095 }
00096 }
00097
00098 void append(const QRegionPrivate *r);
00099 inline bool canAppend(const QRegionPrivate *r) const;
00100
00101 #endif
00102 };
00103
00104 #ifdef QT_EXPERIMENTAL_REGIONS
00105 static inline bool isEmpty(const QRegionPrivate *preg)
00106 {
00107 return !preg || preg->numRects == 0;
00108 }
00109
00110 void QRegionPrivate::append(const QRegionPrivate *r)
00111 {
00112 Q_ASSERT(!isEmpty(r));
00113
00114 const int newNumRects = numRects + r->numRects;
00115 if (newNumRects > rects.size())
00116 rects.resize(newNumRects);
00117
00118
00119 QRect *destRect = rects.data() + numRects;
00120 const QRect *srcRect = r->rects.constData();
00121 for (int i = 0; i < r->numRects; ++i)
00122 *destRect++ = *srcRect++;
00123
00124
00125 if (innerArea < r->innerArea) {
00126 innerArea = r->innerArea;
00127 innerRect = r->innerRect;
00128 }
00129
00130
00131 destRect = &extents;
00132 srcRect = &r->extents;
00133 extents.setCoords(qMin(destRect->left(), srcRect->left()),
00134 qMin(destRect->top(), srcRect->top()),
00135 qMax(destRect->right(), srcRect->right()),
00136 qMax(destRect->bottom(), srcRect->bottom()));
00137
00138 numRects = newNumRects;
00139 }
00140
00141 bool QRegionPrivate::canAppend(const QRegionPrivate *r) const
00142 {
00143 Q_ASSERT(!isEmpty(r));
00144
00145 const QRect *rFirst = r->rects.constData();
00146 const QRect *myLast = rects.constData() + (numRects - 1);
00147
00148
00149
00150
00151 if (rFirst->top() > myLast->bottom()
00152 || (rFirst->top() == myLast->top()
00153 && rFirst->height() == myLast->height()
00154 && rFirst->left() > myLast->right()))
00155 {
00156 return true;
00157 }
00158
00159 return false;
00160 }
00161 #endif // QT_EXPERIMENTAL_REGIONS
00162
00163 #if defined(Q_WS_X11)
00164 # include "qregion_x11.cpp"
00165 #elif defined(Q_WS_MAC)
00166 # include "qregion_mac.cpp"
00167 #elif defined(Q_WS_QWS)
00168 static QRegionPrivate qrp;
00169 QRegion::QRegionData QRegion::shared_empty = {Q_ATOMIC_INIT(1), &qrp};
00170 #endif
00171
00172 #ifndef QT_EXPERIMENTAL_REGIONS
00173 static inline bool isEmpty(const QRegionPrivate *preg)
00174 {
00175 return !preg || preg->numRects == 0;
00176 }
00177 #endif
00178
00179 typedef void (*OverlapFunc)(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
00180 register const QRect *r2, const QRect *r2End, register int y1, register int y2);
00181 typedef void (*NonOverlapFunc)(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
00182 register int y1, register int y2);
00183
00184 static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2);
00185 static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest);
00186 static void miRegionOp(register QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2,
00187 OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
00188 NonOverlapFunc nonOverlap2Func);
00189
00190 #define RectangleOut 0
00191 #define RectangleIn 1
00192 #define RectanglePart 2
00193 #define EvenOddRule 0
00194 #define WindingRule 1
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246 #ifndef _XREGION_H
00247 #define _XREGION_H
00248
00249 #include <limits.h>
00250
00251
00252
00253
00254
00255 #define EXTENTCHECK(r1, r2) \
00256 ((r1)->right() >= (r2)->left() && \
00257 (r1)->left() <= (r2)->right() && \
00258 (r1)->bottom() >= (r2)->top() && \
00259 (r1)->top() <= (r2)->bottom())
00260
00261
00262
00263
00264 #define EXTENTS(r,idRect){\
00265 if((r)->left() < (idRect)->extents.left())\
00266 (idRect)->extents.setLeft((r)->left());\
00267 if((r)->top() < (idRect)->extents.top())\
00268 (idRect)->extents.setTop((r)->top());\
00269 if((r)->right() > (idRect)->extents.right())\
00270 (idRect)->extents.setRight((r)->right());\
00271 if((r)->bottom() > (idRect)->extents.bottom())\
00272 (idRect)->extents.setBottom((r)->bottom());\
00273 }
00274
00275
00276
00277
00278 #define MEMCHECK(dest, rect, firstrect){\
00279 if ((dest).numRects >= ((dest).rects.size()-1)){\
00280 firstrect.resize(firstrect.size() * 2); \
00281 (rect) = (firstrect).data() + (dest).numRects;\
00282 }\
00283 }
00284
00285
00286
00287
00288
00289
00290 #define NUMPTSTOBUFFER 200
00291
00292
00293
00294
00295
00296 typedef struct _POINTBLOCK {
00297 QPoint pts[NUMPTSTOBUFFER];
00298 struct _POINTBLOCK *next;
00299 } POINTBLOCK;
00300
00301 #endif
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370
00371
00372
00373
00374
00375
00376
00377
00378
00379
00380 static void UnionRectWithRegion(register const QRect *rect, const QRegionPrivate *source,
00381 QRegionPrivate &dest)
00382 {
00383 if (!rect->width() || !rect->height())
00384 return;
00385
00386 QRegionPrivate region;
00387 region.rects.resize(1);
00388 region.numRects = 1;
00389 region.rects[0] = *rect;
00390 region.extents = *rect;
00391 #ifdef QT_EXPERIMENTAL_REGIONS
00392 region.innerRect = *rect;
00393 region.innerArea = rect->width() * rect->height();
00394 #endif
00395
00396 UnionRegion(®ion, source, dest);
00397 return;
00398 }
00399
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415 static void miSetExtents(QRegionPrivate &dest)
00416 {
00417 register const QRect *pBox,
00418 *pBoxEnd;
00419 register QRect *pExtents;
00420
00421 #ifdef QT_EXPERIMENTAL_REGIONS
00422 dest.innerRect.setCoords(0, 0, -1, -1);
00423 dest.innerArea = -1;
00424 #endif
00425 if (dest.numRects == 0) {
00426 dest.extents.setCoords(0, 0, 0, 0);
00427 return;
00428 }
00429
00430 pExtents = &dest.extents;
00431 pBox = dest.rects.constData();
00432 pBoxEnd = &pBox[dest.numRects - 1];
00433
00434
00435
00436
00437
00438
00439
00440
00441 pExtents->setLeft(pBox->left());
00442 pExtents->setTop(pBox->top());
00443 pExtents->setRight(pBoxEnd->right());
00444 pExtents->setBottom(pBoxEnd->bottom());
00445
00446 Q_ASSERT(pExtents->top() <= pExtents->bottom());
00447 while (pBox <= pBoxEnd) {
00448 if (pBox->left() < pExtents->left())
00449 pExtents->setLeft(pBox->left());
00450 if (pBox->right() > pExtents->right())
00451 pExtents->setRight(pBox->right());
00452 #ifdef QT_EXPERIMENTAL_REGIONS
00453 dest.updateInnerRect(*pBox);
00454 #endif
00455 ++pBox;
00456 }
00457 Q_ASSERT(pExtents->left() <= pExtents->right());
00458 }
00459
00460
00461
00462
00463
00464
00465 static void OffsetRegion(register QRegionPrivate ®ion, register int x, register int y)
00466 {
00467 register int nbox;
00468 register QRect *pbox;
00469
00470 pbox = region.rects.data();
00471 nbox = region.numRects;
00472
00473 while (nbox--) {
00474 pbox->translate(x, y);
00475 ++pbox;
00476 }
00477 region.extents.translate(x, y);
00478 #ifdef QT_EXPERIMENTAL_REGIONS
00479 region.innerRect.translate(x, y);
00480 #endif
00481 }
00482
00483
00484
00485
00486
00487
00488
00489
00490
00491
00492
00493
00494
00495
00496
00497
00498
00499 static void miIntersectO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
00500 register const QRect *r2, const QRect *r2End, int y1, int y2)
00501 {
00502 register int x1;
00503 register int x2;
00504 register QRect *pNextRect;
00505
00506 pNextRect = dest.rects.data() + dest.numRects;
00507
00508 while (r1 != r1End && r2 != r2End) {
00509 x1 = qMax(r1->left(), r2->left());
00510 x2 = qMin(r1->right(), r2->right());
00511
00512
00513
00514
00515
00516
00517
00518
00519 if (x1 <= x2) {
00520 Q_ASSERT(y1 <= y2);
00521 MEMCHECK(dest, pNextRect, dest.rects)
00522 pNextRect->setCoords(x1, y1, x2, y2);
00523 ++dest.numRects;
00524 ++pNextRect;
00525 }
00526
00527
00528
00529
00530
00531
00532 if (r1->right() < r2->right()) {
00533 ++r1;
00534 } else if (r2->right() < r1->right()) {
00535 ++r2;
00536 } else {
00537 ++r1;
00538 ++r2;
00539 }
00540 }
00541 }
00542
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562
00563
00564 static int miCoalesce(register QRegionPrivate &dest, int prevStart, int curStart)
00565 {
00566 register QRect *pPrevBox;
00567 register QRect *pCurBox;
00568 register QRect *pRegEnd;
00569 int curNumRects;
00570 int prevNumRects;
00571 int bandY1;
00572 QRect *rData = dest.rects.data();
00573
00574 pRegEnd = rData + dest.numRects;
00575
00576 pPrevBox = rData + prevStart;
00577 prevNumRects = curStart - prevStart;
00578
00579
00580
00581
00582
00583
00584 pCurBox = rData + curStart;
00585 bandY1 = pCurBox->top();
00586 for (curNumRects = 0; pCurBox != pRegEnd && pCurBox->top() == bandY1; ++curNumRects) {
00587 ++pCurBox;
00588 }
00589
00590 if (pCurBox != pRegEnd) {
00591
00592
00593
00594
00595
00596
00597 --pRegEnd;
00598 while ((pRegEnd - 1)->top() == pRegEnd->top())
00599 --pRegEnd;
00600 curStart = pRegEnd - rData;
00601 pRegEnd = rData + dest.numRects;
00602 }
00603
00604 if (curNumRects == prevNumRects && curNumRects != 0) {
00605 pCurBox -= curNumRects;
00606
00607
00608
00609
00610 if (pPrevBox->bottom() == pCurBox->top() - 1) {
00611
00612
00613
00614
00615
00616
00617 do {
00618 if (pPrevBox->left() != pCurBox->left() || pPrevBox->right() != pCurBox->right()) {
00619
00620 return curStart;
00621 }
00622 ++pPrevBox;
00623 ++pCurBox;
00624 --prevNumRects;
00625 } while (prevNumRects != 0);
00626
00627 dest.numRects -= curNumRects;
00628 pCurBox -= curNumRects;
00629 pPrevBox -= curNumRects;
00630
00631
00632
00633
00634
00635
00636 do {
00637 pPrevBox->setBottom(pCurBox->bottom());
00638 #ifdef QT_EXPERIMENTAL_REGIONS
00639 dest.updateInnerRect(*pPrevBox);
00640 #endif
00641 ++pPrevBox;
00642 ++pCurBox;
00643 curNumRects -= 1;
00644 } while (curNumRects != 0);
00645
00646
00647
00648
00649
00650
00651
00652
00653
00654
00655
00656 if (pCurBox == pRegEnd) {
00657 curStart = prevStart;
00658 } else {
00659 do {
00660 *pPrevBox++ = *pCurBox++;
00661 #ifdef QT_EXPERIMENTAL_REGIONS
00662 dest.updateInnerRect(*pPrevBox);
00663 #endif
00664 } while (pCurBox != pRegEnd);
00665 }
00666 }
00667 }
00668 return curStart;
00669 }
00670
00671
00672
00673
00674
00675
00676
00677
00678
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694
00695
00696
00697 static void miRegionOp(register QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2,
00698 OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
00699 NonOverlapFunc nonOverlap2Func)
00700 {
00701 register const QRect *r1;
00702 register const QRect *r2;
00703 const QRect *r1End;
00704 const QRect *r2End;
00705 register int ybot;
00706 register int ytop;
00707 int prevBand;
00708 int curBand;
00709 register const QRect *r1BandEnd;
00710 register const QRect *r2BandEnd;
00711 int top;
00712 int bot;
00713
00714
00715
00716
00717
00718
00719
00720
00721 r1 = reg1->rects.data();
00722 r2 = reg2->rects.data();
00723 r1End = r1 + reg1->numRects;
00724 r2End = r2 + reg2->numRects;
00725
00726 QVector<QRect> oldRects = dest.rects;
00727
00728 dest.numRects = 0;
00729
00730
00731
00732
00733
00734
00735
00736
00737 dest.rects.resize(qMax(reg1->numRects,reg2->numRects) * 2);
00738
00739
00740
00741
00742
00743
00744
00745
00746
00747
00748
00749
00750
00751
00752 if (reg1->extents.top() < reg2->extents.top())
00753 ybot = reg1->extents.top() - 1;
00754 else
00755 ybot = reg2->extents.top() - 1;
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766 prevBand = 0;
00767
00768 do {
00769 curBand = dest.numRects;
00770
00771
00772
00773
00774
00775
00776
00777
00778 r1BandEnd = r1;
00779 while (r1BandEnd != r1End && r1BandEnd->top() == r1->top())
00780 ++r1BandEnd;
00781
00782 r2BandEnd = r2;
00783 while (r2BandEnd != r2End && r2BandEnd->top() == r2->top())
00784 ++r2BandEnd;
00785
00786
00787
00788
00789
00790
00791
00792
00793
00794 if (r1->top() < r2->top()) {
00795 top = qMax(r1->top(), ybot + 1);
00796 bot = qMin(r1->bottom(), r2->top() - 1);
00797
00798 if (nonOverlap1Func != 0 && bot >= top)
00799 (*nonOverlap1Func)(dest, r1, r1BandEnd, top, bot);
00800 ytop = r2->top();
00801 } else if (r2->top() < r1->top()) {
00802 top = qMax(r2->top(), ybot + 1);
00803 bot = qMin(r2->bottom(), r1->top() - 1);
00804
00805 if (nonOverlap2Func != 0 && bot >= top)
00806 (*nonOverlap2Func)(dest, r2, r2BandEnd, top, bot);
00807 ytop = r1->top();
00808 } else {
00809 ytop = r1->top();
00810 }
00811
00812
00813
00814
00815
00816
00817
00818 if (dest.numRects != curBand)
00819 prevBand = miCoalesce(dest, prevBand, curBand);
00820
00821
00822
00823
00824
00825 ybot = qMin(r1->bottom(), r2->bottom());
00826 curBand = dest.numRects;
00827 if (ybot >= ytop)
00828 (*overlapFunc)(dest, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
00829
00830 if (dest.numRects != curBand)
00831 prevBand = miCoalesce(dest, prevBand, curBand);
00832
00833
00834
00835
00836
00837 if (r1->bottom() == ybot)
00838 r1 = r1BandEnd;
00839 if (r2->bottom() == ybot)
00840 r2 = r2BandEnd;
00841 } while (r1 != r1End && r2 != r2End);
00842
00843
00844
00845
00846 curBand = dest.numRects;
00847 if (r1 != r1End) {
00848 if (nonOverlap1Func != 0) {
00849 do {
00850 r1BandEnd = r1;
00851 while (r1BandEnd < r1End && r1BandEnd->top() == r1->top())
00852 ++r1BandEnd;
00853 (*nonOverlap1Func)(dest, r1, r1BandEnd, qMax(r1->top(), ybot + 1), r1->bottom());
00854 r1 = r1BandEnd;
00855 } while (r1 != r1End);
00856 }
00857 } else if ((r2 != r2End) && (nonOverlap2Func != 0)) {
00858 do {
00859 r2BandEnd = r2;
00860 while (r2BandEnd < r2End && r2BandEnd->top() == r2->top())
00861 ++r2BandEnd;
00862 (*nonOverlap2Func)(dest, r2, r2BandEnd, qMax(r2->top(), ybot + 1), r2->bottom());
00863 r2 = r2BandEnd;
00864 } while (r2 != r2End);
00865 }
00866
00867 if (dest.numRects != curBand)
00868 (void)miCoalesce(dest, prevBand, curBand);
00869
00870
00871
00872
00873
00874
00875
00876
00877
00878 #ifdef QT_EXPERIMENTAL_REGIONS
00879 if (qMax(4, dest.numRects) < (dest.rects.size() >> 1))
00880 #else
00881 if (dest.numRects < (dest.rects.size() >> 1))
00882 #endif
00883 dest.rects.resize(dest.numRects);
00884 }
00885
00886
00887
00888
00889
00890
00891
00892
00893
00894
00895
00896
00897
00898
00899
00900
00901
00902
00903
00904
00905
00906
00907 static void miUnionNonO(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
00908 register int y1, register int y2)
00909 {
00910 register QRect *pNextRect;
00911
00912 pNextRect = dest.rects.data() + dest.numRects;
00913
00914 Q_ASSERT(y1 <= y2);
00915
00916 while (r != rEnd) {
00917 Q_ASSERT(r->left() <= r->right());
00918 MEMCHECK(dest, pNextRect, dest.rects)
00919 pNextRect->setCoords(r->left(), y1, r->right(), y2);
00920 dest.numRects++;
00921 ++pNextRect;
00922 ++r;
00923 }
00924 }
00925
00926
00927
00928
00929
00930
00931
00932
00933
00934
00935
00936
00937
00938
00939
00940
00941
00942
00943 static void miUnionO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
00944 register const QRect *r2, const QRect *r2End, register int y1, register int y2)
00945 {
00946 register QRect *pNextRect;
00947
00948 pNextRect = dest.rects.data() + dest.numRects;
00949
00950 #ifndef QT_EXPERIMENTAL_REGIONS
00951 #define MERGERECT(r) \
00952 if ((dest.numRects != 0) && \
00953 (pNextRect[-1].top() == y1) && \
00954 (pNextRect[-1].bottom() == y2) && \
00955 (pNextRect[-1].right() >= r->left()-1)) { \
00956 if (pNextRect[-1].right() < r->right()) { \
00957 pNextRect[-1].setRight(r->right()); \
00958 Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
00959 } \
00960 } else { \
00961 MEMCHECK(dest, pNextRect, dest.rects) \
00962 pNextRect->setCoords(r->left(), y1, r->right(), y2); \
00963 dest.numRects++; \
00964 pNextRect++; \
00965 } \
00966 r++;
00967 #else
00968 #define MERGERECT(r) \
00969 if ((dest.numRects != 0) && \
00970 (pNextRect[-1].top() == y1) && \
00971 (pNextRect[-1].bottom() == y2) && \
00972 (pNextRect[-1].right() >= r->left()-1)) { \
00973 if (pNextRect[-1].right() < r->right()) { \
00974 pNextRect[-1].setRight(r->right()); \
00975 dest.updateInnerRect(pNextRect[-1]); \
00976 Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
00977 } \
00978 } else { \
00979 MEMCHECK(dest, pNextRect, dest.rects) \
00980 pNextRect->setCoords(r->left(), y1, r->right(), y2); \
00981 dest.updateInnerRect(*pNextRect); \
00982 dest.numRects++; \
00983 pNextRect++; \
00984 } \
00985 r++;
00986 #endif
00987
00988 Q_ASSERT(y1 <= y2);
00989 while (r1 != r1End && r2 != r2End) {
00990 if (r1->left() < r2->left()) {
00991 MERGERECT(r1)
00992 } else {
00993 MERGERECT(r2)
00994 }
00995 }
00996
00997 if (r1 != r1End) {
00998 do {
00999 MERGERECT(r1)
01000 } while (r1 != r1End);
01001 } else {
01002 while (r2 != r2End) {
01003 MERGERECT(r2)
01004 }
01005 }
01006 }
01007
01008 static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest)
01009 {
01010 #ifdef QT_EXPERIMENTAL_REGIONS
01011
01012
01013
01014 if (isEmpty(reg1)) {
01015 dest = *reg2;
01016 return;
01017 }
01018 if (isEmpty(reg2)) {
01019 dest = *reg1;
01020 return;
01021 }
01022
01023
01024
01025
01026 if (reg1->contains(*reg2)) {
01027 dest = *reg1;
01028 return;
01029 }
01030 if (reg2->contains(*reg1)) {
01031 dest = *reg2;
01032 return;
01033 }
01034
01035
01036
01037
01038 if (EqualRegion(reg1, reg2)) {
01039 dest = *reg1;
01040 return;
01041 }
01042
01043
01044
01045
01046 if (reg1->canAppend(reg2)) {
01047 dest = *reg1;
01048 dest.append(reg2);
01049 return;
01050 }
01051
01052
01053
01054
01055 if (reg2->canAppend(reg1)) {
01056 dest = *reg2;
01057 dest.append(reg1);
01058 return;
01059 }
01060 #else
01061
01062
01063
01064 if (reg1 == reg2 || isEmpty(reg1)) {
01065 if (!isEmpty(reg2))
01066 dest = *reg2;
01067 return;
01068 }
01069
01070
01071
01072
01073 if (isEmpty(reg2)) {
01074 dest = *reg1;
01075 return;
01076 }
01077
01078
01079
01080
01081 if (reg1->numRects == 1 && reg1->extents.left() <= reg2->extents.left()
01082 && reg1->extents.top() <= reg2->extents.top()
01083 && reg1->extents.right() >= reg2->extents.right()
01084 && reg1->extents.bottom() >= reg2->extents.bottom()) {
01085 dest = *reg1;
01086 return;
01087 }
01088
01089
01090
01091
01092 if (reg2->numRects == 1 && reg2->extents.left() <= reg1->extents.left()
01093 && reg2->extents.top() <= reg1->extents.top()
01094 && reg2->extents.right() >= reg1->extents.right()
01095 && reg2->extents.bottom() >= reg1->extents.bottom()) {
01096 dest = *reg2;
01097 return;
01098 }
01099 #endif
01100
01101 #ifdef QT_EXPERIMENTAL_REGIONS
01102 if (reg1->innerArea > reg2->innerArea) {
01103 dest.innerArea = reg1->innerArea;
01104 dest.innerRect = reg1->innerRect;
01105 } else {
01106 dest.innerArea = reg2->innerArea;
01107 dest.innerRect = reg2->innerRect;
01108 }
01109 #endif
01110 miRegionOp(dest, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO);
01111
01112 dest.extents.setCoords(qMin(reg1->extents.left(), reg2->extents.left()),
01113 qMin(reg1->extents.top(), reg2->extents.top()),
01114 qMax(reg1->extents.right(), reg2->extents.right()),
01115 qMax(reg1->extents.bottom(), reg2->extents.bottom()));
01116 }
01117
01118
01119
01120
01121
01122
01123
01124
01125
01126
01127
01128
01129
01130
01131
01132
01133
01134
01135
01136
01137 static void miSubtractNonO1(register QRegionPrivate &dest, register const QRect *r,
01138 const QRect *rEnd, register int y1, register int y2)
01139 {
01140 register QRect *pNextRect;
01141
01142 pNextRect = dest.rects.data() + dest.numRects;
01143
01144 Q_ASSERT(y1<=y2);
01145
01146 while (r != rEnd) {
01147 Q_ASSERT(r->left() <= r->right());
01148 MEMCHECK(dest, pNextRect, dest.rects)
01149 pNextRect->setCoords(r->left(), y1, r->right(), y2);
01150 ++dest.numRects;
01151 ++pNextRect;
01152 ++r;
01153 }
01154 }
01155
01156
01157
01158
01159
01160
01161
01162
01163
01164
01165
01166
01167
01168
01169
01170
01171 static void miSubtractO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
01172 register const QRect *r2, const QRect *r2End, register int y1, register int y2)
01173 {
01174 register QRect *pNextRect;
01175 register int x1;
01176
01177 x1 = r1->left();
01178
01179 Q_ASSERT(y1 <= y2);
01180 pNextRect = dest.rects.data() + dest.numRects;
01181
01182 while (r1 != r1End && r2 != r2End) {
01183 if (r2->right() < x1) {
01184
01185
01186
01187 ++r2;
01188 } else if (r2->left() <= x1) {
01189
01190
01191
01192 x1 = r2->right() + 1;
01193 if (x1 > r1->right()) {
01194
01195
01196
01197
01198 ++r1;
01199 if (r1 != r1End)
01200 x1 = r1->left();
01201 } else {
01202
01203 ++r2;
01204 }
01205 } else if (r2->left() <= r1->right()) {
01206
01207
01208
01209
01210 Q_ASSERT(x1 < r2->left());
01211 MEMCHECK(dest, pNextRect, dest.rects)
01212 pNextRect->setCoords(x1, y1, r2->left() - 1, y2);
01213 ++dest.numRects;
01214 ++pNextRect;
01215
01216 x1 = r2->right() + 1;
01217 if (x1 > r1->right()) {
01218
01219
01220
01221 ++r1;
01222 if (r1 != r1End)
01223 x1 = r1->left();
01224 } else {
01225
01226 ++r2;
01227 }
01228 } else {
01229
01230
01231
01232 if (r1->right() >= x1) {
01233 MEMCHECK(dest, pNextRect, dest.rects)
01234 pNextRect->setCoords(x1, y1, r1->right(), y2);
01235 ++dest.numRects;
01236 ++pNextRect;
01237 }
01238 ++r1;
01239 if (r1 != r1End)
01240 x1 = r1->left();
01241 }
01242 }
01243
01244
01245
01246
01247 while (r1 != r1End) {
01248 Q_ASSERT(x1 <= r1->right());
01249 MEMCHECK(dest, pNextRect, dest.rects)
01250 pNextRect->setCoords(x1, y1, r1->right(), y2);
01251 ++dest.numRects;
01252 ++pNextRect;
01253
01254 ++r1;
01255 if (r1 != r1End)
01256 x1 = r1->left();
01257 }
01258 }
01259
01260
01261
01262
01263
01264
01265
01266
01267
01268
01269
01270
01271
01272 static void SubtractRegion(QRegionPrivate *regM, QRegionPrivate *regS,
01273 register QRegionPrivate &dest)
01274 {
01275
01276 if (isEmpty(regM))
01277 return;
01278
01279 if (isEmpty(regS) || !EXTENTCHECK(®M->extents, ®S->extents)) {
01280 dest = *regM;
01281 return;
01282 }
01283
01284 #ifdef QT_EXPERIMENTAL_REGIONS
01285 if (regS->contains(*regM)) {
01286 dest = QRegionPrivate();
01287 return;
01288 }
01289
01290 if (EqualRegion(regM, regS)) {
01291 dest = QRegionPrivate();
01292 return;
01293 }
01294 #endif
01295
01296 miRegionOp(dest, regM, regS, miSubtractO, miSubtractNonO1, 0);
01297
01298
01299
01300
01301
01302
01303
01304
01305 miSetExtents(dest);
01306 }
01307
01308 static void XorRegion(QRegionPrivate *sra, QRegionPrivate *srb, QRegionPrivate &dest)
01309 {
01310 QRegionPrivate tra, trb;
01311
01312 SubtractRegion(sra, srb, tra);
01313 SubtractRegion(srb, sra, trb);
01314 UnionRegion(&tra, &trb, dest);
01315 }
01316
01317
01318
01319
01320 static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2)
01321 {
01322 if (r1->numRects != r2->numRects) {
01323 return false;
01324 } else if (r1->numRects == 0) {
01325 return true;
01326 } else if (r1->extents != r2->extents) {
01327 return false;
01328 } else {
01329 const QRect *rr1 = r1->rects.constData();
01330 const QRect *rr2 = r2->rects.constData();
01331 for (int i = 0; i < r1->numRects; ++i, ++rr1, ++rr2) {
01332 if (*rr1 != *rr2)
01333 return false;
01334 }
01335 }
01336
01337 return true;
01338 }
01339
01340 static bool PointInRegion(QRegionPrivate *pRegion, int x, int y)
01341 {
01342 int i;
01343
01344 if (isEmpty(pRegion))
01345 return false;
01346 if (!pRegion->extents.contains(x, y))
01347 return false;
01348 #ifdef QT_EXPERIMENTAL_REGIONS
01349 if (pRegion->innerRect.contains(x, y))
01350 return true;
01351 #endif
01352 for (i = 0; i < pRegion->numRects; ++i) {
01353 if (pRegion->rects[i].contains(x, y))
01354 return true;
01355 }
01356 return false;
01357 }
01358
01359 static bool RectInRegion(register QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight)
01360 {
01361 register const QRect *pbox;
01362 register const QRect *pboxEnd;
01363 QRect rect(rx, ry, rwidth, rheight);
01364 register QRect *prect = ▭
01365 int partIn, partOut;
01366
01367 if (!region || region->numRects == 0 || !EXTENTCHECK(®ion->extents, prect))
01368 return RectangleOut;
01369
01370 partOut = false;
01371 partIn = false;
01372
01373
01374 for (pbox = region->rects.constData(), pboxEnd = pbox + region->numRects;
01375 pbox < pboxEnd; ++pbox) {
01376 if (pbox->bottom() < ry)
01377 continue;
01378
01379 if (pbox->top() > ry) {
01380 partOut = true;
01381 if (partIn || pbox->top() > prect->bottom())
01382 break;
01383 ry = pbox->top();
01384 }
01385
01386 if (pbox->right() < rx)
01387 continue;
01388
01389 if (pbox->left() > rx) {
01390 partOut = true;
01391 if (partIn)
01392 break;
01393 }
01394
01395 if (pbox->left() <= prect->right()) {
01396 partIn = true;
01397 if (partOut)
01398 break;
01399 }
01400
01401 if (pbox->right() >= prect->right()) {
01402 ry = pbox->bottom() + 1;
01403 if (ry > prect->bottom())
01404 break;
01405 rx = prect->left();
01406 } else {
01407
01408
01409
01410
01411
01412
01413
01414 break;
01415 }
01416 }
01417 return partIn ? ((ry <= prect->bottom()) ? RectanglePart : RectangleIn) : RectangleOut;
01418 }
01419
01420
01421
01422
01423
01424
01425
01426
01427
01428
01429
01430
01431
01432
01433
01434
01435
01436
01437
01438
01439
01440
01441
01442
01443
01444
01445
01446
01447
01448
01449
01450
01451
01452
01453
01454
01455
01456
01457
01458
01459
01460
01461
01462
01463
01464
01465
01466
01467
01468
01469
01470
01471
01472
01473
01474
01475
01476
01477
01478
01479
01480
01481
01482
01483
01484
01485
01486
01487
01488
01489
01490
01491
01492
01493
01494
01495
01496
01497
01498
01499
01500
01501
01502
01503
01504
01505 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
01506 int dx; \
01507 \
01508
01509
01510
01511 \
01512 if ((dy) != 0) { \
01513 xStart = (x1); \
01514 dx = (x2) - xStart; \
01515 if (dx < 0) { \
01516 m = dx / (dy); \
01517 m1 = m - 1; \
01518 incr1 = -2 * dx + 2 * (dy) * m1; \
01519 incr2 = -2 * dx + 2 * (dy) * m; \
01520 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
01521 } else { \
01522 m = dx / (dy); \
01523 m1 = m + 1; \
01524 incr1 = 2 * dx - 2 * (dy) * m1; \
01525 incr2 = 2 * dx - 2 * (dy) * m; \
01526 d = -2 * m * (dy) + 2 * dx; \
01527 } \
01528 } \
01529 }
01530
01531 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
01532 if (m1 > 0) { \
01533 if (d > 0) { \
01534 minval += m1; \
01535 d += incr1; \
01536 } \
01537 else { \
01538 minval += m; \
01539 d += incr2; \
01540 } \
01541 } else {\
01542 if (d >= 0) { \
01543 minval += m1; \
01544 d += incr1; \
01545 } \
01546 else { \
01547 minval += m; \
01548 d += incr2; \
01549 } \
01550 } \
01551 }
01552
01553
01554
01555
01556
01557
01558
01559
01560
01561 typedef struct {
01562 int minor_axis;
01563 int d;
01564 int m, m1;
01565 int incr1, incr2;
01566 } BRESINFO;
01567
01568
01569 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
01570 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
01571 bres.m, bres.m1, bres.incr1, bres.incr2)
01572
01573 #define BRESINCRPGONSTRUCT(bres) \
01574 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
01575
01576
01577
01578
01579
01580
01581
01582
01583
01584
01585
01586
01587
01588
01589
01590
01591
01592
01593
01594
01595
01596
01597
01598
01599
01600
01601
01602
01603
01604
01605
01606
01607
01608
01609
01610
01611
01612
01613
01614
01615
01616
01617
01618
01619
01620
01621
01622
01623
01624
01625
01626
01627 #define CLOCKWISE 1
01628 #define COUNTERCLOCKWISE -1
01629
01630 typedef struct _EdgeTableEntry {
01631 int ymax;
01632 BRESINFO bres;
01633 struct _EdgeTableEntry *next;
01634 struct _EdgeTableEntry *back;
01635 struct _EdgeTableEntry *nextWETE;
01636 int ClockWise;
01637 } EdgeTableEntry;
01638
01639
01640 typedef struct _ScanLineList{
01641 int scanline;
01642 EdgeTableEntry *edgelist;
01643 struct _ScanLineList *next;
01644 } ScanLineList;
01645
01646
01647 typedef struct {
01648 int ymax;
01649 int ymin;
01650 ScanLineList scanlines;
01651 } EdgeTable;
01652
01653
01654
01655
01656
01657
01658
01659 #define SLLSPERBLOCK 25
01660
01661 typedef struct _ScanLineListBlock {
01662 ScanLineList SLLs[SLLSPERBLOCK];
01663 struct _ScanLineListBlock *next;
01664 } ScanLineListBlock;
01665
01666
01667
01668
01669
01670
01671
01672
01673
01674
01675
01676
01677
01678
01679
01680
01681 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
01682 if (pAET->ymax == y) { \
01683 pPrevAET->next = pAET->next; \
01684 pAET = pPrevAET->next; \
01685 fixWAET = 1; \
01686 if (pAET) \
01687 pAET->back = pPrevAET; \
01688 } \
01689 else { \
01690 BRESINCRPGONSTRUCT(pAET->bres) \
01691 pPrevAET = pAET; \
01692 pAET = pAET->next; \
01693 } \
01694 }
01695
01696
01697
01698
01699
01700
01701
01702
01703
01704 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
01705 if (pAET->ymax == y) { \
01706 pPrevAET->next = pAET->next; \
01707 pAET = pPrevAET->next; \
01708 if (pAET) \
01709 pAET->back = pPrevAET; \
01710 } \
01711 else { \
01712 BRESINCRPGONSTRUCT(pAET->bres) \
01713 pPrevAET = pAET; \
01714 pAET = pAET->next; \
01715 } \
01716 }
01717
01718
01719
01720
01721
01722
01723
01724
01725
01726
01727
01728
01729
01730
01731
01732
01733
01734
01735
01736
01737
01738
01739
01740
01741
01742
01743
01744
01745
01746
01747
01748
01749
01750
01751
01752
01753
01754
01755
01756
01757
01758
01759
01760
01761
01762
01763
01764
01765
01766
01767
01768
01769 #define LARGE_COORDINATE 1000000
01770 #define SMALL_COORDINATE -LARGE_COORDINATE
01771
01772
01773
01774
01775
01776
01777
01778
01779
01780
01781 static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline,
01782 ScanLineListBlock **SLLBlock, int *iSLLBlock)
01783 {
01784 register EdgeTableEntry *start, *prev;
01785 register ScanLineList *pSLL, *pPrevSLL;
01786 ScanLineListBlock *tmpSLLBlock;
01787
01788
01789
01790
01791 pPrevSLL = &ET->scanlines;
01792 pSLL = pPrevSLL->next;
01793 while (pSLL && (pSLL->scanline < scanline)) {
01794 pPrevSLL = pSLL;
01795 pSLL = pSLL->next;
01796 }
01797
01798
01799
01800
01801 if ((!pSLL) || (pSLL->scanline > scanline)) {
01802 if (*iSLLBlock > SLLSPERBLOCK-1)
01803 {
01804 tmpSLLBlock =
01805 (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock));
01806 (*SLLBlock)->next = tmpSLLBlock;
01807 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
01808 *SLLBlock = tmpSLLBlock;
01809 *iSLLBlock = 0;
01810 }
01811 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
01812
01813 pSLL->next = pPrevSLL->next;
01814 pSLL->edgelist = (EdgeTableEntry *)NULL;
01815 pPrevSLL->next = pSLL;
01816 }
01817 pSLL->scanline = scanline;
01818
01819
01820
01821
01822 prev = 0;
01823 start = pSLL->edgelist;
01824 while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) {
01825 prev = start;
01826 start = start->next;
01827 }
01828 ETE->next = start;
01829
01830 if (prev)
01831 prev->next = ETE;
01832 else
01833 pSLL->edgelist = ETE;
01834 }
01835
01836
01837
01838
01839
01840
01841
01842
01843
01844
01845
01846
01847
01848
01849
01850
01851
01852
01853
01854
01855
01856
01857
01858
01859
01860
01861 static void CreateETandAET(register int count, register const QPoint *pts,
01862 EdgeTable *ET, EdgeTableEntry *AET, register EdgeTableEntry *pETEs,
01863 ScanLineListBlock *pSLLBlock)
01864 {
01865 register const QPoint *top,
01866 *bottom,
01867 *PrevPt,
01868 *CurrPt;
01869 int iSLLBlock = 0;
01870 int dy;
01871
01872 if (count < 2)
01873 return;
01874
01875
01876
01877
01878 AET->next = 0;
01879 AET->back = 0;
01880 AET->nextWETE = 0;
01881 AET->bres.minor_axis = SMALL_COORDINATE;
01882
01883
01884
01885
01886 ET->scanlines.next = 0;
01887 ET->ymax = SMALL_COORDINATE;
01888 ET->ymin = LARGE_COORDINATE;
01889 pSLLBlock->next = 0;
01890
01891 PrevPt = &pts[count - 1];
01892
01893
01894
01895
01896
01897
01898 while (count--) {
01899 CurrPt = pts++;
01900
01901
01902
01903
01904 if (PrevPt->y() > CurrPt->y()) {
01905 bottom = PrevPt;
01906 top = CurrPt;
01907 pETEs->ClockWise = 0;
01908 } else {
01909 bottom = CurrPt;
01910 top = PrevPt;
01911 pETEs->ClockWise = 1;
01912 }
01913
01914
01915
01916
01917 if (bottom->y() != top->y()) {
01918 pETEs->ymax = bottom->y() - 1;
01919
01920
01921
01922
01923 dy = bottom->y() - top->y();
01924 BRESINITPGONSTRUCT(dy, top->x(), bottom->x(), pETEs->bres)
01925
01926 InsertEdgeInET(ET, pETEs, top->y(), &pSLLBlock, &iSLLBlock);
01927
01928 if (PrevPt->y() > ET->ymax)
01929 ET->ymax = PrevPt->y();
01930 if (PrevPt->y() < ET->ymin)
01931 ET->ymin = PrevPt->y();
01932 ++pETEs;
01933 }
01934
01935 PrevPt = CurrPt;
01936 }
01937 }
01938
01939
01940
01941
01942
01943
01944
01945
01946
01947
01948 static void loadAET(register EdgeTableEntry *AET, register EdgeTableEntry *ETEs)
01949 {
01950 register EdgeTableEntry *pPrevAET;
01951 register EdgeTableEntry *tmp;
01952
01953 pPrevAET = AET;
01954 AET = AET->next;
01955 while (ETEs) {
01956 while (AET && AET->bres.minor_axis < ETEs->bres.minor_axis) {
01957 pPrevAET = AET;
01958 AET = AET->next;
01959 }
01960 tmp = ETEs->next;
01961 ETEs->next = AET;
01962 if (AET)
01963 AET->back = ETEs;
01964 ETEs->back = pPrevAET;
01965 pPrevAET->next = ETEs;
01966 pPrevAET = ETEs;
01967
01968 ETEs = tmp;
01969 }
01970 }
01971
01972
01973
01974
01975
01976
01977
01978
01979
01980
01981
01982
01983
01984
01985
01986
01987
01988
01989
01990
01991
01992 static void computeWAET(register EdgeTableEntry *AET)
01993 {
01994 register EdgeTableEntry *pWETE;
01995 register int inside = 1;
01996 register int isInside = 0;
01997
01998 AET->nextWETE = 0;
01999 pWETE = AET;
02000 AET = AET->next;
02001 while (AET) {
02002 if (AET->ClockWise)
02003 ++isInside;
02004 else
02005 --isInside;
02006
02007 if (!inside && !isInside || inside && isInside) {
02008 pWETE->nextWETE = AET;
02009 pWETE = AET;
02010 inside = !inside;
02011 }
02012 AET = AET->next;
02013 }
02014 pWETE->nextWETE = 0;
02015 }
02016
02017
02018
02019
02020
02021
02022
02023
02024
02025
02026 static int InsertionSort(register EdgeTableEntry *AET)
02027 {
02028 register EdgeTableEntry *pETEchase;
02029 register EdgeTableEntry *pETEinsert;
02030 register EdgeTableEntry *pETEchaseBackTMP;
02031 register int changed = 0;
02032
02033 AET = AET->next;
02034 while (AET) {
02035 pETEinsert = AET;
02036 pETEchase = AET;
02037 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
02038 pETEchase = pETEchase->back;
02039
02040 AET = AET->next;
02041 if (pETEchase != pETEinsert) {
02042 pETEchaseBackTMP = pETEchase->back;
02043 pETEinsert->back->next = AET;
02044 if (AET)
02045 AET->back = pETEinsert->back;
02046 pETEinsert->next = pETEchase;
02047 pETEchase->back->next = pETEinsert;
02048 pETEchase->back = pETEinsert;
02049 pETEinsert->back = pETEchaseBackTMP;
02050 changed = 1;
02051 }
02052 }
02053 return changed;
02054 }
02055
02056
02057
02058
02059 static void FreeStorage(register ScanLineListBlock *pSLLBlock)
02060 {
02061 register ScanLineListBlock *tmpSLLBlock;
02062
02063 while (pSLLBlock) {
02064 tmpSLLBlock = pSLLBlock->next;
02065 free(pSLLBlock);
02066 pSLLBlock = tmpSLLBlock;
02067 }
02068 }
02069
02070
02071
02072
02073
02074
02075
02076
02077
02078 static void PtsToRegion(register int numFullPtBlocks, register int iCurPtBlock,
02079 POINTBLOCK *FirstPtBlock, QRegionPrivate *reg)
02080 {
02081 register QRect *rects;
02082 register QPoint *pts;
02083 register POINTBLOCK *CurPtBlock;
02084 register int i;
02085 register QRect *extents;
02086 register int numRects;
02087
02088 extents = ®->extents;
02089 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
02090
02091 reg->rects.resize(numRects);
02092
02093 CurPtBlock = FirstPtBlock;
02094 rects = reg->rects.data() - 1;
02095 numRects = 0;
02096 extents->setLeft(INT_MAX);
02097 extents->setRight(INT_MIN);
02098 #ifdef QT_EXPERIMENTAL_REGIONS
02099 reg->innerArea = -1;
02100 #endif
02101
02102 for (; numFullPtBlocks >= 0; --numFullPtBlocks) {
02103
02104 i = NUMPTSTOBUFFER >> 1;
02105 if (!numFullPtBlocks)
02106 i = iCurPtBlock >> 1;
02107 if(i) {
02108 for (pts = CurPtBlock->pts; i--; pts += 2) {
02109 if (pts->x() == pts[1].x())
02110 continue;
02111 if (numRects && pts->x() == rects->left() && pts->y() == rects->bottom() + 1
02112 && pts[1].x() == rects->right()+1 && (numRects == 1 || rects[-1].top() != rects->top())
02113 && (i && pts[2].y() > pts[1].y())) {
02114 rects->setBottom(pts[1].y());
02115 #ifdef QT_EXPERIMENTAL_REGIONS
02116 reg->updateInnerRect(*rects);
02117 #endif
02118 continue;
02119 }
02120 ++numRects;
02121 ++rects;
02122 rects->setCoords(pts->x(), pts->y(), pts[1].x() - 1, pts[1].y());
02123 if (rects->left() < extents->left())
02124 extents->setLeft(rects->left());
02125 if (rects->right() > extents->right())
02126 extents->setRight(rects->right());
02127 #ifdef QT_EXPERIMENTAL_REGIONS
02128 reg->updateInnerRect(*rects);
02129 #endif
02130 }
02131 }
02132 CurPtBlock = CurPtBlock->next;
02133 }
02134
02135 if (numRects) {
02136 extents->setTop(reg->rects[0].top());
02137 extents->setBottom(rects->bottom());
02138 } else {
02139 extents->setCoords(0, 0, 0, 0);
02140 }
02141 reg->numRects = numRects;
02142 }
02143
02144
02145
02146
02147
02148
02149
02150
02151 static QRegionPrivate *PolygonRegion(const QPoint *Pts, int Count, int rule)
02152
02153
02154
02155 {
02156 QRegionPrivate *region;
02157 register EdgeTableEntry *pAET;
02158 register int y;
02159 register int iPts = 0;
02160 register EdgeTableEntry *pWETE;
02161 register ScanLineList *pSLL;
02162 register QPoint *pts;
02163 EdgeTableEntry *pPrevAET;
02164 EdgeTable ET;
02165 EdgeTableEntry AET;
02166 EdgeTableEntry *pETEs;
02167 ScanLineListBlock SLLBlock;
02168 int fixWAET = false;
02169 POINTBLOCK FirstPtBlock, *curPtBlock;
02170 POINTBLOCK *tmpPtBlock;
02171 int numFullPtBlocks = 0;
02172
02173 if (!(region = new QRegionPrivate))
02174 return 0;
02175
02176
02177 if (((Count == 4) ||
02178 ((Count == 5) && (Pts[4].x() == Pts[0].x()) && (Pts[4].y() == Pts[0].y())))
02179 && (((Pts[0].y() == Pts[1].y()) && (Pts[1].x() == Pts[2].x()) && (Pts[2].y() == Pts[3].y())
02180 && (Pts[3].x() == Pts[0].x())) || ((Pts[0].x() == Pts[1].x())
02181 && (Pts[1].y() == Pts[2].y()) && (Pts[2].x() == Pts[3].x())
02182 && (Pts[3].y() == Pts[0].y())))) {
02183 int x = qMin(Pts[0].x(), Pts[2].x());
02184 region->extents.setLeft(x);
02185 int y = qMin(Pts[0].y(), Pts[2].y());
02186 region->extents.setTop(y);
02187 region->extents.setWidth(qMax(Pts[0].x(), Pts[2].x()) - x);
02188 region->extents.setHeight(qMax(Pts[0].y(), Pts[2].y()) - y);
02189 if ((region->extents.left() <= region->extents.right()) &&
02190 (region->extents.top() <= region->extents.bottom())) {
02191 region->numRects = 1;
02192 region->rects.resize(1);
02193 region->rects[0] = region->extents;
02194 #ifdef QT_EXPERIMENTAL_REGIONS
02195 region->innerRect = region->extents;
02196 region->innerArea = region->innerRect.width() * region->innerRect.height();
02197 #endif
02198 }
02199 return region;
02200 }
02201
02202 if (!(pETEs = static_cast<EdgeTableEntry *>(malloc(sizeof(EdgeTableEntry) * Count))))
02203 return 0;
02204
02205 pts = FirstPtBlock.pts;
02206 CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
02207 pSLL = ET.scanlines.next;
02208 curPtBlock = &FirstPtBlock;
02209
02210 if (rule == EvenOddRule) {
02211
02212
02213
02214 for (y = ET.ymin; y < ET.ymax; ++y) {
02215
02216
02217
02218
02219 if (pSLL && y == pSLL->scanline) {
02220 loadAET(&AET, pSLL->edgelist);
02221 pSLL = pSLL->next;
02222 }
02223 pPrevAET = &AET;
02224 pAET = AET.next;
02225
02226
02227
02228
02229 while (pAET) {
02230 pts->setX(pAET->bres.minor_axis);
02231 pts->setY(y);
02232 ++pts;
02233 ++iPts;
02234
02235
02236
02237
02238 if (iPts == NUMPTSTOBUFFER) {
02239 tmpPtBlock = (POINTBLOCK *)malloc(sizeof(POINTBLOCK));
02240 curPtBlock->next = tmpPtBlock;
02241 curPtBlock = tmpPtBlock;
02242 pts = curPtBlock->pts;
02243 ++numFullPtBlocks;
02244 iPts = 0;
02245 }
02246 EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
02247 }
02248 InsertionSort(&AET);
02249 }
02250 } else {
02251
02252
02253
02254 for (y = ET.ymin; y < ET.ymax; ++y) {
02255
02256
02257
02258
02259 if (pSLL && y == pSLL->scanline) {
02260 loadAET(&AET, pSLL->edgelist);
02261 computeWAET(&AET);
02262 pSLL = pSLL->next;
02263 }
02264 pPrevAET = &AET;
02265 pAET = AET.next;
02266 pWETE = pAET;
02267
02268
02269
02270
02271 while (pAET) {
02272
02273
02274
02275
02276 if (pWETE == pAET) {
02277 pts->setX(pAET->bres.minor_axis);
02278 pts->setY(y);
02279 ++pts;
02280 ++iPts;
02281
02282
02283
02284
02285 if (iPts == NUMPTSTOBUFFER) {
02286 tmpPtBlock = static_cast<POINTBLOCK *>(malloc(sizeof(POINTBLOCK)));
02287 curPtBlock->next = tmpPtBlock;
02288 curPtBlock = tmpPtBlock;
02289 pts = curPtBlock->pts;
02290 ++numFullPtBlocks;
02291 iPts = 0;
02292 }
02293 pWETE = pWETE->nextWETE;
02294 }
02295 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
02296 }
02297
02298
02299
02300
02301
02302 if (InsertionSort(&AET) || fixWAET) {
02303 computeWAET(&AET);
02304 fixWAET = false;
02305 }
02306 }
02307 }
02308 FreeStorage(SLLBlock.next);
02309 PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
02310 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
02311 tmpPtBlock = curPtBlock->next;
02312 free(curPtBlock);
02313 curPtBlock = tmpPtBlock;
02314 }
02315 free(pETEs);
02316 return region;
02317 }
02318
02319
02320 QRegionPrivate *qt_bitmapToRegion(const QBitmap& bitmap)
02321 {
02322 QImage image = bitmap.toImage();
02323
02324 QRegionPrivate *region = new QRegionPrivate;
02325 QRect xr;
02326
02327 #define AddSpan \
02328 { \
02329 xr.setCoords(prev1, y, x-1, y); \
02330 UnionRectWithRegion(&xr, region, *region); \
02331 }
02332
02333 const uchar zero = 0;
02334 bool little = image.format() == QImage::Format_MonoLSB;
02335
02336 int x,
02337 y;
02338 for (y = 0; y < image.height(); ++y) {
02339 uchar *line = image.scanLine(y);
02340 int w = image.width();
02341 uchar all = zero;
02342 int prev1 = -1;
02343 for (x = 0; x < w;) {
02344 uchar byte = line[x / 8];
02345 if (x > w - 8 || byte!=all) {
02346 if (little) {
02347 for (int b = 8; b > 0 && x < w; --b) {
02348 if (!(byte & 0x01) == !all) {
02349
02350 } else {
02351
02352 if (all!=zero) {
02353 AddSpan
02354 all = zero;
02355 } else {
02356 prev1 = x;
02357 all = ~zero;
02358 }
02359 }
02360 byte >>= 1;
02361 ++x;
02362 }
02363 } else {
02364 for (int b = 8; b > 0 && x < w; --b) {
02365 if (!(byte & 0x80) == !all) {
02366
02367 } else {
02368
02369 if (all != zero) {
02370 AddSpan
02371 all = zero;
02372 } else {
02373 prev1 = x;
02374 all = ~zero;
02375 }
02376 }
02377 byte <<= 1;
02378 ++x;
02379 }
02380 }
02381 } else {
02382 x += 8;
02383 }
02384 }
02385 if (all != zero) {
02386 AddSpan
02387 }
02388 }
02389 #undef AddSpan
02390
02391 return region;
02392 }
02393
02400 QRegion::QRegion()
02401 : d(&shared_empty)
02402 {
02403 d->ref.ref();
02404 }
02405
02416 QRegion::QRegion(const QRect &r, RegionType t)
02417 {
02418 if (r.isEmpty()) {
02419 d = &shared_empty;
02420 d->ref.ref();
02421 } else {
02422 d = new QRegionData;
02423 d->ref.init(1);
02424 #if defined(Q_WS_X11)
02425 d->rgn = 0;
02426 d->xrectangles = 0;
02427 #elif defined(Q_WS_MAC)
02428 d->rgn = 0;
02429 #endif
02430 if (t == Rectangle) {
02431 d->qt_rgn = new QRegionPrivate(r);
02432 } else if (t == Ellipse) {
02433 QPainterPath path;
02434 path.addEllipse(r.x(), r.y(), r.width(), r.height());
02435 QPolygon a = path.toSubpathPolygons().at(0).toPolygon();
02436 d->qt_rgn = PolygonRegion(a.constData(), a.size(), EvenOddRule);
02437 }
02438 }
02439 }
02440
02453 QRegion::QRegion(const QPolygon &a, Qt::FillRule fillRule)
02454 {
02455 if (a.count() > 2) {
02456 d = new QRegionData;
02457 d->ref.init(1);
02458 #if defined(Q_WS_X11)
02459 d->rgn = 0;
02460 d->xrectangles = 0;
02461 #elif defined(Q_WS_MAC)
02462 d->rgn = 0;
02463 #endif
02464 d->qt_rgn = PolygonRegion(a.constData(), a.size(),
02465 fillRule == Qt::WindingFill ? WindingRule : EvenOddRule);
02466 } else {
02467 d = &shared_empty;
02468 d->ref.ref();
02469 }
02470 }
02471
02472
02477 QRegion::QRegion(const QRegion &r)
02478 {
02479 d = r.d;
02480 d->ref.ref();
02481 }
02482
02483
02494 QRegion::QRegion(const QBitmap &bm)
02495 {
02496 if (bm.isNull()) {
02497 d = &shared_empty;
02498 d->ref.ref();
02499 } else {
02500 d = new QRegionData;
02501 d->ref.init(1);
02502 #if defined(Q_WS_X11)
02503 d->rgn = 0;
02504 d->xrectangles = 0;
02505 #elif defined(Q_WS_MAC)
02506 d->rgn = 0;
02507 #endif
02508 d->qt_rgn = qt_bitmapToRegion(bm);
02509 }
02510 }
02511
02512 void QRegion::cleanUp(QRegion::QRegionData *x)
02513 {
02514 delete x->qt_rgn;
02515 #if defined(Q_WS_X11)
02516 if (x->rgn)
02517 XDestroyRegion(x->rgn);
02518 if (x->xrectangles)
02519 free(x->xrectangles);
02520 #elif defined(Q_WS_MAC)
02521 if (x->rgn)
02522 qt_mac_dispose_rgn(x->rgn);
02523 #endif
02524 delete x;
02525 }
02526
02531 QRegion::~QRegion()
02532 {
02533 if (!d->ref.deref())
02534 cleanUp(d);
02535 }
02536
02537
02542 QRegion &QRegion::operator=(const QRegion &r)
02543 {
02544 QRegionData *x = r.d;
02545 x->ref.ref();
02546 x = qAtomicSetPtr(&d, x);
02547 if (!x->ref.deref())
02548 cleanUp(x);
02549 return *this;
02550 }
02551
02552
02557 QRegion QRegion::copy() const
02558 {
02559 QRegion r;
02560 QRegionData *x = new QRegionData;
02561 x->ref.init(1);
02562 #if defined(Q_WS_X11)
02563 x->rgn = 0;
02564 x->xrectangles = 0;
02565 #elif defined(Q_WS_MAC)
02566 x->rgn = 0;
02567 #endif
02568 if (d->qt_rgn)
02569 x->qt_rgn = new QRegionPrivate(*d->qt_rgn);
02570 else
02571 x->qt_rgn = new QRegionPrivate;
02572 x = qAtomicSetPtr(&r.d, x);
02573 if (!x->ref.deref())
02574 cleanUp(x);
02575 return r;
02576 }
02577
02603 bool QRegion::isEmpty() const
02604 {
02605 return d == &shared_empty || d->qt_rgn->numRects == 0;
02606 }
02607
02608
02614 bool QRegion::contains(const QPoint &p) const
02615 {
02616 return PointInRegion(d->qt_rgn, p.x(), p.y());
02617 }
02618
02626 bool QRegion::contains(const QRect &r) const
02627 {
02628 return RectInRegion(d->qt_rgn, r.left(), r.top(), r.width(), r.height()) != RectangleOut;
02629 }
02630
02631
02632
02638 void QRegion::translate(int dx, int dy)
02639 {
02640 detach();
02641 OffsetRegion(*d->qt_rgn, dx, dy);
02642 #if defined(Q_WS_X11)
02643 if (d->xrectangles) {
02644 free(d->xrectangles);
02645 d->xrectangles = 0;
02646 }
02647 #elif defined(Q_WS_MAC)
02648 if(d->rgn) {
02649 qt_mac_dispose_rgn(d->rgn);
02650 d->rgn = 0;
02651 }
02652 #endif
02653 }
02654
02675 QRegion QRegion::unite(const QRegion &r) const
02676 {
02677 QRegion result;
02678 result.detach();
02679 UnionRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
02680 return result;
02681 }
02682
02683 #ifdef QT_EXPERIMENTAL_REGIONS
02684 QRegion& QRegion::operator+=(const QRegion &r)
02685 {
02686 if (isEmpty())
02687 return *this = r;
02688 if (r.isEmpty())
02689 return *this;
02690
02691 if (d->qt_rgn->canAppend(r.d->qt_rgn)) {
02692 detach();
02693 d->qt_rgn->append(r.d->qt_rgn);
02694 return *this;
02695 }
02696
02697 return *this = unite(r);
02698 }
02699 #endif
02700
02719 QRegion QRegion::intersect(const QRegion &r) const
02720 {
02721 QRegion result;
02722 if (::isEmpty(d->qt_rgn) || ::isEmpty(r.d->qt_rgn)
02723 || !EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents))
02724 return result;
02725
02726 #ifdef QT_EXPERIMENTAL_REGIONS
02727
02728 if (r.d->qt_rgn->contains(*d->qt_rgn))
02729 return *this;
02730
02731
02732 if (d->qt_rgn->contains(*r.d->qt_rgn))
02733 return r;
02734 #endif
02735
02736 result.detach();
02737 miRegionOp(*result.d->qt_rgn, d->qt_rgn, r.d->qt_rgn, miIntersectO, 0, 0);
02738
02739
02740
02741
02742
02743
02744
02745
02746 miSetExtents(*result.d->qt_rgn);
02747 return result;
02748 }
02749
02771 QRegion QRegion::subtract(const QRegion &r) const
02772 {
02773 QRegion result;
02774 result.detach();
02775 SubtractRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
02776 return result;
02777 }
02778
02800 QRegion QRegion::eor(const QRegion &r) const
02801 {
02802 QRegion result;
02803 result.detach();
02804 XorRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
02805 return result;
02806 }
02807
02813 QRect QRegion::boundingRect() const
02814 {
02815 if (isEmpty())
02816 return QRect();
02817 return d->qt_rgn->extents;
02818 }
02819
02820 #ifdef QT_EXPERIMENTAL_REGIONS
02821
02828 bool qt_region_strictContains(const QRegion ®ion, const QRect &rect)
02829 {
02830 if (region.isEmpty() || rect.isNull())
02831 return false;
02832
02833 #if 0 // TEST_INNERRECT
02834 static bool guard = false;
02835 if (guard)
02836 return QRect();
02837 guard = true;
02838 QRegion inner = region.d->qt_rgn->innerRect;
02839 Q_ASSERT((inner - region).isEmpty());
02840 guard = false;
02841
02842 int maxArea = 0;
02843 for (int i = 0; i < region.d->qt_rgn->numRects; ++i) {
02844 const QRect r = region.d->qt_rgn->rects.at(i);
02845 if (r.width() * r.height() > maxArea)
02846 maxArea = r.width() * r.height();
02847 }
02848
02849 if (maxArea > region.d->qt_rgn->innerArea) {
02850 qDebug() << "not largest rectangle" << region << region.d->qt_rgn->innerRect;
02851 }
02852 Q_ASSERT(maxArea <= region.d->qt_rgn->innerArea);
02853 #endif
02854
02855 const QRect r1 = region.d->qt_rgn->innerRect;
02856 const QRect r2 = rect.normalized();
02857 return (r2.left() >= r1.left() && r2.right() <= r1.right()
02858 && r2.top() >= r1.top() && r2.bottom() <= r1.bottom());
02859 }
02860 #endif // QT_EXPERIMENTAL_REGIONS
02861
02868 QVector<QRect> QRegion::rects() const
02869 {
02870 if (d->qt_rgn) {
02871 d->qt_rgn->rects.resize(d->qt_rgn->numRects);
02872 return d->qt_rgn->rects;
02873 } else {
02874 return QVector<QRect>();
02875 }
02876 }
02877
02897 void QRegion::setRects(const QRect *rects, int num)
02898 {
02899 *this = QRegion();
02900 detach();
02901 if (!rects || (num == 1 && rects->isEmpty()))
02902 num = 0;
02903
02904 d->qt_rgn->rects.resize(num);
02905 d->qt_rgn->numRects = num;
02906 if (num == 0) {
02907 d->qt_rgn->extents = QRect();
02908 } else {
02909 int left = INT_MAX,
02910 right = INT_MIN,
02911 top = INT_MAX,
02912 bottom = INT_MIN;
02913 for (int i = 0; i < num; ++i) {
02914 const QRect &rect = rects[i];
02915 d->qt_rgn->rects[i] = rect;
02916 left = qMin(rect.left(), left);
02917 right = qMax(rect.right(), right);
02918 top = qMin(rect.top(), top);
02919 bottom = qMax(rect.bottom(), bottom);
02920 #ifdef QT_EXPERIMENTAL_REGIONS
02921 d->qt_rgn->updateInnerRect(rect);
02922 #endif
02923 }
02924 d->qt_rgn->extents = QRect(QPoint(left, top), QPoint(right, bottom));
02925 }
02926 }
02927
02933 bool QRegion::operator==(const QRegion &r) const
02934 {
02935 if (!d->qt_rgn || !r.d->qt_rgn)
02936 return r.d->qt_rgn == d->qt_rgn;
02937
02938 if (d == r.d)
02939 return true;
02940 else
02941 return EqualRegion(d->qt_rgn, r.d->qt_rgn);
02942 }