1 /***********************************************************
3 Copyright (c) 1987, 1988, 1989 X Consortium
5 Permission is hereby granted, free of charge, to any person obtaining a copy
6 of this software and associated documentation files (the "Software"), to deal
7 in the Software without restriction, including without limitation the rights
8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 copies of the Software, and to permit persons to whom the Software is
10 furnished to do so, subject to the following conditions:
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 X CONSORTIUM 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 X Consortium 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 X Consortium.
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 /* $XConsortium: miregion.c,v 1.60 94/04/17 20:27:49 dpw Exp $ */
52 #include "miscstruct.h"
53 #include "regionstr.h"
54 #include "Xprotostr.h"
57 #if defined (__GNUC__) && !defined (NO_INLINES)
58 #define INLINE __inline
64 * hack until callers of these functions can deal with out-of-memory
67 extern Bool Must_have_memory;
70 #define assert(expr) {if (!(expr)) \
71 FatalError("Assertion failed file %s, line %d: expr\n", \
72 __FILE__, __LINE__); }
77 #define good(reg) assert(miValidRegion(reg))
80 * The functions in this file implement the Region abstraction used extensively
81 * throughout the X11 sample server. A Region is simply a set of disjoint
82 * (non-overlapping) rectangles, plus an "extent" rectangle which is the
83 * smallest single rectangle that contains all the non-overlapping rectangles.
85 * A Region is implemented as a "y-x-banded" array of rectangles. This array
86 * imposes two degrees of order. First, all rectangles are sorted by top side
87 * y coordinate first (y1), and then by left side x coordinate (x1).
89 * Furthermore, the rectangles are grouped into "bands". Each rectangle in a
90 * band has the same top y coordinate (y1), and each has the same bottom y
91 * coordinate (y2). Thus all rectangles in a band differ only in their left
92 * and right side (x1 and x2). Bands are implicit in the array of rectangles:
93 * there is no separate list of band start pointers.
95 * The y-x band representation does not minimize rectangles. In particular,
96 * if a rectangle vertically crosses a band (the rectangle has scanlines in
97 * the y1 to y2 area spanned by the band), then the rectangle may be broken
98 * down into two or more smaller rectangles stacked one atop the other.
100 * ----------- -----------
102 * | | -------- ----------- --------
103 * | | | | in y-x banded | | | | band 1
104 * | | | | form is | | | |
105 * ----------- | | ----------- --------
109 * An added constraint on the rectangles is that they must cover as much
110 * horizontal area as possible: no two rectangles within a band are allowed
113 * Whenever possible, bands will be merged together to cover a greater vertical
114 * distance (and thus reduce the number of rectangles). Two bands can be merged
115 * only if the bottom of one touches the top of the other and they have
116 * rectangles in the same places (of the same width, of course).
118 * Adam de Boor wrote most of the original region code. Joel McCormack
119 * substantially modified or rewrote most of the core arithmetic routines,
120 * and added miRegionValidate in order to support several speed improvements
121 * to miValidateTree. Bob Scheifler changed the representation to be more
122 * compact when empty or a single rectangle, and did a bunch of gratuitous
126 /* true iff two Boxes overlap */
127 #define EXTENTCHECK(r1,r2) \
128 (!( ((r1)->x2 <= (r2)->x1) || \
129 ((r1)->x1 >= (r2)->x2) || \
130 ((r1)->y2 <= (r2)->y1) || \
131 ((r1)->y1 >= (r2)->y2) ) )
133 /* true iff (x,y) is in Box */
134 #define INBOX(r,x,y) \
140 /* true iff Box r1 contains Box r2 */
141 #define SUBSUMES(r1,r2) \
142 ( ((r1)->x1 <= (r2)->x1) && \
143 ((r1)->x2 >= (r2)->x2) && \
144 ((r1)->y1 <= (r2)->y1) && \
145 ((r1)->y2 >= (r2)->y2) )
147 #define xallocData(n) (RegDataPtr)xalloc(REGION_SZOF(n))
148 #define xfreeData(reg) if ((reg)->data && (reg)->data->size) xfree((reg)->data)
150 #define RECTALLOC(pReg,n) \
151 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
154 #define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \
156 pNextRect->x1 = nx1; \
157 pNextRect->y1 = ny1; \
158 pNextRect->x2 = nx2; \
159 pNextRect->y2 = ny2; \
163 #define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \
165 if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
167 miRectAlloc(pReg, 1); \
168 pNextRect = REGION_TOP(pReg); \
170 ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \
171 pReg->data->numRects++; \
172 assert(pReg->data->numRects<=pReg->data->size); \
176 #define DOWNSIZE(reg,numRects) \
177 if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
179 RegDataPtr NewData; \
180 NewData = (RegDataPtr)xrealloc((reg)->data, REGION_SZOF(numRects)); \
183 NewData->size = (numRects); \
184 (reg)->data = NewData; \
189 BoxRec miEmptyBox = {0, 0, 0, 0};
190 RegDataRec miEmptyData = {0, 0};
201 num = REGION_NUM_RECTS(rgn);
202 size = REGION_SIZE(rgn);
203 rects = REGION_RECTS(rgn);
204 ErrorF("num: %d size: %d\n", num, size);
205 ErrorF("extents: %d %d %d %d\n",
206 rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
207 for (i = 0; i < num; i++)
208 ErrorF("%d %d %d %d \n",
209 rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
216 miRegionsEqual(reg1, reg2)
221 BoxPtr rects1, rects2;
223 if (reg1->extents.x1 != reg2->extents.x1) return FALSE;
224 if (reg1->extents.x2 != reg2->extents.x2) return FALSE;
225 if (reg1->extents.y1 != reg2->extents.y1) return FALSE;
226 if (reg1->extents.y2 != reg2->extents.y2) return FALSE;
227 if (REGION_NUM_RECTS(reg1) != REGION_NUM_RECTS(reg2)) return FALSE;
229 rects1 = REGION_RECTS(reg1);
230 rects2 = REGION_RECTS(reg2);
231 for (i = 0; i != REGION_NUM_RECTS(reg1); i++) {
232 if (rects1[i].x1 != rects2[i].x1) return FALSE;
233 if (rects1[i].x2 != rects2[i].x2) return FALSE;
234 if (rects1[i].y1 != rects2[i].y1) return FALSE;
235 if (rects1[i].y2 != rects2[i].y2) return FALSE;
244 register int i, numRects;
246 if ((reg->extents.x1 > reg->extents.x2) ||
247 (reg->extents.y1 > reg->extents.y2))
249 numRects = REGION_NUM_RECTS(reg);
251 return ((reg->extents.x1 == reg->extents.x2) &&
252 (reg->extents.y1 == reg->extents.y2) &&
253 (reg->data->size || (reg->data == &miEmptyData)));
254 else if (numRects == 1)
258 register BoxPtr pboxP, pboxN;
261 pboxP = REGION_RECTS(reg);
263 box.y2 = pboxP[numRects-1].y2;
265 for (i = numRects; --i > 0; pboxP++, pboxN++)
267 if ((pboxN->x1 >= pboxN->x2) ||
268 (pboxN->y1 >= pboxN->y2))
270 if (pboxN->x1 < box.x1)
272 if (pboxN->x2 > box.x2)
274 if ((pboxN->y1 < pboxP->y1) ||
275 ((pboxN->y1 == pboxP->y1) &&
276 ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2))))
279 return ((box.x1 == reg->extents.x1) &&
280 (box.x2 == reg->extents.x2) &&
281 (box.y1 == reg->extents.y1) &&
282 (box.y2 == reg->extents.y2));
289 /*****************************************************************
290 * RegionCreate(rect, size)
291 * This routine does a simple malloc to make a structure of
292 * REGION of "size" number of rectangles.
293 *****************************************************************/
296 miRegionCreate(rect, size)
300 register RegionPtr pReg;
302 Must_have_memory = TRUE; /* XXX */
303 pReg = (RegionPtr)xalloc(sizeof(RegionRec));
304 Must_have_memory = FALSE; /* XXX */
307 pReg->extents = *rect;
308 pReg->data = (RegDataPtr)NULL;
312 pReg->extents = miEmptyBox;
313 if ((size > 1) && (pReg->data = xallocData(size)))
315 pReg->data->size = size;
316 pReg->data->numRects = 0;
319 pReg->data = &miEmptyData;
324 /*****************************************************************
325 * RegionInit(pReg, rect, size)
326 * Outer region rect is statically allocated.
327 *****************************************************************/
330 miRegionInit(pReg, rect, size)
337 pReg->extents = *rect;
338 pReg->data = (RegDataPtr)NULL;
342 pReg->extents = miEmptyBox;
343 if ((size > 1) && (pReg->data = xallocData(size)))
345 pReg->data->size = size;
346 pReg->data->numRects = 0;
349 pReg->data = &miEmptyData;
354 miRegionDestroy(pReg)
372 register RegionPtr pRgn;
375 Must_have_memory = TRUE; /* XXX */
379 pRgn->data = xallocData(n);
380 pRgn->data->numRects = 1;
381 *REGION_BOXPTR(pRgn) = pRgn->extents;
383 else if (!pRgn->data->size)
385 pRgn->data = xallocData(n);
386 pRgn->data->numRects = 0;
392 n = pRgn->data->numRects;
393 if (n > 500) /* XXX pick numbers out of a hat */
396 n += pRgn->data->numRects;
397 pRgn->data = (RegDataPtr)xrealloc(pRgn->data, REGION_SZOF(n));
399 Must_have_memory = FALSE; /* XXX */
400 pRgn->data->size = n;
405 miRegionCopy(dst, src)
406 register RegionPtr dst;
407 register RegionPtr src;
413 dst->extents = src->extents;
414 if (!src->data || !src->data->size)
417 dst->data = src->data;
420 if (!dst->data || (dst->data->size < src->data->numRects))
423 Must_have_memory = TRUE; /* XXX */
424 dst->data = xallocData(src->data->numRects);
425 Must_have_memory = FALSE; /* XXX */
426 dst->data->size = src->data->numRects;
428 dst->data->numRects = src->data->numRects;
429 memmove((char *)REGION_BOXPTR(dst),(char *)REGION_BOXPTR(src),
430 dst->data->numRects * sizeof(BoxRec));
435 /*======================================================================
436 * Generic Region Operator
437 *====================================================================*/
440 *-----------------------------------------------------------------------
442 * Attempt to merge the boxes in the current band with those in the
443 * previous one. We are guaranteed that the current band extends to
444 * the end of the rects array. Used only by miRegionOp.
447 * The new index for the previous band.
450 * If coalescing takes place:
451 * - rectangles in the previous band will have their y2 fields
453 * - pReg->data->numRects will be decreased.
455 *-----------------------------------------------------------------------
458 miCoalesce (pReg, prevStart, curStart)
459 register RegionPtr pReg; /* Region to coalesce */
460 int prevStart; /* Index of start of previous band */
461 int curStart; /* Index of start of current band */
463 register BoxPtr pPrevBox; /* Current box in previous band */
464 register BoxPtr pCurBox; /* Current box in current band */
465 register int numRects; /* Number rectangles in both bands */
466 register int y2; /* Bottom of current band */
468 * Figure out how many rectangles are in the band.
470 numRects = curStart - prevStart;
471 assert(numRects == pReg->data->numRects - curStart);
473 if (!numRects) return curStart;
476 * The bands may only be coalesced if the bottom of the previous
477 * matches the top scanline of the current.
479 pPrevBox = REGION_BOX(pReg, prevStart);
480 pCurBox = REGION_BOX(pReg, curStart);
481 if (pPrevBox->y2 != pCurBox->y1) return curStart;
484 * Make sure the bands have boxes in the same places. This
485 * assumes that boxes have been added in such a way that they
486 * cover the most area possible. I.e. two boxes in a band must
487 * have some horizontal space between them.
492 if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) {
501 * The bands may be merged, so set the bottom y of each box
502 * in the previous band to the bottom y of the current band.
504 numRects = curStart - prevStart;
505 pReg->data->numRects -= numRects;
515 /* Quicky macro to avoid trivial reject procedure calls to miCoalesce */
517 #define Coalesce(newReg, prevBand, curBand) \
518 if (curBand - prevBand == newReg->data->numRects - curBand) { \
519 prevBand = miCoalesce(newReg, prevBand, curBand); \
521 prevBand = curBand; \
525 *-----------------------------------------------------------------------
527 * Handle a non-overlapping band for the union and subtract operations.
528 * Just adds the (top/bottom-clipped) rectangles into the region.
529 * Doesn't have to check for subsumption or anything.
535 * pReg->data->numRects is incremented and the rectangles overwritten
536 * with the rectangles we're passed.
538 *-----------------------------------------------------------------------
542 miAppendNonO (pReg, r, rEnd, y1, y2)
543 register RegionPtr pReg;
549 register BoxPtr pNextRect;
550 register int newRects;
555 assert(newRects != 0);
557 /* Make sure we have enough space for all rectangles to be added */
558 RECTALLOC(pReg, newRects);
559 pNextRect = REGION_TOP(pReg);
560 pReg->data->numRects += newRects;
562 assert(r->x1 < r->x2);
563 ADDRECT(pNextRect, r->x1, y1, r->x2, y2);
570 #define FindBand(r, rBandEnd, rEnd, ry1) \
574 while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \
579 #define AppendRegions(newReg, r, rEnd) \
582 if (newRects = rEnd - r) { \
583 RECTALLOC(newReg, newRects); \
584 memmove((char *)REGION_TOP(newReg),(char *)r, \
585 newRects * sizeof(BoxRec)); \
586 newReg->data->numRects += newRects; \
591 *-----------------------------------------------------------------------
593 * Apply an operation to two regions. Called by miUnion, miInverse,
594 * miSubtract, miIntersect.... Both regions MUST have at least one
595 * rectangle, and cannot be the same object.
598 * TRUE if successful.
601 * The new region is overwritten.
602 * pOverlap set to TRUE if overlapFunc ever returns TRUE.
605 * The idea behind this function is to view the two regions as sets.
606 * Together they cover a rectangle of area that this function divides
607 * into horizontal bands where points are covered only by one region
608 * or by both. For the first case, the nonOverlapFunc is called with
609 * each the band and the band's upper and lower extents. For the
610 * second, the overlapFunc is called to process the entire band. It
611 * is responsible for clipping the rectangles in the band, though
612 * this function provides the boundaries.
613 * At the end of each band, the new region is coalesced, if possible,
614 * to reduce the number of rectangles in the region.
616 *-----------------------------------------------------------------------
619 miRegionOp(newReg, reg1, reg2, overlapFunc, appendNon1, appendNon2, pOverlap)
620 RegionPtr newReg; /* Place to store result */
621 RegionPtr reg1; /* First region in operation */
622 RegionPtr reg2; /* 2d region in operation */
623 Bool (*overlapFunc)(); /* Function to call for over-
625 Bool appendNon1; /* Append non-overlapping bands */
627 Bool appendNon2; /* Append non-overlapping bands */
631 register BoxPtr r1; /* Pointer into first region */
632 register BoxPtr r2; /* Pointer into 2d region */
633 BoxPtr r1End; /* End of 1st region */
634 BoxPtr r2End; /* End of 2d region */
635 short ybot; /* Bottom of intersection */
636 short ytop; /* Top of intersection */
637 RegDataPtr oldData; /* Old data for newReg */
638 int prevBand; /* Index of start of
639 * previous band in newReg */
640 int curBand; /* Index of start of current
642 register BoxPtr r1BandEnd; /* End of current band in r1 */
643 register BoxPtr r2BandEnd; /* End of current band in r2 */
644 short top; /* Top of non-overlapping band */
645 short bot; /* Bottom of non-overlapping band*/
646 register int r1y1; /* Temps for r1->y1 and r2->y1 */
653 * set r1, r2, r1End and r2End appropriately, save the rectangles
654 * of the destination region until the end in case it's one of
655 * the two source regions, then mark the "new" region empty, allocating
656 * another array of rectangles for it to use.
659 r1 = REGION_RECTS(reg1);
660 newSize = REGION_NUM_RECTS(reg1);
661 r1End = r1 + newSize;
662 numRects = REGION_NUM_RECTS(reg2);
663 r2 = REGION_RECTS(reg2);
664 r2End = r2 + numRects;
668 oldData = (RegDataPtr)NULL;
669 if (((newReg == reg1) && (newSize > 1)) ||
670 ((newReg == reg2) && (numRects > 1)))
672 oldData = newReg->data;
673 newReg->data = &miEmptyData;
675 /* guess at new size */
676 if (numRects > newSize)
680 newReg->data = &miEmptyData;
681 else if (newReg->data->size)
682 newReg->data->numRects = 0;
683 if (newSize > newReg->data->size)
684 miRectAlloc(newReg, newSize);
688 * In the upcoming loop, ybot and ytop serve different functions depending
689 * on whether the band being handled is an overlapping or non-overlapping
691 * In the case of a non-overlapping band (only one of the regions
692 * has points in the band), ybot is the bottom of the most recent
693 * intersection and thus clips the top of the rectangles in that band.
694 * ytop is the top of the next intersection between the two regions and
695 * serves to clip the bottom of the rectangles in the current band.
696 * For an overlapping band (where the two regions intersect), ytop clips
697 * the top of the rectangles of both regions and ybot clips the bottoms.
700 ybot = min(r1->y1, r2->y1);
703 * prevBand serves to mark the start of the previous band so rectangles
704 * can be coalesced into larger rectangles. qv. miCoalesce, above.
705 * In the beginning, there is no previous band, so prevBand == curBand
706 * (curBand is set later on, of course, but the first band will always
707 * start at index 0). prevBand and curBand must be indices because of
708 * the possible expansion, and resultant moving, of the new region's
709 * array of rectangles.
715 * This algorithm proceeds one source-band (as opposed to a
716 * destination band, which is determined by where the two regions
717 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
718 * rectangle after the last one in the current band for their
719 * respective regions.
724 FindBand(r1, r1BandEnd, r1End, r1y1);
725 FindBand(r2, r2BandEnd, r2End, r2y1);
728 * First handle the band that doesn't intersect, if any.
730 * Note that attention is restricted to one band in the
731 * non-intersecting region at once, so if a region has n
732 * bands between the current position and the next place it overlaps
733 * the other, this entire loop will be passed through n times.
737 top = max(r1y1, ybot);
738 bot = min(r1->y2, r2y1);
740 curBand = newReg->data->numRects;
741 miAppendNonO(newReg, r1, r1BandEnd, top, bot);
742 Coalesce(newReg, prevBand, curBand);
746 } else if (r2y1 < r1y1) {
748 top = max(r2y1, ybot);
749 bot = min(r2->y2, r1y1);
751 curBand = newReg->data->numRects;
752 miAppendNonO(newReg, r2, r2BandEnd, top, bot);
753 Coalesce(newReg, prevBand, curBand);
762 * Now see if we've hit an intersecting band. The two bands only
763 * intersect if ybot > ytop
765 ybot = min(r1->y2, r2->y2);
767 curBand = newReg->data->numRects;
768 (* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot,
770 Coalesce(newReg, prevBand, curBand);
774 * If we've finished with a band (y2 == ybot) we skip forward
775 * in the region to the next band.
777 if (r1->y2 == ybot) r1 = r1BandEnd;
778 if (r2->y2 == ybot) r2 = r2BandEnd;
780 } while (r1 != r1End && r2 != r2End);
783 * Deal with whichever region (if any) still has rectangles left.
785 * We only need to worry about banding and coalescing for the very first
786 * band left. After that, we can just group all remaining boxes,
787 * regardless of how many bands, into one final append to the list.
790 if ((r1 != r1End) && appendNon1) {
791 /* Do first nonOverlap1Func call, which may be able to coalesce */
792 FindBand(r1, r1BandEnd, r1End, r1y1);
793 curBand = newReg->data->numRects;
794 miAppendNonO(newReg, r1, r1BandEnd, max(r1y1, ybot), r1->y2);
795 Coalesce(newReg, prevBand, curBand);
796 /* Just append the rest of the boxes */
797 AppendRegions(newReg, r1BandEnd, r1End);
799 } else if ((r2 != r2End) && appendNon2) {
800 /* Do first nonOverlap2Func call, which may be able to coalesce */
801 FindBand(r2, r2BandEnd, r2End, r2y1);
802 curBand = newReg->data->numRects;
803 miAppendNonO(newReg, r2, r2BandEnd, max(r2y1, ybot), r2->y2);
804 Coalesce(newReg, prevBand, curBand);
805 /* Append rest of boxes */
806 AppendRegions(newReg, r2BandEnd, r2End);
812 if (!(numRects = newReg->data->numRects))
815 newReg->data = &miEmptyData;
817 else if (numRects == 1)
819 newReg->extents = *REGION_BOXPTR(newReg);
821 newReg->data = (RegDataPtr)NULL;
825 DOWNSIZE(newReg, numRects);
832 *-----------------------------------------------------------------------
834 * Reset the extents of a region to what they should be. Called by
835 * miSubtract and miIntersect as they can't figure it out along the
836 * way or do so easily, as miUnion can.
842 * The region's 'extents' structure is overwritten.
844 *-----------------------------------------------------------------------
848 register RegionPtr pReg;
850 register BoxPtr pBox, pBoxEnd;
854 if (!pReg->data->size)
856 pReg->extents.x2 = pReg->extents.x1;
857 pReg->extents.y2 = pReg->extents.y1;
861 pBox = REGION_BOXPTR(pReg);
862 pBoxEnd = REGION_END(pReg);
865 * Since pBox is the first rectangle in the region, it must have the
866 * smallest y1 and since pBoxEnd is the last rectangle in the region,
867 * it must have the largest y2, because of banding. Initialize x1 and
868 * x2 from pBox and pBoxEnd, resp., as good things to initialize them
871 pReg->extents.x1 = pBox->x1;
872 pReg->extents.y1 = pBox->y1;
873 pReg->extents.x2 = pBoxEnd->x2;
874 pReg->extents.y2 = pBoxEnd->y2;
876 assert(pReg->extents.y1 < pReg->extents.y2);
877 while (pBox <= pBoxEnd) {
878 if (pBox->x1 < pReg->extents.x1)
879 pReg->extents.x1 = pBox->x1;
880 if (pBox->x2 > pReg->extents.x2)
881 pReg->extents.x2 = pBox->x2;
885 assert(pReg->extents.x1 < pReg->extents.x2);
888 /*======================================================================
889 * Region Intersection
890 *====================================================================*/
892 *-----------------------------------------------------------------------
894 * Handle an overlapping band for miIntersect.
897 * TRUE if successful.
900 * Rectangles may be added to the region.
902 *-----------------------------------------------------------------------
906 miIntersectO (pReg, r1, r1End, r2, r2End, y1, y2, pOverlap)
907 register RegionPtr pReg;
918 register BoxPtr pNextRect;
920 pNextRect = REGION_TOP(pReg);
923 assert(r1 != r1End && r2 != r2End);
926 x1 = max(r1->x1, r2->x1);
927 x2 = min(r1->x2, r2->x2);
930 * If there's any overlap between the two rectangles, add that
931 * overlap to the new region.
934 NEWRECT(pReg, pNextRect, x1, y1, x2, y2);
937 * Advance the pointer(s) with the leftmost right side, since the next
938 * rectangle on that list may still overlap the other region's
947 } while ((r1 != r1End) && (r2 != r2End));
954 miIntersect(newReg, reg1, reg2)
955 register RegionPtr newReg; /* destination Region */
956 register RegionPtr reg1;
957 register RegionPtr reg2; /* source regions */
962 /* check for trivial reject */
963 if (REGION_NIL(reg1) || REGION_NIL(reg2) ||
964 !EXTENTCHECK(®1->extents, ®2->extents))
966 /* Covers about 20% of all cases */
968 newReg->extents.x2 = newReg->extents.x1;
969 newReg->extents.y2 = newReg->extents.y1;
970 newReg->data = &miEmptyData;
972 else if (!reg1->data && !reg2->data)
974 /* Covers about 80% of cases that aren't trivially rejected */
975 newReg->extents.x1 = max(reg1->extents.x1, reg2->extents.x1);
976 newReg->extents.y1 = max(reg1->extents.y1, reg2->extents.y1);
977 newReg->extents.x2 = min(reg1->extents.x2, reg2->extents.x2);
978 newReg->extents.y2 = min(reg1->extents.y2, reg2->extents.y2);
980 newReg->data = (RegDataPtr)NULL;
982 else if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
984 return miRegionCopy(newReg, reg1);
986 else if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
988 return miRegionCopy(newReg, reg2);
990 else if (reg1 == reg2)
992 return miRegionCopy(newReg, reg1);
996 /* General purpose intersection */
997 Bool overlap; /* result ignored */
998 if (!miRegionOp(newReg, reg1, reg2, miIntersectO, FALSE, FALSE,
1001 miSetExtents(newReg);
1008 #define MERGERECT(r) \
1010 if (r->x1 <= x2) { \
1011 /* Merge with current rectangle */ \
1012 if (r->x1 < x2) *pOverlap = TRUE; \
1013 if (x2 < r->x2) x2 = r->x2; \
1015 /* Add current rectangle, start new one */ \
1016 NEWRECT(pReg, pNextRect, x1, y1, x2, y2); \
1023 /*======================================================================
1025 *====================================================================*/
1028 *-----------------------------------------------------------------------
1030 * Handle an overlapping band for the union operation. Picks the
1031 * left-most rectangle each time and merges it into the region.
1034 * TRUE if successful.
1037 * pReg is overwritten.
1038 * pOverlap is set to TRUE if any boxes overlap.
1040 *-----------------------------------------------------------------------
1043 miUnionO (pReg, r1, r1End, r2, r2End, y1, y2, pOverlap)
1044 register RegionPtr pReg;
1053 register BoxPtr pNextRect;
1054 register int x1; /* left and right side of current union */
1058 assert(r1 != r1End && r2 != r2End);
1060 pNextRect = REGION_TOP(pReg);
1062 /* Start off current rectangle */
1063 if (r1->x1 < r2->x1)
1075 while (r1 != r1End && r2 != r2End)
1077 if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
1080 /* Finish off whoever (if any) is left */
1086 } while (r1 != r1End);
1088 else if (r2 != r2End)
1093 } while (r2 != r2End);
1096 /* Add current rectangle */
1097 NEWRECT(pReg, pNextRect, x1, y1, x2, y2);
1103 miUnion(newReg, reg1, reg2)
1104 RegionPtr newReg; /* destination Region */
1105 register RegionPtr reg1;
1106 register RegionPtr reg2; /* source regions */
1108 Bool overlap; /* result ignored */
1110 /* Return TRUE if some overlap between reg1, reg2 */
1114 /* checks all the simple cases */
1117 * Region 1 and 2 are the same
1121 return miRegionCopy(newReg, reg1);
1127 if (REGION_NIL(reg1))
1130 return miRegionCopy(newReg, reg2);
1137 if (REGION_NIL(reg2))
1140 return miRegionCopy(newReg, reg1);
1145 * Region 1 completely subsumes region 2
1147 if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
1150 return miRegionCopy(newReg, reg1);
1155 * Region 2 completely subsumes region 1
1157 if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
1160 return miRegionCopy(newReg, reg2);
1164 if (!miRegionOp(newReg, reg1, reg2, miUnionO, TRUE, TRUE, &overlap))
1167 newReg->extents.x1 = min(reg1->extents.x1, reg2->extents.x1);
1168 newReg->extents.y1 = min(reg1->extents.y1, reg2->extents.y1);
1169 newReg->extents.x2 = max(reg1->extents.x2, reg2->extents.x2);
1170 newReg->extents.y2 = max(reg1->extents.y2, reg2->extents.y2);
1176 /*======================================================================
1177 * Batch Rectangle Union
1178 *====================================================================*/
1181 *-----------------------------------------------------------------------
1184 * "Append" the rgn rectangles onto the end of dstrgn, maintaining
1185 * knowledge of YX-banding when it's easy. Otherwise, dstrgn just
1186 * becomes a non-y-x-banded random collection of rectangles, and not
1187 * yet a true region. After a sequence of appends, the caller must
1188 * call miRegionValidate to ensure that a valid region is constructed.
1191 * TRUE if successful.
1194 * dstrgn is modified if rgn has rectangles.
1198 miRegionAppend(dstrgn, rgn)
1199 register RegionPtr dstrgn;
1200 register RegionPtr rgn;
1202 int numRects, dnumRects, size;
1206 if (!rgn->data && (dstrgn->data == &miEmptyData))
1208 dstrgn->extents = rgn->extents;
1209 dstrgn->data = (RegDataPtr)NULL;
1213 numRects = REGION_NUM_RECTS(rgn);
1218 dnumRects = REGION_NUM_RECTS(dstrgn);
1219 if (!dnumRects && (size < 200))
1220 size = 200; /* XXX pick numbers out of a hat */
1221 RECTALLOC(dstrgn, size);
1222 old = REGION_RECTS(rgn);
1224 dstrgn->extents = rgn->extents;
1225 else if (dstrgn->extents.x2 > dstrgn->extents.x1)
1227 register BoxPtr first, last;
1230 last = REGION_BOXPTR(dstrgn) + (dnumRects - 1);
1231 if ((first->y1 > last->y2) ||
1232 ((first->y1 == last->y1) && (first->y2 == last->y2) &&
1233 (first->x1 > last->x2)))
1235 if (rgn->extents.x1 < dstrgn->extents.x1)
1236 dstrgn->extents.x1 = rgn->extents.x1;
1237 if (rgn->extents.x2 > dstrgn->extents.x2)
1238 dstrgn->extents.x2 = rgn->extents.x2;
1239 dstrgn->extents.y2 = rgn->extents.y2;
1243 first = REGION_BOXPTR(dstrgn);
1244 last = old + (numRects - 1);
1245 if ((first->y1 > last->y2) ||
1246 ((first->y1 == last->y1) && (first->y2 == last->y2) &&
1247 (first->x1 > last->x2)))
1250 if (rgn->extents.x1 < dstrgn->extents.x1)
1251 dstrgn->extents.x1 = rgn->extents.x1;
1252 if (rgn->extents.x2 > dstrgn->extents.x2)
1253 dstrgn->extents.x2 = rgn->extents.x2;
1254 dstrgn->extents.y1 = rgn->extents.y1;
1257 dstrgn->extents.x2 = dstrgn->extents.x1;
1262 new = REGION_BOX(dstrgn, numRects);
1264 *new = *REGION_BOXPTR(dstrgn);
1266 memmove((char *)new,(char *)REGION_BOXPTR(dstrgn),
1267 dnumRects * sizeof(BoxRec));
1268 new = REGION_BOXPTR(dstrgn);
1271 new = REGION_BOXPTR(dstrgn) + dnumRects;
1275 memmove((char *)new, (char *)old, numRects * sizeof(BoxRec));
1276 dstrgn->data->numRects += numRects;
1281 #define ExchangeRects(a, b) \
1285 rects[a] = rects[b]; \
1290 QuickSortRects(rects, numRects)
1291 register BoxRec rects[];
1292 register int numRects;
1299 /* Always called with numRects > 1 */
1305 if (rects[0].y1 > rects[1].y1 ||
1306 (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
1307 ExchangeRects(0, 1);
1311 /* Choose partition element, stick in location 0 */
1312 ExchangeRects(0, numRects >> 1);
1316 /* Partition array */
1326 } while (i != numRects &&
1327 (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
1333 } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
1335 ExchangeRects(i, j);
1338 /* Move partition element back to middle */
1339 ExchangeRects(0, j);
1342 if (numRects-j-1 > 1)
1343 QuickSortRects(&rects[j+1], numRects-j-1);
1345 } while (numRects > 1);
1349 *-----------------------------------------------------------------------
1350 * miRegionValidate --
1352 * Take a ``region'' which is a non-y-x-banded random collection of
1353 * rectangles, and compute a nice region which is the union of all the
1357 * TRUE if successful.
1360 * The passed-in ``region'' may be modified.
1361 * pOverlap set to TRUE if any retangles overlapped, else FALSE;
1364 * Step 1. Sort the rectangles into ascending order with primary key y1
1365 * and secondary key x1.
1367 * Step 2. Split the rectangles into the minimum number of proper y-x
1368 * banded regions. This may require horizontally merging
1369 * rectangles, and vertically coalescing bands. With any luck,
1370 * this step in an identity tranformation (ala the Box widget),
1371 * or a coalescing into 1 box (ala Menus).
1373 * Step 3. Merge the separate regions down to a single region by calling
1374 * miUnion. Maximize the work each miUnion call does by using
1377 *-----------------------------------------------------------------------
1381 miRegionValidate(badreg, pOverlap)
1385 /* Descriptor for regions under construction in Step 2. */
1392 int numRects; /* Original numRects for badreg */
1393 RegionInfo *ri; /* Array of current regions */
1394 int numRI; /* Number of entries used in ri */
1395 int sizeRI; /* Number of entries available in ri */
1396 int i; /* Index into rects */
1397 register int j; /* Index into ri */
1398 register RegionInfo *rit; /* &ri[j] */
1399 register RegionPtr reg; /* ri[j].reg */
1400 register BoxPtr box; /* Current box in rects */
1401 register BoxPtr riBox; /* Last box in ri[j].reg */
1402 register RegionPtr hreg; /* ri[j_half].reg */
1410 numRects = badreg->data->numRects;
1416 if (badreg->extents.x1 < badreg->extents.x2)
1418 if ((numRects) == 1)
1421 badreg->data = (RegDataPtr) NULL;
1425 DOWNSIZE(badreg, numRects);
1431 /* Step 1: Sort the rects array into ascending (y1, x1) order */
1432 QuickSortRects(REGION_BOXPTR(badreg), numRects);
1434 /* Step 2: Scatter the sorted array into the minimum number of regions */
1436 /* Set up the first region to be the first rectangle in badreg */
1437 /* Note that step 2 code will never overflow the ri[0].reg rects array */
1438 Must_have_memory = TRUE; /* XXX */
1439 ri = (RegionInfo *) xalloc(4 * sizeof(RegionInfo));
1440 Must_have_memory = FALSE; /* XXX */
1445 ri[0].reg = *badreg;
1446 box = REGION_BOXPTR(&ri[0].reg);
1447 ri[0].reg.extents = *box;
1448 ri[0].reg.data->numRects = 1;
1450 /* Now scatter rectangles into the minimum set of valid regions. If the
1451 next rectangle to be added to a region would force an existing rectangle
1452 in the region to be split up in order to maintain y-x banding, just
1453 forget it. Try the next region. If it doesn't fit cleanly into any
1454 region, make a new one. */
1456 for (i = numRects; --i > 0;)
1459 /* Look for a region to append box to */
1460 for (j = numRI, rit = ri; --j >= 0; rit++)
1463 riBox = REGION_END(reg);
1465 if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
1467 /* box is in same band as riBox. Merge or append it */
1468 if (box->x1 <= riBox->x2)
1470 /* Merge it with riBox */
1471 if (box->x1 < riBox->x2) *pOverlap = TRUE;
1472 if (box->x2 > riBox->x2) riBox->x2 = box->x2;
1477 *REGION_TOP(reg) = *box;
1478 reg->data->numRects++;
1480 goto NextRect; /* So sue me */
1482 else if (box->y1 >= riBox->y2)
1484 /* Put box into new band */
1485 if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1486 if (reg->extents.x1 > box->x1) reg->extents.x1 = box->x1;
1487 Coalesce(reg, rit->prevBand, rit->curBand);
1488 rit->curBand = reg->data->numRects;
1490 *REGION_TOP(reg) = *box;
1491 reg->data->numRects++;
1494 /* Well, this region was inappropriate. Try the next one. */
1497 /* Uh-oh. No regions were appropriate. Create a new one. */
1498 if (sizeRI == numRI)
1500 /* Oops, allocate space for new region information */
1502 Must_have_memory = TRUE; /* XXX */
1503 ri = (RegionInfo *) xrealloc(ri, sizeRI * sizeof(RegionInfo));
1504 Must_have_memory = FALSE; /* XXX */
1510 rit->reg.extents = *box;
1511 rit->reg.data = (RegDataPtr)NULL;
1512 miRectAlloc(&rit->reg, (i+numRI) / numRI); /* MUST force allocation */
1516 /* Make a final pass over each region in order to Coalesce and set
1517 extents.x2 and extents.y2 */
1519 for (j = numRI, rit = ri; --j >= 0; rit++)
1522 riBox = REGION_END(reg);
1523 reg->extents.y2 = riBox->y2;
1524 if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1525 Coalesce(reg, rit->prevBand, rit->curBand);
1526 if (reg->data->numRects == 1) /* keep unions happy below */
1529 reg->data = (RegDataPtr)NULL;
1533 /* Step 3: Union all regions into a single region */
1537 for (j = numRI & 1; j < (half + (numRI & 1)); j++)
1540 hreg = &ri[j+half].reg;
1541 miRegionOp(reg, reg, hreg, miUnionO, TRUE, TRUE, pOverlap);
1542 if (hreg->extents.x1 < reg->extents.x1)
1543 reg->extents.x1 = hreg->extents.x1;
1544 if (hreg->extents.y1 < reg->extents.y1)
1545 reg->extents.y1 = hreg->extents.y1;
1546 if (hreg->extents.x2 > reg->extents.x2)
1547 reg->extents.x2 = hreg->extents.x2;
1548 if (hreg->extents.y2 > reg->extents.y2)
1549 reg->extents.y2 = hreg->extents.y2;
1554 *badreg = ri[0].reg;
1561 miRectsToRegion(nrects, prect, ctype)
1563 register xRectangle *prect;
1566 register RegionPtr pRgn;
1567 register RegDataPtr pData;
1568 register BoxPtr pBox;
1572 pRgn = miRegionCreate(NullBox, 0);
1579 if ((x2 = x1 + (int) prect->width) > MAXSHORT)
1581 if ((y2 = y1 + (int) prect->height) > MAXSHORT)
1583 if (x1 != x2 && y1 != y2)
1585 pRgn->extents.x1 = x1;
1586 pRgn->extents.y1 = y1;
1587 pRgn->extents.x2 = x2;
1588 pRgn->extents.y2 = y2;
1589 pRgn->data = (RegDataPtr)NULL;
1593 Must_have_memory = TRUE; /* XXX */
1594 pData = xallocData(nrects);
1595 pBox = (BoxPtr) (pData + 1);
1596 Must_have_memory = FALSE; /* XXX */
1597 for (i = nrects; --i >= 0; prect++)
1601 if ((x2 = x1 + (int) prect->width) > MAXSHORT)
1603 if ((y2 = y1 + (int) prect->height) > MAXSHORT)
1605 if (x1 != x2 && y1 != y2)
1614 if (pBox != (BoxPtr) (pData + 1))
1616 pData->size = nrects;
1617 pData->numRects = pBox - (BoxPtr) (pData + 1);
1619 if (ctype != CT_YXBANDED)
1621 Bool overlap; /* result ignored */
1622 pRgn->extents.x1 = pRgn->extents.x2 = 0;
1623 miRegionValidate(pRgn, &overlap);
1636 /*======================================================================
1637 * Region Subtraction
1638 *====================================================================*/
1642 *-----------------------------------------------------------------------
1644 * Overlapping band subtraction. x1 is the left-most point not yet
1648 * TRUE if successful.
1651 * pReg may have rectangles added to it.
1653 *-----------------------------------------------------------------------
1657 miSubtractO (pReg, r1, r1End, r2, r2End, y1, y2, pOverlap)
1658 register RegionPtr pReg;
1667 register BoxPtr pNextRect;
1673 assert(r1 != r1End && r2 != r2End);
1675 pNextRect = REGION_TOP(pReg);
1682 * Subtrahend entirely to left of minuend: go to next subtrahend.
1686 else if (r2->x1 <= x1)
1689 * Subtrahend preceeds minuend: nuke left edge of minuend.
1695 * Minuend completely covered: advance to next minuend and
1696 * reset left fence to edge of new minuend.
1705 * Subtrahend now used up since it doesn't extend beyond
1711 else if (r2->x1 < r1->x2)
1714 * Left part of subtrahend covers part of minuend: add uncovered
1715 * part of minuend to region and skip to next subtrahend.
1718 NEWRECT(pReg, pNextRect, x1, y1, r2->x1, y2);
1724 * Minuend used up: advance to new...
1733 * Subtrahend used up
1741 * Minuend used up: add any remaining piece before advancing.
1744 NEWRECT(pReg, pNextRect, x1, y1, r1->x2, y2);
1749 } while ((r1 != r1End) && (r2 != r2End));
1753 * Add remaining minuend rectangles to region.
1758 NEWRECT(pReg, pNextRect, x1, y1, r1->x2, y2);
1767 *-----------------------------------------------------------------------
1769 * Subtract regS from regM and leave the result in regD.
1770 * S stands for subtrahend, M for minuend and D for difference.
1773 * TRUE if successful.
1776 * regD is overwritten.
1778 *-----------------------------------------------------------------------
1781 miSubtract(regD, regM, regS)
1782 register RegionPtr regD;
1783 register RegionPtr regM;
1784 register RegionPtr regS;
1786 Bool overlap; /* result ignored */
1791 /* check for trivial rejects */
1792 if (REGION_NIL(regM) || REGION_NIL(regS) ||
1793 !EXTENTCHECK(®M->extents, ®S->extents))
1795 return miRegionCopy(regD, regM);
1797 else if (regM == regS)
1800 regD->extents.x2 = regD->extents.x1;
1801 regD->extents.y2 = regD->extents.y1;
1802 regD->data = &miEmptyData;
1806 /* Add those rectangles in region 1 that aren't in region 2,
1807 do yucky substraction for overlaps, and
1808 just throw away rectangles in region 2 that aren't in region 1 */
1809 if (!miRegionOp(regD, regM, regS, miSubtractO, TRUE, FALSE, &overlap))
1813 * Can't alter RegD's extents before we call miRegionOp because
1814 * it might be one of the source regions and miRegionOp depends
1815 * on the extents of those regions being unaltered. Besides, this
1816 * way there's no checking against rectangles that will be nuked
1817 * due to coalescing, so we have to examine fewer rectangles.
1824 /*======================================================================
1826 *====================================================================*/
1829 *-----------------------------------------------------------------------
1831 * Take a region and a box and return a region that is everything
1832 * in the box but not in the region. The careful reader will note
1833 * that this is the same as subtracting the region from the box...
1839 * newReg is overwritten.
1841 *-----------------------------------------------------------------------
1844 miInverse(newReg, reg1, invRect)
1845 RegionPtr newReg; /* Destination region */
1846 RegionPtr reg1; /* Region to invert */
1847 BoxPtr invRect; /* Bounding box for inversion */
1849 RegionRec invReg; /* Quick and dirty region made from the
1851 Bool overlap; /* result ignored */
1855 /* check for trivial rejects */
1856 if (REGION_NIL(reg1) || !EXTENTCHECK(invRect, ®1->extents))
1858 newReg->extents = *invRect;
1860 newReg->data = (RegDataPtr)NULL;
1864 /* Add those rectangles in region 1 that aren't in region 2,
1865 do yucky substraction for overlaps, and
1866 just throw away rectangles in region 2 that aren't in region 1 */
1867 invReg.extents = *invRect;
1868 invReg.data = (RegDataPtr)NULL;
1869 if (!miRegionOp(newReg, &invReg, reg1, miSubtractO, TRUE, FALSE, &overlap))
1873 * Can't alter newReg's extents before we call miRegionOp because
1874 * it might be one of the source regions and miRegionOp depends
1875 * on the extents of those regions being unaltered. Besides, this
1876 * way there's no checking against rectangles that will be nuked
1877 * due to coalescing, so we have to examine fewer rectangles.
1879 miSetExtents(newReg);
1885 * RectIn(region, rect)
1886 * This routine takes a pointer to a region and a pointer to a box
1887 * and determines if the box is outside/inside/partly inside the region.
1889 * The idea is to travel through the list of rectangles trying to cover the
1890 * passed box with them. Anytime a piece of the rectangle isn't covered
1891 * by a band of rectangles, partOut is set TRUE. Any time a rectangle in
1892 * the region covers part of the box, partIn is set TRUE. The process ends
1893 * when either the box has been completely covered (we reached a band that
1894 * doesn't overlap the box, partIn is TRUE and partOut is false), the
1895 * box has been partially covered (partIn == partOut == TRUE -- because of
1896 * the banding, the first time this is true we know the box is only
1897 * partially in the region) or is outside the region (we reached a band
1898 * that doesn't overlap the box at all and partIn is false)
1902 miRectIn(region, prect)
1903 register RegionPtr region;
1904 register BoxPtr prect;
1908 register BoxPtr pbox;
1909 register BoxPtr pboxEnd;
1910 int partIn, partOut;
1914 numRects = REGION_NUM_RECTS(region);
1915 /* useful optimization */
1916 if (!numRects || !EXTENTCHECK(®ion->extents, prect))
1921 /* We know that it must be rgnIN or rgnPART */
1922 if (SUBSUMES(®ion->extents, prect))
1931 /* (x,y) starts at upper left of rect, moving to the right and down */
1935 /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
1936 for (pbox = REGION_BOXPTR(region), pboxEnd = pbox + numRects;
1942 continue; /* getting up to speed or skipping remainder of band */
1946 partOut = TRUE; /* missed part of rectangle above */
1947 if (partIn || (pbox->y1 >= prect->y2))
1949 y = pbox->y1; /* x guaranteed to be == prect->x1 */
1953 continue; /* not far enough over yet */
1957 partOut = TRUE; /* missed part of rectangle to left */
1962 if (pbox->x1 < prect->x2)
1964 partIn = TRUE; /* definitely overlap */
1969 if (pbox->x2 >= prect->x2)
1971 y = pbox->y2; /* finished with this band */
1974 x = prect->x1; /* reset x out to left again */
1979 * Because boxes in a band are maximal width, if the first box
1980 * to overlap the rectangle doesn't completely cover it in that
1981 * band, the rectangle must be partially out, since some of it
1982 * will be uncovered in that band. partIn will have been set true
1990 return(partIn ? ((y < prect->y2) ? rgnPART : rgnIN) : rgnOUT);
1993 /* TranslateRegion(pReg, x, y)
1998 miTranslateRegion(pReg, x, y)
1999 register RegionPtr pReg;
2005 register BoxPtr pbox;
2008 pReg->extents.x1 = x1 = pReg->extents.x1 + x;
2009 pReg->extents.y1 = y1 = pReg->extents.y1 + y;
2010 pReg->extents.x2 = x2 = pReg->extents.x2 + x;
2011 pReg->extents.y2 = y2 = pReg->extents.y2 + y;
2012 if (((x1 - MINSHORT)|(y1 - MINSHORT)|(MAXSHORT - x2)|(MAXSHORT - y2)) >= 0)
2014 if (pReg->data && (nbox = pReg->data->numRects))
2016 for (pbox = REGION_BOXPTR(pReg); nbox--; pbox++)
2026 if (((x2 - MINSHORT)|(y2 - MINSHORT)|(MAXSHORT - x1)|(MAXSHORT - y1)) <= 0)
2028 pReg->extents.x2 = pReg->extents.x1;
2029 pReg->extents.y2 = pReg->extents.y1;
2031 pReg->data = &miEmptyData;
2035 pReg->extents.x1 = MINSHORT;
2036 else if (x2 > MAXSHORT)
2037 pReg->extents.x2 = MAXSHORT;
2039 pReg->extents.y1 = MINSHORT;
2040 else if (y2 > MAXSHORT)
2041 pReg->extents.y2 = MAXSHORT;
2042 if (pReg->data && (nbox = pReg->data->numRects))
2044 register BoxPtr pboxout;
2046 for (pboxout = pbox = REGION_BOXPTR(pReg); nbox--; pbox++)
2048 pboxout->x1 = x1 = pbox->x1 + x;
2049 pboxout->y1 = y1 = pbox->y1 + y;
2050 pboxout->x2 = x2 = pbox->x2 + x;
2051 pboxout->y2 = y2 = pbox->y2 + y;
2052 if (((x2 - MINSHORT)|(y2 - MINSHORT)|
2053 (MAXSHORT - x1)|(MAXSHORT - y1)) <= 0)
2055 pReg->data->numRects--;
2059 pboxout->x1 = MINSHORT;
2060 else if (x2 > MAXSHORT)
2061 pboxout->x2 = MAXSHORT;
2063 pboxout->y1 = MINSHORT;
2064 else if (y2 > MAXSHORT)
2065 pboxout->y2 = MAXSHORT;
2068 if (pboxout != pbox)
2070 if (pReg->data->numRects == 1)
2072 pReg->extents = *REGION_BOXPTR(pReg);
2074 pReg->data = (RegDataPtr)NULL;
2083 miRegionReset(pReg, pBox)
2088 assert(pBox->x1<=pBox->x2);
2089 assert(pBox->y1<=pBox->y2);
2090 pReg->extents = *pBox;
2092 pReg->data = (RegDataPtr)NULL;
2096 miPointInRegion(pReg, x, y, box)
2097 register RegionPtr pReg;
2099 BoxPtr box; /* "return" value */
2101 register BoxPtr pbox, pboxEnd;
2105 numRects = REGION_NUM_RECTS(pReg);
2106 if (!numRects || !INBOX(&pReg->extents, x, y))
2110 *box = pReg->extents;
2113 for (pbox = REGION_BOXPTR(pReg), pboxEnd = pbox + numRects;
2118 continue; /* not there yet */
2119 if ((y < pbox->y1) || (x < pbox->x1))
2120 break; /* missed it */
2122 continue; /* not there yet */
2130 miRegionNotEmpty(pReg)
2134 return(!REGION_NIL(pReg));
2144 pReg->extents.x2 = pReg->extents.x1;
2145 pReg->extents.y2 = pReg->extents.y1;
2146 pReg->data = &miEmptyData;
2150 miRegionExtents(pReg)
2154 return(&pReg->extents);
2157 #define ExchangeSpans(a, b) \
2162 tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt; \
2163 tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
2166 /* ||| I should apply the merge sort code to rectangle sorting above, and see
2167 if mapping time can be improved. But right now I've been at work 12 hours,
2171 static void QuickSortSpans(spans, widths, numSpans)
2172 register DDXPointRec spans[];
2173 register int widths[];
2174 register int numSpans;
2177 register int i, j, m;
2178 register DDXPointPtr r;
2180 /* Always called with numSpans > 1 */
2181 /* Sorts only by y, doesn't bother to sort by x */
2187 /* Do insertion sort */
2193 { /* while i != numSpans */
2197 /* spans[i] is out of order. Move into proper location. */
2201 for (j = 0; y >= spans[j].y; j++) {}
2204 for (k = i; k != j; k--)
2206 spans[k] = spans[k-1];
2207 widths[k] = widths[k-1];
2212 } /* if out of order */
2215 } while (i != numSpans);
2219 /* Choose partition element, stick in location 0 */
2221 if (spans[m].y > spans[0].y) ExchangeSpans(m, 0);
2222 if (spans[m].y > spans[numSpans-1].y) ExchangeSpans(m, numSpans-1);
2223 if (spans[m].y > spans[0].y) ExchangeSpans(m, 0);
2226 /* Partition array */
2236 } while (i != numSpans && r->y < y);
2244 ExchangeSpans(i, j);
2247 /* Move partition element back to middle */
2248 ExchangeSpans(0, j);
2251 if (numSpans-j-1 > 1)
2252 QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1);
2254 } while (numSpans > 1);
2257 #define NextBand() \
2259 clipy1 = pboxBandStart->y1; \
2260 clipy2 = pboxBandStart->y2; \
2261 pboxBandEnd = pboxBandStart + 1; \
2262 while (pboxBandEnd != pboxLast && pboxBandEnd->y1 == clipy1) { \
2265 for (; ppt != pptLast && ppt->y < clipy1; ppt++, pwidth++) {} \
2269 Clip a list of scanlines to a region. The caller has allocated the
2270 space. FSorted is non-zero if the scanline origins are in ascending
2272 returns the number of new, clipped scanlines.
2276 miClipSpans(prgnDst, ppt, pwidth, nspans, pptNew, pwidthNew, fSorted)
2278 register DDXPointPtr ppt;
2279 register int *pwidth;
2281 register DDXPointPtr pptNew;
2285 register DDXPointPtr pptLast;
2286 int *pwidthNewStart; /* the vengeance of Xerox! */
2287 register int y, x1, x2;
2288 register int numRects;
2291 pptLast = ppt + nspans;
2292 pwidthNewStart = pwidthNew;
2296 /* Do special fast code with clip boundaries in registers(?) */
2297 /* It doesn't pay much to make use of fSorted in this case,
2298 so we lump everything together. */
2300 register int clipx1, clipx2, clipy1, clipy2;
2302 clipx1 = prgnDst->extents.x1;
2303 clipy1 = prgnDst->extents.y1;
2304 clipx2 = prgnDst->extents.x2;
2305 clipy2 = prgnDst->extents.y2;
2307 for (; ppt != pptLast; ppt++, pwidth++)
2311 if (clipy1 <= y && y < clipy2)
2314 if (x1 < clipx1) x1 = clipx1;
2315 if (x2 > clipx2) x2 = clipx2;
2318 /* part of span in clip rectangle */
2321 *pwidthNew = x2 - x1;
2329 else if (numRects = prgnDst->data->numRects)
2331 /* Have to clip against many boxes */
2332 BoxPtr pboxBandStart, pboxBandEnd;
2333 register BoxPtr pbox;
2334 register BoxPtr pboxLast;
2335 register int clipy1, clipy2;
2337 /* In this case, taking advantage of sorted spans gains more than
2338 the sorting costs. */
2339 if ((! fSorted) && (nspans > 1))
2340 QuickSortSpans(ppt, pwidth, nspans);
2342 pboxBandStart = REGION_BOXPTR(prgnDst);
2343 pboxLast = pboxBandStart + numRects;
2347 for (; ppt != pptLast; )
2352 /* span is in the current band */
2353 pbox = pboxBandStart;
2357 { /* For each box in band */
2358 register int newx1, newx2;
2362 if (newx1 < pbox->x1) newx1 = pbox->x1;
2363 if (newx2 > pbox->x2) newx2 = pbox->x2;
2366 /* Part of span in clip rectangle */
2369 *pwidthNew = newx2 - newx1;
2374 } while (pbox != pboxBandEnd);
2380 /* Move to next band, adjust ppt as needed */
2381 pboxBandStart = pboxBandEnd;
2382 if (pboxBandStart == pboxLast)
2383 break; /* We're completely done */
2388 return (pwidthNew - pwidthNewStart);
2391 /* find the band in a region with the most rectangles */
2397 register BoxPtr pbox;
2398 register int nThisBand;
2399 register int nMaxBand = 0;
2403 nbox = REGION_NUM_RECTS(prgn);
2404 pbox = REGION_RECTS(prgn);
2408 yThisBand = pbox->y1;
2410 while((nbox > 0) && (pbox->y1 == yThisBand))
2416 if (nThisBand > nMaxBand)
2417 nMaxBand = nThisBand;