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>
90 #define assert(expr) { \
93 ErrorF("Assertion failed file %s, line %d: %s\n", \
94 __FILE__, __LINE__, #expr); \
95 *foo = 0xdeadbeef; /* to get a backtrace */ \
102 #define good(reg) assert(RegionIsValid(reg))
105 * The functions in this file implement the Region abstraction used extensively
106 * throughout the X11 sample server. A Region is simply a set of disjoint
107 * (non-overlapping) rectangles, plus an "extent" rectangle which is the
108 * smallest single rectangle that contains all the non-overlapping rectangles.
110 * A Region is implemented as a "y-x-banded" array of rectangles. This array
111 * imposes two degrees of order. First, all rectangles are sorted by top side
112 * y coordinate first (y1), and then by left side x coordinate (x1).
114 * Furthermore, the rectangles are grouped into "bands". Each rectangle in a
115 * band has the same top y coordinate (y1), and each has the same bottom y
116 * coordinate (y2). Thus all rectangles in a band differ only in their left
117 * and right side (x1 and x2). Bands are implicit in the array of rectangles:
118 * there is no separate list of band start pointers.
120 * The y-x band representation does not minimize rectangles. In particular,
121 * if a rectangle vertically crosses a band (the rectangle has scanlines in
122 * the y1 to y2 area spanned by the band), then the rectangle may be broken
123 * down into two or more smaller rectangles stacked one atop the other.
125 * ----------- -----------
127 * | | -------- ----------- --------
128 * | | | | in y-x banded | | | | band 1
129 * | | | | form is | | | |
130 * ----------- | | ----------- --------
134 * An added constraint on the rectangles is that they must cover as much
135 * horizontal area as possible: no two rectangles within a band are allowed
138 * Whenever possible, bands will be merged together to cover a greater vertical
139 * distance (and thus reduce the number of rectangles). Two bands can be merged
140 * only if the bottom of one touches the top of the other and they have
141 * rectangles in the same places (of the same width, of course).
143 * Adam de Boor wrote most of the original region code. Joel McCormack
144 * substantially modified or rewrote most of the core arithmetic routines,
145 * and added RegionValidate in order to support several speed improvements
146 * to miValidateTree. Bob Scheifler changed the representation to be more
147 * compact when empty or a single rectangle, and did a bunch of gratuitous
151 /* true iff two Boxes overlap */
152 #define EXTENTCHECK(r1,r2) \
153 (!( ((r1)->x2 <= (r2)->x1) || \
154 ((r1)->x1 >= (r2)->x2) || \
155 ((r1)->y2 <= (r2)->y1) || \
156 ((r1)->y1 >= (r2)->y2) ) )
158 /* true iff (x,y) is in Box */
159 #define INBOX(r,x,y) \
165 /* true iff Box r1 contains Box r2 */
166 #define SUBSUMES(r1,r2) \
167 ( ((r1)->x1 <= (r2)->x1) && \
168 ((r1)->x2 >= (r2)->x2) && \
169 ((r1)->y1 <= (r2)->y1) && \
170 ((r1)->y2 >= (r2)->y2) )
172 #define xallocData(n) malloc(RegionSizeof(n))
173 #define xfreeData(reg) if ((reg)->data && (reg)->data->size) free((reg)->data)
175 #define RECTALLOC_BAIL(pReg,n,bail) \
176 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
177 if (!RegionRectAlloc(pReg, n)) { goto bail; }
179 #define RECTALLOC(pReg,n) \
180 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
181 if (!RegionRectAlloc(pReg, n)) { return FALSE; }
183 #define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \
185 pNextRect->x1 = nx1; \
186 pNextRect->y1 = ny1; \
187 pNextRect->x2 = nx2; \
188 pNextRect->y2 = ny2; \
192 #define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \
194 if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
196 if (!RegionRectAlloc(pReg, 1)) \
198 pNextRect = RegionTop(pReg); \
200 ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \
201 pReg->data->numRects++; \
202 assert(pReg->data->numRects<=pReg->data->size); \
205 #define DOWNSIZE(reg,numRects) \
206 if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
208 RegDataPtr NewData; \
209 NewData = (RegDataPtr)realloc((reg)->data, RegionSizeof(numRects)); \
212 NewData->size = (numRects); \
213 (reg)->data = NewData; \
217 BoxRec RegionEmptyBox
= { 0, 0, 0, 0 };
218 RegDataRec RegionEmptyData
= { 0, 0 };
220 RegDataRec RegionBrokenData
= { 0, 0 };
221 static RegionRec RegionBrokenRegion
= { {0, 0, 0, 0}, &RegionBrokenData
};
226 pixman_region_set_static_pointers(&RegionEmptyBox
, &RegionEmptyData
,
230 /*****************************************************************
231 * RegionCreate(rect, size)
232 * This routine does a simple malloc to make a structure of
233 * REGION of "size" number of rectangles.
234 *****************************************************************/
237 RegionCreate(BoxPtr rect
, int size
)
241 pReg
= (RegionPtr
) malloc(sizeof(RegionRec
));
243 return &RegionBrokenRegion
;
245 RegionInit(pReg
, rect
, size
);
251 RegionDestroy(RegionPtr pReg
)
253 pixman_region_fini(pReg
);
254 if (pReg
!= &RegionBrokenRegion
)
259 RegionDuplicate(RegionPtr pOld
)
263 pNew
= RegionCreate(&pOld
->extents
, 0);
266 if (!RegionCopy(pNew
, pOld
)) {
274 RegionPrint(RegionPtr rgn
)
280 num
= RegionNumRects(rgn
);
281 size
= RegionSize(rgn
);
282 rects
= RegionRects(rgn
);
283 ErrorF("[mi] num: %d size: %d\n", num
, size
);
284 ErrorF("[mi] extents: %d %d %d %d\n",
285 rgn
->extents
.x1
, rgn
->extents
.y1
, rgn
->extents
.x2
, rgn
->extents
.y2
);
286 for (i
= 0; i
< num
; i
++)
287 ErrorF("[mi] %d %d %d %d \n",
288 rects
[i
].x1
, rects
[i
].y1
, rects
[i
].x2
, rects
[i
].y2
);
294 RegionIsValid(RegionPtr reg
)
298 if ((reg
->extents
.x1
> reg
->extents
.x2
) ||
299 (reg
->extents
.y1
> reg
->extents
.y2
))
301 numRects
= RegionNumRects(reg
);
303 return ((reg
->extents
.x1
== reg
->extents
.x2
) &&
304 (reg
->extents
.y1
== reg
->extents
.y2
) &&
305 (reg
->data
->size
|| (reg
->data
== &RegionEmptyData
)));
306 else if (numRects
== 1)
312 pboxP
= RegionRects(reg
);
314 box
.y2
= pboxP
[numRects
- 1].y2
;
316 for (i
= numRects
; --i
> 0; pboxP
++, pboxN
++) {
317 if ((pboxN
->x1
>= pboxN
->x2
) || (pboxN
->y1
>= pboxN
->y2
))
319 if (pboxN
->x1
< box
.x1
)
321 if (pboxN
->x2
> box
.x2
)
323 if ((pboxN
->y1
< pboxP
->y1
) ||
324 ((pboxN
->y1
== pboxP
->y1
) &&
325 ((pboxN
->x1
< pboxP
->x2
) || (pboxN
->y2
!= pboxP
->y2
))))
328 return ((box
.x1
== reg
->extents
.x1
) &&
329 (box
.x2
== reg
->extents
.x2
) &&
330 (box
.y1
== reg
->extents
.y1
) && (box
.y2
== reg
->extents
.y2
));
336 RegionBreak(RegionPtr pReg
)
339 pReg
->extents
= RegionEmptyBox
;
340 pReg
->data
= &RegionBrokenData
;
345 RegionRectAlloc(RegionPtr pRgn
, int n
)
351 pRgn
->data
= xallocData(n
);
353 return RegionBreak(pRgn
);
354 pRgn
->data
->numRects
= 1;
355 *RegionBoxptr(pRgn
) = pRgn
->extents
;
357 else if (!pRgn
->data
->size
) {
358 pRgn
->data
= xallocData(n
);
360 return RegionBreak(pRgn
);
361 pRgn
->data
->numRects
= 0;
365 n
= pRgn
->data
->numRects
;
366 if (n
> 500) /* XXX pick numbers out of a hat */
369 n
+= pRgn
->data
->numRects
;
370 data
= (RegDataPtr
) realloc(pRgn
->data
, RegionSizeof(n
));
372 return RegionBreak(pRgn
);
375 pRgn
->data
->size
= n
;
379 /*======================================================================
380 * Generic Region Operator
381 *====================================================================*/
384 *-----------------------------------------------------------------------
386 * Attempt to merge the boxes in the current band with those in the
387 * previous one. We are guaranteed that the current band extends to
388 * the end of the rects array. Used only by RegionOp.
391 * The new index for the previous band.
394 * If coalescing takes place:
395 * - rectangles in the previous band will have their y2 fields
397 * - pReg->data->numRects will be decreased.
399 *-----------------------------------------------------------------------
402 RegionCoalesce(RegionPtr pReg
, /* Region to coalesce */
403 int prevStart
, /* Index of start of previous band */
405 { /* Index of start of current band */
406 BoxPtr pPrevBox
; /* Current box in previous band */
407 BoxPtr pCurBox
; /* Current box in current band */
408 int numRects
; /* Number rectangles in both bands */
409 int y2
; /* Bottom of current band */
412 * Figure out how many rectangles are in the band.
414 numRects
= curStart
- prevStart
;
415 assert(numRects
== pReg
->data
->numRects
- curStart
);
421 * The bands may only be coalesced if the bottom of the previous
422 * matches the top scanline of the current.
424 pPrevBox
= RegionBox(pReg
, prevStart
);
425 pCurBox
= RegionBox(pReg
, curStart
);
426 if (pPrevBox
->y2
!= pCurBox
->y1
)
430 * Make sure the bands have boxes in the same places. This
431 * assumes that boxes have been added in such a way that they
432 * cover the most area possible. I.e. two boxes in a band must
433 * have some horizontal space between them.
438 if ((pPrevBox
->x1
!= pCurBox
->x1
) || (pPrevBox
->x2
!= pCurBox
->x2
)) {
447 * The bands may be merged, so set the bottom y of each box
448 * in the previous band to the bottom y of the current band.
450 numRects
= curStart
- prevStart
;
451 pReg
->data
->numRects
-= numRects
;
460 /* Quicky macro to avoid trivial reject procedure calls to RegionCoalesce */
462 #define Coalesce(newReg, prevBand, curBand) \
463 if (curBand - prevBand == newReg->data->numRects - curBand) { \
464 prevBand = RegionCoalesce(newReg, prevBand, curBand); \
466 prevBand = curBand; \
470 *-----------------------------------------------------------------------
471 * RegionAppendNonO --
472 * Handle a non-overlapping band for the union and subtract operations.
473 * Just adds the (top/bottom-clipped) rectangles into the region.
474 * Doesn't have to check for subsumption or anything.
480 * pReg->data->numRects is incremented and the rectangles overwritten
481 * with the rectangles we're passed.
483 *-----------------------------------------------------------------------
486 _X_INLINE
static Bool
487 RegionAppendNonO(RegionPtr pReg
, BoxPtr r
, BoxPtr rEnd
, int y1
, int y2
)
495 assert(newRects
!= 0);
497 /* Make sure we have enough space for all rectangles to be added */
498 RECTALLOC(pReg
, newRects
);
499 pNextRect
= RegionTop(pReg
);
500 pReg
->data
->numRects
+= newRects
;
502 assert(r
->x1
< r
->x2
);
503 ADDRECT(pNextRect
, r
->x1
, y1
, r
->x2
, y2
);
510 #define FindBand(r, rBandEnd, rEnd, ry1) \
514 while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \
519 #define AppendRegions(newReg, r, rEnd) \
522 if ((newRects = rEnd - r)) { \
523 RECTALLOC(newReg, newRects); \
524 memmove((char *)RegionTop(newReg),(char *)r, \
525 newRects * sizeof(BoxRec)); \
526 newReg->data->numRects += newRects; \
531 *-----------------------------------------------------------------------
533 * Apply an operation to two regions. Called by RegionUnion, RegionInverse,
534 * RegionSubtract, RegionIntersect.... Both regions MUST have at least one
535 * rectangle, and cannot be the same object.
538 * TRUE if successful.
541 * The new region is overwritten.
542 * pOverlap set to TRUE if overlapFunc ever returns TRUE.
545 * The idea behind this function is to view the two regions as sets.
546 * Together they cover a rectangle of area that this function divides
547 * into horizontal bands where points are covered only by one region
548 * or by both. For the first case, the nonOverlapFunc is called with
549 * each the band and the band's upper and lower extents. For the
550 * second, the overlapFunc is called to process the entire band. It
551 * is responsible for clipping the rectangles in the band, though
552 * this function provides the boundaries.
553 * At the end of each band, the new region is coalesced, if possible,
554 * to reduce the number of rectangles in the region.
556 *-----------------------------------------------------------------------
559 typedef Bool (*OverlapProcPtr
) (RegionPtr pReg
,
564 short y1
, short y2
, Bool
*pOverlap
);
567 RegionOp(RegionPtr newReg
, /* Place to store result */
568 RegionPtr reg1
, /* First region in operation */
569 RegionPtr reg2
, /* 2d region in operation */
570 OverlapProcPtr overlapFunc
, /* Function to call for over-
572 Bool appendNon1
, /* Append non-overlapping bands */
574 Bool appendNon2
, /* Append non-overlapping bands */
578 BoxPtr r1
; /* Pointer into first region */
579 BoxPtr r2
; /* Pointer into 2d region */
580 BoxPtr r1End
; /* End of 1st region */
581 BoxPtr r2End
; /* End of 2d region */
582 short ybot
; /* Bottom of intersection */
583 short ytop
; /* Top of intersection */
584 RegDataPtr oldData
; /* Old data for newReg */
585 int prevBand
; /* Index of start of
586 * previous band in newReg */
587 int curBand
; /* Index of start of current
589 BoxPtr r1BandEnd
; /* End of current band in r1 */
590 BoxPtr r2BandEnd
; /* End of current band in r2 */
591 short top
; /* Top of non-overlapping band */
592 short bot
; /* Bottom of non-overlapping band */
593 int r1y1
; /* Temps for r1->y1 and r2->y1 */
599 * Break any region computed from a broken region
601 if (RegionNar(reg1
) || RegionNar(reg2
))
602 return RegionBreak(newReg
);
606 * set r1, r2, r1End and r2End appropriately, save the rectangles
607 * of the destination region until the end in case it's one of
608 * the two source regions, then mark the "new" region empty, allocating
609 * another array of rectangles for it to use.
612 r1
= RegionRects(reg1
);
613 newSize
= RegionNumRects(reg1
);
614 r1End
= r1
+ newSize
;
615 numRects
= RegionNumRects(reg2
);
616 r2
= RegionRects(reg2
);
617 r2End
= r2
+ numRects
;
622 if (((newReg
== reg1
) && (newSize
> 1)) ||
623 ((newReg
== reg2
) && (numRects
> 1))) {
624 oldData
= newReg
->data
;
625 newReg
->data
= &RegionEmptyData
;
627 /* guess at new size */
628 if (numRects
> newSize
)
632 newReg
->data
= &RegionEmptyData
;
633 else if (newReg
->data
->size
)
634 newReg
->data
->numRects
= 0;
635 if (newSize
> newReg
->data
->size
)
636 if (!RegionRectAlloc(newReg
, newSize
))
641 * In the upcoming loop, ybot and ytop serve different functions depending
642 * on whether the band being handled is an overlapping or non-overlapping
644 * In the case of a non-overlapping band (only one of the regions
645 * has points in the band), ybot is the bottom of the most recent
646 * intersection and thus clips the top of the rectangles in that band.
647 * ytop is the top of the next intersection between the two regions and
648 * serves to clip the bottom of the rectangles in the current band.
649 * For an overlapping band (where the two regions intersect), ytop clips
650 * the top of the rectangles of both regions and ybot clips the bottoms.
653 ybot
= min(r1
->y1
, r2
->y1
);
656 * prevBand serves to mark the start of the previous band so rectangles
657 * can be coalesced into larger rectangles. qv. RegionCoalesce, above.
658 * In the beginning, there is no previous band, so prevBand == curBand
659 * (curBand is set later on, of course, but the first band will always
660 * start at index 0). prevBand and curBand must be indices because of
661 * the possible expansion, and resultant moving, of the new region's
662 * array of rectangles.
668 * This algorithm proceeds one source-band (as opposed to a
669 * destination band, which is determined by where the two regions
670 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
671 * rectangle after the last one in the current band for their
672 * respective regions.
677 FindBand(r1
, r1BandEnd
, r1End
, r1y1
);
678 FindBand(r2
, r2BandEnd
, r2End
, r2y1
);
681 * First handle the band that doesn't intersect, if any.
683 * Note that attention is restricted to one band in the
684 * non-intersecting region at once, so if a region has n
685 * bands between the current position and the next place it overlaps
686 * the other, this entire loop will be passed through n times.
690 top
= max(r1y1
, ybot
);
691 bot
= min(r1
->y2
, r2y1
);
693 curBand
= newReg
->data
->numRects
;
694 RegionAppendNonO(newReg
, r1
, r1BandEnd
, top
, bot
);
695 Coalesce(newReg
, prevBand
, curBand
);
700 else if (r2y1
< r1y1
) {
702 top
= max(r2y1
, ybot
);
703 bot
= min(r2
->y2
, r1y1
);
705 curBand
= newReg
->data
->numRects
;
706 RegionAppendNonO(newReg
, r2
, r2BandEnd
, top
, bot
);
707 Coalesce(newReg
, prevBand
, curBand
);
717 * Now see if we've hit an intersecting band. The two bands only
718 * intersect if ybot > ytop
720 ybot
= min(r1
->y2
, r2
->y2
);
722 curBand
= newReg
->data
->numRects
;
723 (*overlapFunc
) (newReg
, r1
, r1BandEnd
, r2
, r2BandEnd
, ytop
, ybot
,
725 Coalesce(newReg
, prevBand
, curBand
);
729 * If we've finished with a band (y2 == ybot) we skip forward
730 * in the region to the next band.
737 } while (r1
!= r1End
&& r2
!= r2End
);
740 * Deal with whichever region (if any) still has rectangles left.
742 * We only need to worry about banding and coalescing for the very first
743 * band left. After that, we can just group all remaining boxes,
744 * regardless of how many bands, into one final append to the list.
747 if ((r1
!= r1End
) && appendNon1
) {
748 /* Do first nonOverlap1Func call, which may be able to coalesce */
749 FindBand(r1
, r1BandEnd
, r1End
, r1y1
);
750 curBand
= newReg
->data
->numRects
;
751 RegionAppendNonO(newReg
, r1
, r1BandEnd
, max(r1y1
, ybot
), r1
->y2
);
752 Coalesce(newReg
, prevBand
, curBand
);
753 /* Just append the rest of the boxes */
754 AppendRegions(newReg
, r1BandEnd
, r1End
);
757 else if ((r2
!= r2End
) && appendNon2
) {
758 /* Do first nonOverlap2Func call, which may be able to coalesce */
759 FindBand(r2
, r2BandEnd
, r2End
, r2y1
);
760 curBand
= newReg
->data
->numRects
;
761 RegionAppendNonO(newReg
, r2
, r2BandEnd
, max(r2y1
, ybot
), r2
->y2
);
762 Coalesce(newReg
, prevBand
, curBand
);
763 /* Append rest of boxes */
764 AppendRegions(newReg
, r2BandEnd
, r2End
);
769 if (!(numRects
= newReg
->data
->numRects
)) {
771 newReg
->data
= &RegionEmptyData
;
773 else if (numRects
== 1) {
774 newReg
->extents
= *RegionBoxptr(newReg
);
779 DOWNSIZE(newReg
, numRects
);
786 *-----------------------------------------------------------------------
787 * RegionSetExtents --
788 * Reset the extents of a region to what they should be. Called by
789 * Subtract and Intersect as they can't figure it out along the
790 * way or do so easily, as Union can.
796 * The region's 'extents' structure is overwritten.
798 *-----------------------------------------------------------------------
801 RegionSetExtents(RegionPtr pReg
)
803 BoxPtr pBox
, pBoxEnd
;
807 if (!pReg
->data
->size
) {
808 pReg
->extents
.x2
= pReg
->extents
.x1
;
809 pReg
->extents
.y2
= pReg
->extents
.y1
;
813 pBox
= RegionBoxptr(pReg
);
814 pBoxEnd
= RegionEnd(pReg
);
817 * Since pBox is the first rectangle in the region, it must have the
818 * smallest y1 and since pBoxEnd is the last rectangle in the region,
819 * it must have the largest y2, because of banding. Initialize x1 and
820 * x2 from pBox and pBoxEnd, resp., as good things to initialize them
823 pReg
->extents
.x1
= pBox
->x1
;
824 pReg
->extents
.y1
= pBox
->y1
;
825 pReg
->extents
.x2
= pBoxEnd
->x2
;
826 pReg
->extents
.y2
= pBoxEnd
->y2
;
828 assert(pReg
->extents
.y1
< pReg
->extents
.y2
);
829 while (pBox
<= pBoxEnd
) {
830 if (pBox
->x1
< pReg
->extents
.x1
)
831 pReg
->extents
.x1
= pBox
->x1
;
832 if (pBox
->x2
> pReg
->extents
.x2
)
833 pReg
->extents
.x2
= pBox
->x2
;
837 assert(pReg
->extents
.x1
< pReg
->extents
.x2
);
840 /*======================================================================
841 * Region Intersection
842 *====================================================================*/
844 *-----------------------------------------------------------------------
845 * RegionIntersectO --
846 * Handle an overlapping band for RegionIntersect.
849 * TRUE if successful.
852 * Rectangles may be added to the region.
854 *-----------------------------------------------------------------------
857 #define MERGERECT(r) \
860 /* Merge with current rectangle */ \
861 if (r->x1 < x2) *pOverlap = TRUE; \
862 if (x2 < r->x2) x2 = r->x2; \
864 /* Add current rectangle, start new one */ \
865 NEWRECT(pReg, pNextRect, x1, y1, x2, y2); \
871 /*======================================================================
873 *====================================================================*/
875 *-----------------------------------------------------------------------
877 * Handle an overlapping band for the union operation. Picks the
878 * left-most rectangle each time and merges it into the region.
881 * TRUE if successful.
884 * pReg is overwritten.
885 * pOverlap is set to TRUE if any boxes overlap.
887 *-----------------------------------------------------------------------
890 RegionUnionO(RegionPtr pReg
,
893 BoxPtr r2
, BoxPtr r2End
, short y1
, short y2
, Bool
*pOverlap
)
896 int x1
; /* left and right side of current union */
900 assert(r1
!= r1End
&& r2
!= r2End
);
902 pNextRect
= RegionTop(pReg
);
904 /* Start off current rectangle */
905 if (r1
->x1
< r2
->x1
) {
915 while (r1
!= r1End
&& r2
!= r2End
) {
922 /* Finish off whoever (if any) is left */
926 } while (r1
!= r1End
);
928 else if (r2
!= r2End
) {
931 } while (r2
!= r2End
);
934 /* Add current rectangle */
935 NEWRECT(pReg
, pNextRect
, x1
, y1
, x2
, y2
);
940 /*======================================================================
941 * Batch Rectangle Union
942 *====================================================================*/
945 *-----------------------------------------------------------------------
948 * "Append" the rgn rectangles onto the end of dstrgn, maintaining
949 * knowledge of YX-banding when it's easy. Otherwise, dstrgn just
950 * becomes a non-y-x-banded random collection of rectangles, and not
951 * yet a true region. After a sequence of appends, the caller must
952 * call RegionValidate to ensure that a valid region is constructed.
955 * TRUE if successful.
958 * dstrgn is modified if rgn has rectangles.
962 RegionAppend(RegionPtr dstrgn
, RegionPtr rgn
)
964 int numRects
, dnumRects
, size
;
969 return RegionBreak(dstrgn
);
971 if (!rgn
->data
&& (dstrgn
->data
== &RegionEmptyData
)) {
972 dstrgn
->extents
= rgn
->extents
;
977 numRects
= RegionNumRects(rgn
);
982 dnumRects
= RegionNumRects(dstrgn
);
983 if (!dnumRects
&& (size
< 200))
984 size
= 200; /* XXX pick numbers out of a hat */
985 RECTALLOC(dstrgn
, size
);
986 old
= RegionRects(rgn
);
988 dstrgn
->extents
= rgn
->extents
;
989 else if (dstrgn
->extents
.x2
> dstrgn
->extents
.x1
) {
993 last
= RegionBoxptr(dstrgn
) + (dnumRects
- 1);
994 if ((first
->y1
> last
->y2
) ||
995 ((first
->y1
== last
->y1
) && (first
->y2
== last
->y2
) &&
996 (first
->x1
> last
->x2
))) {
997 if (rgn
->extents
.x1
< dstrgn
->extents
.x1
)
998 dstrgn
->extents
.x1
= rgn
->extents
.x1
;
999 if (rgn
->extents
.x2
> dstrgn
->extents
.x2
)
1000 dstrgn
->extents
.x2
= rgn
->extents
.x2
;
1001 dstrgn
->extents
.y2
= rgn
->extents
.y2
;
1004 first
= RegionBoxptr(dstrgn
);
1005 last
= old
+ (numRects
- 1);
1006 if ((first
->y1
> last
->y2
) ||
1007 ((first
->y1
== last
->y1
) && (first
->y2
== last
->y2
) &&
1008 (first
->x1
> last
->x2
))) {
1010 if (rgn
->extents
.x1
< dstrgn
->extents
.x1
)
1011 dstrgn
->extents
.x1
= rgn
->extents
.x1
;
1012 if (rgn
->extents
.x2
> dstrgn
->extents
.x2
)
1013 dstrgn
->extents
.x2
= rgn
->extents
.x2
;
1014 dstrgn
->extents
.y1
= rgn
->extents
.y1
;
1017 dstrgn
->extents
.x2
= dstrgn
->extents
.x1
;
1021 new = RegionBox(dstrgn
, numRects
);
1023 *new = *RegionBoxptr(dstrgn
);
1025 memmove((char *) new, (char *) RegionBoxptr(dstrgn
),
1026 dnumRects
* sizeof(BoxRec
));
1027 new = RegionBoxptr(dstrgn
);
1030 new = RegionBoxptr(dstrgn
) + dnumRects
;
1034 memmove((char *) new, (char *) old
, numRects
* sizeof(BoxRec
));
1035 dstrgn
->data
->numRects
+= numRects
;
1039 #define ExchangeRects(a, b) \
1043 rects[a] = rects[b]; \
1048 QuickSortRects(BoxRec rects
[], int numRects
)
1055 /* Always called with numRects > 1 */
1058 if (numRects
== 2) {
1059 if (rects
[0].y1
> rects
[1].y1
||
1060 (rects
[0].y1
== rects
[1].y1
&& rects
[0].x1
> rects
[1].x1
))
1061 ExchangeRects(0, 1);
1065 /* Choose partition element, stick in location 0 */
1066 ExchangeRects(0, numRects
>> 1);
1070 /* Partition array */
1078 } while (i
!= numRects
&&
1079 (r
->y1
< y1
|| (r
->y1
== y1
&& r
->x1
< x1
)));
1084 } while (y1
< r
->y1
|| (y1
== r
->y1
&& x1
< r
->x1
));
1086 ExchangeRects(i
, j
);
1089 /* Move partition element back to middle */
1090 ExchangeRects(0, j
);
1093 if (numRects
- j
- 1 > 1)
1094 QuickSortRects(&rects
[j
+ 1], numRects
- j
- 1);
1096 } while (numRects
> 1);
1100 *-----------------------------------------------------------------------
1103 * Take a ``region'' which is a non-y-x-banded random collection of
1104 * rectangles, and compute a nice region which is the union of all the
1108 * TRUE if successful.
1111 * The passed-in ``region'' may be modified.
1112 * pOverlap set to TRUE if any retangles overlapped, else FALSE;
1115 * Step 1. Sort the rectangles into ascending order with primary key y1
1116 * and secondary key x1.
1118 * Step 2. Split the rectangles into the minimum number of proper y-x
1119 * banded regions. This may require horizontally merging
1120 * rectangles, and vertically coalescing bands. With any luck,
1121 * this step in an identity tranformation (ala the Box widget),
1122 * or a coalescing into 1 box (ala Menus).
1124 * Step 3. Merge the separate regions down to a single region by calling
1125 * Union. Maximize the work each Union call does by using
1128 *-----------------------------------------------------------------------
1132 RegionValidate(RegionPtr badreg
, Bool
*pOverlap
)
1134 /* Descriptor for regions under construction in Step 2. */
1141 int numRects
; /* Original numRects for badreg */
1142 RegionInfo
*ri
; /* Array of current regions */
1143 int numRI
; /* Number of entries used in ri */
1144 int sizeRI
; /* Number of entries available in ri */
1145 int i
; /* Index into rects */
1146 int j
; /* Index into ri */
1147 RegionInfo
*rit
; /* &ri[j] */
1148 RegionPtr reg
; /* ri[j].reg */
1149 BoxPtr box
; /* Current box in rects */
1150 BoxPtr riBox
; /* Last box in ri[j].reg */
1151 RegionPtr hreg
; /* ri[j_half].reg */
1155 if (!badreg
->data
) {
1159 numRects
= badreg
->data
->numRects
;
1161 if (RegionNar(badreg
))
1166 if (badreg
->extents
.x1
< badreg
->extents
.x2
) {
1167 if ((numRects
) == 1) {
1169 badreg
->data
= (RegDataPtr
) NULL
;
1172 DOWNSIZE(badreg
, numRects
);
1178 /* Step 1: Sort the rects array into ascending (y1, x1) order */
1179 QuickSortRects(RegionBoxptr(badreg
), numRects
);
1181 /* Step 2: Scatter the sorted array into the minimum number of regions */
1183 /* Set up the first region to be the first rectangle in badreg */
1184 /* Note that step 2 code will never overflow the ri[0].reg rects array */
1185 ri
= (RegionInfo
*) malloc(4 * sizeof(RegionInfo
));
1187 return RegionBreak(badreg
);
1192 ri
[0].reg
= *badreg
;
1193 box
= RegionBoxptr(&ri
[0].reg
);
1194 ri
[0].reg
.extents
= *box
;
1195 ri
[0].reg
.data
->numRects
= 1;
1197 /* Now scatter rectangles into the minimum set of valid regions. If the
1198 next rectangle to be added to a region would force an existing rectangle
1199 in the region to be split up in order to maintain y-x banding, just
1200 forget it. Try the next region. If it doesn't fit cleanly into any
1201 region, make a new one. */
1203 for (i
= numRects
; --i
> 0;) {
1205 /* Look for a region to append box to */
1206 for (j
= numRI
, rit
= ri
; --j
>= 0; rit
++) {
1208 riBox
= RegionEnd(reg
);
1210 if (box
->y1
== riBox
->y1
&& box
->y2
== riBox
->y2
) {
1211 /* box is in same band as riBox. Merge or append it */
1212 if (box
->x1
<= riBox
->x2
) {
1213 /* Merge it with riBox */
1214 if (box
->x1
< riBox
->x2
)
1216 if (box
->x2
> riBox
->x2
)
1217 riBox
->x2
= box
->x2
;
1220 RECTALLOC_BAIL(reg
, 1, bail
);
1221 *RegionTop(reg
) = *box
;
1222 reg
->data
->numRects
++;
1224 goto NextRect
; /* So sue me */
1226 else if (box
->y1
>= riBox
->y2
) {
1227 /* Put box into new band */
1228 if (reg
->extents
.x2
< riBox
->x2
)
1229 reg
->extents
.x2
= riBox
->x2
;
1230 if (reg
->extents
.x1
> box
->x1
)
1231 reg
->extents
.x1
= box
->x1
;
1232 Coalesce(reg
, rit
->prevBand
, rit
->curBand
);
1233 rit
->curBand
= reg
->data
->numRects
;
1234 RECTALLOC_BAIL(reg
, 1, bail
);
1235 *RegionTop(reg
) = *box
;
1236 reg
->data
->numRects
++;
1239 /* Well, this region was inappropriate. Try the next one. */
1242 /* Uh-oh. No regions were appropriate. Create a new one. */
1243 if (sizeRI
== numRI
) {
1244 /* Oops, allocate space for new region information */
1246 rit
= (RegionInfo
*) realloc(ri
, sizeRI
* sizeof(RegionInfo
));
1255 rit
->reg
.extents
= *box
;
1256 rit
->reg
.data
= NULL
;
1257 if (!RegionRectAlloc(&rit
->reg
, (i
+ numRI
) / numRI
)) /* MUST force allocation */
1262 /* Make a final pass over each region in order to Coalesce and set
1263 extents.x2 and extents.y2 */
1265 for (j
= numRI
, rit
= ri
; --j
>= 0; rit
++) {
1267 riBox
= RegionEnd(reg
);
1268 reg
->extents
.y2
= riBox
->y2
;
1269 if (reg
->extents
.x2
< riBox
->x2
)
1270 reg
->extents
.x2
= riBox
->x2
;
1271 Coalesce(reg
, rit
->prevBand
, rit
->curBand
);
1272 if (reg
->data
->numRects
== 1) { /* keep unions happy below */
1278 /* Step 3: Union all regions into a single region */
1280 int half
= numRI
/ 2;
1282 for (j
= numRI
& 1; j
< (half
+ (numRI
& 1)); j
++) {
1284 hreg
= &ri
[j
+ half
].reg
;
1285 if (!RegionOp(reg
, reg
, hreg
, RegionUnionO
, TRUE
, TRUE
, pOverlap
))
1287 if (hreg
->extents
.x1
< reg
->extents
.x1
)
1288 reg
->extents
.x1
= hreg
->extents
.x1
;
1289 if (hreg
->extents
.y1
< reg
->extents
.y1
)
1290 reg
->extents
.y1
= hreg
->extents
.y1
;
1291 if (hreg
->extents
.x2
> reg
->extents
.x2
)
1292 reg
->extents
.x2
= hreg
->extents
.x2
;
1293 if (hreg
->extents
.y2
> reg
->extents
.y2
)
1294 reg
->extents
.y2
= hreg
->extents
.y2
;
1299 *badreg
= ri
[0].reg
;
1304 for (i
= 0; i
< numRI
; i
++)
1305 xfreeData(&ri
[i
].reg
);
1307 return RegionBreak(badreg
);
1311 RegionFromRects(int nrects
, xRectangle
*prect
, int ctype
)
1320 pRgn
= RegionCreate(NullBox
, 0);
1321 if (RegionNar(pRgn
))
1328 if ((x2
= x1
+ (int) prect
->width
) > MAXSHORT
)
1330 if ((y2
= y1
+ (int) prect
->height
) > MAXSHORT
)
1332 if (x1
!= x2
&& y1
!= y2
) {
1333 pRgn
->extents
.x1
= x1
;
1334 pRgn
->extents
.y1
= y1
;
1335 pRgn
->extents
.x2
= x2
;
1336 pRgn
->extents
.y2
= y2
;
1341 pData
= xallocData(nrects
);
1346 pBox
= (BoxPtr
) (pData
+ 1);
1347 for (i
= nrects
; --i
>= 0; prect
++) {
1350 if ((x2
= x1
+ (int) prect
->width
) > MAXSHORT
)
1352 if ((y2
= y1
+ (int) prect
->height
) > MAXSHORT
)
1354 if (x1
!= x2
&& y1
!= y2
) {
1362 if (pBox
!= (BoxPtr
) (pData
+ 1)) {
1363 pData
->size
= nrects
;
1364 pData
->numRects
= pBox
- (BoxPtr
) (pData
+ 1);
1366 if (ctype
!= CT_YXBANDED
) {
1367 Bool overlap
; /* result ignored */
1369 pRgn
->extents
.x1
= pRgn
->extents
.x2
= 0;
1370 RegionValidate(pRgn
, &overlap
);
1373 RegionSetExtents(pRgn
);