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.
25 Copyright 1987, 1988, 1989 by
26 Digital Equipment Corporation, Maynard, Massachusetts.
30 Permission to use, copy, modify, and distribute this software and its
31 documentation for any purpose and without fee is hereby granted,
32 provided that the above copyright notice appear in all copies and that
33 both that copyright notice and this permission notice appear in
34 supporting documentation, and that the name of Digital not be
35 used in advertising or publicity pertaining to distribution of the
36 software without specific, written prior permission.
38 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
39 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
40 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
41 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
42 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
43 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
46 ******************************************************************/
53 struct pixman_region16_data {
56 /* pixman_box16_t rects[size]; in memory but not explicitly declared */
59 typedef struct pixman_region16_point {
61 } pixman_region16_point_t;
63 #define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)
65 #define PIXREGION_NAR(reg) ((reg)->data == &pixman_brokendata)
66 #define PIXREGION_NUM_RECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)
67 #define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)
68 #define PIXREGION_RECTS(reg) ((reg)->data ? (pixman_box16_t *)((reg)->data + 1) \
70 #define PIXREGION_BOXPTR(reg) ((pixman_box16_t *)((reg)->data + 1))
71 #define PIXREGION_BOX(reg,i) (&PIXREGION_BOXPTR(reg)[i])
72 #define PIXREGION_TOP(reg) PIXREGION_BOX(reg, (reg)->data->numRects)
73 #define PIXREGION_END(reg) PIXREGION_BOX(reg, (reg)->data->numRects - 1)
74 #define PIXREGION_SZOF(n) (sizeof(pixman_region16_data_t) + ((n) * sizeof(pixman_box16_t)))
78 #ifdef DEBUG_PIXREGION
79 #define assert(expr) {if (!(expr)) \
80 FatalError("Assertion failed file %s, line %d: expr\n", \
81 __FILE__, __LINE__); }
86 #define good(reg) assert(pixman_region16_valid(reg))
89 #define MIN(a,b) ((a) < (b) ? (a) : (b))
91 #define MAX(a,b) ((a) > (b) ? (a) : (b))
93 static pixman_box16_t pixman_region_emptyBox = {0, 0, 0, 0};
94 static pixman_region16_data_t pixman_region_emptyData = {0, 0};
95 static pixman_region16_data_t pixman_brokendata = {0, 0};
98 pixman_break (pixman_region16_t *pReg);
101 * The functions in this file implement the Region abstraction used extensively
102 * throughout the X11 sample server. A Region is simply a set of disjoint
103 * (non-overlapping) rectangles, plus an "extent" rectangle which is the
104 * smallest single rectangle that contains all the non-overlapping rectangles.
106 * A Region is implemented as a "y-x-banded" array of rectangles. This array
107 * imposes two degrees of order. First, all rectangles are sorted by top side
108 * y coordinate first (y1), and then by left side x coordinate (x1).
110 * Furthermore, the rectangles are grouped into "bands". Each rectangle in a
111 * band has the same top y coordinate (y1), and each has the same bottom y
112 * coordinate (y2). Thus all rectangles in a band differ only in their left
113 * and right side (x1 and x2). Bands are implicit in the array of rectangles:
114 * there is no separate list of band start pointers.
116 * The y-x band representation does not minimize rectangles. In particular,
117 * if a rectangle vertically crosses a band (the rectangle has scanlines in
118 * the y1 to y2 area spanned by the band), then the rectangle may be broken
119 * down into two or more smaller rectangles stacked one atop the other.
121 * ----------- -----------
123 * | | -------- ----------- --------
124 * | | | | in y-x banded | | | | band 1
125 * | | | | form is | | | |
126 * ----------- | | ----------- --------
130 * An added constraint on the rectangles is that they must cover as much
131 * horizontal area as possible: no two rectangles within a band are allowed
134 * Whenever possible, bands will be merged together to cover a greater vertical
135 * distance (and thus reduce the number of rectangles). Two bands can be merged
136 * only if the bottom of one touches the top of the other and they have
137 * rectangles in the same places (of the same width, of course).
139 * Adam de Boor wrote most of the original region code. Joel McCormack
140 * substantially modified or rewrote most of the core arithmetic routines, and
141 * added pixman_region_validate in order to support several speed improvements to
142 * pixman_region_validateTree. Bob Scheifler changed the representation to be more
143 * compact when empty or a single rectangle, and did a bunch of gratuitous
144 * reformatting. Carl Worth did further gratuitous reformatting while re-merging
145 * the server and client region code into libpixregion.
148 /* true iff two Boxes overlap */
149 #define EXTENTCHECK(r1,r2) \
150 (!( ((r1)->x2 <= (r2)->x1) || \
151 ((r1)->x1 >= (r2)->x2) || \
152 ((r1)->y2 <= (r2)->y1) || \
153 ((r1)->y1 >= (r2)->y2) ) )
155 /* true iff (x,y) is in Box */
156 #define INBOX(r,x,y) \
162 /* true iff Box r1 contains Box r2 */
163 #define SUBSUMES(r1,r2) \
164 ( ((r1)->x1 <= (r2)->x1) && \
165 ((r1)->x2 >= (r2)->x2) && \
166 ((r1)->y1 <= (r2)->y1) && \
167 ((r1)->y2 >= (r2)->y2) )
169 #define allocData(n) malloc(PIXREGION_SZOF(n))
170 #define freeData(reg) if ((reg)->data && (reg)->data->size) free((reg)->data)
172 #define RECTALLOC_BAIL(pReg,n,bail) \
173 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
174 if (!pixman_rect_alloc(pReg, n)) { goto bail; }
176 #define RECTALLOC(pReg,n) \
177 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
178 if (!pixman_rect_alloc(pReg, n)) { return FALSE; }
180 #define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \
182 pNextRect->x1 = nx1; \
183 pNextRect->y1 = ny1; \
184 pNextRect->x2 = nx2; \
185 pNextRect->y2 = ny2; \
189 #define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \
191 if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
193 if (!pixman_rect_alloc(pReg, 1)) \
195 pNextRect = PIXREGION_TOP(pReg); \
197 ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \
198 pReg->data->numRects++; \
199 assert(pReg->data->numRects<=pReg->data->size); \
202 #define DOWNSIZE(reg,numRects) \
203 if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
205 pixman_region16_data_t * NewData; \
206 NewData = (pixman_region16_data_t *)realloc((reg)->data, PIXREGION_SZOF(numRects)); \
209 NewData->size = (numRects); \
210 (reg)->data = NewData; \
214 #ifdef DEBUG_PIXREGION
216 pixman_region16_print(rgn)
217 pixman_region16_t * rgn;
221 pixman_box16_t * rects;
223 num = PIXREGION_NUM_RECTS(rgn);
224 size = PIXREGION_SIZE(rgn);
225 rects = PIXREGION_RECTS(rgn);
226 ErrorF("num: %d size: %d\n", num, size);
227 ErrorF("extents: %d %d %d %d\n",
228 rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
229 for (i = 0; i < num; i++)
230 ErrorF("%d %d %d %d \n",
231 rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
237 pixman_region16_tsEqual(reg1, reg2)
238 pixman_region16_t * reg1;
239 pixman_region16_t * reg2;
242 pixman_box16_t * rects1, rects2;
244 if (reg1->extents.x1 != reg2->extents.x1) return FALSE;
245 if (reg1->extents.x2 != reg2->extents.x2) return FALSE;
246 if (reg1->extents.y1 != reg2->extents.y1) return FALSE;
247 if (reg1->extents.y2 != reg2->extents.y2) return FALSE;
248 if (PIXREGION_NUM_RECTS(reg1) != PIXREGION_NUM_RECTS(reg2)) return FALSE;
250 rects1 = PIXREGION_RECTS(reg1);
251 rects2 = PIXREGION_RECTS(reg2);
252 for (i = 0; i != PIXREGION_NUM_RECTS(reg1); i++) {
253 if (rects1[i].x1 != rects2[i].x1) return FALSE;
254 if (rects1[i].x2 != rects2[i].x2) return FALSE;
255 if (rects1[i].y1 != rects2[i].y1) return FALSE;
256 if (rects1[i].y2 != rects2[i].y2) return FALSE;
262 pixman_region16_valid(reg)
263 pixman_region16_t * reg;
267 if ((reg->extents.x1 > reg->extents.x2) ||
268 (reg->extents.y1 > reg->extents.y2))
270 numRects = PIXREGION_NUM_RECTS(reg);
272 return ((reg->extents.x1 == reg->extents.x2) &&
273 (reg->extents.y1 == reg->extents.y2) &&
274 (reg->data->size || (reg->data == &pixman_region_emptyData)));
275 else if (numRects == 1)
279 pixman_box16_t * pboxP, pboxN;
282 pboxP = PIXREGION_RECTS(reg);
284 box.y2 = pboxP[numRects-1].y2;
286 for (i = numRects; --i > 0; pboxP++, pboxN++)
288 if ((pboxN->x1 >= pboxN->x2) ||
289 (pboxN->y1 >= pboxN->y2))
291 if (pboxN->x1 < box.x1)
293 if (pboxN->x2 > box.x2)
295 if ((pboxN->y1 < pboxP->y1) ||
296 ((pboxN->y1 == pboxP->y1) &&
297 ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2))))
300 return ((box.x1 == reg->extents.x1) &&
301 (box.x2 == reg->extents.x2) &&
302 (box.y1 == reg->extents.y1) &&
303 (box.y2 == reg->extents.y2));
307 #endif /* DEBUG_PIXREGION */
310 pixman_region_init (pixman_region16_t *region)
312 region->extents = pixman_region_emptyBox;
313 region->data = &pixman_region_emptyData;
317 pixman_region_init_rect (pixman_region16_t *region,
318 int x, int y, unsigned int width, unsigned int height)
320 region->extents.x1 = x;
321 region->extents.y1 = y;
322 region->extents.x2 = x + width;
323 region->extents.y2 = y + height;
328 pixman_region_init_with_extents (pixman_region16_t *region, pixman_box16_t *extents)
330 region->extents = *extents;
335 pixman_region_fini (pixman_region16_t *region)
342 pixman_region_num_rects (pixman_region16_t *region)
344 return PIXREGION_NUM_RECTS (region);
348 pixman_region_rects (pixman_region16_t *region)
350 return PIXREGION_RECTS (region);
353 const pixman_box16_t *
354 pixman_region_rectangles (pixman_region16_t *region,
358 *n_rects = PIXREGION_NUM_RECTS (region);
360 return PIXREGION_RECTS (region);
364 pixman_break (pixman_region16_t *region)
367 region->extents = pixman_region_emptyBox;
368 region->data = &pixman_brokendata;
373 pixman_rect_alloc (pixman_region16_t * region, int n)
375 pixman_region16_data_t *data;
380 region->data = allocData(n);
382 return pixman_break (region);
383 region->data->numRects = 1;
384 *PIXREGION_BOXPTR(region) = region->extents;
386 else if (!region->data->size)
388 region->data = allocData(n);
390 return pixman_break (region);
391 region->data->numRects = 0;
397 n = region->data->numRects;
398 if (n > 500) /* XXX pick numbers out of a hat */
401 n += region->data->numRects;
402 data = (pixman_region16_data_t *)realloc(region->data, PIXREGION_SZOF(n));
404 return pixman_break (region);
407 region->data->size = n;
412 pixman_region_copy(pixman_region16_t *dst, pixman_region16_t *src)
418 dst->extents = src->extents;
419 if (!src->data || !src->data->size)
422 dst->data = src->data;
425 if (!dst->data || (dst->data->size < src->data->numRects))
428 dst->data = allocData(src->data->numRects);
430 return pixman_break (dst);
431 dst->data->size = src->data->numRects;
433 dst->data->numRects = src->data->numRects;
434 memmove((char *)PIXREGION_BOXPTR(dst),(char *)PIXREGION_BOXPTR(src),
435 dst->data->numRects * sizeof(pixman_box16_t));
439 /*======================================================================
440 * Generic Region Operator
441 *====================================================================*/
444 *-----------------------------------------------------------------------
446 * Attempt to merge the boxes in the current band with those in the
447 * previous one. We are guaranteed that the current band extends to
448 * the end of the rects array. Used only by pixman_op.
451 * The new index for the previous band.
454 * If coalescing takes place:
455 * - rectangles in the previous band will have their y2 fields
457 * - region->data->numRects will be decreased.
459 *-----------------------------------------------------------------------
463 pixman_region16_t * region, /* Region to coalesce */
464 int prevStart, /* Index of start of previous band */
465 int curStart) /* Index of start of current band */
467 pixman_box16_t * pPrevBox; /* Current box in previous band */
468 pixman_box16_t * pCurBox; /* Current box in current band */
469 int numRects; /* Number rectangles in both bands */
470 int y2; /* Bottom of current band */
472 * Figure out how many rectangles are in the band.
474 numRects = curStart - prevStart;
475 assert(numRects == region->data->numRects - curStart);
477 if (!numRects) return curStart;
480 * The bands may only be coalesced if the bottom of the previous
481 * matches the top scanline of the current.
483 pPrevBox = PIXREGION_BOX(region, prevStart);
484 pCurBox = PIXREGION_BOX(region, curStart);
485 if (pPrevBox->y2 != pCurBox->y1) return curStart;
488 * Make sure the bands have boxes in the same places. This
489 * assumes that boxes have been added in such a way that they
490 * cover the most area possible. I.e. two boxes in a band must
491 * have some horizontal space between them.
496 if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) {
505 * The bands may be merged, so set the bottom y of each box
506 * in the previous band to the bottom y of the current band.
508 numRects = curStart - prevStart;
509 region->data->numRects -= numRects;
518 /* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */
520 #define Coalesce(newReg, prevBand, curBand) \
521 if (curBand - prevBand == newReg->data->numRects - curBand) { \
522 prevBand = pixman_coalesce(newReg, prevBand, curBand); \
524 prevBand = curBand; \
528 *-----------------------------------------------------------------------
529 * pixman_region_appendNonO --
530 * Handle a non-overlapping band for the union and subtract operations.
531 * Just adds the (top/bottom-clipped) rectangles into the region.
532 * Doesn't have to check for subsumption or anything.
538 * region->data->numRects is incremented and the rectangles overwritten
539 * with the rectangles we're passed.
541 *-----------------------------------------------------------------------
544 static inline pixman_bool_t
545 pixman_region_appendNonO (
546 pixman_region16_t * region,
548 pixman_box16_t * rEnd,
552 pixman_box16_t * pNextRect;
558 assert(newRects != 0);
560 /* Make sure we have enough space for all rectangles to be added */
561 RECTALLOC(region, newRects);
562 pNextRect = PIXREGION_TOP(region);
563 region->data->numRects += newRects;
565 assert(r->x1 < r->x2);
566 ADDRECT(pNextRect, r->x1, y1, r->x2, y2);
573 #define FindBand(r, rBandEnd, rEnd, ry1) \
577 while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \
582 #define AppendRegions(newReg, r, rEnd) \
585 if ((newRects = rEnd - r)) { \
586 RECTALLOC(newReg, newRects); \
587 memmove((char *)PIXREGION_TOP(newReg),(char *)r, \
588 newRects * sizeof(pixman_box16_t)); \
589 newReg->data->numRects += newRects; \
594 *-----------------------------------------------------------------------
596 * Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,
597 * pixman_region_subtract, pixman_region_intersect.... Both regions MUST have at least one
598 * rectangle, and cannot be the same object.
601 * TRUE if successful.
604 * The new region is overwritten.
605 * pOverlap set to TRUE if overlapFunc ever returns TRUE.
608 * The idea behind this function is to view the two regions as sets.
609 * Together they cover a rectangle of area that this function divides
610 * into horizontal bands where points are covered only by one region
611 * or by both. For the first case, the nonOverlapFunc is called with
612 * each the band and the band's upper and lower extents. For the
613 * second, the overlapFunc is called to process the entire band. It
614 * is responsible for clipping the rectangles in the band, though
615 * this function provides the boundaries.
616 * At the end of each band, the new region is coalesced, if possible,
617 * to reduce the number of rectangles in the region.
619 *-----------------------------------------------------------------------
622 typedef pixman_bool_t (*OverlapProcPtr)(
623 pixman_region16_t *region,
625 pixman_box16_t *r1End,
627 pixman_box16_t *r2End,
634 pixman_region16_t *newReg, /* Place to store result */
635 pixman_region16_t * reg1, /* First region in operation */
636 pixman_region16_t * reg2, /* 2d region in operation */
637 OverlapProcPtr overlapFunc, /* Function to call for over-
639 int appendNon1, /* Append non-overlapping bands */
641 int appendNon2, /* Append non-overlapping bands */
645 pixman_box16_t * r1; /* Pointer into first region */
646 pixman_box16_t * r2; /* Pointer into 2d region */
647 pixman_box16_t * r1End; /* End of 1st region */
648 pixman_box16_t * r2End; /* End of 2d region */
649 short ybot; /* Bottom of intersection */
650 short ytop; /* Top of intersection */
651 pixman_region16_data_t * oldData; /* Old data for newReg */
652 int prevBand; /* Index of start of
653 * previous band in newReg */
654 int curBand; /* Index of start of current
656 pixman_box16_t * r1BandEnd; /* End of current band in r1 */
657 pixman_box16_t * r2BandEnd; /* End of current band in r2 */
658 short top; /* Top of non-overlapping band */
659 short bot; /* Bottom of non-overlapping band*/
660 int r1y1; /* Temps for r1->y1 and r2->y1 */
666 * Break any region computed from a broken region
668 if (PIXREGION_NAR (reg1) || PIXREGION_NAR(reg2))
669 return pixman_break (newReg);
673 * set r1, r2, r1End and r2End appropriately, save the rectangles
674 * of the destination region until the end in case it's one of
675 * the two source regions, then mark the "new" region empty, allocating
676 * another array of rectangles for it to use.
679 r1 = PIXREGION_RECTS(reg1);
680 newSize = PIXREGION_NUM_RECTS(reg1);
681 r1End = r1 + newSize;
682 numRects = PIXREGION_NUM_RECTS(reg2);
683 r2 = PIXREGION_RECTS(reg2);
684 r2End = r2 + numRects;
688 oldData = (pixman_region16_data_t *)NULL;
689 if (((newReg == reg1) && (newSize > 1)) ||
690 ((newReg == reg2) && (numRects > 1)))
692 oldData = newReg->data;
693 newReg->data = &pixman_region_emptyData;
695 /* guess at new size */
696 if (numRects > newSize)
700 newReg->data = &pixman_region_emptyData;
701 else if (newReg->data->size)
702 newReg->data->numRects = 0;
703 if (newSize > newReg->data->size) {
704 if (!pixman_rect_alloc(newReg, newSize)) {
713 * In the upcoming loop, ybot and ytop serve different functions depending
714 * on whether the band being handled is an overlapping or non-overlapping
716 * In the case of a non-overlapping band (only one of the regions
717 * has points in the band), ybot is the bottom of the most recent
718 * intersection and thus clips the top of the rectangles in that band.
719 * ytop is the top of the next intersection between the two regions and
720 * serves to clip the bottom of the rectangles in the current band.
721 * For an overlapping band (where the two regions intersect), ytop clips
722 * the top of the rectangles of both regions and ybot clips the bottoms.
725 ybot = MIN(r1->y1, r2->y1);
728 * prevBand serves to mark the start of the previous band so rectangles
729 * can be coalesced into larger rectangles. qv. pixman_coalesce, above.
730 * In the beginning, there is no previous band, so prevBand == curBand
731 * (curBand is set later on, of course, but the first band will always
732 * start at index 0). prevBand and curBand must be indices because of
733 * the possible expansion, and resultant moving, of the new region's
734 * array of rectangles.
740 * This algorithm proceeds one source-band (as opposed to a
741 * destination band, which is determined by where the two regions
742 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
743 * rectangle after the last one in the current band for their
744 * respective regions.
749 FindBand(r1, r1BandEnd, r1End, r1y1);
750 FindBand(r2, r2BandEnd, r2End, r2y1);
753 * First handle the band that doesn't intersect, if any.
755 * Note that attention is restricted to one band in the
756 * non-intersecting region at once, so if a region has n
757 * bands between the current position and the next place it overlaps
758 * the other, this entire loop will be passed through n times.
762 top = MAX(r1y1, ybot);
763 bot = MIN(r1->y2, r2y1);
765 curBand = newReg->data->numRects;
766 pixman_region_appendNonO(newReg, r1, r1BandEnd, top, bot);
767 Coalesce(newReg, prevBand, curBand);
771 } else if (r2y1 < r1y1) {
773 top = MAX(r2y1, ybot);
774 bot = MIN(r2->y2, r1y1);
776 curBand = newReg->data->numRects;
777 pixman_region_appendNonO(newReg, r2, r2BandEnd, top, bot);
778 Coalesce(newReg, prevBand, curBand);
787 * Now see if we've hit an intersecting band. The two bands only
788 * intersect if ybot > ytop
790 ybot = MIN(r1->y2, r2->y2);
792 curBand = newReg->data->numRects;
793 (* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot,
795 Coalesce(newReg, prevBand, curBand);
799 * If we've finished with a band (y2 == ybot) we skip forward
800 * in the region to the next band.
802 if (r1->y2 == ybot) r1 = r1BandEnd;
803 if (r2->y2 == ybot) r2 = r2BandEnd;
805 } while (r1 != r1End && r2 != r2End);
808 * Deal with whichever region (if any) still has rectangles left.
810 * We only need to worry about banding and coalescing for the very first
811 * band left. After that, we can just group all remaining boxes,
812 * regardless of how many bands, into one final append to the list.
815 if ((r1 != r1End) && appendNon1) {
816 /* Do first nonOverlap1Func call, which may be able to coalesce */
817 FindBand(r1, r1BandEnd, r1End, r1y1);
818 curBand = newReg->data->numRects;
819 pixman_region_appendNonO(newReg, r1, r1BandEnd, MAX(r1y1, ybot), r1->y2);
820 Coalesce(newReg, prevBand, curBand);
821 /* Just append the rest of the boxes */
822 AppendRegions(newReg, r1BandEnd, r1End);
824 } else if ((r2 != r2End) && appendNon2) {
825 /* Do first nonOverlap2Func call, which may be able to coalesce */
826 FindBand(r2, r2BandEnd, r2End, r2y1);
827 curBand = newReg->data->numRects;
828 pixman_region_appendNonO(newReg, r2, r2BandEnd, MAX(r2y1, ybot), r2->y2);
829 Coalesce(newReg, prevBand, curBand);
830 /* Append rest of boxes */
831 AppendRegions(newReg, r2BandEnd, r2End);
837 if (!(numRects = newReg->data->numRects))
840 newReg->data = &pixman_region_emptyData;
842 else if (numRects == 1)
844 newReg->extents = *PIXREGION_BOXPTR(newReg);
846 newReg->data = (pixman_region16_data_t *)NULL;
850 DOWNSIZE(newReg, numRects);
857 *-----------------------------------------------------------------------
858 * pixman_set_extents --
859 * Reset the extents of a region to what they should be. Called by
860 * pixman_region_subtract and pixman_region_intersect as they can't figure it out along the
861 * way or do so easily, as pixman_region_union can.
867 * The region's 'extents' structure is overwritten.
869 *-----------------------------------------------------------------------
872 pixman_set_extents (pixman_region16_t *region)
874 pixman_box16_t *box, *boxEnd;
878 if (!region->data->size)
880 region->extents.x2 = region->extents.x1;
881 region->extents.y2 = region->extents.y1;
885 box = PIXREGION_BOXPTR(region);
886 boxEnd = PIXREGION_END(region);
889 * Since box is the first rectangle in the region, it must have the
890 * smallest y1 and since boxEnd is the last rectangle in the region,
891 * it must have the largest y2, because of banding. Initialize x1 and
892 * x2 from box and boxEnd, resp., as good things to initialize them
895 region->extents.x1 = box->x1;
896 region->extents.y1 = box->y1;
897 region->extents.x2 = boxEnd->x2;
898 region->extents.y2 = boxEnd->y2;
900 assert(region->extents.y1 < region->extents.y2);
901 while (box <= boxEnd) {
902 if (box->x1 < region->extents.x1)
903 region->extents.x1 = box->x1;
904 if (box->x2 > region->extents.x2)
905 region->extents.x2 = box->x2;
909 assert(region->extents.x1 < region->extents.x2);
912 /*======================================================================
913 * Region Intersection
914 *====================================================================*/
916 *-----------------------------------------------------------------------
917 * pixman_region_intersectO --
918 * Handle an overlapping band for pixman_region_intersect.
921 * TRUE if successful.
924 * Rectangles may be added to the region.
926 *-----------------------------------------------------------------------
930 pixman_region_intersectO (pixman_region16_t *region,
932 pixman_box16_t *r1End,
934 pixman_box16_t *r2End,
941 pixman_box16_t * pNextRect;
943 pNextRect = PIXREGION_TOP(region);
946 assert(r1 != r1End && r2 != r2End);
949 x1 = MAX(r1->x1, r2->x1);
950 x2 = MIN(r1->x2, r2->x2);
953 * If there's any overlap between the two rectangles, add that
954 * overlap to the new region.
957 NEWRECT(region, pNextRect, x1, y1, x2, y2);
960 * Advance the pointer(s) with the leftmost right side, since the next
961 * rectangle on that list may still overlap the other region's
970 } while ((r1 != r1End) && (r2 != r2End));
976 pixman_region_intersect (pixman_region16_t * newReg,
977 pixman_region16_t * reg1,
978 pixman_region16_t * reg2)
983 /* check for trivial reject */
984 if (PIXREGION_NIL(reg1) || PIXREGION_NIL(reg2) ||
985 !EXTENTCHECK(®1->extents, ®2->extents))
987 /* Covers about 20% of all cases */
989 newReg->extents.x2 = newReg->extents.x1;
990 newReg->extents.y2 = newReg->extents.y1;
991 if (PIXREGION_NAR(reg1) || PIXREGION_NAR(reg2))
993 newReg->data = &pixman_brokendata;
997 newReg->data = &pixman_region_emptyData;
999 else if (!reg1->data && !reg2->data)
1001 /* Covers about 80% of cases that aren't trivially rejected */
1002 newReg->extents.x1 = MAX(reg1->extents.x1, reg2->extents.x1);
1003 newReg->extents.y1 = MAX(reg1->extents.y1, reg2->extents.y1);
1004 newReg->extents.x2 = MIN(reg1->extents.x2, reg2->extents.x2);
1005 newReg->extents.y2 = MIN(reg1->extents.y2, reg2->extents.y2);
1007 newReg->data = (pixman_region16_data_t *)NULL;
1009 else if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
1011 return pixman_region_copy(newReg, reg1);
1013 else if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
1015 return pixman_region_copy(newReg, reg2);
1017 else if (reg1 == reg2)
1019 return pixman_region_copy(newReg, reg1);
1023 /* General purpose intersection */
1024 int overlap; /* result ignored */
1025 if (!pixman_op(newReg, reg1, reg2, pixman_region_intersectO, FALSE, FALSE,
1028 pixman_set_extents(newReg);
1035 #define MERGERECT(r) \
1037 if (r->x1 <= x2) { \
1038 /* Merge with current rectangle */ \
1039 if (r->x1 < x2) *pOverlap = TRUE; \
1040 if (x2 < r->x2) x2 = r->x2; \
1042 /* Add current rectangle, start new one */ \
1043 NEWRECT(region, pNextRect, x1, y1, x2, y2); \
1050 /*======================================================================
1052 *====================================================================*/
1055 *-----------------------------------------------------------------------
1056 * pixman_region_unionO --
1057 * Handle an overlapping band for the union operation. Picks the
1058 * left-most rectangle each time and merges it into the region.
1061 * TRUE if successful.
1064 * region is overwritten.
1065 * pOverlap is set to TRUE if any boxes overlap.
1067 *-----------------------------------------------------------------------
1069 static pixman_bool_t
1070 pixman_region_unionO (
1071 pixman_region16_t *region,
1073 pixman_box16_t *r1End,
1075 pixman_box16_t *r2End,
1080 pixman_box16_t * pNextRect;
1081 int x1; /* left and right side of current union */
1085 assert(r1 != r1End && r2 != r2End);
1087 pNextRect = PIXREGION_TOP(region);
1089 /* Start off current rectangle */
1090 if (r1->x1 < r2->x1)
1102 while (r1 != r1End && r2 != r2End)
1104 if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
1107 /* Finish off whoever (if any) is left */
1113 } while (r1 != r1End);
1115 else if (r2 != r2End)
1120 } while (r2 != r2End);
1123 /* Add current rectangle */
1124 NEWRECT(region, pNextRect, x1, y1, x2, y2);
1129 /* Convenience function for performing union of region with a
1133 pixman_region_union_rect (pixman_region16_t *dest,
1134 pixman_region16_t *source,
1136 unsigned int width, unsigned int height)
1138 pixman_region16_t region;
1140 if (!width || !height)
1141 return pixman_region_copy (dest, source);
1143 region.extents.x1 = x;
1144 region.extents.y1 = y;
1145 region.extents.x2 = x + width;
1146 region.extents.y2 = y + height;
1148 return pixman_region_union (dest, source, ®ion);
1152 pixman_region_union (pixman_region16_t *newReg,
1153 pixman_region16_t *reg1,
1154 pixman_region16_t *reg2)
1156 int overlap; /* result ignored */
1158 /* Return TRUE if some overlap
1159 * between reg1, reg2
1164 /* checks all the simple cases */
1167 * Region 1 and 2 are the same
1171 return pixman_region_copy(newReg, reg1);
1177 if (PIXREGION_NIL(reg1))
1179 if (PIXREGION_NAR(reg1))
1180 return pixman_break (newReg);
1182 return pixman_region_copy(newReg, reg2);
1189 if (PIXREGION_NIL(reg2))
1191 if (PIXREGION_NAR(reg2))
1192 return pixman_break (newReg);
1194 return pixman_region_copy(newReg, reg1);
1199 * Region 1 completely subsumes region 2
1201 if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
1204 return pixman_region_copy(newReg, reg1);
1209 * Region 2 completely subsumes region 1
1211 if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
1214 return pixman_region_copy(newReg, reg2);
1218 if (!pixman_op(newReg, reg1, reg2, pixman_region_unionO, TRUE, TRUE, &overlap))
1221 newReg->extents.x1 = MIN(reg1->extents.x1, reg2->extents.x1);
1222 newReg->extents.y1 = MIN(reg1->extents.y1, reg2->extents.y1);
1223 newReg->extents.x2 = MAX(reg1->extents.x2, reg2->extents.x2);
1224 newReg->extents.y2 = MAX(reg1->extents.y2, reg2->extents.y2);
1229 /*======================================================================
1230 * Batch Rectangle Union
1231 *====================================================================*/
1234 *-----------------------------------------------------------------------
1235 * pixman_region_append --
1237 * "Append" the rgn rectangles onto the end of dstrgn, maintaining
1238 * knowledge of YX-banding when it's easy. Otherwise, dstrgn just
1239 * becomes a non-y-x-banded random collection of rectangles, and not
1240 * yet a true region. After a sequence of appends, the caller must
1241 * call pixman_region_validate to ensure that a valid region is
1245 * TRUE if successful.
1248 * dstrgn is modified if rgn has rectangles.
1252 pixman_region_append (pixman_region16_t * dstrgn,
1253 pixman_region16_t * rgn)
1255 int numRects, dnumRects, size;
1256 pixman_box16_t *new, *old;
1259 if (PIXREGION_NAR(rgn))
1260 return pixman_break (dstrgn);
1262 if (!rgn->data && (dstrgn->data == &pixman_region_emptyData))
1264 dstrgn->extents = rgn->extents;
1265 dstrgn->data = (pixman_region16_data_t *)NULL;
1269 numRects = PIXREGION_NUM_RECTS(rgn);
1274 dnumRects = PIXREGION_NUM_RECTS(dstrgn);
1275 if (!dnumRects && (size < 200))
1276 size = 200; /* XXX pick numbers out of a hat */
1277 RECTALLOC(dstrgn, size);
1278 old = PIXREGION_RECTS(rgn);
1280 dstrgn->extents = rgn->extents;
1281 else if (dstrgn->extents.x2 > dstrgn->extents.x1)
1283 pixman_box16_t *first, *last;
1286 last = PIXREGION_BOXPTR(dstrgn) + (dnumRects - 1);
1287 if ((first->y1 > last->y2) ||
1288 ((first->y1 == last->y1) && (first->y2 == last->y2) &&
1289 (first->x1 > last->x2)))
1291 if (rgn->extents.x1 < dstrgn->extents.x1)
1292 dstrgn->extents.x1 = rgn->extents.x1;
1293 if (rgn->extents.x2 > dstrgn->extents.x2)
1294 dstrgn->extents.x2 = rgn->extents.x2;
1295 dstrgn->extents.y2 = rgn->extents.y2;
1299 first = PIXREGION_BOXPTR(dstrgn);
1300 last = old + (numRects - 1);
1301 if ((first->y1 > last->y2) ||
1302 ((first->y1 == last->y1) && (first->y2 == last->y2) &&
1303 (first->x1 > last->x2)))
1306 if (rgn->extents.x1 < dstrgn->extents.x1)
1307 dstrgn->extents.x1 = rgn->extents.x1;
1308 if (rgn->extents.x2 > dstrgn->extents.x2)
1309 dstrgn->extents.x2 = rgn->extents.x2;
1310 dstrgn->extents.y1 = rgn->extents.y1;
1313 dstrgn->extents.x2 = dstrgn->extents.x1;
1318 new = PIXREGION_BOX(dstrgn, numRects);
1320 *new = *PIXREGION_BOXPTR(dstrgn);
1322 memmove((char *)new,(char *)PIXREGION_BOXPTR(dstrgn),
1323 dnumRects * sizeof(pixman_box16_t));
1324 new = PIXREGION_BOXPTR(dstrgn);
1327 new = PIXREGION_BOXPTR(dstrgn) + dnumRects;
1331 memmove((char *)new, (char *)old, numRects * sizeof(pixman_box16_t));
1332 dstrgn->data->numRects += numRects;
1336 #define ExchangeRects(a, b) \
1340 rects[a] = rects[b]; \
1346 pixman_box16_t rects[],
1354 /* Always called with numRects > 1 */
1360 if (rects[0].y1 > rects[1].y1 ||
1361 (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
1362 ExchangeRects(0, 1);
1366 /* Choose partition element, stick in location 0 */
1367 ExchangeRects(0, numRects >> 1);
1371 /* Partition array */
1381 } while (i != numRects &&
1382 (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
1388 } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
1390 ExchangeRects(i, j);
1393 /* Move partition element back to middle */
1394 ExchangeRects(0, j);
1397 if (numRects-j-1 > 1)
1398 QuickSortRects(&rects[j+1], numRects-j-1);
1400 } while (numRects > 1);
1404 *-----------------------------------------------------------------------
1405 * pixman_region_validate --
1407 * Take a ``region'' which is a non-y-x-banded random collection of
1408 * rectangles, and compute a nice region which is the union of all the
1412 * TRUE if successful.
1415 * The passed-in ``region'' may be modified.
1416 * pOverlap set to TRUE if any retangles overlapped,
1420 * Step 1. Sort the rectangles into ascending order with primary key y1
1421 * and secondary key x1.
1423 * Step 2. Split the rectangles into the minimum number of proper y-x
1424 * banded regions. This may require horizontally merging
1425 * rectangles, and vertically coalescing bands. With any luck,
1426 * this step in an identity transformation (ala the Box widget),
1427 * or a coalescing into 1 box (ala Menus).
1429 * Step 3. Merge the separate regions down to a single region by calling
1430 * pixman_region_union. Maximize the work each pixman_region_union call does by using
1433 *-----------------------------------------------------------------------
1437 pixman_region_validate(pixman_region16_t * badreg,
1440 /* Descriptor for regions under construction in Step 2. */
1442 pixman_region16_t reg;
1447 int numRects; /* Original numRects for badreg */
1448 RegionInfo *ri; /* Array of current regions */
1449 int numRI; /* Number of entries used in ri */
1450 int sizeRI; /* Number of entries available in ri */
1451 int i; /* Index into rects */
1452 int j; /* Index into ri */
1453 RegionInfo *rit; /* &ri[j] */
1454 pixman_region16_t * reg; /* ri[j].reg */
1455 pixman_box16_t * box; /* Current box in rects */
1456 pixman_box16_t * riBox; /* Last box in ri[j].reg */
1457 pixman_region16_t * hreg; /* ri[j_half].reg */
1458 pixman_bool_t ret = TRUE;
1466 numRects = badreg->data->numRects;
1469 if (PIXREGION_NAR(badreg))
1474 if (badreg->extents.x1 < badreg->extents.x2)
1476 if ((numRects) == 1)
1479 badreg->data = (pixman_region16_data_t *) NULL;
1483 DOWNSIZE(badreg, numRects);
1489 /* Step 1: Sort the rects array into ascending (y1, x1) order */
1490 QuickSortRects(PIXREGION_BOXPTR(badreg), numRects);
1492 /* Step 2: Scatter the sorted array into the minimum number of regions */
1494 /* Set up the first region to be the first rectangle in badreg */
1495 /* Note that step 2 code will never overflow the ri[0].reg rects array */
1496 ri = (RegionInfo *) malloc(4 * sizeof(RegionInfo));
1498 return pixman_break (badreg);
1503 ri[0].reg = *badreg;
1504 box = PIXREGION_BOXPTR(&ri[0].reg);
1505 ri[0].reg.extents = *box;
1506 ri[0].reg.data->numRects = 1;
1508 /* Now scatter rectangles into the minimum set of valid regions. If the
1509 next rectangle to be added to a region would force an existing rectangle
1510 in the region to be split up in order to maintain y-x banding, just
1511 forget it. Try the next region. If it doesn't fit cleanly into any
1512 region, make a new one. */
1514 for (i = numRects; --i > 0;)
1517 /* Look for a region to append box to */
1518 for (j = numRI, rit = ri; --j >= 0; rit++)
1521 riBox = PIXREGION_END(reg);
1523 if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
1525 /* box is in same band as riBox. Merge or append it */
1526 if (box->x1 <= riBox->x2)
1528 /* Merge it with riBox */
1529 if (box->x1 < riBox->x2) *pOverlap = TRUE;
1530 if (box->x2 > riBox->x2) riBox->x2 = box->x2;
1534 RECTALLOC_BAIL(reg, 1, bail);
1535 *PIXREGION_TOP(reg) = *box;
1536 reg->data->numRects++;
1538 goto NextRect; /* So sue me */
1540 else if (box->y1 >= riBox->y2)
1542 /* Put box into new band */
1543 if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1544 if (reg->extents.x1 > box->x1) reg->extents.x1 = box->x1;
1545 Coalesce(reg, rit->prevBand, rit->curBand);
1546 rit->curBand = reg->data->numRects;
1547 RECTALLOC_BAIL(reg, 1, bail);
1548 *PIXREGION_TOP(reg) = *box;
1549 reg->data->numRects++;
1552 /* Well, this region was inappropriate. Try the next one. */
1555 /* Uh-oh. No regions were appropriate. Create a new one. */
1556 if (sizeRI == numRI)
1558 /* Oops, allocate space for new region information */
1560 rit = (RegionInfo *) realloc(ri, sizeRI * sizeof(RegionInfo));
1569 rit->reg.extents = *box;
1570 rit->reg.data = (pixman_region16_data_t *)NULL;
1571 if (!pixman_rect_alloc(&rit->reg, (i+numRI) / numRI)) /* MUST force allocation */
1576 /* Make a final pass over each region in order to Coalesce and set
1577 extents.x2 and extents.y2 */
1579 for (j = numRI, rit = ri; --j >= 0; rit++)
1582 riBox = PIXREGION_END(reg);
1583 reg->extents.y2 = riBox->y2;
1584 if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1585 Coalesce(reg, rit->prevBand, rit->curBand);
1586 if (reg->data->numRects == 1) /* keep unions happy below */
1589 reg->data = (pixman_region16_data_t *)NULL;
1593 /* Step 3: Union all regions into a single region */
1597 for (j = numRI & 1; j < (half + (numRI & 1)); j++)
1600 hreg = &ri[j+half].reg;
1601 if (!pixman_op(reg, reg, hreg, pixman_region_unionO, TRUE, TRUE, pOverlap))
1603 if (hreg->extents.x1 < reg->extents.x1)
1604 reg->extents.x1 = hreg->extents.x1;
1605 if (hreg->extents.y1 < reg->extents.y1)
1606 reg->extents.y1 = hreg->extents.y1;
1607 if (hreg->extents.x2 > reg->extents.x2)
1608 reg->extents.x2 = hreg->extents.x2;
1609 if (hreg->extents.y2 > reg->extents.y2)
1610 reg->extents.y2 = hreg->extents.y2;
1615 *badreg = ri[0].reg;
1620 for (i = 0; i < numRI; i++)
1621 freeData(&ri[i].reg);
1623 return pixman_break (badreg);
1626 /* XXX: Need to fix this to not use any X data structure
1628 pixman_region_rectsToRegion(nrects, prect, ctype)
1633 pixman_region16_t * region;
1634 pixman_region16_data_t * pData;
1635 pixman_box16_t * box;
1639 region = pixman_region_create(NullBox, 0);
1640 if (PIXREGION_NAR (region))
1648 if ((x2 = x1 + (int) prect->width) > SHRT_MAX)
1650 if ((y2 = y1 + (int) prect->height) > SHRT_MAX)
1652 if (x1 != x2 && y1 != y2)
1654 region->extents.x1 = x1;
1655 region->extents.y1 = y1;
1656 region->extents.x2 = x2;
1657 region->extents.y2 = y2;
1658 region->data = (pixman_region16_data_t *)NULL;
1662 pData = allocData(nrects);
1665 pixman_break (region);
1668 box = (pixman_box16_t *) (pData + 1);
1669 for (i = nrects; --i >= 0; prect++)
1673 if ((x2 = x1 + (int) prect->width) > SHRT_MAX)
1675 if ((y2 = y1 + (int) prect->height) > SHRT_MAX)
1677 if (x1 != x2 && y1 != y2)
1686 if (box != (pixman_box16_t *) (pData + 1))
1688 pData->size = nrects;
1689 pData->numRects = box - (pixman_box16_t *) (pData + 1);
1690 region->data = pData;
1691 if (ctype != CT_YXBANDED)
1694 region->extents.x1 = region->extents.x2 = 0;
1695 pixman_region_validate(region, &overlap);
1698 pixman_set_extents(region);
1709 /*======================================================================
1710 * Region Subtraction
1711 *====================================================================*/
1714 *-----------------------------------------------------------------------
1715 * pixman_region_subtractO --
1716 * Overlapping band subtraction. x1 is the left-most point not yet
1720 * TRUE if successful.
1723 * region may have rectangles added to it.
1725 *-----------------------------------------------------------------------
1728 static pixman_bool_t
1729 pixman_region_subtractO (
1730 pixman_region16_t * region,
1731 pixman_box16_t * r1,
1732 pixman_box16_t * r1End,
1733 pixman_box16_t * r2,
1734 pixman_box16_t * r2End,
1739 pixman_box16_t * pNextRect;
1745 assert(r1 != r1End && r2 != r2End);
1747 pNextRect = PIXREGION_TOP(region);
1754 * Subtrahend entirely to left of minuend: go to next subtrahend.
1758 else if (r2->x1 <= x1)
1761 * Subtrahend preceeds minuend: nuke left edge of minuend.
1767 * Minuend completely covered: advance to next minuend and
1768 * reset left fence to edge of new minuend.
1777 * Subtrahend now used up since it doesn't extend beyond
1783 else if (r2->x1 < r1->x2)
1786 * Left part of subtrahend covers part of minuend: add uncovered
1787 * part of minuend to region and skip to next subtrahend.
1790 NEWRECT(region, pNextRect, x1, y1, r2->x1, y2);
1796 * Minuend used up: advance to new...
1805 * Subtrahend used up
1813 * Minuend used up: add any remaining piece before advancing.
1816 NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
1821 } while ((r1 != r1End) && (r2 != r2End));
1824 * Add remaining minuend rectangles to region.
1829 NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
1838 *-----------------------------------------------------------------------
1839 * pixman_region_subtract --
1840 * Subtract regS from regM and leave the result in regD.
1841 * S stands for subtrahend, M for minuend and D for difference.
1844 * TRUE if successful.
1847 * regD is overwritten.
1849 *-----------------------------------------------------------------------
1852 pixman_region_subtract(pixman_region16_t * regD,
1853 pixman_region16_t * regM,
1854 pixman_region16_t * regS)
1856 int overlap; /* result ignored */
1861 /* check for trivial rejects */
1862 if (PIXREGION_NIL(regM) || PIXREGION_NIL(regS) ||
1863 !EXTENTCHECK(®M->extents, ®S->extents))
1865 if (PIXREGION_NAR (regS))
1866 return pixman_break (regD);
1867 return pixman_region_copy(regD, regM);
1869 else if (regM == regS)
1872 regD->extents.x2 = regD->extents.x1;
1873 regD->extents.y2 = regD->extents.y1;
1874 regD->data = &pixman_region_emptyData;
1878 /* Add those rectangles in region 1 that aren't in region 2,
1879 do yucky substraction for overlaps, and
1880 just throw away rectangles in region 2 that aren't in region 1 */
1881 if (!pixman_op(regD, regM, regS, pixman_region_subtractO, TRUE, FALSE, &overlap))
1885 * Can't alter RegD's extents before we call pixman_op because
1886 * it might be one of the source regions and pixman_op depends
1887 * on the extents of those regions being unaltered. Besides, this
1888 * way there's no checking against rectangles that will be nuked
1889 * due to coalescing, so we have to examine fewer rectangles.
1891 pixman_set_extents(regD);
1896 /*======================================================================
1898 *====================================================================*/
1901 *-----------------------------------------------------------------------
1902 * pixman_region_inverse --
1903 * Take a region and a box and return a region that is everything
1904 * in the box but not in the region. The careful reader will note
1905 * that this is the same as subtracting the region from the box...
1911 * newReg is overwritten.
1913 *-----------------------------------------------------------------------
1916 pixman_region_inverse(pixman_region16_t * newReg, /* Destination region */
1917 pixman_region16_t * reg1, /* Region to invert */
1918 pixman_box16_t * invRect) /* Bounding box for inversion */
1920 pixman_region16_t invReg; /* Quick and dirty region made from the
1922 int overlap; /* result ignored */
1926 /* check for trivial rejects */
1927 if (PIXREGION_NIL(reg1) || !EXTENTCHECK(invRect, ®1->extents))
1929 if (PIXREGION_NAR(reg1))
1930 return pixman_break (newReg);
1931 newReg->extents = *invRect;
1933 newReg->data = (pixman_region16_data_t *)NULL;
1937 /* Add those rectangles in region 1 that aren't in region 2,
1938 do yucky substraction for overlaps, and
1939 just throw away rectangles in region 2 that aren't in region 1 */
1940 invReg.extents = *invRect;
1941 invReg.data = (pixman_region16_data_t *)NULL;
1942 if (!pixman_op(newReg, &invReg, reg1, pixman_region_subtractO, TRUE, FALSE, &overlap))
1946 * Can't alter newReg's extents before we call pixman_op because
1947 * it might be one of the source regions and pixman_op depends
1948 * on the extents of those regions being unaltered. Besides, this
1949 * way there's no checking against rectangles that will be nuked
1950 * due to coalescing, so we have to examine fewer rectangles.
1952 pixman_set_extents(newReg);
1958 * RectIn(region, rect)
1959 * This routine takes a pointer to a region and a pointer to a box
1960 * and determines if the box is outside/inside/partly inside the region.
1962 * The idea is to travel through the list of rectangles trying to cover the
1963 * passed box with them. Anytime a piece of the rectangle isn't covered
1964 * by a band of rectangles, partOut is set TRUE. Any time a rectangle in
1965 * the region covers part of the box, partIn is set TRUE. The process ends
1966 * when either the box has been completely covered (we reached a band that
1967 * doesn't overlap the box, partIn is TRUE and partOut is false), the
1968 * box has been partially covered (partIn == partOut == TRUE -- because of
1969 * the banding, the first time this is true we know the box is only
1970 * partially in the region) or is outside the region (we reached a band
1971 * that doesn't overlap the box at all and partIn is false)
1975 pixman_region_contains_rectangle(pixman_region16_t * region,
1976 pixman_box16_t * prect)
1980 pixman_box16_t * pbox;
1981 pixman_box16_t * pboxEnd;
1982 int partIn, partOut;
1986 numRects = PIXREGION_NUM_RECTS(region);
1987 /* useful optimization */
1988 if (!numRects || !EXTENTCHECK(®ion->extents, prect))
1989 return(PIXMAN_REGION_OUT);
1993 /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
1994 if (SUBSUMES(®ion->extents, prect))
1995 return(PIXMAN_REGION_IN);
1997 return(PIXMAN_REGION_PART);
2003 /* (x,y) starts at upper left of rect, moving to the right and down */
2007 /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
2008 for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
2014 continue; /* getting up to speed or skipping remainder of band */
2018 partOut = TRUE; /* missed part of rectangle above */
2019 if (partIn || (pbox->y1 >= prect->y2))
2021 y = pbox->y1; /* x guaranteed to be == prect->x1 */
2025 continue; /* not far enough over yet */
2029 partOut = TRUE; /* missed part of rectangle to left */
2034 if (pbox->x1 < prect->x2)
2036 partIn = TRUE; /* definitely overlap */
2041 if (pbox->x2 >= prect->x2)
2043 y = pbox->y2; /* finished with this band */
2046 x = prect->x1; /* reset x out to left again */
2051 * Because boxes in a band are maximal width, if the first box
2052 * to overlap the rectangle doesn't completely cover it in that
2053 * band, the rectangle must be partially out, since some of it
2054 * will be uncovered in that band. partIn will have been set true
2065 return PIXMAN_REGION_PART;
2067 return PIXMAN_REGION_IN;
2071 return PIXMAN_REGION_OUT;
2075 /* pixman_region_translate (region, x, y)
2080 pixman_region_translate (pixman_region16_t * region, int x, int y)
2084 pixman_box16_t * pbox;
2087 region->extents.x1 = x1 = region->extents.x1 + x;
2088 region->extents.y1 = y1 = region->extents.y1 + y;
2089 region->extents.x2 = x2 = region->extents.x2 + x;
2090 region->extents.y2 = y2 = region->extents.y2 + y;
2091 if (((x1 - SHRT_MIN)|(y1 - SHRT_MIN)|(SHRT_MAX - x2)|(SHRT_MAX - y2)) >= 0)
2093 if (region->data && (nbox = region->data->numRects))
2095 for (pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
2105 if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|(SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
2107 region->extents.x2 = region->extents.x1;
2108 region->extents.y2 = region->extents.y1;
2110 region->data = &pixman_region_emptyData;
2114 region->extents.x1 = SHRT_MIN;
2115 else if (x2 > SHRT_MAX)
2116 region->extents.x2 = SHRT_MAX;
2118 region->extents.y1 = SHRT_MIN;
2119 else if (y2 > SHRT_MAX)
2120 region->extents.y2 = SHRT_MAX;
2121 if (region->data && (nbox = region->data->numRects))
2123 pixman_box16_t * pboxout;
2125 for (pboxout = pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
2127 pboxout->x1 = x1 = pbox->x1 + x;
2128 pboxout->y1 = y1 = pbox->y1 + y;
2129 pboxout->x2 = x2 = pbox->x2 + x;
2130 pboxout->y2 = y2 = pbox->y2 + y;
2131 if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|
2132 (SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
2134 region->data->numRects--;
2138 pboxout->x1 = SHRT_MIN;
2139 else if (x2 > SHRT_MAX)
2140 pboxout->x2 = SHRT_MAX;
2142 pboxout->y1 = SHRT_MIN;
2143 else if (y2 > SHRT_MAX)
2144 pboxout->y2 = SHRT_MAX;
2147 if (pboxout != pbox)
2149 if (region->data->numRects == 1)
2151 region->extents = *PIXREGION_BOXPTR(region);
2153 region->data = (pixman_region16_data_t *)NULL;
2156 pixman_set_extents(region);
2161 /* XXX: Do we need this?
2162 static pixman_bool_t
2163 pixman_region16_data_copy(pixman_region16_t * dst, pixman_region16_t * src)
2171 if (!src->data || !src->data->size)
2174 dst->data = (pixman_region16_data_t *)NULL;
2177 if (!dst->data || (dst->data->size < src->data->numRects))
2180 dst->data = allocData(src->data->numRects);
2182 return pixman_break (dst);
2184 dst->data->size = src->data->size;
2185 dst->data->numRects = src->data->numRects;
2191 pixman_region_reset(pixman_region16_t *region, pixman_box16_t *box)
2194 assert(box->x1<=box->x2);
2195 assert(box->y1<=box->y2);
2196 region->extents = *box;
2198 region->data = (pixman_region16_data_t *)NULL;
2201 /* box is "return" value */
2203 pixman_region_contains_point(pixman_region16_t * region,
2205 pixman_box16_t * box)
2207 pixman_box16_t *pbox, *pboxEnd;
2211 numRects = PIXREGION_NUM_RECTS(region);
2212 if (!numRects || !INBOX(®ion->extents, x, y))
2216 *box = region->extents;
2219 for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
2224 continue; /* not there yet */
2225 if ((y < pbox->y1) || (x < pbox->x1))
2226 break; /* missed it */
2228 continue; /* not there yet */
2236 pixman_region_not_empty(pixman_region16_t * region)
2239 return(!PIXREGION_NIL(region));
2242 /* XXX: Do we need this?
2244 pixman_region16_broken(pixman_region16_t * region)
2247 return (PIXREGION_NAR(region));
2252 pixman_region_empty(pixman_region16_t * region)
2256 region->extents.x2 = region->extents.x1;
2257 region->extents.y2 = region->extents.y1;
2258 region->data = &pixman_region_emptyData;
2262 pixman_region_extents(pixman_region16_t * region)
2265 return(®ion->extents);
2268 #define ExchangeSpans(a, b) \
2270 pixman_region16_point_t tpt; \
2273 tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt; \
2274 tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
2277 /* ||| I should apply the merge sort code to rectangle sorting above, and see
2278 if mapping time can be improved. But right now I've been at work 12 hours,
2282 static void QuickSortSpans(
2283 pixman_region16_point_t spans[],
2289 pixman_region16_point_t *r;
2291 /* Always called with numSpans > 1 */
2292 /* Sorts only by y, doesn't bother to sort by x */
2298 /* Do insertion sort */
2304 { /* while i != numSpans */
2308 /* spans[i] is out of order. Move into proper location. */
2309 pixman_region16_point_t tpt;
2312 for (j = 0; y >= spans[j].y; j++) {}
2315 for (k = i; k != j; k--)
2317 spans[k] = spans[k-1];
2318 widths[k] = widths[k-1];
2323 } /* if out of order */
2326 } while (i != numSpans);
2330 /* Choose partition element, stick in location 0 */
2332 if (spans[m].y > spans[0].y) ExchangeSpans(m, 0);
2333 if (spans[m].y > spans[numSpans-1].y) ExchangeSpans(m, numSpans-1);
2334 if (spans[m].y > spans[0].y) ExchangeSpans(m, 0);
2337 /* Partition array */
2347 } while (i != numSpans && r->y < y);
2355 ExchangeSpans(i, j);
2358 /* Move partition element back to middle */
2359 ExchangeSpans(0, j);
2362 if (numSpans-j-1 > 1)
2363 QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1);
2365 } while (numSpans > 1);
2368 #define NextBand() \
2370 clipy1 = pboxBandStart->y1; \
2371 clipy2 = pboxBandStart->y2; \
2372 pboxBandEnd = pboxBandStart + 1; \
2373 while (pboxBandEnd != pboxLast && pboxBandEnd->y1 == clipy1) { \
2376 for (; ppt != pptLast && ppt->y < clipy1; ppt++, pwidth++) {} \
2380 Clip a list of scanlines to a region. The caller has allocated the
2381 space. FSorted is non-zero if the scanline origins are in ascending
2383 returns the number of new, clipped scanlines.
2386 #ifdef XXX_DO_WE_NEED_THIS
2388 pixman_region16_clip_spans(
2389 pixman_region16_t *prgnDst,
2390 pixman_region16_point_t *ppt,
2393 pixman_region16_point_t *pptNew,
2397 pixman_region16_point_t *pptLast;
2398 int *pwidthNewStart; /* the vengeance of Xerox! */
2403 pptLast = ppt + nspans;
2404 pwidthNewStart = pwidthNew;
2408 /* Do special fast code with clip boundaries in registers(?) */
2409 /* It doesn't pay much to make use of fSorted in this case,
2410 so we lump everything together. */
2412 int clipx1, clipx2, clipy1, clipy2;
2414 clipx1 = prgnDst->extents.x1;
2415 clipy1 = prgnDst->extents.y1;
2416 clipx2 = prgnDst->extents.x2;
2417 clipy2 = prgnDst->extents.y2;
2419 for (; ppt != pptLast; ppt++, pwidth++)
2423 if (clipy1 <= y && y < clipy2)
2426 if (x1 < clipx1) x1 = clipx1;
2427 if (x2 > clipx2) x2 = clipx2;
2430 /* part of span in clip rectangle */
2433 *pwidthNew = x2 - x1;
2441 else if ((numRects = prgnDst->data->numRects))
2443 /* Have to clip against many boxes */
2444 pixman_box16_t *pboxBandStart, *pboxBandEnd;
2445 pixman_box16_t *pbox;
2446 pixman_box16_t *pboxLast;
2449 /* In this case, taking advantage of sorted spans gains more than
2450 the sorting costs. */
2451 if ((! fSorted) && (nspans > 1))
2452 QuickSortSpans(ppt, pwidth, nspans);
2454 pboxBandStart = PIXREGION_BOXPTR(prgnDst);
2455 pboxLast = pboxBandStart + numRects;
2459 for (; ppt != pptLast; )
2464 /* span is in the current band */
2465 pbox = pboxBandStart;
2469 { /* For each box in band */
2474 if (newx1 < pbox->x1) newx1 = pbox->x1;
2475 if (newx2 > pbox->x2) newx2 = pbox->x2;
2478 /* Part of span in clip rectangle */
2481 *pwidthNew = newx2 - newx1;
2486 } while (pbox != pboxBandEnd);
2492 /* Move to next band, adjust ppt as needed */
2493 pboxBandStart = pboxBandEnd;
2494 if (pboxBandStart == pboxLast)
2495 break; /* We're completely done */
2500 return (pwidthNew - pwidthNewStart);
2503 /* find the band in a region with the most rectangles */
2505 pixman_region16_find_max_band(pixman_region16_t * prgn)
2508 pixman_box16_t * pbox;
2514 nbox = PIXREGION_NUM_RECTS(prgn);
2515 pbox = PIXREGION_RECTS(prgn);
2519 yThisBand = pbox->y1;
2521 while((nbox > 0) && (pbox->y1 == yThisBand))
2527 if (nThisBand > nMaxBand)
2528 nMaxBand = nThisBand;
2532 #endif /* XXX_DO_WE_NEED_THIS */