Commit | Line | Data |
---|---|---|
a09e091a JB |
1 | /*********************************************************** |
2 | ||
3 | Copyright 1987, 1988, 1989, 1998 The Open Group | |
4 | ||
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 | |
9 | documentation. | |
10 | ||
11 | The above copyright notice and this permission notice shall be included in | |
12 | all copies or substantial portions of the Software. | |
13 | ||
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. | |
20 | ||
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. | |
24 | ||
25 | ||
26 | Copyright 1987, 1988, 1989 by | |
27 | Digital Equipment Corporation, Maynard, Massachusetts. | |
28 | ||
29 | All Rights Reserved | |
30 | ||
31 | Permission to use, copy, modify, and distribute this software and its | |
32 | documentation for any purpose and without fee is hereby granted, | |
33 | provided that the above copyright notice appear in all copies and that | |
34 | both that copyright notice and this permission notice appear in | |
35 | supporting documentation, and that the name of Digital not be | |
36 | used in advertising or publicity pertaining to distribution of the | |
37 | software without specific, written prior permission. | |
38 | ||
39 | DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING | |
40 | ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL | |
41 | DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR | |
42 | ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, | |
43 | WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, | |
44 | ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS | |
45 | SOFTWARE. | |
46 | ||
47 | ******************************************************************/ | |
48 | ||
49 | /* The panoramix components contained the following notice */ | |
50 | /***************************************************************** | |
51 | ||
52 | Copyright (c) 1991, 1997 Digital Equipment Corporation, Maynard, Massachusetts. | |
53 | ||
54 | Permission is hereby granted, free of charge, to any person obtaining a copy | |
55 | of this software and associated documentation files (the "Software"), to deal | |
56 | in the Software without restriction, including without limitation the rights | |
57 | to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
58 | copies of the Software. | |
59 | ||
60 | The above copyright notice and this permission notice shall be included in | |
61 | all copies or substantial portions of the Software. | |
62 | ||
63 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
64 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
65 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | |
66 | DIGITAL EQUIPMENT CORPORATION BE LIABLE FOR ANY CLAIM, DAMAGES, INCLUDING, | |
67 | BUT NOT LIMITED TO CONSEQUENTIAL OR INCIDENTAL DAMAGES, OR OTHER LIABILITY, | |
68 | WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR | |
69 | IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | |
70 | ||
71 | Except as contained in this notice, the name of Digital Equipment Corporation | |
72 | shall not be used in advertising or otherwise to promote the sale, use or other | |
73 | dealings in this Software without prior written authorization from Digital | |
74 | Equipment Corporation. | |
75 | ||
76 | ******************************************************************/ | |
77 | ||
78 | #ifdef HAVE_DIX_CONFIG_H | |
79 | #include <dix-config.h> | |
80 | #endif | |
81 | ||
82 | #include "regionstr.h" | |
83 | #include <X11/Xprotostr.h> | |
84 | #include <X11/Xfuncproto.h> | |
85 | #include "gc.h" | |
86 | #include <pixman.h> | |
87 | ||
88 | #undef assert | |
89 | #ifdef REGION_DEBUG | |
90 | #define assert(expr) { \ | |
91 | CARD32 *foo = NULL; \ | |
92 | if (!(expr)) { \ | |
93 | ErrorF("Assertion failed file %s, line %d: %s\n", \ | |
94 | __FILE__, __LINE__, #expr); \ | |
95 | *foo = 0xdeadbeef; /* to get a backtrace */ \ | |
96 | } \ | |
97 | } | |
98 | #else | |
99 | #define assert(expr) | |
100 | #endif | |
101 | ||
102 | #define good(reg) assert(RegionIsValid(reg)) | |
103 | ||
104 | /* | |
105 | * The functions in this file implement the Region abstraction used extensively | |
106 | * throughout the X11 sample server. A Region is simply a set of disjoint | |
107 | * (non-overlapping) rectangles, plus an "extent" rectangle which is the | |
108 | * smallest single rectangle that contains all the non-overlapping rectangles. | |
109 | * | |
110 | * A Region is implemented as a "y-x-banded" array of rectangles. This array | |
111 | * imposes two degrees of order. First, all rectangles are sorted by top side | |
112 | * y coordinate first (y1), and then by left side x coordinate (x1). | |
113 | * | |
114 | * Furthermore, the rectangles are grouped into "bands". Each rectangle in a | |
115 | * band has the same top y coordinate (y1), and each has the same bottom y | |
116 | * coordinate (y2). Thus all rectangles in a band differ only in their left | |
117 | * and right side (x1 and x2). Bands are implicit in the array of rectangles: | |
118 | * there is no separate list of band start pointers. | |
119 | * | |
120 | * The y-x band representation does not minimize rectangles. In particular, | |
121 | * if a rectangle vertically crosses a band (the rectangle has scanlines in | |
122 | * the y1 to y2 area spanned by the band), then the rectangle may be broken | |
123 | * down into two or more smaller rectangles stacked one atop the other. | |
124 | * | |
125 | * ----------- ----------- | |
126 | * | | | | band 0 | |
127 | * | | -------- ----------- -------- | |
128 | * | | | | in y-x banded | | | | band 1 | |
129 | * | | | | form is | | | | | |
130 | * ----------- | | ----------- -------- | |
131 | * | | | | band 2 | |
132 | * -------- -------- | |
133 | * | |
134 | * An added constraint on the rectangles is that they must cover as much | |
135 | * horizontal area as possible: no two rectangles within a band are allowed | |
136 | * to touch. | |
137 | * | |
138 | * Whenever possible, bands will be merged together to cover a greater vertical | |
139 | * distance (and thus reduce the number of rectangles). Two bands can be merged | |
140 | * only if the bottom of one touches the top of the other and they have | |
141 | * rectangles in the same places (of the same width, of course). | |
142 | * | |
143 | * Adam de Boor wrote most of the original region code. Joel McCormack | |
144 | * substantially modified or rewrote most of the core arithmetic routines, | |
145 | * and added RegionValidate in order to support several speed improvements | |
146 | * to miValidateTree. Bob Scheifler changed the representation to be more | |
147 | * compact when empty or a single rectangle, and did a bunch of gratuitous | |
148 | * reformatting. | |
149 | */ | |
150 | ||
151 | /* true iff two Boxes overlap */ | |
152 | #define EXTENTCHECK(r1,r2) \ | |
153 | (!( ((r1)->x2 <= (r2)->x1) || \ | |
154 | ((r1)->x1 >= (r2)->x2) || \ | |
155 | ((r1)->y2 <= (r2)->y1) || \ | |
156 | ((r1)->y1 >= (r2)->y2) ) ) | |
157 | ||
158 | /* true iff (x,y) is in Box */ | |
159 | #define INBOX(r,x,y) \ | |
160 | ( ((r)->x2 > x) && \ | |
161 | ((r)->x1 <= x) && \ | |
162 | ((r)->y2 > y) && \ | |
163 | ((r)->y1 <= y) ) | |
164 | ||
165 | /* true iff Box r1 contains Box r2 */ | |
166 | #define SUBSUMES(r1,r2) \ | |
167 | ( ((r1)->x1 <= (r2)->x1) && \ | |
168 | ((r1)->x2 >= (r2)->x2) && \ | |
169 | ((r1)->y1 <= (r2)->y1) && \ | |
170 | ((r1)->y2 >= (r2)->y2) ) | |
171 | ||
172 | #define xallocData(n) malloc(RegionSizeof(n)) | |
173 | #define xfreeData(reg) if ((reg)->data && (reg)->data->size) free((reg)->data) | |
174 | ||
175 | #define RECTALLOC_BAIL(pReg,n,bail) \ | |
176 | if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \ | |
177 | if (!RegionRectAlloc(pReg, n)) { goto bail; } | |
178 | ||
179 | #define RECTALLOC(pReg,n) \ | |
180 | if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \ | |
181 | if (!RegionRectAlloc(pReg, n)) { return FALSE; } | |
182 | ||
183 | #define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \ | |
184 | { \ | |
185 | pNextRect->x1 = nx1; \ | |
186 | pNextRect->y1 = ny1; \ | |
187 | pNextRect->x2 = nx2; \ | |
188 | pNextRect->y2 = ny2; \ | |
189 | pNextRect++; \ | |
190 | } | |
191 | ||
192 | #define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \ | |
193 | { \ | |
194 | if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\ | |
195 | { \ | |
196 | if (!RegionRectAlloc(pReg, 1)) \ | |
197 | return FALSE; \ | |
198 | pNextRect = RegionTop(pReg); \ | |
199 | } \ | |
200 | ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \ | |
201 | pReg->data->numRects++; \ | |
202 | assert(pReg->data->numRects<=pReg->data->size); \ | |
203 | } | |
204 | ||
205 | #define DOWNSIZE(reg,numRects) \ | |
206 | if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \ | |
207 | { \ | |
208 | RegDataPtr NewData; \ | |
209 | NewData = (RegDataPtr)realloc((reg)->data, RegionSizeof(numRects)); \ | |
210 | if (NewData) \ | |
211 | { \ | |
212 | NewData->size = (numRects); \ | |
213 | (reg)->data = NewData; \ | |
214 | } \ | |
215 | } | |
216 | ||
217 | BoxRec RegionEmptyBox = { 0, 0, 0, 0 }; | |
218 | RegDataRec RegionEmptyData = { 0, 0 }; | |
219 | ||
220 | RegDataRec RegionBrokenData = { 0, 0 }; | |
221 | static RegionRec RegionBrokenRegion = { {0, 0, 0, 0}, &RegionBrokenData }; | |
222 | ||
223 | void | |
224 | InitRegions(void) | |
225 | { | |
226 | pixman_region_set_static_pointers(&RegionEmptyBox, &RegionEmptyData, | |
227 | &RegionBrokenData); | |
228 | } | |
229 | ||
230 | /***************************************************************** | |
231 | * RegionCreate(rect, size) | |
232 | * This routine does a simple malloc to make a structure of | |
233 | * REGION of "size" number of rectangles. | |
234 | *****************************************************************/ | |
235 | ||
236 | RegionPtr | |
237 | RegionCreate(BoxPtr rect, int size) | |
238 | { | |
239 | RegionPtr pReg; | |
240 | ||
241 | pReg = (RegionPtr) malloc(sizeof(RegionRec)); | |
242 | if (!pReg) | |
243 | return &RegionBrokenRegion; | |
244 | ||
245 | RegionInit(pReg, rect, size); | |
246 | ||
247 | return pReg; | |
248 | } | |
249 | ||
250 | void | |
251 | RegionDestroy(RegionPtr pReg) | |
252 | { | |
253 | pixman_region_fini(pReg); | |
254 | if (pReg != &RegionBrokenRegion) | |
255 | free(pReg); | |
256 | } | |
257 | ||
258 | RegionPtr | |
259 | RegionDuplicate(RegionPtr pOld) | |
260 | { | |
261 | RegionPtr pNew; | |
262 | ||
263 | pNew = RegionCreate(&pOld->extents, 0); | |
264 | if (!pNew) | |
265 | return NULL; | |
266 | if (!RegionCopy(pNew, pOld)) { | |
267 | RegionDestroy(pNew); | |
268 | return NULL; | |
269 | } | |
270 | return pNew; | |
271 | } | |
272 | ||
273 | void | |
274 | RegionPrint(RegionPtr rgn) | |
275 | { | |
276 | int num, size; | |
277 | int i; | |
278 | BoxPtr rects; | |
279 | ||
280 | num = RegionNumRects(rgn); | |
281 | size = RegionSize(rgn); | |
282 | rects = RegionRects(rgn); | |
283 | ErrorF("[mi] num: %d size: %d\n", num, size); | |
284 | ErrorF("[mi] extents: %d %d %d %d\n", | |
285 | rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2); | |
286 | for (i = 0; i < num; i++) | |
287 | ErrorF("[mi] %d %d %d %d \n", | |
288 | rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2); | |
289 | ErrorF("[mi] \n"); | |
290 | } | |
291 | ||
292 | #ifdef DEBUG | |
293 | Bool | |
294 | RegionIsValid(RegionPtr reg) | |
295 | { | |
296 | int i, numRects; | |
297 | ||
298 | if ((reg->extents.x1 > reg->extents.x2) || | |
299 | (reg->extents.y1 > reg->extents.y2)) | |
300 | return FALSE; | |
301 | numRects = RegionNumRects(reg); | |
302 | if (!numRects) | |
303 | return ((reg->extents.x1 == reg->extents.x2) && | |
304 | (reg->extents.y1 == reg->extents.y2) && | |
305 | (reg->data->size || (reg->data == &RegionEmptyData))); | |
306 | else if (numRects == 1) | |
307 | return !reg->data; | |
308 | else { | |
309 | BoxPtr pboxP, pboxN; | |
310 | BoxRec box; | |
311 | ||
312 | pboxP = RegionRects(reg); | |
313 | box = *pboxP; | |
314 | box.y2 = pboxP[numRects - 1].y2; | |
315 | pboxN = pboxP + 1; | |
316 | for (i = numRects; --i > 0; pboxP++, pboxN++) { | |
317 | if ((pboxN->x1 >= pboxN->x2) || (pboxN->y1 >= pboxN->y2)) | |
318 | return FALSE; | |
319 | if (pboxN->x1 < box.x1) | |
320 | box.x1 = pboxN->x1; | |
321 | if (pboxN->x2 > box.x2) | |
322 | box.x2 = pboxN->x2; | |
323 | if ((pboxN->y1 < pboxP->y1) || | |
324 | ((pboxN->y1 == pboxP->y1) && | |
325 | ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2)))) | |
326 | return FALSE; | |
327 | } | |
328 | return ((box.x1 == reg->extents.x1) && | |
329 | (box.x2 == reg->extents.x2) && | |
330 | (box.y1 == reg->extents.y1) && (box.y2 == reg->extents.y2)); | |
331 | } | |
332 | } | |
333 | #endif /* DEBUG */ | |
334 | ||
335 | Bool | |
336 | RegionBreak(RegionPtr pReg) | |
337 | { | |
338 | xfreeData(pReg); | |
339 | pReg->extents = RegionEmptyBox; | |
340 | pReg->data = &RegionBrokenData; | |
341 | return FALSE; | |
342 | } | |
343 | ||
344 | Bool | |
345 | RegionRectAlloc(RegionPtr pRgn, int n) | |
346 | { | |
347 | RegDataPtr data; | |
348 | ||
349 | if (!pRgn->data) { | |
350 | n++; | |
351 | pRgn->data = xallocData(n); | |
352 | if (!pRgn->data) | |
353 | return RegionBreak(pRgn); | |
354 | pRgn->data->numRects = 1; | |
355 | *RegionBoxptr(pRgn) = pRgn->extents; | |
356 | } | |
357 | else if (!pRgn->data->size) { | |
358 | pRgn->data = xallocData(n); | |
359 | if (!pRgn->data) | |
360 | return RegionBreak(pRgn); | |
361 | pRgn->data->numRects = 0; | |
362 | } | |
363 | else { | |
364 | if (n == 1) { | |
365 | n = pRgn->data->numRects; | |
366 | if (n > 500) /* XXX pick numbers out of a hat */ | |
367 | n = 250; | |
368 | } | |
369 | n += pRgn->data->numRects; | |
370 | data = (RegDataPtr) realloc(pRgn->data, RegionSizeof(n)); | |
371 | if (!data) | |
372 | return RegionBreak(pRgn); | |
373 | pRgn->data = data; | |
374 | } | |
375 | pRgn->data->size = n; | |
376 | return TRUE; | |
377 | } | |
378 | ||
379 | /*====================================================================== | |
380 | * Generic Region Operator | |
381 | *====================================================================*/ | |
382 | ||
383 | /*- | |
384 | *----------------------------------------------------------------------- | |
385 | * RegionCoalesce -- | |
386 | * Attempt to merge the boxes in the current band with those in the | |
387 | * previous one. We are guaranteed that the current band extends to | |
388 | * the end of the rects array. Used only by RegionOp. | |
389 | * | |
390 | * Results: | |
391 | * The new index for the previous band. | |
392 | * | |
393 | * Side Effects: | |
394 | * If coalescing takes place: | |
395 | * - rectangles in the previous band will have their y2 fields | |
396 | * altered. | |
397 | * - pReg->data->numRects will be decreased. | |
398 | * | |
399 | *----------------------------------------------------------------------- | |
400 | */ | |
401 | _X_INLINE static int | |
402 | RegionCoalesce(RegionPtr pReg, /* Region to coalesce */ | |
403 | int prevStart, /* Index of start of previous band */ | |
404 | int curStart) | |
405 | { /* Index of start of current band */ | |
406 | BoxPtr pPrevBox; /* Current box in previous band */ | |
407 | BoxPtr pCurBox; /* Current box in current band */ | |
408 | int numRects; /* Number rectangles in both bands */ | |
409 | int y2; /* Bottom of current band */ | |
410 | ||
411 | /* | |
412 | * Figure out how many rectangles are in the band. | |
413 | */ | |
414 | numRects = curStart - prevStart; | |
415 | assert(numRects == pReg->data->numRects - curStart); | |
416 | ||
417 | if (!numRects) | |
418 | return curStart; | |
419 | ||
420 | /* | |
421 | * The bands may only be coalesced if the bottom of the previous | |
422 | * matches the top scanline of the current. | |
423 | */ | |
424 | pPrevBox = RegionBox(pReg, prevStart); | |
425 | pCurBox = RegionBox(pReg, curStart); | |
426 | if (pPrevBox->y2 != pCurBox->y1) | |
427 | return curStart; | |
428 | ||
429 | /* | |
430 | * Make sure the bands have boxes in the same places. This | |
431 | * assumes that boxes have been added in such a way that they | |
432 | * cover the most area possible. I.e. two boxes in a band must | |
433 | * have some horizontal space between them. | |
434 | */ | |
435 | y2 = pCurBox->y2; | |
436 | ||
437 | do { | |
438 | if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) { | |
439 | return curStart; | |
440 | } | |
441 | pPrevBox++; | |
442 | pCurBox++; | |
443 | numRects--; | |
444 | } while (numRects); | |
445 | ||
446 | /* | |
447 | * The bands may be merged, so set the bottom y of each box | |
448 | * in the previous band to the bottom y of the current band. | |
449 | */ | |
450 | numRects = curStart - prevStart; | |
451 | pReg->data->numRects -= numRects; | |
452 | do { | |
453 | pPrevBox--; | |
454 | pPrevBox->y2 = y2; | |
455 | numRects--; | |
456 | } while (numRects); | |
457 | return prevStart; | |
458 | } | |
459 | ||
460 | /* Quicky macro to avoid trivial reject procedure calls to RegionCoalesce */ | |
461 | ||
462 | #define Coalesce(newReg, prevBand, curBand) \ | |
463 | if (curBand - prevBand == newReg->data->numRects - curBand) { \ | |
464 | prevBand = RegionCoalesce(newReg, prevBand, curBand); \ | |
465 | } else { \ | |
466 | prevBand = curBand; \ | |
467 | } | |
468 | ||
469 | /*- | |
470 | *----------------------------------------------------------------------- | |
471 | * RegionAppendNonO -- | |
472 | * Handle a non-overlapping band for the union and subtract operations. | |
473 | * Just adds the (top/bottom-clipped) rectangles into the region. | |
474 | * Doesn't have to check for subsumption or anything. | |
475 | * | |
476 | * Results: | |
477 | * None. | |
478 | * | |
479 | * Side Effects: | |
480 | * pReg->data->numRects is incremented and the rectangles overwritten | |
481 | * with the rectangles we're passed. | |
482 | * | |
483 | *----------------------------------------------------------------------- | |
484 | */ | |
485 | ||
486 | _X_INLINE static Bool | |
487 | RegionAppendNonO(RegionPtr pReg, BoxPtr r, BoxPtr rEnd, int y1, int y2) | |
488 | { | |
489 | BoxPtr pNextRect; | |
490 | int newRects; | |
491 | ||
492 | newRects = rEnd - r; | |
493 | ||
494 | assert(y1 < y2); | |
495 | assert(newRects != 0); | |
496 | ||
497 | /* Make sure we have enough space for all rectangles to be added */ | |
498 | RECTALLOC(pReg, newRects); | |
499 | pNextRect = RegionTop(pReg); | |
500 | pReg->data->numRects += newRects; | |
501 | do { | |
502 | assert(r->x1 < r->x2); | |
503 | ADDRECT(pNextRect, r->x1, y1, r->x2, y2); | |
504 | r++; | |
505 | } while (r != rEnd); | |
506 | ||
507 | return TRUE; | |
508 | } | |
509 | ||
510 | #define FindBand(r, rBandEnd, rEnd, ry1) \ | |
511 | { \ | |
512 | ry1 = r->y1; \ | |
513 | rBandEnd = r+1; \ | |
514 | while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \ | |
515 | rBandEnd++; \ | |
516 | } \ | |
517 | } | |
518 | ||
519 | #define AppendRegions(newReg, r, rEnd) \ | |
520 | { \ | |
521 | int newRects; \ | |
522 | if ((newRects = rEnd - r)) { \ | |
523 | RECTALLOC(newReg, newRects); \ | |
524 | memmove((char *)RegionTop(newReg),(char *)r, \ | |
525 | newRects * sizeof(BoxRec)); \ | |
526 | newReg->data->numRects += newRects; \ | |
527 | } \ | |
528 | } | |
529 | ||
530 | /*- | |
531 | *----------------------------------------------------------------------- | |
532 | * RegionOp -- | |
533 | * Apply an operation to two regions. Called by RegionUnion, RegionInverse, | |
534 | * RegionSubtract, RegionIntersect.... Both regions MUST have at least one | |
535 | * rectangle, and cannot be the same object. | |
536 | * | |
537 | * Results: | |
538 | * TRUE if successful. | |
539 | * | |
540 | * Side Effects: | |
541 | * The new region is overwritten. | |
542 | * pOverlap set to TRUE if overlapFunc ever returns TRUE. | |
543 | * | |
544 | * Notes: | |
545 | * The idea behind this function is to view the two regions as sets. | |
546 | * Together they cover a rectangle of area that this function divides | |
547 | * into horizontal bands where points are covered only by one region | |
548 | * or by both. For the first case, the nonOverlapFunc is called with | |
549 | * each the band and the band's upper and lower extents. For the | |
550 | * second, the overlapFunc is called to process the entire band. It | |
551 | * is responsible for clipping the rectangles in the band, though | |
552 | * this function provides the boundaries. | |
553 | * At the end of each band, the new region is coalesced, if possible, | |
554 | * to reduce the number of rectangles in the region. | |
555 | * | |
556 | *----------------------------------------------------------------------- | |
557 | */ | |
558 | ||
559 | typedef Bool (*OverlapProcPtr) (RegionPtr pReg, | |
560 | BoxPtr r1, | |
561 | BoxPtr r1End, | |
562 | BoxPtr r2, | |
563 | BoxPtr r2End, | |
564 | short y1, short y2, Bool *pOverlap); | |
565 | ||
566 | static Bool | |
567 | RegionOp(RegionPtr newReg, /* Place to store result */ | |
568 | RegionPtr reg1, /* First region in operation */ | |
569 | RegionPtr reg2, /* 2d region in operation */ | |
570 | OverlapProcPtr overlapFunc, /* Function to call for over- | |
571 | * lapping bands */ | |
572 | Bool appendNon1, /* Append non-overlapping bands */ | |
573 | /* in region 1 ? */ | |
574 | Bool appendNon2, /* Append non-overlapping bands */ | |
575 | /* in region 2 ? */ | |
576 | Bool *pOverlap) | |
577 | { | |
578 | BoxPtr r1; /* Pointer into first region */ | |
579 | BoxPtr r2; /* Pointer into 2d region */ | |
580 | BoxPtr r1End; /* End of 1st region */ | |
581 | BoxPtr r2End; /* End of 2d region */ | |
582 | short ybot; /* Bottom of intersection */ | |
583 | short ytop; /* Top of intersection */ | |
584 | RegDataPtr oldData; /* Old data for newReg */ | |
585 | int prevBand; /* Index of start of | |
586 | * previous band in newReg */ | |
587 | int curBand; /* Index of start of current | |
588 | * band in newReg */ | |
589 | BoxPtr r1BandEnd; /* End of current band in r1 */ | |
590 | BoxPtr r2BandEnd; /* End of current band in r2 */ | |
591 | short top; /* Top of non-overlapping band */ | |
592 | short bot; /* Bottom of non-overlapping band */ | |
593 | int r1y1; /* Temps for r1->y1 and r2->y1 */ | |
594 | int r2y1; | |
595 | int newSize; | |
596 | int numRects; | |
597 | ||
598 | /* | |
599 | * Break any region computed from a broken region | |
600 | */ | |
601 | if (RegionNar(reg1) || RegionNar(reg2)) | |
602 | return RegionBreak(newReg); | |
603 | ||
604 | /* | |
605 | * Initialization: | |
606 | * set r1, r2, r1End and r2End appropriately, save the rectangles | |
607 | * of the destination region until the end in case it's one of | |
608 | * the two source regions, then mark the "new" region empty, allocating | |
609 | * another array of rectangles for it to use. | |
610 | */ | |
611 | ||
612 | r1 = RegionRects(reg1); | |
613 | newSize = RegionNumRects(reg1); | |
614 | r1End = r1 + newSize; | |
615 | numRects = RegionNumRects(reg2); | |
616 | r2 = RegionRects(reg2); | |
617 | r2End = r2 + numRects; | |
618 | assert(r1 != r1End); | |
619 | assert(r2 != r2End); | |
620 | ||
621 | oldData = NULL; | |
622 | if (((newReg == reg1) && (newSize > 1)) || | |
623 | ((newReg == reg2) && (numRects > 1))) { | |
624 | oldData = newReg->data; | |
625 | newReg->data = &RegionEmptyData; | |
626 | } | |
627 | /* guess at new size */ | |
628 | if (numRects > newSize) | |
629 | newSize = numRects; | |
630 | newSize <<= 1; | |
631 | if (!newReg->data) | |
632 | newReg->data = &RegionEmptyData; | |
633 | else if (newReg->data->size) | |
634 | newReg->data->numRects = 0; | |
635 | if (newSize > newReg->data->size) | |
636 | if (!RegionRectAlloc(newReg, newSize)) | |
637 | return FALSE; | |
638 | ||
639 | /* | |
640 | * Initialize ybot. | |
641 | * In the upcoming loop, ybot and ytop serve different functions depending | |
642 | * on whether the band being handled is an overlapping or non-overlapping | |
643 | * band. | |
644 | * In the case of a non-overlapping band (only one of the regions | |
645 | * has points in the band), ybot is the bottom of the most recent | |
646 | * intersection and thus clips the top of the rectangles in that band. | |
647 | * ytop is the top of the next intersection between the two regions and | |
648 | * serves to clip the bottom of the rectangles in the current band. | |
649 | * For an overlapping band (where the two regions intersect), ytop clips | |
650 | * the top of the rectangles of both regions and ybot clips the bottoms. | |
651 | */ | |
652 | ||
653 | ybot = min(r1->y1, r2->y1); | |
654 | ||
655 | /* | |
656 | * prevBand serves to mark the start of the previous band so rectangles | |
657 | * can be coalesced into larger rectangles. qv. RegionCoalesce, above. | |
658 | * In the beginning, there is no previous band, so prevBand == curBand | |
659 | * (curBand is set later on, of course, but the first band will always | |
660 | * start at index 0). prevBand and curBand must be indices because of | |
661 | * the possible expansion, and resultant moving, of the new region's | |
662 | * array of rectangles. | |
663 | */ | |
664 | prevBand = 0; | |
665 | ||
666 | do { | |
667 | /* | |
668 | * This algorithm proceeds one source-band (as opposed to a | |
669 | * destination band, which is determined by where the two regions | |
670 | * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the | |
671 | * rectangle after the last one in the current band for their | |
672 | * respective regions. | |
673 | */ | |
674 | assert(r1 != r1End); | |
675 | assert(r2 != r2End); | |
676 | ||
677 | FindBand(r1, r1BandEnd, r1End, r1y1); | |
678 | FindBand(r2, r2BandEnd, r2End, r2y1); | |
679 | ||
680 | /* | |
681 | * First handle the band that doesn't intersect, if any. | |
682 | * | |
683 | * Note that attention is restricted to one band in the | |
684 | * non-intersecting region at once, so if a region has n | |
685 | * bands between the current position and the next place it overlaps | |
686 | * the other, this entire loop will be passed through n times. | |
687 | */ | |
688 | if (r1y1 < r2y1) { | |
689 | if (appendNon1) { | |
690 | top = max(r1y1, ybot); | |
691 | bot = min(r1->y2, r2y1); | |
692 | if (top != bot) { | |
693 | curBand = newReg->data->numRects; | |
694 | RegionAppendNonO(newReg, r1, r1BandEnd, top, bot); | |
695 | Coalesce(newReg, prevBand, curBand); | |
696 | } | |
697 | } | |
698 | ytop = r2y1; | |
699 | } | |
700 | else if (r2y1 < r1y1) { | |
701 | if (appendNon2) { | |
702 | top = max(r2y1, ybot); | |
703 | bot = min(r2->y2, r1y1); | |
704 | if (top != bot) { | |
705 | curBand = newReg->data->numRects; | |
706 | RegionAppendNonO(newReg, r2, r2BandEnd, top, bot); | |
707 | Coalesce(newReg, prevBand, curBand); | |
708 | } | |
709 | } | |
710 | ytop = r1y1; | |
711 | } | |
712 | else { | |
713 | ytop = r1y1; | |
714 | } | |
715 | ||
716 | /* | |
717 | * Now see if we've hit an intersecting band. The two bands only | |
718 | * intersect if ybot > ytop | |
719 | */ | |
720 | ybot = min(r1->y2, r2->y2); | |
721 | if (ybot > ytop) { | |
722 | curBand = newReg->data->numRects; | |
723 | (*overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, | |
724 | pOverlap); | |
725 | Coalesce(newReg, prevBand, curBand); | |
726 | } | |
727 | ||
728 | /* | |
729 | * If we've finished with a band (y2 == ybot) we skip forward | |
730 | * in the region to the next band. | |
731 | */ | |
732 | if (r1->y2 == ybot) | |
733 | r1 = r1BandEnd; | |
734 | if (r2->y2 == ybot) | |
735 | r2 = r2BandEnd; | |
736 | ||
737 | } while (r1 != r1End && r2 != r2End); | |
738 | ||
739 | /* | |
740 | * Deal with whichever region (if any) still has rectangles left. | |
741 | * | |
742 | * We only need to worry about banding and coalescing for the very first | |
743 | * band left. After that, we can just group all remaining boxes, | |
744 | * regardless of how many bands, into one final append to the list. | |
745 | */ | |
746 | ||
747 | if ((r1 != r1End) && appendNon1) { | |
748 | /* Do first nonOverlap1Func call, which may be able to coalesce */ | |
749 | FindBand(r1, r1BandEnd, r1End, r1y1); | |
750 | curBand = newReg->data->numRects; | |
751 | RegionAppendNonO(newReg, r1, r1BandEnd, max(r1y1, ybot), r1->y2); | |
752 | Coalesce(newReg, prevBand, curBand); | |
753 | /* Just append the rest of the boxes */ | |
754 | AppendRegions(newReg, r1BandEnd, r1End); | |
755 | ||
756 | } | |
757 | else if ((r2 != r2End) && appendNon2) { | |
758 | /* Do first nonOverlap2Func call, which may be able to coalesce */ | |
759 | FindBand(r2, r2BandEnd, r2End, r2y1); | |
760 | curBand = newReg->data->numRects; | |
761 | RegionAppendNonO(newReg, r2, r2BandEnd, max(r2y1, ybot), r2->y2); | |
762 | Coalesce(newReg, prevBand, curBand); | |
763 | /* Append rest of boxes */ | |
764 | AppendRegions(newReg, r2BandEnd, r2End); | |
765 | } | |
766 | ||
767 | free(oldData); | |
768 | ||
769 | if (!(numRects = newReg->data->numRects)) { | |
770 | xfreeData(newReg); | |
771 | newReg->data = &RegionEmptyData; | |
772 | } | |
773 | else if (numRects == 1) { | |
774 | newReg->extents = *RegionBoxptr(newReg); | |
775 | xfreeData(newReg); | |
776 | newReg->data = NULL; | |
777 | } | |
778 | else { | |
779 | DOWNSIZE(newReg, numRects); | |
780 | } | |
781 | ||
782 | return TRUE; | |
783 | } | |
784 | ||
785 | /*- | |
786 | *----------------------------------------------------------------------- | |
787 | * RegionSetExtents -- | |
788 | * Reset the extents of a region to what they should be. Called by | |
789 | * Subtract and Intersect as they can't figure it out along the | |
790 | * way or do so easily, as Union can. | |
791 | * | |
792 | * Results: | |
793 | * None. | |
794 | * | |
795 | * Side Effects: | |
796 | * The region's 'extents' structure is overwritten. | |
797 | * | |
798 | *----------------------------------------------------------------------- | |
799 | */ | |
800 | static void | |
801 | RegionSetExtents(RegionPtr pReg) | |
802 | { | |
803 | BoxPtr pBox, pBoxEnd; | |
804 | ||
805 | if (!pReg->data) | |
806 | return; | |
807 | if (!pReg->data->size) { | |
808 | pReg->extents.x2 = pReg->extents.x1; | |
809 | pReg->extents.y2 = pReg->extents.y1; | |
810 | return; | |
811 | } | |
812 | ||
813 | pBox = RegionBoxptr(pReg); | |
814 | pBoxEnd = RegionEnd(pReg); | |
815 | ||
816 | /* | |
817 | * Since pBox is the first rectangle in the region, it must have the | |
818 | * smallest y1 and since pBoxEnd is the last rectangle in the region, | |
819 | * it must have the largest y2, because of banding. Initialize x1 and | |
820 | * x2 from pBox and pBoxEnd, resp., as good things to initialize them | |
821 | * to... | |
822 | */ | |
823 | pReg->extents.x1 = pBox->x1; | |
824 | pReg->extents.y1 = pBox->y1; | |
825 | pReg->extents.x2 = pBoxEnd->x2; | |
826 | pReg->extents.y2 = pBoxEnd->y2; | |
827 | ||
828 | assert(pReg->extents.y1 < pReg->extents.y2); | |
829 | while (pBox <= pBoxEnd) { | |
830 | if (pBox->x1 < pReg->extents.x1) | |
831 | pReg->extents.x1 = pBox->x1; | |
832 | if (pBox->x2 > pReg->extents.x2) | |
833 | pReg->extents.x2 = pBox->x2; | |
834 | pBox++; | |
835 | }; | |
836 | ||
837 | assert(pReg->extents.x1 < pReg->extents.x2); | |
838 | } | |
839 | ||
840 | /*====================================================================== | |
841 | * Region Intersection | |
842 | *====================================================================*/ | |
843 | /*- | |
844 | *----------------------------------------------------------------------- | |
845 | * RegionIntersectO -- | |
846 | * Handle an overlapping band for RegionIntersect. | |
847 | * | |
848 | * Results: | |
849 | * TRUE if successful. | |
850 | * | |
851 | * Side Effects: | |
852 | * Rectangles may be added to the region. | |
853 | * | |
854 | *----------------------------------------------------------------------- | |
855 | */ | |
856 | /*ARGSUSED*/ | |
857 | #define MERGERECT(r) \ | |
858 | { \ | |
859 | if (r->x1 <= x2) { \ | |
860 | /* Merge with current rectangle */ \ | |
861 | if (r->x1 < x2) *pOverlap = TRUE; \ | |
862 | if (x2 < r->x2) x2 = r->x2; \ | |
863 | } else { \ | |
864 | /* Add current rectangle, start new one */ \ | |
865 | NEWRECT(pReg, pNextRect, x1, y1, x2, y2); \ | |
866 | x1 = r->x1; \ | |
867 | x2 = r->x2; \ | |
868 | } \ | |
869 | r++; \ | |
870 | } | |
871 | /*====================================================================== | |
872 | * Region Union | |
873 | *====================================================================*/ | |
874 | /*- | |
875 | *----------------------------------------------------------------------- | |
876 | * RegionUnionO -- | |
877 | * Handle an overlapping band for the union operation. Picks the | |
878 | * left-most rectangle each time and merges it into the region. | |
879 | * | |
880 | * Results: | |
881 | * TRUE if successful. | |
882 | * | |
883 | * Side Effects: | |
884 | * pReg is overwritten. | |
885 | * pOverlap is set to TRUE if any boxes overlap. | |
886 | * | |
887 | *----------------------------------------------------------------------- | |
888 | */ | |
889 | static Bool | |
890 | RegionUnionO(RegionPtr pReg, | |
891 | BoxPtr r1, | |
892 | BoxPtr r1End, | |
893 | BoxPtr r2, BoxPtr r2End, short y1, short y2, Bool *pOverlap) | |
894 | { | |
895 | BoxPtr pNextRect; | |
896 | int x1; /* left and right side of current union */ | |
897 | int x2; | |
898 | ||
899 | assert(y1 < y2); | |
900 | assert(r1 != r1End && r2 != r2End); | |
901 | ||
902 | pNextRect = RegionTop(pReg); | |
903 | ||
904 | /* Start off current rectangle */ | |
905 | if (r1->x1 < r2->x1) { | |
906 | x1 = r1->x1; | |
907 | x2 = r1->x2; | |
908 | r1++; | |
909 | } | |
910 | else { | |
911 | x1 = r2->x1; | |
912 | x2 = r2->x2; | |
913 | r2++; | |
914 | } | |
915 | while (r1 != r1End && r2 != r2End) { | |
916 | if (r1->x1 < r2->x1) | |
917 | MERGERECT(r1) | |
918 | else | |
919 | MERGERECT(r2); | |
920 | } | |
921 | ||
922 | /* Finish off whoever (if any) is left */ | |
923 | if (r1 != r1End) { | |
924 | do { | |
925 | MERGERECT(r1); | |
926 | } while (r1 != r1End); | |
927 | } | |
928 | else if (r2 != r2End) { | |
929 | do { | |
930 | MERGERECT(r2); | |
931 | } while (r2 != r2End); | |
932 | } | |
933 | ||
934 | /* Add current rectangle */ | |
935 | NEWRECT(pReg, pNextRect, x1, y1, x2, y2); | |
936 | ||
937 | return TRUE; | |
938 | } | |
939 | ||
940 | /*====================================================================== | |
941 | * Batch Rectangle Union | |
942 | *====================================================================*/ | |
943 | ||
944 | /*- | |
945 | *----------------------------------------------------------------------- | |
946 | * RegionAppend -- | |
947 | * | |
948 | * "Append" the rgn rectangles onto the end of dstrgn, maintaining | |
949 | * knowledge of YX-banding when it's easy. Otherwise, dstrgn just | |
950 | * becomes a non-y-x-banded random collection of rectangles, and not | |
951 | * yet a true region. After a sequence of appends, the caller must | |
952 | * call RegionValidate to ensure that a valid region is constructed. | |
953 | * | |
954 | * Results: | |
955 | * TRUE if successful. | |
956 | * | |
957 | * Side Effects: | |
958 | * dstrgn is modified if rgn has rectangles. | |
959 | * | |
960 | */ | |
961 | Bool | |
962 | RegionAppend(RegionPtr dstrgn, RegionPtr rgn) | |
963 | { | |
964 | int numRects, dnumRects, size; | |
965 | BoxPtr new, old; | |
966 | Bool prepend; | |
967 | ||
968 | if (RegionNar(rgn)) | |
969 | return RegionBreak(dstrgn); | |
970 | ||
971 | if (!rgn->data && (dstrgn->data == &RegionEmptyData)) { | |
972 | dstrgn->extents = rgn->extents; | |
973 | dstrgn->data = NULL; | |
974 | return TRUE; | |
975 | } | |
976 | ||
977 | numRects = RegionNumRects(rgn); | |
978 | if (!numRects) | |
979 | return TRUE; | |
980 | prepend = FALSE; | |
981 | size = numRects; | |
982 | dnumRects = RegionNumRects(dstrgn); | |
983 | if (!dnumRects && (size < 200)) | |
984 | size = 200; /* XXX pick numbers out of a hat */ | |
985 | RECTALLOC(dstrgn, size); | |
986 | old = RegionRects(rgn); | |
987 | if (!dnumRects) | |
988 | dstrgn->extents = rgn->extents; | |
989 | else if (dstrgn->extents.x2 > dstrgn->extents.x1) { | |
990 | BoxPtr first, last; | |
991 | ||
992 | first = old; | |
993 | last = RegionBoxptr(dstrgn) + (dnumRects - 1); | |
994 | if ((first->y1 > last->y2) || | |
995 | ((first->y1 == last->y1) && (first->y2 == last->y2) && | |
996 | (first->x1 > last->x2))) { | |
997 | if (rgn->extents.x1 < dstrgn->extents.x1) | |
998 | dstrgn->extents.x1 = rgn->extents.x1; | |
999 | if (rgn->extents.x2 > dstrgn->extents.x2) | |
1000 | dstrgn->extents.x2 = rgn->extents.x2; | |
1001 | dstrgn->extents.y2 = rgn->extents.y2; | |
1002 | } | |
1003 | else { | |
1004 | first = RegionBoxptr(dstrgn); | |
1005 | last = old + (numRects - 1); | |
1006 | if ((first->y1 > last->y2) || | |
1007 | ((first->y1 == last->y1) && (first->y2 == last->y2) && | |
1008 | (first->x1 > last->x2))) { | |
1009 | prepend = TRUE; | |
1010 | if (rgn->extents.x1 < dstrgn->extents.x1) | |
1011 | dstrgn->extents.x1 = rgn->extents.x1; | |
1012 | if (rgn->extents.x2 > dstrgn->extents.x2) | |
1013 | dstrgn->extents.x2 = rgn->extents.x2; | |
1014 | dstrgn->extents.y1 = rgn->extents.y1; | |
1015 | } | |
1016 | else | |
1017 | dstrgn->extents.x2 = dstrgn->extents.x1; | |
1018 | } | |
1019 | } | |
1020 | if (prepend) { | |
1021 | new = RegionBox(dstrgn, numRects); | |
1022 | if (dnumRects == 1) | |
1023 | *new = *RegionBoxptr(dstrgn); | |
1024 | else | |
1025 | memmove((char *) new, (char *) RegionBoxptr(dstrgn), | |
1026 | dnumRects * sizeof(BoxRec)); | |
1027 | new = RegionBoxptr(dstrgn); | |
1028 | } | |
1029 | else | |
1030 | new = RegionBoxptr(dstrgn) + dnumRects; | |
1031 | if (numRects == 1) | |
1032 | *new = *old; | |
1033 | else | |
1034 | memmove((char *) new, (char *) old, numRects * sizeof(BoxRec)); | |
1035 | dstrgn->data->numRects += numRects; | |
1036 | return TRUE; | |
1037 | } | |
1038 | ||
1039 | #define ExchangeRects(a, b) \ | |
1040 | { \ | |
1041 | BoxRec t; \ | |
1042 | t = rects[a]; \ | |
1043 | rects[a] = rects[b]; \ | |
1044 | rects[b] = t; \ | |
1045 | } | |
1046 | ||
1047 | static void | |
1048 | QuickSortRects(BoxRec rects[], int numRects) | |
1049 | { | |
1050 | int y1; | |
1051 | int x1; | |
1052 | int i, j; | |
1053 | BoxPtr r; | |
1054 | ||
1055 | /* Always called with numRects > 1 */ | |
1056 | ||
1057 | do { | |
1058 | if (numRects == 2) { | |
1059 | if (rects[0].y1 > rects[1].y1 || | |
1060 | (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1)) | |
1061 | ExchangeRects(0, 1); | |
1062 | return; | |
1063 | } | |
1064 | ||
1065 | /* Choose partition element, stick in location 0 */ | |
1066 | ExchangeRects(0, numRects >> 1); | |
1067 | y1 = rects[0].y1; | |
1068 | x1 = rects[0].x1; | |
1069 | ||
1070 | /* Partition array */ | |
1071 | i = 0; | |
1072 | j = numRects; | |
1073 | do { | |
1074 | r = &(rects[i]); | |
1075 | do { | |
1076 | r++; | |
1077 | i++; | |
1078 | } while (i != numRects && | |
1079 | (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1))); | |
1080 | r = &(rects[j]); | |
1081 | do { | |
1082 | r--; | |
1083 | j--; | |
1084 | } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1)); | |
1085 | if (i < j) | |
1086 | ExchangeRects(i, j); | |
1087 | } while (i < j); | |
1088 | ||
1089 | /* Move partition element back to middle */ | |
1090 | ExchangeRects(0, j); | |
1091 | ||
1092 | /* Recurse */ | |
1093 | if (numRects - j - 1 > 1) | |
1094 | QuickSortRects(&rects[j + 1], numRects - j - 1); | |
1095 | numRects = j; | |
1096 | } while (numRects > 1); | |
1097 | } | |
1098 | ||
1099 | /*- | |
1100 | *----------------------------------------------------------------------- | |
1101 | * RegionValidate -- | |
1102 | * | |
1103 | * Take a ``region'' which is a non-y-x-banded random collection of | |
1104 | * rectangles, and compute a nice region which is the union of all the | |
1105 | * rectangles. | |
1106 | * | |
1107 | * Results: | |
1108 | * TRUE if successful. | |
1109 | * | |
1110 | * Side Effects: | |
1111 | * The passed-in ``region'' may be modified. | |
1112 | * pOverlap set to TRUE if any retangles overlapped, else FALSE; | |
1113 | * | |
1114 | * Strategy: | |
1115 | * Step 1. Sort the rectangles into ascending order with primary key y1 | |
1116 | * and secondary key x1. | |
1117 | * | |
1118 | * Step 2. Split the rectangles into the minimum number of proper y-x | |
1119 | * banded regions. This may require horizontally merging | |
1120 | * rectangles, and vertically coalescing bands. With any luck, | |
1121 | * this step in an identity tranformation (ala the Box widget), | |
1122 | * or a coalescing into 1 box (ala Menus). | |
1123 | * | |
1124 | * Step 3. Merge the separate regions down to a single region by calling | |
1125 | * Union. Maximize the work each Union call does by using | |
1126 | * a binary merge. | |
1127 | * | |
1128 | *----------------------------------------------------------------------- | |
1129 | */ | |
1130 | ||
1131 | Bool | |
1132 | RegionValidate(RegionPtr badreg, Bool *pOverlap) | |
1133 | { | |
1134 | /* Descriptor for regions under construction in Step 2. */ | |
1135 | typedef struct { | |
1136 | RegionRec reg; | |
1137 | int prevBand; | |
1138 | int curBand; | |
1139 | } RegionInfo; | |
1140 | ||
1141 | int numRects; /* Original numRects for badreg */ | |
1142 | RegionInfo *ri; /* Array of current regions */ | |
1143 | int numRI; /* Number of entries used in ri */ | |
1144 | int sizeRI; /* Number of entries available in ri */ | |
1145 | int i; /* Index into rects */ | |
1146 | int j; /* Index into ri */ | |
1147 | RegionInfo *rit; /* &ri[j] */ | |
1148 | RegionPtr reg; /* ri[j].reg */ | |
1149 | BoxPtr box; /* Current box in rects */ | |
1150 | BoxPtr riBox; /* Last box in ri[j].reg */ | |
1151 | RegionPtr hreg; /* ri[j_half].reg */ | |
1152 | Bool ret = TRUE; | |
1153 | ||
1154 | *pOverlap = FALSE; | |
1155 | if (!badreg->data) { | |
1156 | good(badreg); | |
1157 | return TRUE; | |
1158 | } | |
1159 | numRects = badreg->data->numRects; | |
1160 | if (!numRects) { | |
1161 | if (RegionNar(badreg)) | |
1162 | return FALSE; | |
1163 | good(badreg); | |
1164 | return TRUE; | |
1165 | } | |
1166 | if (badreg->extents.x1 < badreg->extents.x2) { | |
1167 | if ((numRects) == 1) { | |
1168 | xfreeData(badreg); | |
1169 | badreg->data = (RegDataPtr) NULL; | |
1170 | } | |
1171 | else { | |
1172 | DOWNSIZE(badreg, numRects); | |
1173 | } | |
1174 | good(badreg); | |
1175 | return TRUE; | |
1176 | } | |
1177 | ||
1178 | /* Step 1: Sort the rects array into ascending (y1, x1) order */ | |
1179 | QuickSortRects(RegionBoxptr(badreg), numRects); | |
1180 | ||
1181 | /* Step 2: Scatter the sorted array into the minimum number of regions */ | |
1182 | ||
1183 | /* Set up the first region to be the first rectangle in badreg */ | |
1184 | /* Note that step 2 code will never overflow the ri[0].reg rects array */ | |
1185 | ri = (RegionInfo *) malloc(4 * sizeof(RegionInfo)); | |
1186 | if (!ri) | |
1187 | return RegionBreak(badreg); | |
1188 | sizeRI = 4; | |
1189 | numRI = 1; | |
1190 | ri[0].prevBand = 0; | |
1191 | ri[0].curBand = 0; | |
1192 | ri[0].reg = *badreg; | |
1193 | box = RegionBoxptr(&ri[0].reg); | |
1194 | ri[0].reg.extents = *box; | |
1195 | ri[0].reg.data->numRects = 1; | |
1196 | ||
1197 | /* Now scatter rectangles into the minimum set of valid regions. If the | |
1198 | next rectangle to be added to a region would force an existing rectangle | |
1199 | in the region to be split up in order to maintain y-x banding, just | |
1200 | forget it. Try the next region. If it doesn't fit cleanly into any | |
1201 | region, make a new one. */ | |
1202 | ||
1203 | for (i = numRects; --i > 0;) { | |
1204 | box++; | |
1205 | /* Look for a region to append box to */ | |
1206 | for (j = numRI, rit = ri; --j >= 0; rit++) { | |
1207 | reg = &rit->reg; | |
1208 | riBox = RegionEnd(reg); | |
1209 | ||
1210 | if (box->y1 == riBox->y1 && box->y2 == riBox->y2) { | |
1211 | /* box is in same band as riBox. Merge or append it */ | |
1212 | if (box->x1 <= riBox->x2) { | |
1213 | /* Merge it with riBox */ | |
1214 | if (box->x1 < riBox->x2) | |
1215 | *pOverlap = TRUE; | |
1216 | if (box->x2 > riBox->x2) | |
1217 | riBox->x2 = box->x2; | |
1218 | } | |
1219 | else { | |
1220 | RECTALLOC_BAIL(reg, 1, bail); | |
1221 | *RegionTop(reg) = *box; | |
1222 | reg->data->numRects++; | |
1223 | } | |
1224 | goto NextRect; /* So sue me */ | |
1225 | } | |
1226 | else if (box->y1 >= riBox->y2) { | |
1227 | /* Put box into new band */ | |
1228 | if (reg->extents.x2 < riBox->x2) | |
1229 | reg->extents.x2 = riBox->x2; | |
1230 | if (reg->extents.x1 > box->x1) | |
1231 | reg->extents.x1 = box->x1; | |
1232 | Coalesce(reg, rit->prevBand, rit->curBand); | |
1233 | rit->curBand = reg->data->numRects; | |
1234 | RECTALLOC_BAIL(reg, 1, bail); | |
1235 | *RegionTop(reg) = *box; | |
1236 | reg->data->numRects++; | |
1237 | goto NextRect; | |
1238 | } | |
1239 | /* Well, this region was inappropriate. Try the next one. */ | |
1240 | } /* for j */ | |
1241 | ||
1242 | /* Uh-oh. No regions were appropriate. Create a new one. */ | |
1243 | if (sizeRI == numRI) { | |
1244 | /* Oops, allocate space for new region information */ | |
1245 | sizeRI <<= 1; | |
1246 | rit = (RegionInfo *) realloc(ri, sizeRI * sizeof(RegionInfo)); | |
1247 | if (!rit) | |
1248 | goto bail; | |
1249 | ri = rit; | |
1250 | rit = &ri[numRI]; | |
1251 | } | |
1252 | numRI++; | |
1253 | rit->prevBand = 0; | |
1254 | rit->curBand = 0; | |
1255 | rit->reg.extents = *box; | |
1256 | rit->reg.data = NULL; | |
1257 | if (!RegionRectAlloc(&rit->reg, (i + numRI) / numRI)) /* MUST force allocation */ | |
1258 | goto bail; | |
1259 | NextRect:; | |
1260 | } /* for i */ | |
1261 | ||
1262 | /* Make a final pass over each region in order to Coalesce and set | |
1263 | extents.x2 and extents.y2 */ | |
1264 | ||
1265 | for (j = numRI, rit = ri; --j >= 0; rit++) { | |
1266 | reg = &rit->reg; | |
1267 | riBox = RegionEnd(reg); | |
1268 | reg->extents.y2 = riBox->y2; | |
1269 | if (reg->extents.x2 < riBox->x2) | |
1270 | reg->extents.x2 = riBox->x2; | |
1271 | Coalesce(reg, rit->prevBand, rit->curBand); | |
1272 | if (reg->data->numRects == 1) { /* keep unions happy below */ | |
1273 | xfreeData(reg); | |
1274 | reg->data = NULL; | |
1275 | } | |
1276 | } | |
1277 | ||
1278 | /* Step 3: Union all regions into a single region */ | |
1279 | while (numRI > 1) { | |
1280 | int half = numRI / 2; | |
1281 | ||
1282 | for (j = numRI & 1; j < (half + (numRI & 1)); j++) { | |
1283 | reg = &ri[j].reg; | |
1284 | hreg = &ri[j + half].reg; | |
1285 | if (!RegionOp(reg, reg, hreg, RegionUnionO, TRUE, TRUE, pOverlap)) | |
1286 | ret = FALSE; | |
1287 | if (hreg->extents.x1 < reg->extents.x1) | |
1288 | reg->extents.x1 = hreg->extents.x1; | |
1289 | if (hreg->extents.y1 < reg->extents.y1) | |
1290 | reg->extents.y1 = hreg->extents.y1; | |
1291 | if (hreg->extents.x2 > reg->extents.x2) | |
1292 | reg->extents.x2 = hreg->extents.x2; | |
1293 | if (hreg->extents.y2 > reg->extents.y2) | |
1294 | reg->extents.y2 = hreg->extents.y2; | |
1295 | xfreeData(hreg); | |
1296 | } | |
1297 | numRI -= half; | |
1298 | } | |
1299 | *badreg = ri[0].reg; | |
1300 | free(ri); | |
1301 | good(badreg); | |
1302 | return ret; | |
1303 | bail: | |
1304 | for (i = 0; i < numRI; i++) | |
1305 | xfreeData(&ri[i].reg); | |
1306 | free(ri); | |
1307 | return RegionBreak(badreg); | |
1308 | } | |
1309 | ||
1310 | RegionPtr | |
1311 | RegionFromRects(int nrects, xRectangle *prect, int ctype) | |
1312 | { | |
1313 | ||
1314 | RegionPtr pRgn; | |
1315 | RegDataPtr pData; | |
1316 | BoxPtr pBox; | |
1317 | int i; | |
1318 | int x1, y1, x2, y2; | |
1319 | ||
1320 | pRgn = RegionCreate(NullBox, 0); | |
1321 | if (RegionNar(pRgn)) | |
1322 | return pRgn; | |
1323 | if (!nrects) | |
1324 | return pRgn; | |
1325 | if (nrects == 1) { | |
1326 | x1 = prect->x; | |
1327 | y1 = prect->y; | |
1328 | if ((x2 = x1 + (int) prect->width) > MAXSHORT) | |
1329 | x2 = MAXSHORT; | |
1330 | if ((y2 = y1 + (int) prect->height) > MAXSHORT) | |
1331 | y2 = MAXSHORT; | |
1332 | if (x1 != x2 && y1 != y2) { | |
1333 | pRgn->extents.x1 = x1; | |
1334 | pRgn->extents.y1 = y1; | |
1335 | pRgn->extents.x2 = x2; | |
1336 | pRgn->extents.y2 = y2; | |
1337 | pRgn->data = NULL; | |
1338 | } | |
1339 | return pRgn; | |
1340 | } | |
1341 | pData = xallocData(nrects); | |
1342 | if (!pData) { | |
1343 | RegionBreak(pRgn); | |
1344 | return pRgn; | |
1345 | } | |
1346 | pBox = (BoxPtr) (pData + 1); | |
1347 | for (i = nrects; --i >= 0; prect++) { | |
1348 | x1 = prect->x; | |
1349 | y1 = prect->y; | |
1350 | if ((x2 = x1 + (int) prect->width) > MAXSHORT) | |
1351 | x2 = MAXSHORT; | |
1352 | if ((y2 = y1 + (int) prect->height) > MAXSHORT) | |
1353 | y2 = MAXSHORT; | |
1354 | if (x1 != x2 && y1 != y2) { | |
1355 | pBox->x1 = x1; | |
1356 | pBox->y1 = y1; | |
1357 | pBox->x2 = x2; | |
1358 | pBox->y2 = y2; | |
1359 | pBox++; | |
1360 | } | |
1361 | } | |
1362 | if (pBox != (BoxPtr) (pData + 1)) { | |
1363 | pData->size = nrects; | |
1364 | pData->numRects = pBox - (BoxPtr) (pData + 1); | |
1365 | pRgn->data = pData; | |
1366 | if (ctype != CT_YXBANDED) { | |
1367 | Bool overlap; /* result ignored */ | |
1368 | ||
1369 | pRgn->extents.x1 = pRgn->extents.x2 = 0; | |
1370 | RegionValidate(pRgn, &overlap); | |
1371 | } | |
1372 | else | |
1373 | RegionSetExtents(pRgn); | |
1374 | good(pRgn); | |
1375 | } | |
1376 | else { | |
1377 | free(pData); | |
1378 | } | |
1379 | return pRgn; | |
1380 | } |