1
/* $XFree86: xc/programs/Xserver/mi/miregion.c,v 1.9 2003/04/23 21:51:53 tsi Exp $ */
2
/***********************************************************
4
Copyright 1987, 1988, 1989, 1998 The Open Group
6
Permission to use, copy, modify, distribute, and sell this software and its
7
documentation for any purpose is hereby granted without fee, provided that
8
the above copyright notice appear in all copies and that both that
9
copyright notice and this permission notice appear in supporting
12
The above copyright notice and this permission notice shall be included in
13
all copies or substantial portions of the Software.
15
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18
OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
19
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
20
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22
Except as contained in this notice, the name of The Open Group shall not be
23
used in advertising or otherwise to promote the sale, use or other dealings
24
in this Software without prior written authorization from The Open Group.
27
Copyright 1987, 1988, 1989 by
28
Digital Equipment Corporation, Maynard, Massachusetts.
32
Permission to use, copy, modify, and distribute this software and its
33
documentation for any purpose and without fee is hereby granted,
34
provided that the above copyright notice appear in all copies and that
35
both that copyright notice and this permission notice appear in
36
supporting documentation, and that the name of Digital not be
37
used in advertising or publicity pertaining to distribution of the
38
software without specific, written prior permission.
40
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
41
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
42
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
43
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
44
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
45
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
48
******************************************************************/
49
/* $Xorg: miregion.c,v 1.4 2001/02/09 02:05:21 xorgcvs Exp $ */
51
/* The panoramix components contained the following notice */
52
/*****************************************************************
54
Copyright (c) 1991, 1997 Digital Equipment Corporation, Maynard, Massachusetts.
56
Permission is hereby granted, free of charge, to any person obtaining a copy
57
of this software and associated documentation files (the "Software"), to deal
58
in the Software without restriction, including without limitation the rights
59
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
60
copies of the Software.
62
The above copyright notice and this permission notice shall be included in
63
all copies or substantial portions of the Software.
65
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
66
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
67
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
68
DIGITAL EQUIPMENT CORPORATION BE LIABLE FOR ANY CLAIM, DAMAGES, INCLUDING,
69
BUT NOT LIMITED TO CONSEQUENTIAL OR INCIDENTAL DAMAGES, OR OTHER LIABILITY,
70
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
71
IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
73
Except as contained in this notice, the name of Digital Equipment Corporation
74
shall not be used in advertising or otherwise to promote the sale, use or other
75
dealings in this Software without prior written authorization from Digital
76
Equipment Corporation.
78
******************************************************************/
80
#ifdef HAVE_DIX_CONFIG_H
81
#include <dix-config.h>
84
#include "regionstr.h"
85
#include <X11/Xprotostr.h>
90
#if defined (__GNUC__) && !defined (NO_INLINES)
91
#define INLINE __inline
98
#define assert(expr) {if (!(expr)) \
99
FatalError("Assertion failed file %s, line %d: expr\n", \
100
__FILE__, __LINE__); }
105
#define good(reg) assert(miValidRegion(reg))
108
* The functions in this file implement the Region abstraction used extensively
109
* throughout the X11 sample server. A Region is simply a set of disjoint
110
* (non-overlapping) rectangles, plus an "extent" rectangle which is the
111
* smallest single rectangle that contains all the non-overlapping rectangles.
113
* A Region is implemented as a "y-x-banded" array of rectangles. This array
114
* imposes two degrees of order. First, all rectangles are sorted by top side
115
* y coordinate first (y1), and then by left side x coordinate (x1).
117
* Furthermore, the rectangles are grouped into "bands". Each rectangle in a
118
* band has the same top y coordinate (y1), and each has the same bottom y
119
* coordinate (y2). Thus all rectangles in a band differ only in their left
120
* and right side (x1 and x2). Bands are implicit in the array of rectangles:
121
* there is no separate list of band start pointers.
123
* The y-x band representation does not minimize rectangles. In particular,
124
* if a rectangle vertically crosses a band (the rectangle has scanlines in
125
* the y1 to y2 area spanned by the band), then the rectangle may be broken
126
* down into two or more smaller rectangles stacked one atop the other.
128
* ----------- -----------
130
* | | -------- ----------- --------
131
* | | | | in y-x banded | | | | band 1
132
* | | | | form is | | | |
133
* ----------- | | ----------- --------
137
* An added constraint on the rectangles is that they must cover as much
138
* horizontal area as possible: no two rectangles within a band are allowed
141
* Whenever possible, bands will be merged together to cover a greater vertical
142
* distance (and thus reduce the number of rectangles). Two bands can be merged
143
* only if the bottom of one touches the top of the other and they have
144
* rectangles in the same places (of the same width, of course).
146
* Adam de Boor wrote most of the original region code. Joel McCormack
147
* substantially modified or rewrote most of the core arithmetic routines,
148
* and added miRegionValidate in order to support several speed improvements
149
* to miValidateTree. Bob Scheifler changed the representation to be more
150
* compact when empty or a single rectangle, and did a bunch of gratuitous
154
/* true iff two Boxes overlap */
155
#define EXTENTCHECK(r1,r2) \
156
(!( ((r1)->x2 <= (r2)->x1) || \
157
((r1)->x1 >= (r2)->x2) || \
158
((r1)->y2 <= (r2)->y1) || \
159
((r1)->y1 >= (r2)->y2) ) )
161
/* true iff (x,y) is in Box */
162
#define INBOX(r,x,y) \
168
/* true iff Box r1 contains Box r2 */
169
#define SUBSUMES(r1,r2) \
170
( ((r1)->x1 <= (r2)->x1) && \
171
((r1)->x2 >= (r2)->x2) && \
172
((r1)->y1 <= (r2)->y1) && \
173
((r1)->y2 >= (r2)->y2) )
175
#define xallocData(n) (RegDataPtr)xalloc(REGION_SZOF(n))
176
#define xfreeData(reg) if ((reg)->data && (reg)->data->size) xfree((reg)->data)
178
#define RECTALLOC_BAIL(pReg,n,bail) \
179
if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
180
if (!miRectAlloc(pReg, n)) { goto bail; }
182
#define RECTALLOC(pReg,n) \
183
if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
184
if (!miRectAlloc(pReg, n)) { return FALSE; }
186
#define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \
188
pNextRect->x1 = nx1; \
189
pNextRect->y1 = ny1; \
190
pNextRect->x2 = nx2; \
191
pNextRect->y2 = ny2; \
195
#define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \
197
if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
199
if (!miRectAlloc(pReg, 1)) \
201
pNextRect = REGION_TOP(pReg); \
203
ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \
204
pReg->data->numRects++; \
205
assert(pReg->data->numRects<=pReg->data->size); \
209
#define DOWNSIZE(reg,numRects) \
210
if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
212
RegDataPtr NewData; \
213
NewData = (RegDataPtr)xrealloc((reg)->data, REGION_SZOF(numRects)); \
216
NewData->size = (numRects); \
217
(reg)->data = NewData; \
222
BoxRec miEmptyBox = {0, 0, 0, 0};
223
RegDataRec miEmptyData = {0, 0};
225
RegDataRec miBrokenData = {0, 0};
226
RegionRec miBrokenRegion = { { 0, 0, 0, 0 }, &miBrokenData };
237
num = REGION_NUM_RECTS(rgn);
238
size = REGION_SIZE(rgn);
239
rects = REGION_RECTS(rgn);
240
ErrorF("num: %d size: %d\n", num, size);
241
ErrorF("extents: %d %d %d %d\n",
242
rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
243
for (i = 0; i < num; i++)
244
ErrorF("%d %d %d %d \n",
245
rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
252
miRegionEqual(reg1, reg2)
257
BoxPtr rects1, rects2;
259
if (reg1->extents.x1 != reg2->extents.x1) return FALSE;
260
if (reg1->extents.x2 != reg2->extents.x2) return FALSE;
261
if (reg1->extents.y1 != reg2->extents.y1) return FALSE;
262
if (reg1->extents.y2 != reg2->extents.y2) return FALSE;
264
num = REGION_NUM_RECTS(reg1);
265
if (num != REGION_NUM_RECTS(reg2)) return FALSE;
267
rects1 = REGION_RECTS(reg1);
268
rects2 = REGION_RECTS(reg2);
269
for (i = 0; i != num; i++) {
270
if (rects1[i].x1 != rects2[i].x1) return FALSE;
271
if (rects1[i].x2 != rects2[i].x2) return FALSE;
272
if (rects1[i].y1 != rects2[i].y1) return FALSE;
273
if (rects1[i].y2 != rects2[i].y2) return FALSE;
283
register int i, numRects;
285
if ((reg->extents.x1 > reg->extents.x2) ||
286
(reg->extents.y1 > reg->extents.y2))
288
numRects = REGION_NUM_RECTS(reg);
290
return ((reg->extents.x1 == reg->extents.x2) &&
291
(reg->extents.y1 == reg->extents.y2) &&
292
(reg->data->size || (reg->data == &miEmptyData)));
293
else if (numRects == 1)
297
register BoxPtr pboxP, pboxN;
300
pboxP = REGION_RECTS(reg);
302
box.y2 = pboxP[numRects-1].y2;
304
for (i = numRects; --i > 0; pboxP++, pboxN++)
306
if ((pboxN->x1 >= pboxN->x2) ||
307
(pboxN->y1 >= pboxN->y2))
309
if (pboxN->x1 < box.x1)
311
if (pboxN->x2 > box.x2)
313
if ((pboxN->y1 < pboxP->y1) ||
314
((pboxN->y1 == pboxP->y1) &&
315
((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2))))
318
return ((box.x1 == reg->extents.x1) &&
319
(box.x2 == reg->extents.x2) &&
320
(box.y1 == reg->extents.y1) &&
321
(box.y2 == reg->extents.y2));
328
/*****************************************************************
329
* RegionCreate(rect, size)
330
* This routine does a simple malloc to make a structure of
331
* REGION of "size" number of rectangles.
332
*****************************************************************/
335
miRegionCreate(rect, size)
339
register RegionPtr pReg;
341
pReg = (RegionPtr)xalloc(sizeof(RegionRec));
343
return &miBrokenRegion;
346
pReg->extents = *rect;
347
pReg->data = (RegDataPtr)NULL;
351
pReg->extents = miEmptyBox;
352
if ((size > 1) && (pReg->data = xallocData(size)))
354
pReg->data->size = size;
355
pReg->data->numRects = 0;
358
pReg->data = &miEmptyData;
363
/*****************************************************************
364
* RegionInit(pReg, rect, size)
365
* Outer region rect is statically allocated.
366
*****************************************************************/
369
miRegionInit(pReg, rect, size)
376
pReg->extents = *rect;
377
pReg->data = (RegDataPtr)NULL;
381
pReg->extents = miEmptyBox;
382
if ((size > 1) && (pReg->data = xallocData(size)))
384
pReg->data->size = size;
385
pReg->data->numRects = 0;
388
pReg->data = &miEmptyData;
393
miRegionDestroy(pReg)
398
if (pReg != &miBrokenRegion)
415
pReg->extents = miEmptyBox;
416
pReg->data = &miBrokenData;
422
register RegionPtr pRgn,
430
pRgn->data = xallocData(n);
432
return miRegionBreak (pRgn);
433
pRgn->data->numRects = 1;
434
*REGION_BOXPTR(pRgn) = pRgn->extents;
436
else if (!pRgn->data->size)
438
pRgn->data = xallocData(n);
440
return miRegionBreak (pRgn);
441
pRgn->data->numRects = 0;
447
n = pRgn->data->numRects;
448
if (n > 500) /* XXX pick numbers out of a hat */
451
n += pRgn->data->numRects;
452
data = (RegDataPtr)xrealloc(pRgn->data, REGION_SZOF(n));
454
return miRegionBreak (pRgn);
457
pRgn->data->size = n;
462
miRegionCopy(dst, src)
463
register RegionPtr dst;
464
register RegionPtr src;
470
dst->extents = src->extents;
471
if (!src->data || !src->data->size)
474
dst->data = src->data;
477
if (!dst->data || (dst->data->size < src->data->numRects))
480
dst->data = xallocData(src->data->numRects);
482
return miRegionBreak (dst);
483
dst->data->size = src->data->numRects;
485
dst->data->numRects = src->data->numRects;
486
memmove((char *)REGION_BOXPTR(dst),(char *)REGION_BOXPTR(src),
487
dst->data->numRects * sizeof(BoxRec));
492
/*======================================================================
493
* Generic Region Operator
494
*====================================================================*/
497
*-----------------------------------------------------------------------
499
* Attempt to merge the boxes in the current band with those in the
500
* previous one. We are guaranteed that the current band extends to
501
* the end of the rects array. Used only by miRegionOp.
504
* The new index for the previous band.
507
* If coalescing takes place:
508
* - rectangles in the previous band will have their y2 fields
510
* - pReg->data->numRects will be decreased.
512
*-----------------------------------------------------------------------
516
register RegionPtr pReg, /* Region to coalesce */
517
int prevStart, /* Index of start of previous band */
518
int curStart) /* Index of start of current band */
520
register BoxPtr pPrevBox; /* Current box in previous band */
521
register BoxPtr pCurBox; /* Current box in current band */
522
register int numRects; /* Number rectangles in both bands */
523
register int y2; /* Bottom of current band */
525
* Figure out how many rectangles are in the band.
527
numRects = curStart - prevStart;
528
assert(numRects == pReg->data->numRects - curStart);
530
if (!numRects) return curStart;
533
* The bands may only be coalesced if the bottom of the previous
534
* matches the top scanline of the current.
536
pPrevBox = REGION_BOX(pReg, prevStart);
537
pCurBox = REGION_BOX(pReg, curStart);
538
if (pPrevBox->y2 != pCurBox->y1) return curStart;
541
* Make sure the bands have boxes in the same places. This
542
* assumes that boxes have been added in such a way that they
543
* cover the most area possible. I.e. two boxes in a band must
544
* have some horizontal space between them.
549
if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) {
558
* The bands may be merged, so set the bottom y of each box
559
* in the previous band to the bottom y of the current band.
561
numRects = curStart - prevStart;
562
pReg->data->numRects -= numRects;
572
/* Quicky macro to avoid trivial reject procedure calls to miCoalesce */
574
#define Coalesce(newReg, prevBand, curBand) \
575
if (curBand - prevBand == newReg->data->numRects - curBand) { \
576
prevBand = miCoalesce(newReg, prevBand, curBand); \
578
prevBand = curBand; \
582
*-----------------------------------------------------------------------
584
* Handle a non-overlapping band for the union and subtract operations.
585
* Just adds the (top/bottom-clipped) rectangles into the region.
586
* Doesn't have to check for subsumption or anything.
592
* pReg->data->numRects is incremented and the rectangles overwritten
593
* with the rectangles we're passed.
595
*-----------------------------------------------------------------------
600
register RegionPtr pReg,
606
register BoxPtr pNextRect;
607
register int newRects;
612
assert(newRects != 0);
614
/* Make sure we have enough space for all rectangles to be added */
615
RECTALLOC(pReg, newRects);
616
pNextRect = REGION_TOP(pReg);
617
pReg->data->numRects += newRects;
619
assert(r->x1 < r->x2);
620
ADDRECT(pNextRect, r->x1, y1, r->x2, y2);
627
#define FindBand(r, rBandEnd, rEnd, ry1) \
631
while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \
636
#define AppendRegions(newReg, r, rEnd) \
639
if ((newRects = rEnd - r)) { \
640
RECTALLOC(newReg, newRects); \
641
memmove((char *)REGION_TOP(newReg),(char *)r, \
642
newRects * sizeof(BoxRec)); \
643
newReg->data->numRects += newRects; \
648
*-----------------------------------------------------------------------
650
* Apply an operation to two regions. Called by miUnion, miInverse,
651
* miSubtract, miIntersect.... Both regions MUST have at least one
652
* rectangle, and cannot be the same object.
655
* TRUE if successful.
658
* The new region is overwritten.
659
* pOverlap set to TRUE if overlapFunc ever returns TRUE.
662
* The idea behind this function is to view the two regions as sets.
663
* Together they cover a rectangle of area that this function divides
664
* into horizontal bands where points are covered only by one region
665
* or by both. For the first case, the nonOverlapFunc is called with
666
* each the band and the band's upper and lower extents. For the
667
* second, the overlapFunc is called to process the entire band. It
668
* is responsible for clipping the rectangles in the band, though
669
* this function provides the boundaries.
670
* At the end of each band, the new region is coalesced, if possible,
671
* to reduce the number of rectangles in the region.
673
*-----------------------------------------------------------------------
676
typedef Bool (*OverlapProcPtr)(
688
RegionPtr newReg, /* Place to store result */
689
RegionPtr reg1, /* First region in operation */
690
RegionPtr reg2, /* 2d region in operation */
691
OverlapProcPtr overlapFunc, /* Function to call for over-
693
Bool appendNon1, /* Append non-overlapping bands */
695
Bool appendNon2, /* Append non-overlapping bands */
699
register BoxPtr r1; /* Pointer into first region */
700
register BoxPtr r2; /* Pointer into 2d region */
701
BoxPtr r1End; /* End of 1st region */
702
BoxPtr r2End; /* End of 2d region */
703
short ybot; /* Bottom of intersection */
704
short ytop; /* Top of intersection */
705
RegDataPtr oldData; /* Old data for newReg */
706
int prevBand; /* Index of start of
707
* previous band in newReg */
708
int curBand; /* Index of start of current
710
register BoxPtr r1BandEnd; /* End of current band in r1 */
711
register BoxPtr r2BandEnd; /* End of current band in r2 */
712
short top; /* Top of non-overlapping band */
713
short bot; /* Bottom of non-overlapping band*/
714
register int r1y1; /* Temps for r1->y1 and r2->y1 */
720
* Break any region computed from a broken region
722
if (REGION_NAR (reg1) || REGION_NAR(reg2))
723
return miRegionBreak (newReg);
727
* set r1, r2, r1End and r2End appropriately, save the rectangles
728
* of the destination region until the end in case it's one of
729
* the two source regions, then mark the "new" region empty, allocating
730
* another array of rectangles for it to use.
733
r1 = REGION_RECTS(reg1);
734
newSize = REGION_NUM_RECTS(reg1);
735
r1End = r1 + newSize;
736
numRects = REGION_NUM_RECTS(reg2);
737
r2 = REGION_RECTS(reg2);
738
r2End = r2 + numRects;
742
oldData = (RegDataPtr)NULL;
743
if (((newReg == reg1) && (newSize > 1)) ||
744
((newReg == reg2) && (numRects > 1)))
746
oldData = newReg->data;
747
newReg->data = &miEmptyData;
749
/* guess at new size */
750
if (numRects > newSize)
754
newReg->data = &miEmptyData;
755
else if (newReg->data->size)
756
newReg->data->numRects = 0;
757
if (newSize > newReg->data->size)
758
if (!miRectAlloc(newReg, newSize))
763
* In the upcoming loop, ybot and ytop serve different functions depending
764
* on whether the band being handled is an overlapping or non-overlapping
766
* In the case of a non-overlapping band (only one of the regions
767
* has points in the band), ybot is the bottom of the most recent
768
* intersection and thus clips the top of the rectangles in that band.
769
* ytop is the top of the next intersection between the two regions and
770
* serves to clip the bottom of the rectangles in the current band.
771
* For an overlapping band (where the two regions intersect), ytop clips
772
* the top of the rectangles of both regions and ybot clips the bottoms.
775
ybot = min(r1->y1, r2->y1);
778
* prevBand serves to mark the start of the previous band so rectangles
779
* can be coalesced into larger rectangles. qv. miCoalesce, above.
780
* In the beginning, there is no previous band, so prevBand == curBand
781
* (curBand is set later on, of course, but the first band will always
782
* start at index 0). prevBand and curBand must be indices because of
783
* the possible expansion, and resultant moving, of the new region's
784
* array of rectangles.
790
* This algorithm proceeds one source-band (as opposed to a
791
* destination band, which is determined by where the two regions
792
* intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
793
* rectangle after the last one in the current band for their
794
* respective regions.
799
FindBand(r1, r1BandEnd, r1End, r1y1);
800
FindBand(r2, r2BandEnd, r2End, r2y1);
803
* First handle the band that doesn't intersect, if any.
805
* Note that attention is restricted to one band in the
806
* non-intersecting region at once, so if a region has n
807
* bands between the current position and the next place it overlaps
808
* the other, this entire loop will be passed through n times.
812
top = max(r1y1, ybot);
813
bot = min(r1->y2, r2y1);
815
curBand = newReg->data->numRects;
816
miAppendNonO(newReg, r1, r1BandEnd, top, bot);
817
Coalesce(newReg, prevBand, curBand);
821
} else if (r2y1 < r1y1) {
823
top = max(r2y1, ybot);
824
bot = min(r2->y2, r1y1);
826
curBand = newReg->data->numRects;
827
miAppendNonO(newReg, r2, r2BandEnd, top, bot);
828
Coalesce(newReg, prevBand, curBand);
837
* Now see if we've hit an intersecting band. The two bands only
838
* intersect if ybot > ytop
840
ybot = min(r1->y2, r2->y2);
842
curBand = newReg->data->numRects;
843
(* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot,
845
Coalesce(newReg, prevBand, curBand);
849
* If we've finished with a band (y2 == ybot) we skip forward
850
* in the region to the next band.
852
if (r1->y2 == ybot) r1 = r1BandEnd;
853
if (r2->y2 == ybot) r2 = r2BandEnd;
855
} while (r1 != r1End && r2 != r2End);
858
* Deal with whichever region (if any) still has rectangles left.
860
* We only need to worry about banding and coalescing for the very first
861
* band left. After that, we can just group all remaining boxes,
862
* regardless of how many bands, into one final append to the list.
865
if ((r1 != r1End) && appendNon1) {
866
/* Do first nonOverlap1Func call, which may be able to coalesce */
867
FindBand(r1, r1BandEnd, r1End, r1y1);
868
curBand = newReg->data->numRects;
869
miAppendNonO(newReg, r1, r1BandEnd, max(r1y1, ybot), r1->y2);
870
Coalesce(newReg, prevBand, curBand);
871
/* Just append the rest of the boxes */
872
AppendRegions(newReg, r1BandEnd, r1End);
874
} else if ((r2 != r2End) && appendNon2) {
875
/* Do first nonOverlap2Func call, which may be able to coalesce */
876
FindBand(r2, r2BandEnd, r2End, r2y1);
877
curBand = newReg->data->numRects;
878
miAppendNonO(newReg, r2, r2BandEnd, max(r2y1, ybot), r2->y2);
879
Coalesce(newReg, prevBand, curBand);
880
/* Append rest of boxes */
881
AppendRegions(newReg, r2BandEnd, r2End);
887
if (!(numRects = newReg->data->numRects))
890
newReg->data = &miEmptyData;
892
else if (numRects == 1)
894
newReg->extents = *REGION_BOXPTR(newReg);
896
newReg->data = (RegDataPtr)NULL;
900
DOWNSIZE(newReg, numRects);
907
*-----------------------------------------------------------------------
909
* Reset the extents of a region to what they should be. Called by
910
* miSubtract and miIntersect as they can't figure it out along the
911
* way or do so easily, as miUnion can.
917
* The region's 'extents' structure is overwritten.
919
*-----------------------------------------------------------------------
923
register RegionPtr pReg;
925
register BoxPtr pBox, pBoxEnd;
929
if (!pReg->data->size)
931
pReg->extents.x2 = pReg->extents.x1;
932
pReg->extents.y2 = pReg->extents.y1;
936
pBox = REGION_BOXPTR(pReg);
937
pBoxEnd = REGION_END(pReg);
940
* Since pBox is the first rectangle in the region, it must have the
941
* smallest y1 and since pBoxEnd is the last rectangle in the region,
942
* it must have the largest y2, because of banding. Initialize x1 and
943
* x2 from pBox and pBoxEnd, resp., as good things to initialize them
946
pReg->extents.x1 = pBox->x1;
947
pReg->extents.y1 = pBox->y1;
948
pReg->extents.x2 = pBoxEnd->x2;
949
pReg->extents.y2 = pBoxEnd->y2;
951
assert(pReg->extents.y1 < pReg->extents.y2);
952
while (pBox <= pBoxEnd) {
953
if (pBox->x1 < pReg->extents.x1)
954
pReg->extents.x1 = pBox->x1;
955
if (pBox->x2 > pReg->extents.x2)
956
pReg->extents.x2 = pBox->x2;
960
assert(pReg->extents.x1 < pReg->extents.x2);
963
/*======================================================================
964
* Region Intersection
965
*====================================================================*/
967
*-----------------------------------------------------------------------
969
* Handle an overlapping band for miIntersect.
972
* TRUE if successful.
975
* Rectangles may be added to the region.
977
*-----------------------------------------------------------------------
982
register RegionPtr pReg,
993
register BoxPtr pNextRect;
995
pNextRect = REGION_TOP(pReg);
998
assert(r1 != r1End && r2 != r2End);
1001
x1 = max(r1->x1, r2->x1);
1002
x2 = min(r1->x2, r2->x2);
1005
* If there's any overlap between the two rectangles, add that
1006
* overlap to the new region.
1009
NEWRECT(pReg, pNextRect, x1, y1, x2, y2);
1012
* Advance the pointer(s) with the leftmost right side, since the next
1013
* rectangle on that list may still overlap the other region's
1014
* current rectangle.
1022
} while ((r1 != r1End) && (r2 != r2End));
1029
miIntersect(newReg, reg1, reg2)
1030
register RegionPtr newReg; /* destination Region */
1031
register RegionPtr reg1;
1032
register RegionPtr reg2; /* source regions */
1037
/* check for trivial reject */
1038
if (REGION_NIL(reg1) || REGION_NIL(reg2) ||
1039
!EXTENTCHECK(®1->extents, ®2->extents))
1041
/* Covers about 20% of all cases */
1043
newReg->extents.x2 = newReg->extents.x1;
1044
newReg->extents.y2 = newReg->extents.y1;
1045
if (REGION_NAR(reg1) || REGION_NAR(reg2))
1047
newReg->data = &miBrokenData;
1051
newReg->data = &miEmptyData;
1053
else if (!reg1->data && !reg2->data)
1055
/* Covers about 80% of cases that aren't trivially rejected */
1056
newReg->extents.x1 = max(reg1->extents.x1, reg2->extents.x1);
1057
newReg->extents.y1 = max(reg1->extents.y1, reg2->extents.y1);
1058
newReg->extents.x2 = min(reg1->extents.x2, reg2->extents.x2);
1059
newReg->extents.y2 = min(reg1->extents.y2, reg2->extents.y2);
1061
newReg->data = (RegDataPtr)NULL;
1063
else if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
1065
return miRegionCopy(newReg, reg1);
1067
else if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
1069
return miRegionCopy(newReg, reg2);
1071
else if (reg1 == reg2)
1073
return miRegionCopy(newReg, reg1);
1077
/* General purpose intersection */
1078
Bool overlap; /* result ignored */
1079
if (!miRegionOp(newReg, reg1, reg2, miIntersectO, FALSE, FALSE,
1082
miSetExtents(newReg);
1089
#define MERGERECT(r) \
1091
if (r->x1 <= x2) { \
1092
/* Merge with current rectangle */ \
1093
if (r->x1 < x2) *pOverlap = TRUE; \
1094
if (x2 < r->x2) x2 = r->x2; \
1096
/* Add current rectangle, start new one */ \
1097
NEWRECT(pReg, pNextRect, x1, y1, x2, y2); \
1104
/*======================================================================
1106
*====================================================================*/
1109
*-----------------------------------------------------------------------
1111
* Handle an overlapping band for the union operation. Picks the
1112
* left-most rectangle each time and merges it into the region.
1115
* TRUE if successful.
1118
* pReg is overwritten.
1119
* pOverlap is set to TRUE if any boxes overlap.
1121
*-----------------------------------------------------------------------
1125
register RegionPtr pReg,
1134
register BoxPtr pNextRect;
1135
register int x1; /* left and right side of current union */
1139
assert(r1 != r1End && r2 != r2End);
1141
pNextRect = REGION_TOP(pReg);
1143
/* Start off current rectangle */
1144
if (r1->x1 < r2->x1)
1156
while (r1 != r1End && r2 != r2End)
1158
if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
1161
/* Finish off whoever (if any) is left */
1167
} while (r1 != r1End);
1169
else if (r2 != r2End)
1174
} while (r2 != r2End);
1177
/* Add current rectangle */
1178
NEWRECT(pReg, pNextRect, x1, y1, x2, y2);
1184
miUnion(newReg, reg1, reg2)
1185
RegionPtr newReg; /* destination Region */
1186
register RegionPtr reg1;
1187
register RegionPtr reg2; /* source regions */
1189
Bool overlap; /* result ignored */
1191
/* Return TRUE if some overlap between reg1, reg2 */
1195
/* checks all the simple cases */
1198
* Region 1 and 2 are the same
1202
return miRegionCopy(newReg, reg1);
1208
if (REGION_NIL(reg1))
1210
if (REGION_NAR(reg1))
1211
return miRegionBreak (newReg);
1213
return miRegionCopy(newReg, reg2);
1220
if (REGION_NIL(reg2))
1222
if (REGION_NAR(reg2))
1223
return miRegionBreak (newReg);
1225
return miRegionCopy(newReg, reg1);
1230
* Region 1 completely subsumes region 2
1232
if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
1235
return miRegionCopy(newReg, reg1);
1240
* Region 2 completely subsumes region 1
1242
if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
1245
return miRegionCopy(newReg, reg2);
1249
if (!miRegionOp(newReg, reg1, reg2, miUnionO, TRUE, TRUE, &overlap))
1252
newReg->extents.x1 = min(reg1->extents.x1, reg2->extents.x1);
1253
newReg->extents.y1 = min(reg1->extents.y1, reg2->extents.y1);
1254
newReg->extents.x2 = max(reg1->extents.x2, reg2->extents.x2);
1255
newReg->extents.y2 = max(reg1->extents.y2, reg2->extents.y2);
1261
/*======================================================================
1262
* Batch Rectangle Union
1263
*====================================================================*/
1266
*-----------------------------------------------------------------------
1269
* "Append" the rgn rectangles onto the end of dstrgn, maintaining
1270
* knowledge of YX-banding when it's easy. Otherwise, dstrgn just
1271
* becomes a non-y-x-banded random collection of rectangles, and not
1272
* yet a true region. After a sequence of appends, the caller must
1273
* call miRegionValidate to ensure that a valid region is constructed.
1276
* TRUE if successful.
1279
* dstrgn is modified if rgn has rectangles.
1283
miRegionAppend(dstrgn, rgn)
1284
register RegionPtr dstrgn;
1285
register RegionPtr rgn;
1287
int numRects, dnumRects, size;
1291
if (REGION_NAR(rgn))
1292
return miRegionBreak (dstrgn);
1294
if (!rgn->data && (dstrgn->data == &miEmptyData))
1296
dstrgn->extents = rgn->extents;
1297
dstrgn->data = (RegDataPtr)NULL;
1301
numRects = REGION_NUM_RECTS(rgn);
1306
dnumRects = REGION_NUM_RECTS(dstrgn);
1307
if (!dnumRects && (size < 200))
1308
size = 200; /* XXX pick numbers out of a hat */
1309
RECTALLOC(dstrgn, size);
1310
old = REGION_RECTS(rgn);
1312
dstrgn->extents = rgn->extents;
1313
else if (dstrgn->extents.x2 > dstrgn->extents.x1)
1315
register BoxPtr first, last;
1318
last = REGION_BOXPTR(dstrgn) + (dnumRects - 1);
1319
if ((first->y1 > last->y2) ||
1320
((first->y1 == last->y1) && (first->y2 == last->y2) &&
1321
(first->x1 > last->x2)))
1323
if (rgn->extents.x1 < dstrgn->extents.x1)
1324
dstrgn->extents.x1 = rgn->extents.x1;
1325
if (rgn->extents.x2 > dstrgn->extents.x2)
1326
dstrgn->extents.x2 = rgn->extents.x2;
1327
dstrgn->extents.y2 = rgn->extents.y2;
1331
first = REGION_BOXPTR(dstrgn);
1332
last = old + (numRects - 1);
1333
if ((first->y1 > last->y2) ||
1334
((first->y1 == last->y1) && (first->y2 == last->y2) &&
1335
(first->x1 > last->x2)))
1338
if (rgn->extents.x1 < dstrgn->extents.x1)
1339
dstrgn->extents.x1 = rgn->extents.x1;
1340
if (rgn->extents.x2 > dstrgn->extents.x2)
1341
dstrgn->extents.x2 = rgn->extents.x2;
1342
dstrgn->extents.y1 = rgn->extents.y1;
1345
dstrgn->extents.x2 = dstrgn->extents.x1;
1350
new = REGION_BOX(dstrgn, numRects);
1352
*new = *REGION_BOXPTR(dstrgn);
1354
memmove((char *)new,(char *)REGION_BOXPTR(dstrgn),
1355
dnumRects * sizeof(BoxRec));
1356
new = REGION_BOXPTR(dstrgn);
1359
new = REGION_BOXPTR(dstrgn) + dnumRects;
1363
memmove((char *)new, (char *)old, numRects * sizeof(BoxRec));
1364
dstrgn->data->numRects += numRects;
1369
#define ExchangeRects(a, b) \
1373
rects[a] = rects[b]; \
1379
register BoxRec rects[],
1380
register int numRects)
1387
/* Always called with numRects > 1 */
1393
if (rects[0].y1 > rects[1].y1 ||
1394
(rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
1395
ExchangeRects(0, 1);
1399
/* Choose partition element, stick in location 0 */
1400
ExchangeRects(0, numRects >> 1);
1404
/* Partition array */
1414
} while (i != numRects &&
1415
(r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
1421
} while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
1423
ExchangeRects(i, j);
1426
/* Move partition element back to middle */
1427
ExchangeRects(0, j);
1430
if (numRects-j-1 > 1)
1431
QuickSortRects(&rects[j+1], numRects-j-1);
1433
} while (numRects > 1);
1437
*-----------------------------------------------------------------------
1438
* miRegionValidate --
1440
* Take a ``region'' which is a non-y-x-banded random collection of
1441
* rectangles, and compute a nice region which is the union of all the
1445
* TRUE if successful.
1448
* The passed-in ``region'' may be modified.
1449
* pOverlap set to TRUE if any retangles overlapped, else FALSE;
1452
* Step 1. Sort the rectangles into ascending order with primary key y1
1453
* and secondary key x1.
1455
* Step 2. Split the rectangles into the minimum number of proper y-x
1456
* banded regions. This may require horizontally merging
1457
* rectangles, and vertically coalescing bands. With any luck,
1458
* this step in an identity tranformation (ala the Box widget),
1459
* or a coalescing into 1 box (ala Menus).
1461
* Step 3. Merge the separate regions down to a single region by calling
1462
* miUnion. Maximize the work each miUnion call does by using
1465
*-----------------------------------------------------------------------
1469
miRegionValidate(badreg, pOverlap)
1473
/* Descriptor for regions under construction in Step 2. */
1480
int numRects; /* Original numRects for badreg */
1481
RegionInfo *ri; /* Array of current regions */
1482
int numRI; /* Number of entries used in ri */
1483
int sizeRI; /* Number of entries available in ri */
1484
int i; /* Index into rects */
1485
register int j; /* Index into ri */
1486
register RegionInfo *rit; /* &ri[j] */
1487
register RegionPtr reg; /* ri[j].reg */
1488
register BoxPtr box; /* Current box in rects */
1489
register BoxPtr riBox; /* Last box in ri[j].reg */
1490
register RegionPtr hreg; /* ri[j_half].reg */
1499
numRects = badreg->data->numRects;
1502
if (REGION_NAR(badreg))
1507
if (badreg->extents.x1 < badreg->extents.x2)
1509
if ((numRects) == 1)
1512
badreg->data = (RegDataPtr) NULL;
1516
DOWNSIZE(badreg, numRects);
1522
/* Step 1: Sort the rects array into ascending (y1, x1) order */
1523
QuickSortRects(REGION_BOXPTR(badreg), numRects);
1525
/* Step 2: Scatter the sorted array into the minimum number of regions */
1527
/* Set up the first region to be the first rectangle in badreg */
1528
/* Note that step 2 code will never overflow the ri[0].reg rects array */
1529
ri = (RegionInfo *) xalloc(4 * sizeof(RegionInfo));
1531
return miRegionBreak (badreg);
1536
ri[0].reg = *badreg;
1537
box = REGION_BOXPTR(&ri[0].reg);
1538
ri[0].reg.extents = *box;
1539
ri[0].reg.data->numRects = 1;
1541
/* Now scatter rectangles into the minimum set of valid regions. If the
1542
next rectangle to be added to a region would force an existing rectangle
1543
in the region to be split up in order to maintain y-x banding, just
1544
forget it. Try the next region. If it doesn't fit cleanly into any
1545
region, make a new one. */
1547
for (i = numRects; --i > 0;)
1550
/* Look for a region to append box to */
1551
for (j = numRI, rit = ri; --j >= 0; rit++)
1554
riBox = REGION_END(reg);
1556
if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
1558
/* box is in same band as riBox. Merge or append it */
1559
if (box->x1 <= riBox->x2)
1561
/* Merge it with riBox */
1562
if (box->x1 < riBox->x2) *pOverlap = TRUE;
1563
if (box->x2 > riBox->x2) riBox->x2 = box->x2;
1567
RECTALLOC_BAIL(reg, 1, bail);
1568
*REGION_TOP(reg) = *box;
1569
reg->data->numRects++;
1571
goto NextRect; /* So sue me */
1573
else if (box->y1 >= riBox->y2)
1575
/* Put box into new band */
1576
if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1577
if (reg->extents.x1 > box->x1) reg->extents.x1 = box->x1;
1578
Coalesce(reg, rit->prevBand, rit->curBand);
1579
rit->curBand = reg->data->numRects;
1580
RECTALLOC_BAIL(reg, 1, bail);
1581
*REGION_TOP(reg) = *box;
1582
reg->data->numRects++;
1585
/* Well, this region was inappropriate. Try the next one. */
1588
/* Uh-oh. No regions were appropriate. Create a new one. */
1589
if (sizeRI == numRI)
1591
/* Oops, allocate space for new region information */
1593
rit = (RegionInfo *) xrealloc(ri, sizeRI * sizeof(RegionInfo));
1602
rit->reg.extents = *box;
1603
rit->reg.data = (RegDataPtr)NULL;
1604
if (!miRectAlloc(&rit->reg, (i+numRI) / numRI)) /* MUST force allocation */
1609
/* Make a final pass over each region in order to Coalesce and set
1610
extents.x2 and extents.y2 */
1612
for (j = numRI, rit = ri; --j >= 0; rit++)
1615
riBox = REGION_END(reg);
1616
reg->extents.y2 = riBox->y2;
1617
if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1618
Coalesce(reg, rit->prevBand, rit->curBand);
1619
if (reg->data->numRects == 1) /* keep unions happy below */
1622
reg->data = (RegDataPtr)NULL;
1626
/* Step 3: Union all regions into a single region */
1630
for (j = numRI & 1; j < (half + (numRI & 1)); j++)
1633
hreg = &ri[j+half].reg;
1634
if (!miRegionOp(reg, reg, hreg, miUnionO, TRUE, TRUE, pOverlap))
1636
if (hreg->extents.x1 < reg->extents.x1)
1637
reg->extents.x1 = hreg->extents.x1;
1638
if (hreg->extents.y1 < reg->extents.y1)
1639
reg->extents.y1 = hreg->extents.y1;
1640
if (hreg->extents.x2 > reg->extents.x2)
1641
reg->extents.x2 = hreg->extents.x2;
1642
if (hreg->extents.y2 > reg->extents.y2)
1643
reg->extents.y2 = hreg->extents.y2;
1648
*badreg = ri[0].reg;
1653
for (i = 0; i < numRI; i++)
1654
xfreeData(&ri[i].reg);
1656
return miRegionBreak (badreg);
1660
miRectsToRegion(nrects, prect, ctype)
1662
register xRectangle *prect;
1665
register RegionPtr pRgn;
1666
register RegDataPtr pData;
1667
register BoxPtr pBox;
1671
pRgn = miRegionCreate(NullBox, 0);
1672
if (REGION_NAR (pRgn))
1680
if ((x2 = x1 + (int) prect->width) > MAXSHORT)
1682
if ((y2 = y1 + (int) prect->height) > MAXSHORT)
1684
if (x1 != x2 && y1 != y2)
1686
pRgn->extents.x1 = x1;
1687
pRgn->extents.y1 = y1;
1688
pRgn->extents.x2 = x2;
1689
pRgn->extents.y2 = y2;
1690
pRgn->data = (RegDataPtr)NULL;
1694
pData = xallocData(nrects);
1697
miRegionBreak (pRgn);
1700
pBox = (BoxPtr) (pData + 1);
1701
for (i = nrects; --i >= 0; prect++)
1705
if ((x2 = x1 + (int) prect->width) > MAXSHORT)
1707
if ((y2 = y1 + (int) prect->height) > MAXSHORT)
1709
if (x1 != x2 && y1 != y2)
1718
if (pBox != (BoxPtr) (pData + 1))
1720
pData->size = nrects;
1721
pData->numRects = pBox - (BoxPtr) (pData + 1);
1723
if (ctype != CT_YXBANDED)
1725
Bool overlap; /* result ignored */
1726
pRgn->extents.x1 = pRgn->extents.x2 = 0;
1727
miRegionValidate(pRgn, &overlap);
1740
/*======================================================================
1741
* Region Subtraction
1742
*====================================================================*/
1746
*-----------------------------------------------------------------------
1748
* Overlapping band subtraction. x1 is the left-most point not yet
1752
* TRUE if successful.
1755
* pReg may have rectangles added to it.
1757
*-----------------------------------------------------------------------
1762
register RegionPtr pReg,
1771
register BoxPtr pNextRect;
1777
assert(r1 != r1End && r2 != r2End);
1779
pNextRect = REGION_TOP(pReg);
1786
* Subtrahend entirely to left of minuend: go to next subtrahend.
1790
else if (r2->x1 <= x1)
1793
* Subtrahend preceeds minuend: nuke left edge of minuend.
1799
* Minuend completely covered: advance to next minuend and
1800
* reset left fence to edge of new minuend.
1809
* Subtrahend now used up since it doesn't extend beyond
1815
else if (r2->x1 < r1->x2)
1818
* Left part of subtrahend covers part of minuend: add uncovered
1819
* part of minuend to region and skip to next subtrahend.
1822
NEWRECT(pReg, pNextRect, x1, y1, r2->x1, y2);
1828
* Minuend used up: advance to new...
1837
* Subtrahend used up
1845
* Minuend used up: add any remaining piece before advancing.
1848
NEWRECT(pReg, pNextRect, x1, y1, r1->x2, y2);
1853
} while ((r1 != r1End) && (r2 != r2End));
1857
* Add remaining minuend rectangles to region.
1862
NEWRECT(pReg, pNextRect, x1, y1, r1->x2, y2);
1871
*-----------------------------------------------------------------------
1873
* Subtract regS from regM and leave the result in regD.
1874
* S stands for subtrahend, M for minuend and D for difference.
1877
* TRUE if successful.
1880
* regD is overwritten.
1882
*-----------------------------------------------------------------------
1885
miSubtract(regD, regM, regS)
1886
register RegionPtr regD;
1887
register RegionPtr regM;
1888
register RegionPtr regS;
1890
Bool overlap; /* result ignored */
1895
/* check for trivial rejects */
1896
if (REGION_NIL(regM) || REGION_NIL(regS) ||
1897
!EXTENTCHECK(®M->extents, ®S->extents))
1899
if (REGION_NAR (regS))
1900
return miRegionBreak (regD);
1901
return miRegionCopy(regD, regM);
1903
else if (regM == regS)
1906
regD->extents.x2 = regD->extents.x1;
1907
regD->extents.y2 = regD->extents.y1;
1908
regD->data = &miEmptyData;
1912
/* Add those rectangles in region 1 that aren't in region 2,
1913
do yucky substraction for overlaps, and
1914
just throw away rectangles in region 2 that aren't in region 1 */
1915
if (!miRegionOp(regD, regM, regS, miSubtractO, TRUE, FALSE, &overlap))
1919
* Can't alter RegD's extents before we call miRegionOp because
1920
* it might be one of the source regions and miRegionOp depends
1921
* on the extents of those regions being unaltered. Besides, this
1922
* way there's no checking against rectangles that will be nuked
1923
* due to coalescing, so we have to examine fewer rectangles.
1930
/*======================================================================
1932
*====================================================================*/
1935
*-----------------------------------------------------------------------
1937
* Take a region and a box and return a region that is everything
1938
* in the box but not in the region. The careful reader will note
1939
* that this is the same as subtracting the region from the box...
1945
* newReg is overwritten.
1947
*-----------------------------------------------------------------------
1950
miInverse(newReg, reg1, invRect)
1951
RegionPtr newReg; /* Destination region */
1952
RegionPtr reg1; /* Region to invert */
1953
BoxPtr invRect; /* Bounding box for inversion */
1955
RegionRec invReg; /* Quick and dirty region made from the
1957
Bool overlap; /* result ignored */
1961
/* check for trivial rejects */
1962
if (REGION_NIL(reg1) || !EXTENTCHECK(invRect, ®1->extents))
1964
if (REGION_NAR(reg1))
1965
return miRegionBreak (newReg);
1966
newReg->extents = *invRect;
1968
newReg->data = (RegDataPtr)NULL;
1972
/* Add those rectangles in region 1 that aren't in region 2,
1973
do yucky substraction for overlaps, and
1974
just throw away rectangles in region 2 that aren't in region 1 */
1975
invReg.extents = *invRect;
1976
invReg.data = (RegDataPtr)NULL;
1977
if (!miRegionOp(newReg, &invReg, reg1, miSubtractO, TRUE, FALSE, &overlap))
1981
* Can't alter newReg's extents before we call miRegionOp because
1982
* it might be one of the source regions and miRegionOp depends
1983
* on the extents of those regions being unaltered. Besides, this
1984
* way there's no checking against rectangles that will be nuked
1985
* due to coalescing, so we have to examine fewer rectangles.
1987
miSetExtents(newReg);
1993
* RectIn(region, rect)
1994
* This routine takes a pointer to a region and a pointer to a box
1995
* and determines if the box is outside/inside/partly inside the region.
1997
* The idea is to travel through the list of rectangles trying to cover the
1998
* passed box with them. Anytime a piece of the rectangle isn't covered
1999
* by a band of rectangles, partOut is set TRUE. Any time a rectangle in
2000
* the region covers part of the box, partIn is set TRUE. The process ends
2001
* when either the box has been completely covered (we reached a band that
2002
* doesn't overlap the box, partIn is TRUE and partOut is false), the
2003
* box has been partially covered (partIn == partOut == TRUE -- because of
2004
* the banding, the first time this is true we know the box is only
2005
* partially in the region) or is outside the region (we reached a band
2006
* that doesn't overlap the box at all and partIn is false)
2010
miRectIn(region, prect)
2011
register RegionPtr region;
2012
register BoxPtr prect;
2016
register BoxPtr pbox;
2017
register BoxPtr pboxEnd;
2018
int partIn, partOut;
2022
numRects = REGION_NUM_RECTS(region);
2023
/* useful optimization */
2024
if (!numRects || !EXTENTCHECK(®ion->extents, prect))
2029
/* We know that it must be rgnIN or rgnPART */
2030
if (SUBSUMES(®ion->extents, prect))
2039
/* (x,y) starts at upper left of rect, moving to the right and down */
2043
/* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
2044
for (pbox = REGION_BOXPTR(region), pboxEnd = pbox + numRects;
2050
continue; /* getting up to speed or skipping remainder of band */
2054
partOut = TRUE; /* missed part of rectangle above */
2055
if (partIn || (pbox->y1 >= prect->y2))
2057
y = pbox->y1; /* x guaranteed to be == prect->x1 */
2061
continue; /* not far enough over yet */
2065
partOut = TRUE; /* missed part of rectangle to left */
2070
if (pbox->x1 < prect->x2)
2072
partIn = TRUE; /* definitely overlap */
2077
if (pbox->x2 >= prect->x2)
2079
y = pbox->y2; /* finished with this band */
2082
x = prect->x1; /* reset x out to left again */
2087
* Because boxes in a band are maximal width, if the first box
2088
* to overlap the rectangle doesn't completely cover it in that
2089
* band, the rectangle must be partially out, since some of it
2090
* will be uncovered in that band. partIn will have been set true
2098
return(partIn ? ((y < prect->y2) ? rgnPART : rgnIN) : rgnOUT);
2101
/* TranslateRegion(pReg, x, y)
2106
miTranslateRegion(pReg, x, y)
2107
register RegionPtr pReg;
2113
register BoxPtr pbox;
2116
pReg->extents.x1 = x1 = pReg->extents.x1 + x;
2117
pReg->extents.y1 = y1 = pReg->extents.y1 + y;
2118
pReg->extents.x2 = x2 = pReg->extents.x2 + x;
2119
pReg->extents.y2 = y2 = pReg->extents.y2 + y;
2120
if (((x1 - MINSHORT)|(y1 - MINSHORT)|(MAXSHORT - x2)|(MAXSHORT - y2)) >= 0)
2122
if (pReg->data && (nbox = pReg->data->numRects))
2124
for (pbox = REGION_BOXPTR(pReg); nbox--; pbox++)
2134
if (((x2 - MINSHORT)|(y2 - MINSHORT)|(MAXSHORT - x1)|(MAXSHORT - y1)) <= 0)
2136
pReg->extents.x2 = pReg->extents.x1;
2137
pReg->extents.y2 = pReg->extents.y1;
2139
pReg->data = &miEmptyData;
2143
pReg->extents.x1 = MINSHORT;
2144
else if (x2 > MAXSHORT)
2145
pReg->extents.x2 = MAXSHORT;
2147
pReg->extents.y1 = MINSHORT;
2148
else if (y2 > MAXSHORT)
2149
pReg->extents.y2 = MAXSHORT;
2150
if (pReg->data && (nbox = pReg->data->numRects))
2152
register BoxPtr pboxout;
2154
for (pboxout = pbox = REGION_BOXPTR(pReg); nbox--; pbox++)
2156
pboxout->x1 = x1 = pbox->x1 + x;
2157
pboxout->y1 = y1 = pbox->y1 + y;
2158
pboxout->x2 = x2 = pbox->x2 + x;
2159
pboxout->y2 = y2 = pbox->y2 + y;
2160
if (((x2 - MINSHORT)|(y2 - MINSHORT)|
2161
(MAXSHORT - x1)|(MAXSHORT - y1)) <= 0)
2163
pReg->data->numRects--;
2167
pboxout->x1 = MINSHORT;
2168
else if (x2 > MAXSHORT)
2169
pboxout->x2 = MAXSHORT;
2171
pboxout->y1 = MINSHORT;
2172
else if (y2 > MAXSHORT)
2173
pboxout->y2 = MAXSHORT;
2176
if (pboxout != pbox)
2178
if (pReg->data->numRects == 1)
2180
pReg->extents = *REGION_BOXPTR(pReg);
2182
pReg->data = (RegDataPtr)NULL;
2192
register RegionPtr dst,
2193
register RegionPtr src)
2201
if (!src->data || !src->data->size)
2204
dst->data = (RegDataPtr)NULL;
2207
if (!dst->data || (dst->data->size < src->data->numRects))
2210
dst->data = xallocData(src->data->numRects);
2212
return miRegionBreak (dst);
2214
dst->data->size = src->data->size;
2215
dst->data->numRects = src->data->numRects;
2220
miRegionReset(pReg, pBox)
2225
assert(pBox->x1<=pBox->x2);
2226
assert(pBox->y1<=pBox->y2);
2227
pReg->extents = *pBox;
2229
pReg->data = (RegDataPtr)NULL;
2233
miPointInRegion(pReg, x, y, box)
2234
register RegionPtr pReg;
2236
BoxPtr box; /* "return" value */
2238
register BoxPtr pbox, pboxEnd;
2242
numRects = REGION_NUM_RECTS(pReg);
2243
if (!numRects || !INBOX(&pReg->extents, x, y))
2247
*box = pReg->extents;
2250
for (pbox = REGION_BOXPTR(pReg), pboxEnd = pbox + numRects;
2255
continue; /* not there yet */
2256
if ((y < pbox->y1) || (x < pbox->x1))
2257
break; /* missed it */
2259
continue; /* not there yet */
2267
miRegionNotEmpty(pReg)
2271
return(!REGION_NIL(pReg));
2275
miRegionBroken(RegionPtr pReg)
2278
return (REGION_NAR(pReg));
2287
pReg->extents.x2 = pReg->extents.x1;
2288
pReg->extents.y2 = pReg->extents.y1;
2289
pReg->data = &miEmptyData;
2293
miRegionExtents(pReg)
2297
return(&pReg->extents);
2300
#define ExchangeSpans(a, b) \
2305
tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt; \
2306
tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
2309
/* ||| I should apply the merge sort code to rectangle sorting above, and see
2310
if mapping time can be improved. But right now I've been at work 12 hours,
2314
static void QuickSortSpans(
2315
register DDXPointRec spans[],
2316
register int widths[],
2317
register int numSpans)
2320
register int i, j, m;
2321
register DDXPointPtr r;
2323
/* Always called with numSpans > 1 */
2324
/* Sorts only by y, doesn't bother to sort by x */
2330
/* Do insertion sort */
2336
{ /* while i != numSpans */
2340
/* spans[i] is out of order. Move into proper location. */
2344
for (j = 0; y >= spans[j].y; j++) {}
2347
for (k = i; k != j; k--)
2349
spans[k] = spans[k-1];
2350
widths[k] = widths[k-1];
2355
} /* if out of order */
2358
} while (i != numSpans);
2362
/* Choose partition element, stick in location 0 */
2364
if (spans[m].y > spans[0].y) ExchangeSpans(m, 0);
2365
if (spans[m].y > spans[numSpans-1].y) ExchangeSpans(m, numSpans-1);
2366
if (spans[m].y > spans[0].y) ExchangeSpans(m, 0);
2369
/* Partition array */
2379
} while (i != numSpans && r->y < y);
2387
ExchangeSpans(i, j);
2390
/* Move partition element back to middle */
2391
ExchangeSpans(0, j);
2394
if (numSpans-j-1 > 1)
2395
QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1);
2397
} while (numSpans > 1);
2400
#define NextBand() \
2402
clipy1 = pboxBandStart->y1; \
2403
clipy2 = pboxBandStart->y2; \
2404
pboxBandEnd = pboxBandStart + 1; \
2405
while (pboxBandEnd != pboxLast && pboxBandEnd->y1 == clipy1) { \
2408
for (; ppt != pptLast && ppt->y < clipy1; ppt++, pwidth++) {} \
2412
Clip a list of scanlines to a region. The caller has allocated the
2413
space. FSorted is non-zero if the scanline origins are in ascending
2415
returns the number of new, clipped scanlines.
2421
register DDXPointPtr ppt,
2422
register int *pwidth,
2424
register DDXPointPtr pptNew,
2428
register DDXPointPtr pptLast;
2429
int *pwidthNewStart; /* the vengeance of Xerox! */
2430
register int y, x1, x2;
2431
register int numRects;
2434
pptLast = ppt + nspans;
2435
pwidthNewStart = pwidthNew;
2439
/* Do special fast code with clip boundaries in registers(?) */
2440
/* It doesn't pay much to make use of fSorted in this case,
2441
so we lump everything together. */
2443
register int clipx1, clipx2, clipy1, clipy2;
2445
clipx1 = prgnDst->extents.x1;
2446
clipy1 = prgnDst->extents.y1;
2447
clipx2 = prgnDst->extents.x2;
2448
clipy2 = prgnDst->extents.y2;
2450
for (; ppt != pptLast; ppt++, pwidth++)
2454
if (clipy1 <= y && y < clipy2)
2457
if (x1 < clipx1) x1 = clipx1;
2458
if (x2 > clipx2) x2 = clipx2;
2461
/* part of span in clip rectangle */
2464
*pwidthNew = x2 - x1;
2472
else if ((numRects = prgnDst->data->numRects))
2474
/* Have to clip against many boxes */
2475
BoxPtr pboxBandStart, pboxBandEnd;
2476
register BoxPtr pbox;
2477
register BoxPtr pboxLast;
2478
register int clipy1, clipy2;
2480
/* In this case, taking advantage of sorted spans gains more than
2481
the sorting costs. */
2482
if ((! fSorted) && (nspans > 1))
2483
QuickSortSpans(ppt, pwidth, nspans);
2485
pboxBandStart = REGION_BOXPTR(prgnDst);
2486
pboxLast = pboxBandStart + numRects;
2490
for (; ppt != pptLast; )
2495
/* span is in the current band */
2496
pbox = pboxBandStart;
2500
{ /* For each box in band */
2501
register int newx1, newx2;
2505
if (newx1 < pbox->x1) newx1 = pbox->x1;
2506
if (newx2 > pbox->x2) newx2 = pbox->x2;
2509
/* Part of span in clip rectangle */
2512
*pwidthNew = newx2 - newx1;
2517
} while (pbox != pboxBandEnd);
2523
/* Move to next band, adjust ppt as needed */
2524
pboxBandStart = pboxBandEnd;
2525
if (pboxBandStart == pboxLast)
2526
break; /* We're completely done */
2531
return (pwidthNew - pwidthNewStart);
2534
/* find the band in a region with the most rectangles */
2540
register BoxPtr pbox;
2541
register int nThisBand;
2542
register int nMaxBand = 0;
2546
nbox = REGION_NUM_RECTS(prgn);
2547
pbox = REGION_RECTS(prgn);
2551
yThisBand = pbox->y1;
2553
while((nbox > 0) && (pbox->y1 == yThisBand))
2559
if (nThisBand > nMaxBand)
2560
nMaxBand = nThisBand;
added
removed
mi/miregion.c
