1
/***********************************************************
3
Copyright 1987, 1988, 1989, 1998 The Open Group
5
Permission to use, copy, modify, distribute, and sell this software and its
6
documentation for any purpose is hereby granted without fee, provided that
7
the above copyright notice appear in all copies and that both that
8
copyright notice and this permission notice appear in supporting
11
The above copyright notice and this permission notice shall be included in
12
all copies or substantial portions of the Software.
14
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17
OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21
Except as contained in this notice, the name of The Open Group shall not be
22
used in advertising or otherwise to promote the sale, use or other dealings
23
in this Software without prior written authorization from The Open Group.
26
Copyright 1987, 1988, 1989 by
27
Digital Equipment Corporation, Maynard, Massachusetts.
31
Permission to use, copy, modify, and distribute this software and its
32
documentation for any purpose and without fee is hereby granted,
33
provided that the above copyright notice appear in all copies and that
34
both that copyright notice and this permission notice appear in
35
supporting documentation, and that the name of Digital not be
36
used in advertising or publicity pertaining to distribution of the
37
software without specific, written prior permission.
39
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
40
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
41
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
42
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
43
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
44
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
47
******************************************************************/
49
/* The panoramix components contained the following notice */
50
/*****************************************************************
52
Copyright (c) 1991, 1997 Digital Equipment Corporation, Maynard, Massachusetts.
54
Permission is hereby granted, free of charge, to any person obtaining a copy
55
of this software and associated documentation files (the "Software"), to deal
56
in the Software without restriction, including without limitation the rights
57
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
58
copies of the Software.
60
The above copyright notice and this permission notice shall be included in
61
all copies or substantial portions of the Software.
63
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
64
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
65
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
66
DIGITAL EQUIPMENT CORPORATION BE LIABLE FOR ANY CLAIM, DAMAGES, INCLUDING,
67
BUT NOT LIMITED TO CONSEQUENTIAL OR INCIDENTAL DAMAGES, OR OTHER LIABILITY,
68
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
69
IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
71
Except as contained in this notice, the name of Digital Equipment Corporation
72
shall not be used in advertising or otherwise to promote the sale, use or other
73
dealings in this Software without prior written authorization from Digital
74
Equipment Corporation.
76
******************************************************************/
78
#ifdef HAVE_DIX_CONFIG_H
79
#include <dix-config.h>
82
#include "regionstr.h"
83
#include <X11/Xprotostr.h>
84
#include <X11/Xfuncproto.h>
92
#define assert(expr) { \
95
ErrorF("Assertion failed file %s, line %d: %s\n", \
96
__FILE__, __LINE__, #expr); \
97
*foo = 0xdeadbeef; /* to get a backtrace */ \
104
#define good(reg) assert(miValidRegion(reg))
107
* The functions in this file implement the Region abstraction used extensively
108
* throughout the X11 sample server. A Region is simply a set of disjoint
109
* (non-overlapping) rectangles, plus an "extent" rectangle which is the
110
* smallest single rectangle that contains all the non-overlapping rectangles.
112
* A Region is implemented as a "y-x-banded" array of rectangles. This array
113
* imposes two degrees of order. First, all rectangles are sorted by top side
114
* y coordinate first (y1), and then by left side x coordinate (x1).
116
* Furthermore, the rectangles are grouped into "bands". Each rectangle in a
117
* band has the same top y coordinate (y1), and each has the same bottom y
118
* coordinate (y2). Thus all rectangles in a band differ only in their left
119
* and right side (x1 and x2). Bands are implicit in the array of rectangles:
120
* there is no separate list of band start pointers.
122
* The y-x band representation does not minimize rectangles. In particular,
123
* if a rectangle vertically crosses a band (the rectangle has scanlines in
124
* the y1 to y2 area spanned by the band), then the rectangle may be broken
125
* down into two or more smaller rectangles stacked one atop the other.
127
* ----------- -----------
129
* | | -------- ----------- --------
130
* | | | | in y-x banded | | | | band 1
131
* | | | | form is | | | |
132
* ----------- | | ----------- --------
136
* An added constraint on the rectangles is that they must cover as much
137
* horizontal area as possible: no two rectangles within a band are allowed
140
* Whenever possible, bands will be merged together to cover a greater vertical
141
* distance (and thus reduce the number of rectangles). Two bands can be merged
142
* only if the bottom of one touches the top of the other and they have
143
* rectangles in the same places (of the same width, of course).
145
* Adam de Boor wrote most of the original region code. Joel McCormack
146
* substantially modified or rewrote most of the core arithmetic routines,
147
* and added miRegionValidate in order to support several speed improvements
148
* to miValidateTree. Bob Scheifler changed the representation to be more
149
* compact when empty or a single rectangle, and did a bunch of gratuitous
153
/* true iff two Boxes overlap */
154
#define EXTENTCHECK(r1,r2) \
155
(!( ((r1)->x2 <= (r2)->x1) || \
156
((r1)->x1 >= (r2)->x2) || \
157
((r1)->y2 <= (r2)->y1) || \
158
((r1)->y1 >= (r2)->y2) ) )
160
/* true iff (x,y) is in Box */
161
#define INBOX(r,x,y) \
167
/* true iff Box r1 contains Box r2 */
168
#define SUBSUMES(r1,r2) \
169
( ((r1)->x1 <= (r2)->x1) && \
170
((r1)->x2 >= (r2)->x2) && \
171
((r1)->y1 <= (r2)->y1) && \
172
((r1)->y2 >= (r2)->y2) )
174
#define xallocData(n) xalloc(REGION_SZOF(n))
175
#define xfreeData(reg) if ((reg)->data && (reg)->data->size) xfree((reg)->data)
177
#define RECTALLOC_BAIL(pReg,n,bail) \
178
if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
179
if (!miRectAlloc(pReg, n)) { goto bail; }
181
#define RECTALLOC(pReg,n) \
182
if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
183
if (!miRectAlloc(pReg, n)) { return FALSE; }
185
#define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \
187
pNextRect->x1 = nx1; \
188
pNextRect->y1 = ny1; \
189
pNextRect->x2 = nx2; \
190
pNextRect->y2 = ny2; \
194
#define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \
196
if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
198
if (!miRectAlloc(pReg, 1)) \
200
pNextRect = REGION_TOP(pReg); \
202
ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \
203
pReg->data->numRects++; \
204
assert(pReg->data->numRects<=pReg->data->size); \
208
#define DOWNSIZE(reg,numRects) \
209
if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
211
RegDataPtr NewData; \
212
NewData = (RegDataPtr)xrealloc((reg)->data, REGION_SZOF(numRects)); \
215
NewData->size = (numRects); \
216
(reg)->data = NewData; \
221
BoxRec miEmptyBox = {0, 0, 0, 0};
222
RegDataRec miEmptyData = {0, 0};
224
RegDataRec miBrokenData = {0, 0};
225
static RegionRec miBrokenRegion = { { 0, 0, 0, 0 }, &miBrokenData };
230
pixman_region_set_static_pointers (&miEmptyBox, &miEmptyData, &miBrokenData);
233
/*****************************************************************
234
* RegionCreate(rect, size)
235
* This routine does a simple malloc to make a structure of
236
* REGION of "size" number of rectangles.
237
*****************************************************************/
240
miRegionCreate(BoxPtr rect, int size)
244
pReg = (RegionPtr)xalloc(sizeof(RegionRec));
246
return &miBrokenRegion;
248
miRegionInit (pReg, rect, size);
254
miRegionDestroy(RegionPtr pReg)
256
pixman_region_fini (pReg);
257
if (pReg != &miBrokenRegion)
262
miPrintRegion(RegionPtr rgn)
268
num = REGION_NUM_RECTS(rgn);
269
size = REGION_SIZE(rgn);
270
rects = REGION_RECTS(rgn);
271
ErrorF("[mi] num: %d size: %d\n", num, size);
272
ErrorF("[mi] extents: %d %d %d %d\n",
273
rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
274
for (i = 0; i < num; i++)
275
ErrorF("[mi] %d %d %d %d \n",
276
rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
281
miRegionEqual(RegionPtr reg1, RegionPtr reg2)
283
return pixman_region_equal (reg1, reg2);
288
miValidRegion(RegionPtr reg)
292
if ((reg->extents.x1 > reg->extents.x2) ||
293
(reg->extents.y1 > reg->extents.y2))
295
numRects = REGION_NUM_RECTS(reg);
297
return ((reg->extents.x1 == reg->extents.x2) &&
298
(reg->extents.y1 == reg->extents.y2) &&
299
(reg->data->size || (reg->data == &miEmptyData)));
300
else if (numRects == 1)
307
pboxP = REGION_RECTS(reg);
309
box.y2 = pboxP[numRects-1].y2;
311
for (i = numRects; --i > 0; pboxP++, pboxN++)
313
if ((pboxN->x1 >= pboxN->x2) ||
314
(pboxN->y1 >= pboxN->y2))
316
if (pboxN->x1 < box.x1)
318
if (pboxN->x2 > box.x2)
320
if ((pboxN->y1 < pboxP->y1) ||
321
((pboxN->y1 == pboxP->y1) &&
322
((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2))))
325
return ((box.x1 == reg->extents.x1) &&
326
(box.x2 == reg->extents.x2) &&
327
(box.y1 == reg->extents.y1) &&
328
(box.y2 == reg->extents.y2));
333
/*****************************************************************
334
* RegionInit(pReg, rect, size)
335
* Outer region rect is statically allocated.
336
*****************************************************************/
339
miRegionInit(RegionPtr pReg, BoxPtr rect, int size)
342
pixman_region_init_with_extents (pReg, rect);
344
pixman_region_init (pReg);
348
miRegionUninit(RegionPtr pReg)
350
pixman_region_fini (pReg);
354
miRegionBreak (RegionPtr pReg)
357
pReg->extents = miEmptyBox;
358
pReg->data = &miBrokenData;
363
miRectAlloc(RegionPtr pRgn, int n)
370
pRgn->data = xallocData(n);
372
return miRegionBreak (pRgn);
373
pRgn->data->numRects = 1;
374
*REGION_BOXPTR(pRgn) = pRgn->extents;
376
else if (!pRgn->data->size)
378
pRgn->data = xallocData(n);
380
return miRegionBreak (pRgn);
381
pRgn->data->numRects = 0;
387
n = pRgn->data->numRects;
388
if (n > 500) /* XXX pick numbers out of a hat */
391
n += pRgn->data->numRects;
392
data = (RegDataPtr)xrealloc(pRgn->data, REGION_SZOF(n));
394
return miRegionBreak (pRgn);
397
pRgn->data->size = n;
402
miRegionCopy(RegionPtr dst, RegionPtr src)
404
return pixman_region_copy (dst, src);
407
/*======================================================================
408
* Generic Region Operator
409
*====================================================================*/
412
*-----------------------------------------------------------------------
414
* Attempt to merge the boxes in the current band with those in the
415
* previous one. We are guaranteed that the current band extends to
416
* the end of the rects array. Used only by miRegionOp.
419
* The new index for the previous band.
422
* If coalescing takes place:
423
* - rectangles in the previous band will have their y2 fields
425
* - pReg->data->numRects will be decreased.
427
*-----------------------------------------------------------------------
431
RegionPtr pReg, /* Region to coalesce */
432
int prevStart, /* Index of start of previous band */
433
int curStart) /* Index of start of current band */
435
BoxPtr pPrevBox; /* Current box in previous band */
436
BoxPtr pCurBox; /* Current box in current band */
437
int numRects; /* Number rectangles in both bands */
438
int y2; /* Bottom of current band */
440
* Figure out how many rectangles are in the band.
442
numRects = curStart - prevStart;
443
assert(numRects == pReg->data->numRects - curStart);
445
if (!numRects) return curStart;
448
* The bands may only be coalesced if the bottom of the previous
449
* matches the top scanline of the current.
451
pPrevBox = REGION_BOX(pReg, prevStart);
452
pCurBox = REGION_BOX(pReg, curStart);
453
if (pPrevBox->y2 != pCurBox->y1) return curStart;
456
* Make sure the bands have boxes in the same places. This
457
* assumes that boxes have been added in such a way that they
458
* cover the most area possible. I.e. two boxes in a band must
459
* have some horizontal space between them.
464
if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) {
473
* The bands may be merged, so set the bottom y of each box
474
* in the previous band to the bottom y of the current band.
476
numRects = curStart - prevStart;
477
pReg->data->numRects -= numRects;
487
/* Quicky macro to avoid trivial reject procedure calls to miCoalesce */
489
#define Coalesce(newReg, prevBand, curBand) \
490
if (curBand - prevBand == newReg->data->numRects - curBand) { \
491
prevBand = miCoalesce(newReg, prevBand, curBand); \
493
prevBand = curBand; \
497
*-----------------------------------------------------------------------
499
* Handle a non-overlapping band for the union and subtract operations.
500
* Just adds the (top/bottom-clipped) rectangles into the region.
501
* Doesn't have to check for subsumption or anything.
507
* pReg->data->numRects is incremented and the rectangles overwritten
508
* with the rectangles we're passed.
510
*-----------------------------------------------------------------------
513
_X_INLINE static Bool
527
assert(newRects != 0);
529
/* Make sure we have enough space for all rectangles to be added */
530
RECTALLOC(pReg, newRects);
531
pNextRect = REGION_TOP(pReg);
532
pReg->data->numRects += newRects;
534
assert(r->x1 < r->x2);
535
ADDRECT(pNextRect, r->x1, y1, r->x2, y2);
542
#define FindBand(r, rBandEnd, rEnd, ry1) \
546
while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \
551
#define AppendRegions(newReg, r, rEnd) \
554
if ((newRects = rEnd - r)) { \
555
RECTALLOC(newReg, newRects); \
556
memmove((char *)REGION_TOP(newReg),(char *)r, \
557
newRects * sizeof(BoxRec)); \
558
newReg->data->numRects += newRects; \
563
*-----------------------------------------------------------------------
565
* Apply an operation to two regions. Called by miUnion, miInverse,
566
* miSubtract, miIntersect.... Both regions MUST have at least one
567
* rectangle, and cannot be the same object.
570
* TRUE if successful.
573
* The new region is overwritten.
574
* pOverlap set to TRUE if overlapFunc ever returns TRUE.
577
* The idea behind this function is to view the two regions as sets.
578
* Together they cover a rectangle of area that this function divides
579
* into horizontal bands where points are covered only by one region
580
* or by both. For the first case, the nonOverlapFunc is called with
581
* each the band and the band's upper and lower extents. For the
582
* second, the overlapFunc is called to process the entire band. It
583
* is responsible for clipping the rectangles in the band, though
584
* this function provides the boundaries.
585
* At the end of each band, the new region is coalesced, if possible,
586
* to reduce the number of rectangles in the region.
588
*-----------------------------------------------------------------------
591
typedef Bool (*OverlapProcPtr)(
603
RegionPtr newReg, /* Place to store result */
604
RegionPtr reg1, /* First region in operation */
605
RegionPtr reg2, /* 2d region in operation */
606
OverlapProcPtr overlapFunc, /* Function to call for over-
608
Bool appendNon1, /* Append non-overlapping bands */
610
Bool appendNon2, /* Append non-overlapping bands */
614
BoxPtr r1; /* Pointer into first region */
615
BoxPtr r2; /* Pointer into 2d region */
616
BoxPtr r1End; /* End of 1st region */
617
BoxPtr r2End; /* End of 2d region */
618
short ybot; /* Bottom of intersection */
619
short ytop; /* Top of intersection */
620
RegDataPtr oldData; /* Old data for newReg */
621
int prevBand; /* Index of start of
622
* previous band in newReg */
623
int curBand; /* Index of start of current
625
BoxPtr r1BandEnd; /* End of current band in r1 */
626
BoxPtr r2BandEnd; /* End of current band in r2 */
627
short top; /* Top of non-overlapping band */
628
short bot; /* Bottom of non-overlapping band*/
629
int r1y1; /* Temps for r1->y1 and r2->y1 */
635
* Break any region computed from a broken region
637
if (REGION_NAR (reg1) || REGION_NAR(reg2))
638
return miRegionBreak (newReg);
642
* set r1, r2, r1End and r2End appropriately, save the rectangles
643
* of the destination region until the end in case it's one of
644
* the two source regions, then mark the "new" region empty, allocating
645
* another array of rectangles for it to use.
648
r1 = REGION_RECTS(reg1);
649
newSize = REGION_NUM_RECTS(reg1);
650
r1End = r1 + newSize;
651
numRects = REGION_NUM_RECTS(reg2);
652
r2 = REGION_RECTS(reg2);
653
r2End = r2 + numRects;
658
if (((newReg == reg1) && (newSize > 1)) ||
659
((newReg == reg2) && (numRects > 1)))
661
oldData = newReg->data;
662
newReg->data = &miEmptyData;
664
/* guess at new size */
665
if (numRects > newSize)
669
newReg->data = &miEmptyData;
670
else if (newReg->data->size)
671
newReg->data->numRects = 0;
672
if (newSize > newReg->data->size)
673
if (!miRectAlloc(newReg, newSize))
678
* In the upcoming loop, ybot and ytop serve different functions depending
679
* on whether the band being handled is an overlapping or non-overlapping
681
* In the case of a non-overlapping band (only one of the regions
682
* has points in the band), ybot is the bottom of the most recent
683
* intersection and thus clips the top of the rectangles in that band.
684
* ytop is the top of the next intersection between the two regions and
685
* serves to clip the bottom of the rectangles in the current band.
686
* For an overlapping band (where the two regions intersect), ytop clips
687
* the top of the rectangles of both regions and ybot clips the bottoms.
690
ybot = min(r1->y1, r2->y1);
693
* prevBand serves to mark the start of the previous band so rectangles
694
* can be coalesced into larger rectangles. qv. miCoalesce, above.
695
* In the beginning, there is no previous band, so prevBand == curBand
696
* (curBand is set later on, of course, but the first band will always
697
* start at index 0). prevBand and curBand must be indices because of
698
* the possible expansion, and resultant moving, of the new region's
699
* array of rectangles.
705
* This algorithm proceeds one source-band (as opposed to a
706
* destination band, which is determined by where the two regions
707
* intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
708
* rectangle after the last one in the current band for their
709
* respective regions.
714
FindBand(r1, r1BandEnd, r1End, r1y1);
715
FindBand(r2, r2BandEnd, r2End, r2y1);
718
* First handle the band that doesn't intersect, if any.
720
* Note that attention is restricted to one band in the
721
* non-intersecting region at once, so if a region has n
722
* bands between the current position and the next place it overlaps
723
* the other, this entire loop will be passed through n times.
727
top = max(r1y1, ybot);
728
bot = min(r1->y2, r2y1);
730
curBand = newReg->data->numRects;
731
miAppendNonO(newReg, r1, r1BandEnd, top, bot);
732
Coalesce(newReg, prevBand, curBand);
736
} else if (r2y1 < r1y1) {
738
top = max(r2y1, ybot);
739
bot = min(r2->y2, r1y1);
741
curBand = newReg->data->numRects;
742
miAppendNonO(newReg, r2, r2BandEnd, top, bot);
743
Coalesce(newReg, prevBand, curBand);
752
* Now see if we've hit an intersecting band. The two bands only
753
* intersect if ybot > ytop
755
ybot = min(r1->y2, r2->y2);
757
curBand = newReg->data->numRects;
758
(* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot,
760
Coalesce(newReg, prevBand, curBand);
764
* If we've finished with a band (y2 == ybot) we skip forward
765
* in the region to the next band.
767
if (r1->y2 == ybot) r1 = r1BandEnd;
768
if (r2->y2 == ybot) r2 = r2BandEnd;
770
} while (r1 != r1End && r2 != r2End);
773
* Deal with whichever region (if any) still has rectangles left.
775
* We only need to worry about banding and coalescing for the very first
776
* band left. After that, we can just group all remaining boxes,
777
* regardless of how many bands, into one final append to the list.
780
if ((r1 != r1End) && appendNon1) {
781
/* Do first nonOverlap1Func call, which may be able to coalesce */
782
FindBand(r1, r1BandEnd, r1End, r1y1);
783
curBand = newReg->data->numRects;
784
miAppendNonO(newReg, r1, r1BandEnd, max(r1y1, ybot), r1->y2);
785
Coalesce(newReg, prevBand, curBand);
786
/* Just append the rest of the boxes */
787
AppendRegions(newReg, r1BandEnd, r1End);
789
} else if ((r2 != r2End) && appendNon2) {
790
/* Do first nonOverlap2Func call, which may be able to coalesce */
791
FindBand(r2, r2BandEnd, r2End, r2y1);
792
curBand = newReg->data->numRects;
793
miAppendNonO(newReg, r2, r2BandEnd, max(r2y1, ybot), r2->y2);
794
Coalesce(newReg, prevBand, curBand);
795
/* Append rest of boxes */
796
AppendRegions(newReg, r2BandEnd, r2End);
802
if (!(numRects = newReg->data->numRects))
805
newReg->data = &miEmptyData;
807
else if (numRects == 1)
809
newReg->extents = *REGION_BOXPTR(newReg);
815
DOWNSIZE(newReg, numRects);
822
*-----------------------------------------------------------------------
824
* Reset the extents of a region to what they should be. Called by
825
* miSubtract and miIntersect as they can't figure it out along the
826
* way or do so easily, as miUnion can.
832
* The region's 'extents' structure is overwritten.
834
*-----------------------------------------------------------------------
837
miSetExtents (RegionPtr pReg)
839
BoxPtr pBox, pBoxEnd;
843
if (!pReg->data->size)
845
pReg->extents.x2 = pReg->extents.x1;
846
pReg->extents.y2 = pReg->extents.y1;
850
pBox = REGION_BOXPTR(pReg);
851
pBoxEnd = REGION_END(pReg);
854
* Since pBox is the first rectangle in the region, it must have the
855
* smallest y1 and since pBoxEnd is the last rectangle in the region,
856
* it must have the largest y2, because of banding. Initialize x1 and
857
* x2 from pBox and pBoxEnd, resp., as good things to initialize them
860
pReg->extents.x1 = pBox->x1;
861
pReg->extents.y1 = pBox->y1;
862
pReg->extents.x2 = pBoxEnd->x2;
863
pReg->extents.y2 = pBoxEnd->y2;
865
assert(pReg->extents.y1 < pReg->extents.y2);
866
while (pBox <= pBoxEnd) {
867
if (pBox->x1 < pReg->extents.x1)
868
pReg->extents.x1 = pBox->x1;
869
if (pBox->x2 > pReg->extents.x2)
870
pReg->extents.x2 = pBox->x2;
874
assert(pReg->extents.x1 < pReg->extents.x2);
877
/*======================================================================
878
* Region Intersection
879
*====================================================================*/
881
*-----------------------------------------------------------------------
883
* Handle an overlapping band for miIntersect.
886
* TRUE if successful.
889
* Rectangles may be added to the region.
891
*-----------------------------------------------------------------------
896
RegionPtr newReg, /* destination Region */
898
RegionPtr reg2 /* source regions */
901
return pixman_region_intersect (newReg, reg1, reg2);
904
#define MERGERECT(r) \
907
/* Merge with current rectangle */ \
908
if (r->x1 < x2) *pOverlap = TRUE; \
909
if (x2 < r->x2) x2 = r->x2; \
911
/* Add current rectangle, start new one */ \
912
NEWRECT(pReg, pNextRect, x1, y1, x2, y2); \
919
/*======================================================================
921
*====================================================================*/
924
*-----------------------------------------------------------------------
926
* Handle an overlapping band for the union operation. Picks the
927
* left-most rectangle each time and merges it into the region.
930
* TRUE if successful.
933
* pReg is overwritten.
934
* pOverlap is set to TRUE if any boxes overlap.
936
*-----------------------------------------------------------------------
950
int x1; /* left and right side of current union */
954
assert(r1 != r1End && r2 != r2End);
956
pNextRect = REGION_TOP(pReg);
958
/* Start off current rectangle */
971
while (r1 != r1End && r2 != r2End)
973
if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
976
/* Finish off whoever (if any) is left */
982
} while (r1 != r1End);
984
else if (r2 != r2End)
989
} while (r2 != r2End);
992
/* Add current rectangle */
993
NEWRECT(pReg, pNextRect, x1, y1, x2, y2);
1000
RegionPtr newReg, /* destination Region */
1002
RegionPtr reg2 /* source regions */
1005
return pixman_region_union (newReg, reg1, reg2);
1008
/*======================================================================
1009
* Batch Rectangle Union
1010
*====================================================================*/
1013
*-----------------------------------------------------------------------
1016
* "Append" the rgn rectangles onto the end of dstrgn, maintaining
1017
* knowledge of YX-banding when it's easy. Otherwise, dstrgn just
1018
* becomes a non-y-x-banded random collection of rectangles, and not
1019
* yet a true region. After a sequence of appends, the caller must
1020
* call miRegionValidate to ensure that a valid region is constructed.
1023
* TRUE if successful.
1026
* dstrgn is modified if rgn has rectangles.
1030
miRegionAppend(RegionPtr dstrgn, RegionPtr rgn)
1032
int numRects, dnumRects, size;
1036
if (REGION_NAR(rgn))
1037
return miRegionBreak (dstrgn);
1039
if (!rgn->data && (dstrgn->data == &miEmptyData))
1041
dstrgn->extents = rgn->extents;
1042
dstrgn->data = NULL;
1046
numRects = REGION_NUM_RECTS(rgn);
1051
dnumRects = REGION_NUM_RECTS(dstrgn);
1052
if (!dnumRects && (size < 200))
1053
size = 200; /* XXX pick numbers out of a hat */
1054
RECTALLOC(dstrgn, size);
1055
old = REGION_RECTS(rgn);
1057
dstrgn->extents = rgn->extents;
1058
else if (dstrgn->extents.x2 > dstrgn->extents.x1)
1063
last = REGION_BOXPTR(dstrgn) + (dnumRects - 1);
1064
if ((first->y1 > last->y2) ||
1065
((first->y1 == last->y1) && (first->y2 == last->y2) &&
1066
(first->x1 > last->x2)))
1068
if (rgn->extents.x1 < dstrgn->extents.x1)
1069
dstrgn->extents.x1 = rgn->extents.x1;
1070
if (rgn->extents.x2 > dstrgn->extents.x2)
1071
dstrgn->extents.x2 = rgn->extents.x2;
1072
dstrgn->extents.y2 = rgn->extents.y2;
1076
first = REGION_BOXPTR(dstrgn);
1077
last = old + (numRects - 1);
1078
if ((first->y1 > last->y2) ||
1079
((first->y1 == last->y1) && (first->y2 == last->y2) &&
1080
(first->x1 > last->x2)))
1083
if (rgn->extents.x1 < dstrgn->extents.x1)
1084
dstrgn->extents.x1 = rgn->extents.x1;
1085
if (rgn->extents.x2 > dstrgn->extents.x2)
1086
dstrgn->extents.x2 = rgn->extents.x2;
1087
dstrgn->extents.y1 = rgn->extents.y1;
1090
dstrgn->extents.x2 = dstrgn->extents.x1;
1095
new = REGION_BOX(dstrgn, numRects);
1097
*new = *REGION_BOXPTR(dstrgn);
1099
memmove((char *)new,(char *)REGION_BOXPTR(dstrgn),
1100
dnumRects * sizeof(BoxRec));
1101
new = REGION_BOXPTR(dstrgn);
1104
new = REGION_BOXPTR(dstrgn) + dnumRects;
1108
memmove((char *)new, (char *)old, numRects * sizeof(BoxRec));
1109
dstrgn->data->numRects += numRects;
1114
#define ExchangeRects(a, b) \
1118
rects[a] = rects[b]; \
1132
/* Always called with numRects > 1 */
1138
if (rects[0].y1 > rects[1].y1 ||
1139
(rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
1140
ExchangeRects(0, 1);
1144
/* Choose partition element, stick in location 0 */
1145
ExchangeRects(0, numRects >> 1);
1149
/* Partition array */
1159
} while (i != numRects &&
1160
(r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
1166
} while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
1168
ExchangeRects(i, j);
1171
/* Move partition element back to middle */
1172
ExchangeRects(0, j);
1175
if (numRects-j-1 > 1)
1176
QuickSortRects(&rects[j+1], numRects-j-1);
1178
} while (numRects > 1);
1182
*-----------------------------------------------------------------------
1183
* miRegionValidate --
1185
* Take a ``region'' which is a non-y-x-banded random collection of
1186
* rectangles, and compute a nice region which is the union of all the
1190
* TRUE if successful.
1193
* The passed-in ``region'' may be modified.
1194
* pOverlap set to TRUE if any retangles overlapped, else FALSE;
1197
* Step 1. Sort the rectangles into ascending order with primary key y1
1198
* and secondary key x1.
1200
* Step 2. Split the rectangles into the minimum number of proper y-x
1201
* banded regions. This may require horizontally merging
1202
* rectangles, and vertically coalescing bands. With any luck,
1203
* this step in an identity tranformation (ala the Box widget),
1204
* or a coalescing into 1 box (ala Menus).
1206
* Step 3. Merge the separate regions down to a single region by calling
1207
* miUnion. Maximize the work each miUnion call does by using
1210
*-----------------------------------------------------------------------
1214
miRegionValidate(RegionPtr badreg, Bool *pOverlap)
1216
/* Descriptor for regions under construction in Step 2. */
1223
int numRects; /* Original numRects for badreg */
1224
RegionInfo *ri; /* Array of current regions */
1225
int numRI; /* Number of entries used in ri */
1226
int sizeRI; /* Number of entries available in ri */
1227
int i; /* Index into rects */
1228
int j; /* Index into ri */
1229
RegionInfo *rit; /* &ri[j] */
1230
RegionPtr reg; /* ri[j].reg */
1231
BoxPtr box; /* Current box in rects */
1232
BoxPtr riBox; /* Last box in ri[j].reg */
1233
RegionPtr hreg; /* ri[j_half].reg */
1242
numRects = badreg->data->numRects;
1245
if (REGION_NAR(badreg))
1250
if (badreg->extents.x1 < badreg->extents.x2)
1252
if ((numRects) == 1)
1255
badreg->data = (RegDataPtr) NULL;
1259
DOWNSIZE(badreg, numRects);
1265
/* Step 1: Sort the rects array into ascending (y1, x1) order */
1266
QuickSortRects(REGION_BOXPTR(badreg), numRects);
1268
/* Step 2: Scatter the sorted array into the minimum number of regions */
1270
/* Set up the first region to be the first rectangle in badreg */
1271
/* Note that step 2 code will never overflow the ri[0].reg rects array */
1272
ri = (RegionInfo *) xalloc(4 * sizeof(RegionInfo));
1274
return miRegionBreak (badreg);
1279
ri[0].reg = *badreg;
1280
box = REGION_BOXPTR(&ri[0].reg);
1281
ri[0].reg.extents = *box;
1282
ri[0].reg.data->numRects = 1;
1284
/* Now scatter rectangles into the minimum set of valid regions. If the
1285
next rectangle to be added to a region would force an existing rectangle
1286
in the region to be split up in order to maintain y-x banding, just
1287
forget it. Try the next region. If it doesn't fit cleanly into any
1288
region, make a new one. */
1290
for (i = numRects; --i > 0;)
1293
/* Look for a region to append box to */
1294
for (j = numRI, rit = ri; --j >= 0; rit++)
1297
riBox = REGION_END(reg);
1299
if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
1301
/* box is in same band as riBox. Merge or append it */
1302
if (box->x1 <= riBox->x2)
1304
/* Merge it with riBox */
1305
if (box->x1 < riBox->x2) *pOverlap = TRUE;
1306
if (box->x2 > riBox->x2) riBox->x2 = box->x2;
1310
RECTALLOC_BAIL(reg, 1, bail);
1311
*REGION_TOP(reg) = *box;
1312
reg->data->numRects++;
1314
goto NextRect; /* So sue me */
1316
else if (box->y1 >= riBox->y2)
1318
/* Put box into new band */
1319
if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1320
if (reg->extents.x1 > box->x1) reg->extents.x1 = box->x1;
1321
Coalesce(reg, rit->prevBand, rit->curBand);
1322
rit->curBand = reg->data->numRects;
1323
RECTALLOC_BAIL(reg, 1, bail);
1324
*REGION_TOP(reg) = *box;
1325
reg->data->numRects++;
1328
/* Well, this region was inappropriate. Try the next one. */
1331
/* Uh-oh. No regions were appropriate. Create a new one. */
1332
if (sizeRI == numRI)
1334
/* Oops, allocate space for new region information */
1336
rit = (RegionInfo *) xrealloc(ri, sizeRI * sizeof(RegionInfo));
1345
rit->reg.extents = *box;
1346
rit->reg.data = NULL;
1347
if (!miRectAlloc(&rit->reg, (i+numRI) / numRI)) /* MUST force allocation */
1352
/* Make a final pass over each region in order to Coalesce and set
1353
extents.x2 and extents.y2 */
1355
for (j = numRI, rit = ri; --j >= 0; rit++)
1358
riBox = REGION_END(reg);
1359
reg->extents.y2 = riBox->y2;
1360
if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1361
Coalesce(reg, rit->prevBand, rit->curBand);
1362
if (reg->data->numRects == 1) /* keep unions happy below */
1369
/* Step 3: Union all regions into a single region */
1373
for (j = numRI & 1; j < (half + (numRI & 1)); j++)
1376
hreg = &ri[j+half].reg;
1377
if (!miRegionOp(reg, reg, hreg, miUnionO, TRUE, TRUE, pOverlap))
1379
if (hreg->extents.x1 < reg->extents.x1)
1380
reg->extents.x1 = hreg->extents.x1;
1381
if (hreg->extents.y1 < reg->extents.y1)
1382
reg->extents.y1 = hreg->extents.y1;
1383
if (hreg->extents.x2 > reg->extents.x2)
1384
reg->extents.x2 = hreg->extents.x2;
1385
if (hreg->extents.y2 > reg->extents.y2)
1386
reg->extents.y2 = hreg->extents.y2;
1391
*badreg = ri[0].reg;
1396
for (i = 0; i < numRI; i++)
1397
xfreeData(&ri[i].reg);
1399
return miRegionBreak (badreg);
1403
miRectsToRegion(int nrects, xRectangle *prect, int ctype)
1412
pRgn = miRegionCreate(NullBox, 0);
1413
if (REGION_NAR (pRgn))
1421
if ((x2 = x1 + (int) prect->width) > MAXSHORT)
1423
if ((y2 = y1 + (int) prect->height) > MAXSHORT)
1425
if (x1 != x2 && y1 != y2)
1427
pRgn->extents.x1 = x1;
1428
pRgn->extents.y1 = y1;
1429
pRgn->extents.x2 = x2;
1430
pRgn->extents.y2 = y2;
1435
pData = xallocData(nrects);
1438
miRegionBreak (pRgn);
1441
pBox = (BoxPtr) (pData + 1);
1442
for (i = nrects; --i >= 0; prect++)
1446
if ((x2 = x1 + (int) prect->width) > MAXSHORT)
1448
if ((y2 = y1 + (int) prect->height) > MAXSHORT)
1450
if (x1 != x2 && y1 != y2)
1459
if (pBox != (BoxPtr) (pData + 1))
1461
pData->size = nrects;
1462
pData->numRects = pBox - (BoxPtr) (pData + 1);
1464
if (ctype != CT_YXBANDED)
1466
Bool overlap; /* result ignored */
1467
pRgn->extents.x1 = pRgn->extents.x2 = 0;
1468
miRegionValidate(pRgn, &overlap);
1481
/*======================================================================
1482
* Region Subtraction
1483
*====================================================================*/
1487
*-----------------------------------------------------------------------
1489
* Overlapping band subtraction. x1 is the left-most point not yet
1493
* TRUE if successful.
1496
* pReg may have rectangles added to it.
1498
*-----------------------------------------------------------------------
1503
*-----------------------------------------------------------------------
1505
* Subtract regS from regM and leave the result in regD.
1506
* S stands for subtrahend, M for minuend and D for difference.
1509
* TRUE if successful.
1512
* regD is overwritten.
1514
*-----------------------------------------------------------------------
1517
miSubtract(RegionPtr regD, RegionPtr regM, RegionPtr regS)
1519
return pixman_region_subtract (regD, regM, regS);
1522
/*======================================================================
1524
*====================================================================*/
1527
*-----------------------------------------------------------------------
1529
* Take a region and a box and return a region that is everything
1530
* in the box but not in the region. The careful reader will note
1531
* that this is the same as subtracting the region from the box...
1537
* newReg is overwritten.
1539
*-----------------------------------------------------------------------
1543
RegionPtr newReg, /* Destination region */
1544
RegionPtr reg1, /* Region to invert */
1545
BoxPtr invRect /* Bounding box for inversion */
1548
return pixman_region_inverse (newReg, reg1, invRect);
1551
miRectIn(RegionPtr region, BoxPtr prect)
1553
return pixman_region_contains_rectangle (region, prect);
1556
/* TranslateRegion(pReg, x, y)
1561
miTranslateRegion(RegionPtr pReg, int x, int y)
1563
pixman_region_translate (pReg, x, y);
1567
miRegionReset(RegionPtr pReg, BoxPtr pBox)
1569
pixman_region_reset (pReg, pBox);
1577
BoxPtr box /* "return" value */
1580
return pixman_region_contains_point (pReg, x, y, box);
1584
miRegionNotEmpty(RegionPtr pReg)
1586
return pixman_region_not_empty (pReg);
1590
miRegionBroken(RegionPtr pReg)
1593
return (REGION_NAR(pReg));
1597
miRegionEmpty(RegionPtr pReg)
1601
pReg->extents.x2 = pReg->extents.x1;
1602
pReg->extents.y2 = pReg->extents.y1;
1603
pReg->data = &miEmptyData;
1607
miRegionExtents(RegionPtr pReg)
1610
return(&pReg->extents);
1613
#define ExchangeSpans(a, b) \
1618
tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt; \
1619
tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
1622
/* ||| I should apply the merge sort code to rectangle sorting above, and see
1623
if mapping time can be improved. But right now I've been at work 12 hours,
1627
static void QuickSortSpans(
1628
DDXPointRec spans[],
1636
/* Always called with numSpans > 1 */
1637
/* Sorts only by y, doesn't bother to sort by x */
1643
/* Do insertion sort */
1649
{ /* while i != numSpans */
1653
/* spans[i] is out of order. Move into proper location. */
1657
for (j = 0; y >= spans[j].y; j++) {}
1660
for (k = i; k != j; k--)
1662
spans[k] = spans[k-1];
1663
widths[k] = widths[k-1];
1668
} /* if out of order */
1671
} while (i != numSpans);
1675
/* Choose partition element, stick in location 0 */
1677
if (spans[m].y > spans[0].y) ExchangeSpans(m, 0);
1678
if (spans[m].y > spans[numSpans-1].y) ExchangeSpans(m, numSpans-1);
1679
if (spans[m].y > spans[0].y) ExchangeSpans(m, 0);
1682
/* Partition array */
1692
} while (i != numSpans && r->y < y);
1700
ExchangeSpans(i, j);
1703
/* Move partition element back to middle */
1704
ExchangeSpans(0, j);
1707
if (numSpans-j-1 > 1)
1708
QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1);
1710
} while (numSpans > 1);
1713
#define NextBand() \
1715
clipy1 = pboxBandStart->y1; \
1716
clipy2 = pboxBandStart->y2; \
1717
pboxBandEnd = pboxBandStart + 1; \
1718
while (pboxBandEnd != pboxLast && pboxBandEnd->y1 == clipy1) { \
1721
for (; ppt != pptLast && ppt->y < clipy1; ppt++, pwidth++) {} \
1725
Clip a list of scanlines to a region. The caller has allocated the
1726
space. FSorted is non-zero if the scanline origins are in ascending
1728
returns the number of new, clipped scanlines.
1741
DDXPointPtr pptLast;
1742
int *pwidthNewStart; /* the vengeance of Xerox! */
1747
pptLast = ppt + nspans;
1748
pwidthNewStart = pwidthNew;
1752
/* Do special fast code with clip boundaries in registers(?) */
1753
/* It doesn't pay much to make use of fSorted in this case,
1754
so we lump everything together. */
1756
int clipx1, clipx2, clipy1, clipy2;
1758
clipx1 = prgnDst->extents.x1;
1759
clipy1 = prgnDst->extents.y1;
1760
clipx2 = prgnDst->extents.x2;
1761
clipy2 = prgnDst->extents.y2;
1763
for (; ppt != pptLast; ppt++, pwidth++)
1767
if (clipy1 <= y && y < clipy2)
1770
if (x1 < clipx1) x1 = clipx1;
1771
if (x2 > clipx2) x2 = clipx2;
1774
/* part of span in clip rectangle */
1777
*pwidthNew = x2 - x1;
1785
else if ((numRects = prgnDst->data->numRects))
1787
/* Have to clip against many boxes */
1788
BoxPtr pboxBandStart, pboxBandEnd;
1793
/* In this case, taking advantage of sorted spans gains more than
1794
the sorting costs. */
1795
if ((! fSorted) && (nspans > 1))
1796
QuickSortSpans(ppt, pwidth, nspans);
1798
pboxBandStart = REGION_BOXPTR(prgnDst);
1799
pboxLast = pboxBandStart + numRects;
1803
for (; ppt != pptLast; )
1808
/* span is in the current band */
1809
pbox = pboxBandStart;
1813
{ /* For each box in band */
1818
if (newx1 < pbox->x1) newx1 = pbox->x1;
1819
if (newx2 > pbox->x2) newx2 = pbox->x2;
1822
/* Part of span in clip rectangle */
1825
*pwidthNew = newx2 - newx1;
1830
} while (pbox != pboxBandEnd);
1836
/* Move to next band, adjust ppt as needed */
1837
pboxBandStart = pboxBandEnd;
1838
if (pboxBandStart == pboxLast)
1839
break; /* We're completely done */
1844
return (pwidthNew - pwidthNewStart);
added
removed
mi/miregion.c
