Mercurial > ecos

comparison packages/services/gfx/mw/current/src/engine/devrgn.c @ 208:e0c0827131d1 ecos

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge from eCos master repository on 2002-05-20-20:11:54-BST
author jlarmour
date Mon, 20 May 2002 22:19:26 +0000
parents
children
comparison
equal deleted inserted replaced
207:74c807ddde34 208:e0c0827131d1
1 /*
2 * Portions Copyright (c) 1999, 2000 Greg Haerr <greg@censoft.com>
3 * Somewhat less shamelessly ripped from the Wine distribution
4 *
5 * Device-independent multi-rectangle clipping routines.
6 *
7 * GDI region objects. Shamelessly ripped out from the X11 distribution
8 * Thanks for the nice licence.
9 *
10 * Copyright 1993, 1994, 1995 Alexandre Julliard
11 * Modifications and additions: Copyright 1998 Huw Davies
12 */
13 /************************************************************************
14
15 Copyright (c) 1987, 1988 X Consortium
16
17 Permission is hereby granted, free of charge, to any person obtaining a copy
18 of this software and associated documentation files (the "Software"), to deal
19 in the Software without restriction, including without limitation the rights
20 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
21 copies of the Software, and to permit persons to whom the Software is
22 furnished to do so, subject to the following conditions:
23
24 The above copyright notice and this permission notice shall be included in
25 all copies or substantial portions of the Software.
26
27 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
28 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
29 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
30 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
31 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
32 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33
34 Except as contained in this notice, the name of the X Consortium shall not be
35 used in advertising or otherwise to promote the sale, use or other dealings
36 in this Software without prior written authorization from the X Consortium.
37
38
39 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
40
41 All Rights Reserved
42
43 Permission to use, copy, modify, and distribute this software and its
44 documentation for any purpose and without fee is hereby granted,
45 provided that the above copyright notice appear in all copies and that
46 both that copyright notice and this permission notice appear in
47 supporting documentation, and that the name of Digital not be
48 used in advertising or publicity pertaining to distribution of the
49 software without specific, written prior permission.
50
51 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
52 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
53 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
54 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
55 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
56 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
57 SOFTWARE.
58
59 ************************************************************************/
60 /*
61 * The functions in this file implement the Region abstraction, similar to one
62 * used in the X11 sample server. A Region is simply an area, as the name
63 * implies, and is implemented as a "y-x-banded" array of rectangles. To
64 * explain: Each Region is made up of a certain number of rectangles sorted
65 * by y coordinate first, and then by x coordinate.
66 *
67 * Furthermore, the rectangles are banded such that every rectangle with a
68 * given upper-left y coordinate (y1) will have the same lower-right y
69 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
70 * will span the entire vertical distance of the band. This means that some
71 * areas that could be merged into a taller rectangle will be represented as
72 * several shorter rectangles to account for shorter rectangles to its left
73 * or right but within its "vertical scope".
74 *
75 * An added constraint on the rectangles is that they must cover as much
76 * horizontal area as possible. E.g. no two rectangles in a band are allowed
77 * to touch.
78 *
79 * Whenever possible, bands will be merged together to cover a greater vertical
80 * distance (and thus reduce the number of rectangles). Two bands can be merged
81 * only if the bottom of one touches the top of the other and they have
82 * rectangles in the same places (of the same width, of course). This maintains
83 * the y-x-banding that's so nice to have...
84 */
85 #include <stdio.h>
86 #include <stdlib.h>
87 #include <string.h>
88 #include "device.h"
89
90 typedef void (*voidProcp)();
91
92 /* 1 if two RECTs overlap.
93 * 0 if two RECTs do not overlap.
94 */
95 #define EXTENTCHECK(r1, r2) \
96 ((r1)->right > (r2)->left && \
97 (r1)->left < (r2)->right && \
98 (r1)->bottom > (r2)->top && \
99 (r1)->top < (r2)->bottom)
100
101 /*
102 * Check to see if there is enough memory in the present region.
103 */
104 #define MEMCHECK(reg, rect, firstrect){\
105 if ((reg)->numRects >= ((reg)->size - 1)){\
106 (firstrect) = realloc(\
107 (firstrect), (2 * (sizeof(MWRECT)) * ((reg)->size)));\
108 if ((firstrect) == 0)\
109 return;\
110 (reg)->size *= 2;\
111 (rect) = &(firstrect)[(reg)->numRects];\
112 }\
113 }
114
115 #define REGION_NOT_EMPTY(pReg) pReg->numRects
116
117 #define EMPTY_REGION(pReg) { \
118 (pReg)->numRects = 0; \
119 (pReg)->extents.left = (pReg)->extents.top = 0; \
120 (pReg)->extents.right = (pReg)->extents.bottom = 0; \
121 (pReg)->type = MWREGION_NULL; \
122 }
123
124 #define INRECT(r, x, y) \
125 ( ( ((r).right > x)) && \
126 ( ((r).left <= x)) && \
127 ( ((r).bottom > y)) && \
128 ( ((r).top <= y)) )
129
130 /* return TRUE if point is in region*/
131 MWBOOL
132 GdPtInRegion(MWCLIPREGION *rgn, MWCOORD x, MWCOORD y)
133 {
134 int i;
135
136 if (rgn->numRects > 0 && INRECT(rgn->extents, x, y))
137 for (i = 0; i < rgn->numRects; i++)
138 if (INRECT (rgn->rects[i], x, y))
139 return TRUE;
140 return FALSE;
141 }
142
143 /* return whether rectangle is all in, partly in, or out of region*/
144 int
145 GdRectInRegion(MWCLIPREGION *rgn, const MWRECT *rect)
146 {
147 MWRECT * pCurRect;
148 MWRECT * pRectEnd;
149 MWCOORD rx, ry;
150 MWBOOL partIn, partOut;
151
152 /* this is (just) a useful optimization */
153 if (!rgn->numRects || !EXTENTCHECK(&rgn->extents, rect))
154 return MWRECT_OUT;
155
156 partOut = FALSE;
157 partIn = FALSE;
158 rx = rect->left;
159 ry = rect->top;
160
161 /*
162 * can stop when both partOut and partIn are TRUE,
163 * or we reach rect->bottom
164 */
165 for (pCurRect = rgn->rects, pRectEnd = pCurRect + rgn->numRects;
166 pCurRect < pRectEnd; pCurRect++) {
167
168 if (pCurRect->bottom <= ry)
169 continue; /* not far enough down yet*/
170
171 if (pCurRect->top > ry) {
172 partOut = TRUE; /* missed part of rectangle above */
173 if (partIn || (pCurRect->top >= rect->bottom))
174 break;
175 ry = pCurRect->top; /* x guaranteed to be == rect->left */
176 }
177
178 if (pCurRect->right <= rx)
179 continue; /* not far enough over yet */
180
181 if (pCurRect->left > rx) {
182 partOut = TRUE; /* missed part of rectangle to left */
183 if (partIn)
184 break;
185 }
186
187 if (pCurRect->left < rect->right) {
188 partIn = TRUE; /* definitely overlap */
189 if (partOut)
190 break;
191 }
192
193 if (pCurRect->right >= rect->right) {
194 ry = pCurRect->bottom; /* finished with this band */
195 if (ry >= rect->bottom)
196 break;
197 rx = rect->left; /* reset x out to left again */
198 } else {
199 /*
200 * Because boxes in a band are maximal width, if the first box
201 * to overlap the rectangle doesn't completely cover it in that
202 * band, the rectangle must be partially out, since some of it
203 * will be uncovered in that band. partIn will have been set true
204 * by now...
205 */
206 break;
207 }
208 }
209
210 return(partIn ? ((ry < rect->bottom) ? MWRECT_PARTIN : MWRECT_ALLIN) :
211 MWRECT_OUT);
212 }
213
214 #if 0000
215 /* Returns TRUE if rect is at least partly inside rgn*/
216 MWBOOL
217 GdRectInRegion(MWCLIPREGION *rgn, const MWRECT *rect)
218 {
219 MWRECT *pCurRect, *pRectEnd;
220 MWBOOL ret = FALSE;
221
222 /* this is (just) a useful optimization */
223 if ((rgn->numRects > 0) && EXTENTCHECK(&rgn->extents, rect))
224 {
225 for (pCurRect = rgn->rects, pRectEnd = pCurRect +
226 rgn->numRects; pCurRect < pRectEnd; pCurRect++)
227 {
228 if (pCurRect->bottom <= rect->top)
229 continue; /* not far enough down yet */
230
231 if (pCurRect->top >= rect->bottom) {
232 ret = FALSE; /* too far down */
233 break;
234 }
235
236 if (pCurRect->right <= rect->left)
237 continue; /* not far enough over yet */
238
239 if (pCurRect->left >= rect->right) {
240 continue;
241 }
242
243 ret = TRUE;
244 break;
245 }
246 }
247 return ret;
248 }
249 #endif
250
251 static MWBOOL
252 EQUALRECT(MWRECT *r1, MWRECT *r2)
253 {
254 return ((r1->left == r2->left) && (r1->right == r2->right) &&
255 (r1->top == r2->top) && (r1->bottom == r2->bottom));
256 }
257
258 MWBOOL
259 GdEqualRegion(MWCLIPREGION *r1, MWCLIPREGION *r2)
260 {
261 int i;
262
263 if (r1->numRects != r2->numRects)
264 return FALSE;
265 if (r1->numRects == 0)
266 return TRUE;
267 if (!EQUALRECT(&r1->extents, &r2->extents))
268 return FALSE;
269 for (i = 0; i < r1->numRects; i++) {
270 if (!EQUALRECT(r1->rects + i, r2->rects + i))
271 return FALSE;
272 }
273 return TRUE;
274 }
275
276 MWBOOL
277 GdEmptyRegion(MWCLIPREGION *rgn)
278 {
279 return rgn->numRects == 0;
280 }
281
282 /*
283 * Create a new empty MWCLIPREGION.
284 */
285 MWCLIPREGION *
286 GdAllocRegion(void)
287 {
288 MWCLIPREGION *rgn;
289
290 if ((rgn = malloc(sizeof( MWCLIPREGION ))))
291 {
292 if ((rgn->rects = malloc(sizeof( MWRECT ))))
293 {
294 rgn->size = 1;
295 EMPTY_REGION(rgn);
296 return rgn;
297 }
298 free(rgn);
299 }
300 return NULL;
301 }
302
303 MWCLIPREGION *
304 GdAllocRectRegion(MWCOORD left, MWCOORD top, MWCOORD right, MWCOORD bottom)
305 {
306 MWCLIPREGION *rgn;
307
308 rgn = GdAllocRegion();
309 if (rgn)
310 GdSetRectRegion(rgn, left, top, right, bottom);
311 return rgn;
312 }
313
314 MWCLIPREGION *
315 GdAllocRectRegionIndirect(MWRECT *prc)
316 {
317 return GdAllocRectRegion(prc->left, prc->top, prc->right, prc->bottom);
318 }
319
320 void
321 GdSetRectRegion(MWCLIPREGION *rgn, MWCOORD left, MWCOORD top, MWCOORD right,
322 MWCOORD bottom)
323 {
324 if (left != right && top != bottom) {
325 rgn->rects->left = rgn->extents.left = left;
326 rgn->rects->top = rgn->extents.top = top;
327 rgn->rects->right = rgn->extents.right = right;
328 rgn->rects->bottom = rgn->extents.bottom = bottom;
329 rgn->numRects = 1;
330 rgn->type = MWREGION_SIMPLE;
331 } else
332 EMPTY_REGION(rgn);
333 }
334
335 void
336 GdSetRectRegionIndirect(MWCLIPREGION *rgn, MWRECT *prc)
337 {
338 GdSetRectRegion(rgn, prc->left, prc->top, prc->right, prc->bottom);
339 }
340
341 void
342 GdDestroyRegion(MWCLIPREGION *rgn)
343 {
344 if(rgn) {
345 free(rgn->rects);
346 free(rgn);
347 }
348 }
349
350 void
351 GdOffsetRegion(MWCLIPREGION *rgn, MWCOORD x, MWCOORD y)
352 {
353 int nbox = rgn->numRects;
354 MWRECT *pbox = rgn->rects;
355
356 if(nbox && (x || y)) {
357 while(nbox--) {
358 pbox->left += x;
359 pbox->right += x;
360 pbox->top += y;
361 pbox->bottom += y;
362 pbox++;
363 }
364 rgn->extents.left += x;
365 rgn->extents.right += x;
366 rgn->extents.top += y;
367 rgn->extents.bottom += y;
368 }
369 }
370
371 /* get bounding box for region, return region type*/
372 int
373 GdGetRegionBox(MWCLIPREGION *rgn, MWRECT *prc)
374 {
375 *prc = rgn->extents;
376 return rgn->type;
377 }
378
379 /***********************************************************************
380 * GdUnionRectWithRegion
381 * Adds a rectangle to a MWCLIPREGION
382 */
383 void
384 GdUnionRectWithRegion(const MWRECT *rect, MWCLIPREGION *rgn)
385 {
386 MWCLIPREGION region;
387
388 region.rects = &region.extents;
389 region.numRects = 1;
390 region.size = 1;
391 region.type = MWREGION_SIMPLE;
392 region.extents = *rect;
393 GdUnionRegion(rgn, rgn, &region);
394 }
395
396 /***********************************************************************
397 * GdSubtractRectWithRegion
398 * Subtracts a rectangle from a MWCLIPREGION
399 */
400 void
401 GdSubtractRectFromRegion(const MWRECT *rect, MWCLIPREGION *rgn)
402 {
403 MWCLIPREGION region;
404
405 region.rects = &region.extents;
406 region.numRects = 1;
407 region.size = 1;
408 region.type = MWREGION_SIMPLE;
409 region.extents = *rect;
410 GdSubtractRegion(rgn, rgn, &region);
411 }
412
413
414 /***********************************************************************
415 * GdCopyRegion
416 */
417 void
418 GdCopyRegion(MWCLIPREGION *dst, MWCLIPREGION *src)
419 {
420 if (dst != src) /* don't want to copy to itself */
421 {
422 if (dst->size < src->numRects)
423 {
424 if (! (dst->rects = realloc( dst->rects, src->numRects * sizeof(MWRECT))))
425 return;
426 dst->size = src->numRects;
427 }
428 dst->numRects = src->numRects;
429 dst->extents.left = src->extents.left;
430 dst->extents.top = src->extents.top;
431 dst->extents.right = src->extents.right;
432 dst->extents.bottom = src->extents.bottom;
433 dst->type = src->type;
434
435 memcpy((char *) dst->rects, (char *) src->rects,
436 (int) (src->numRects * sizeof(MWRECT)));
437 }
438 }
439
440
441 /***********************************************************************
442 * REGION_SetExtents
443 * Re-calculate the extents of a region
444 */
445 static void
446 REGION_SetExtents (MWCLIPREGION *pReg)
447 {
448 MWRECT *pRect, *pRectEnd, *pExtents;
449
450 if (pReg->numRects == 0)
451 {
452 pReg->extents.left = 0;
453 pReg->extents.top = 0;
454 pReg->extents.right = 0;
455 pReg->extents.bottom = 0;
456 return;
457 }
458
459 pExtents = &pReg->extents;
460 pRect = pReg->rects;
461 pRectEnd = &pRect[pReg->numRects - 1];
462
463 /*
464 * Since pRect is the first rectangle in the region, it must have the
465 * smallest top and since pRectEnd is the last rectangle in the region,
466 * it must have the largest bottom, because of banding. Initialize left and
467 * right from pRect and pRectEnd, resp., as good things to initialize them
468 * to...
469 */
470 pExtents->left = pRect->left;
471 pExtents->top = pRect->top;
472 pExtents->right = pRectEnd->right;
473 pExtents->bottom = pRectEnd->bottom;
474
475 while (pRect <= pRectEnd)
476 {
477 if (pRect->left < pExtents->left)
478 pExtents->left = pRect->left;
479 if (pRect->right > pExtents->right)
480 pExtents->right = pRect->right;
481 pRect++;
482 }
483 }
484
485
486 /***********************************************************************
487 * REGION_Coalesce
488 *
489 * Attempt to merge the rects in the current band with those in the
490 * previous one. Used only by REGION_RegionOp.
491 *
492 * Results:
493 * The new index for the previous band.
494 *
495 * Side Effects:
496 * If coalescing takes place:
497 * - rectangles in the previous band will have their bottom fields
498 * altered.
499 * - pReg->numRects will be decreased.
500 *
501 */
502 static MWCOORD
503 REGION_Coalesce (
504 MWCLIPREGION *pReg, /* Region to coalesce */
505 MWCOORD prevStart, /* Index of start of previous band */
506 MWCOORD curStart /* Index of start of current band */
507 ) {
508 MWRECT *pPrevRect; /* Current rect in previous band */
509 MWRECT *pCurRect; /* Current rect in current band */
510 MWRECT *pRegEnd; /* End of region */
511 MWCOORD curNumRects; /* Number of rectangles in current band */
512 MWCOORD prevNumRects; /* Number of rectangles in previous band */
513 MWCOORD bandtop; /* top coordinate for current band */
514
515 pRegEnd = &pReg->rects[pReg->numRects];
516
517 pPrevRect = &pReg->rects[prevStart];
518 prevNumRects = curStart - prevStart;
519
520 /*
521 * Figure out how many rectangles are in the current band. Have to do
522 * this because multiple bands could have been added in REGION_RegionOp
523 * at the end when one region has been exhausted.
524 */
525 pCurRect = &pReg->rects[curStart];
526 bandtop = pCurRect->top;
527 for (curNumRects = 0;
528 (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
529 curNumRects++)
530 {
531 pCurRect++;
532 }
533
534 if (pCurRect != pRegEnd)
535 {
536 /*
537 * If more than one band was added, we have to find the start
538 * of the last band added so the next coalescing job can start
539 * at the right place... (given when multiple bands are added,
540 * this may be pointless -- see above).
541 */
542 pRegEnd--;
543 while (pRegEnd[-1].top == pRegEnd->top)
544 {
545 pRegEnd--;
546 }
547 curStart = pRegEnd - pReg->rects;
548 pRegEnd = pReg->rects + pReg->numRects;
549 }
550
551 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
552 pCurRect -= curNumRects;
553 /*
554 * The bands may only be coalesced if the bottom of the previous
555 * matches the top scanline of the current.
556 */
557 if (pPrevRect->bottom == pCurRect->top)
558 {
559 /*
560 * Make sure the bands have rects in the same places. This
561 * assumes that rects have been added in such a way that they
562 * cover the most area possible. I.e. two rects in a band must
563 * have some horizontal space between them.
564 */
565 do
566 {
567 if ((pPrevRect->left != pCurRect->left) ||
568 (pPrevRect->right != pCurRect->right))
569 {
570 /*
571 * The bands don't line up so they can't be coalesced.
572 */
573 return (curStart);
574 }
575 pPrevRect++;
576 pCurRect++;
577 prevNumRects -= 1;
578 } while (prevNumRects != 0);
579
580 pReg->numRects -= curNumRects;
581 pCurRect -= curNumRects;
582 pPrevRect -= curNumRects;
583
584 /*
585 * The bands may be merged, so set the bottom of each rect
586 * in the previous band to that of the corresponding rect in
587 * the current band.
588 */
589 do
590 {
591 pPrevRect->bottom = pCurRect->bottom;
592 pPrevRect++;
593 pCurRect++;
594 curNumRects -= 1;
595 } while (curNumRects != 0);
596
597 /*
598 * If only one band was added to the region, we have to backup
599 * curStart to the start of the previous band.
600 *
601 * If more than one band was added to the region, copy the
602 * other bands down. The assumption here is that the other bands
603 * came from the same region as the current one and no further
604 * coalescing can be done on them since it's all been done
605 * already... curStart is already in the right place.
606 */
607 if (pCurRect == pRegEnd)
608 {
609 curStart = prevStart;
610 }
611 else
612 {
613 do
614 {
615 *pPrevRect++ = *pCurRect++;
616 } while (pCurRect != pRegEnd);
617 }
618
619 }
620 }
621 return (curStart);
622 }
623
624 /***********************************************************************
625 * REGION_RegionOp
626 *
627 * Apply an operation to two regions. Called by GdUnion,
628 * GdXor, GdSubtract, GdIntersect...
629 *
630 * Results:
631 * None.
632 *
633 * Side Effects:
634 * The new region is overwritten.
635 *
636 * Notes:
637 * The idea behind this function is to view the two regions as sets.
638 * Together they cover a rectangle of area that this function divides
639 * into horizontal bands where points are covered only by one region
640 * or by both. For the first case, the nonOverlapFunc is called with
641 * each the band and the band's upper and lower extents. For the
642 * second, the overlapFunc is called to process the entire band. It
643 * is responsible for clipping the rectangles in the band, though
644 * this function provides the boundaries.
645 * At the end of each band, the new region is coalesced, if possible,
646 * to reduce the number of rectangles in the region.
647 *
648 */
649 static void
650 REGION_RegionOp(
651 MWCLIPREGION *newReg, /* Place to store result */
652 MWCLIPREGION *reg1, /* First region in operation */
653 MWCLIPREGION *reg2, /* 2nd region in operation */
654 void (*overlapFunc)(), /* Function to call for over-lapping bands */
655 void (*nonOverlap1Func)(), /* Function to call for non-overlapping bands in region 1 */
656 void (*nonOverlap2Func)() /* Function to call for non-overlapping bands in region 2 */
657 ) {
658 MWRECT *r1; /* Pointer into first region */
659 MWRECT *r2; /* Pointer into 2d region */
660 MWRECT *r1End; /* End of 1st region */
661 MWRECT *r2End; /* End of 2d region */
662 MWCOORD ybot; /* Bottom of intersection */
663 MWCOORD ytop; /* Top of intersection */
664 MWRECT *oldRects; /* Old rects for newReg */
665 MWCOORD prevBand; /* Index of start of
666 * previous band in newReg */
667 MWCOORD curBand; /* Index of start of current
668 * band in newReg */
669 MWRECT *r1BandEnd; /* End of current band in r1 */
670 MWRECT *r2BandEnd; /* End of current band in r2 */
671 MWCOORD top; /* Top of non-overlapping band */
672 MWCOORD bot; /* Bottom of non-overlapping band */
673
674 /*
675 * Initialization:
676 * set r1, r2, r1End and r2End appropriately, preserve the important
677 * parts of the destination region until the end in case it's one of
678 * the two source regions, then mark the "new" region empty, allocating
679 * another array of rectangles for it to use.
680 */
681 r1 = reg1->rects;
682 r2 = reg2->rects;
683 r1End = r1 + reg1->numRects;
684 r2End = r2 + reg2->numRects;
685
686
687 /*
688 * newReg may be one of the src regions so we can't empty it. We keep a
689 * note of its rects pointer (so that we can free them later), preserve its
690 * extents and simply set numRects to zero.
691 */
692
693 oldRects = newReg->rects;
694 newReg->numRects = 0;
695
696 /*
697 * Allocate a reasonable number of rectangles for the new region. The idea
698 * is to allocate enough so the individual functions don't need to
699 * reallocate and copy the array, which is time consuming, yet we don't
700 * have to worry about using too much memory. I hope to be able to
701 * nuke the Xrealloc() at the end of this function eventually.
702 */
703 newReg->size = MWMAX(reg1->numRects,reg2->numRects) * 2;
704
705 if (! (newReg->rects = malloc( sizeof(MWRECT) * newReg->size )))
706 {
707 newReg->size = 0;
708 return;
709 }
710
711 /*
712 * Initialize ybot and ytop.
713 * In the upcoming loop, ybot and ytop serve different functions depending
714 * on whether the band being handled is an overlapping or non-overlapping
715 * band.
716 * In the case of a non-overlapping band (only one of the regions
717 * has points in the band), ybot is the bottom of the most recent
718 * intersection and thus clips the top of the rectangles in that band.
719 * ytop is the top of the next intersection between the two regions and
720 * serves to clip the bottom of the rectangles in the current band.
721 * For an overlapping band (where the two regions intersect), ytop clips
722 * the top of the rectangles of both regions and ybot clips the bottoms.
723 */
724 if (reg1->extents.top < reg2->extents.top)
725 ybot = reg1->extents.top;
726 else
727 ybot = reg2->extents.top;
728
729 /*
730 * prevBand serves to mark the start of the previous band so rectangles
731 * can be coalesced into larger rectangles. qv. miCoalesce, above.
732 * In the beginning, there is no previous band, so prevBand == curBand
733 * (curBand is set later on, of course, but the first band will always
734 * start at index 0). prevBand and curBand must be indices because of
735 * the possible expansion, and resultant moving, of the new region's
736 * array of rectangles.
737 */
738 prevBand = 0;
739
740 do
741 {
742 curBand = newReg->numRects;
743
744 /*
745 * This algorithm proceeds one source-band (as opposed to a
746 * destination band, which is determined by where the two regions
747 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
748 * rectangle after the last one in the current band for their
749 * respective regions.
750 */
751 r1BandEnd = r1;
752 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
753 {
754 r1BandEnd++;
755 }
756
757 r2BandEnd = r2;
758 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
759 {
760 r2BandEnd++;
761 }
762
763 /*
764 * First handle the band that doesn't intersect, if any.
765 *
766 * Note that attention is restricted to one band in the
767 * non-intersecting region at once, so if a region has n
768 * bands between the current position and the next place it overlaps
769 * the other, this entire loop will be passed through n times.
770 */
771 if (r1->top < r2->top)
772 {
773 top = MWMAX(r1->top,ybot);
774 bot = MWMIN(r1->bottom,r2->top);
775
776 if ((top != bot) && (nonOverlap1Func != (void (*)())NULL))
777 {
778 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
779 }
780
781 ytop = r2->top;
782 }
783 else if (r2->top < r1->top)
784 {
785 top = MWMAX(r2->top,ybot);
786 bot = MWMIN(r2->bottom,r1->top);
787
788 if ((top != bot) && (nonOverlap2Func != (void (*)())NULL))
789 {
790 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
791 }
792
793 ytop = r1->top;
794 }
795 else
796 {
797 ytop = r1->top;
798 }
799
800 /*
801 * If any rectangles got added to the region, try and coalesce them
802 * with rectangles from the previous band. Note we could just do
803 * this test in miCoalesce, but some machines incur a not
804 * inconsiderable cost for function calls, so...
805 */
806 if (newReg->numRects != curBand)
807 {
808 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
809 }
810
811 /*
812 * Now see if we've hit an intersecting band. The two bands only
813 * intersect if ybot > ytop
814 */
815 ybot = MWMIN(r1->bottom, r2->bottom);
816 curBand = newReg->numRects;
817 if (ybot > ytop)
818 {
819 (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
820
821 }
822
823 if (newReg->numRects != curBand)
824 {
825 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
826 }
827
828 /*
829 * If we've finished with a band (bottom == ybot) we skip forward
830 * in the region to the next band.
831 */
832 if (r1->bottom == ybot)
833 {
834 r1 = r1BandEnd;
835 }
836 if (r2->bottom == ybot)
837 {
838 r2 = r2BandEnd;
839 }
840 } while ((r1 != r1End) && (r2 != r2End));
841
842 /*
843 * Deal with whichever region still has rectangles left.
844 */
845 curBand = newReg->numRects;
846 if (r1 != r1End)
847 {
848 if (nonOverlap1Func != (void (*)())NULL)
849 {
850 do
851 {
852 r1BandEnd = r1;
853 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
854 {
855 r1BandEnd++;
856 }
857 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
858 MWMAX(r1->top,ybot), r1->bottom);
859 r1 = r1BandEnd;
860 } while (r1 != r1End);
861 }
862 }
863 else if ((r2 != r2End) && (nonOverlap2Func != (void (*)())NULL))
864 {
865 do
866 {
867 r2BandEnd = r2;
868 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
869 {
870 r2BandEnd++;
871 }
872 (* nonOverlap2Func) (newReg, r2, r2BandEnd,
873 MWMAX(r2->top,ybot), r2->bottom);
874 r2 = r2BandEnd;
875 } while (r2 != r2End);
876 }
877
878 if (newReg->numRects != curBand)
879 {
880 (void) REGION_Coalesce (newReg, prevBand, curBand);
881 }
882
883 /*
884 * A bit of cleanup. To keep regions from growing without bound,
885 * we shrink the array of rectangles to match the new number of
886 * rectangles in the region. This never goes to 0, however...
887 *
888 * Only do this stuff if the number of rectangles allocated is more than
889 * twice the number of rectangles in the region (a simple optimization...).
890 */
891 if (newReg->numRects < (newReg->size >> 1))
892 {
893 if (REGION_NOT_EMPTY(newReg))
894 {
895 MWRECT *prev_rects = newReg->rects;
896 newReg->size = newReg->numRects;
897 newReg->rects = realloc( newReg->rects, sizeof(MWRECT) * newReg->size );
898 if (! newReg->rects)
899 newReg->rects = prev_rects;
900 }
901 else
902 {
903 /*
904 * No point in doing the extra work involved in an Xrealloc if
905 * the region is empty
906 */
907 newReg->size = 1;
908 free( newReg->rects );
909 newReg->rects = malloc( sizeof(MWRECT) );
910 }
911 }
912 free( oldRects );
913 }
914
915 /***********************************************************************
916 * Region Intersection
917 ***********************************************************************/
918
919
920 /***********************************************************************
921 * REGION_IntersectO
922 *
923 * Handle an overlapping band for REGION_Intersect.
924 *
925 * Results:
926 * None.
927 *
928 * Side Effects:
929 * Rectangles may be added to the region.
930 *
931 */
932 static void
933 REGION_IntersectO(MWCLIPREGION *pReg, MWRECT *r1, MWRECT *r1End,
934 MWRECT *r2, MWRECT *r2End, MWCOORD top, MWCOORD bottom)
935
936 {
937 MWCOORD left, right;
938 MWRECT *pNextRect;
939
940 pNextRect = &pReg->rects[pReg->numRects];
941
942 while ((r1 != r1End) && (r2 != r2End))
943 {
944 left = MWMAX(r1->left, r2->left);
945 right = MWMIN(r1->right, r2->right);
946
947 /*
948 * If there's any overlap between the two rectangles, add that
949 * overlap to the new region.
950 * There's no need to check for subsumption because the only way
951 * such a need could arise is if some region has two rectangles
952 * right next to each other. Since that should never happen...
953 */
954 if (left < right)
955 {
956 MEMCHECK(pReg, pNextRect, pReg->rects);
957 pNextRect->left = left;
958 pNextRect->top = top;
959 pNextRect->right = right;
960 pNextRect->bottom = bottom;
961 pReg->numRects += 1;
962 pNextRect++;
963 }
964
965 /*
966 * Need to advance the pointers. Shift the one that extends
967 * to the right the least, since the other still has a chance to
968 * overlap with that region's next rectangle, if you see what I mean.
969 */
970 if (r1->right < r2->right)
971 {
972 r1++;
973 }
974 else if (r2->right < r1->right)
975 {
976 r2++;
977 }
978 else
979 {
980 r1++;
981 r2++;
982 }
983 }
984 }
985
986 /***********************************************************************
987 * GdIntersectRegion
988 */
989 void
990 GdIntersectRegion(MWCLIPREGION *newReg, MWCLIPREGION *reg1, MWCLIPREGION *reg2)
991 {
992 /* check for trivial reject */
993 if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
994 (!EXTENTCHECK(&reg1->extents, &reg2->extents)))
995 newReg->numRects = 0;
996 else
997 REGION_RegionOp (newReg, reg1, reg2,
998 (voidProcp) REGION_IntersectO, (voidProcp) NULL, (voidProcp) NULL);
999
1000 /*
1001 * Can't alter newReg's extents before we call miRegionOp because
1002 * it might be one of the source regions and miRegionOp depends
1003 * on the extents of those regions being the same. Besides, this
1004 * way there's no checking against rectangles that will be nuked
1005 * due to coalescing, so we have to examine fewer rectangles.
1006 */
1007 REGION_SetExtents(newReg);
1008 newReg->type = (newReg->numRects) ? MWREGION_COMPLEX : MWREGION_NULL ;
1009 }
1010
1011 /***********************************************************************
1012 * Region Union
1013 ***********************************************************************/
1014
1015 /***********************************************************************
1016 * REGION_UnionNonO
1017 *
1018 * Handle a non-overlapping band for the union operation. Just
1019 * Adds the rectangles into the region. Doesn't have to check for
1020 * subsumption or anything.
1021 *
1022 * Results:
1023 * None.
1024 *
1025 * Side Effects:
1026 * pReg->numRects is incremented and the final rectangles overwritten
1027 * with the rectangles we're passed.
1028 *
1029 */
1030 static void
1031 REGION_UnionNonO(MWCLIPREGION *pReg,MWRECT *r,MWRECT *rEnd,MWCOORD top,
1032 MWCOORD bottom)
1033 {
1034 MWRECT *pNextRect;
1035
1036 pNextRect = &pReg->rects[pReg->numRects];
1037
1038 while (r != rEnd)
1039 {
1040 MEMCHECK(pReg, pNextRect, pReg->rects);
1041 pNextRect->left = r->left;
1042 pNextRect->top = top;
1043 pNextRect->right = r->right;
1044 pNextRect->bottom = bottom;
1045 pReg->numRects += 1;
1046 pNextRect++;
1047 r++;
1048 }
1049 }
1050
1051 /***********************************************************************
1052 * REGION_UnionO
1053 *
1054 * Handle an overlapping band for the union operation. Picks the
1055 * left-most rectangle each time and merges it into the region.
1056 *
1057 * Results:
1058 * None.
1059 *
1060 * Side Effects:
1061 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1062 * be changed.
1063 *
1064 */
1065 static void
1066 REGION_UnionO(MWCLIPREGION *pReg, MWRECT *r1, MWRECT *r1End,
1067 MWRECT *r2, MWRECT *r2End, MWCOORD top, MWCOORD bottom)
1068 {
1069 MWRECT *pNextRect;
1070
1071 pNextRect = &pReg->rects[pReg->numRects];
1072
1073 #define MERGERECT(r) \
1074 if ((pReg->numRects != 0) && \
1075 (pNextRect[-1].top == top) && \
1076 (pNextRect[-1].bottom == bottom) && \
1077 (pNextRect[-1].right >= r->left)) \
1078 { \
1079 if (pNextRect[-1].right < r->right) \
1080 { \
1081 pNextRect[-1].right = r->right; \
1082 } \
1083 } \
1084 else \
1085 { \
1086 MEMCHECK(pReg, pNextRect, pReg->rects); \
1087 pNextRect->top = top; \
1088 pNextRect->bottom = bottom; \
1089 pNextRect->left = r->left; \
1090 pNextRect->right = r->right; \
1091 pReg->numRects += 1; \
1092 pNextRect += 1; \
1093 } \
1094 r++;
1095
1096 while ((r1 != r1End) && (r2 != r2End))
1097 {
1098 if (r1->left < r2->left)
1099 {
1100 MERGERECT(r1);
1101 }
1102 else
1103 {
1104 MERGERECT(r2);
1105 }
1106 }
1107
1108 if (r1 != r1End)
1109 {
1110 do
1111 {
1112 MERGERECT(r1);
1113 } while (r1 != r1End);
1114 }
1115 else while (r2 != r2End)
1116 {
1117 MERGERECT(r2);
1118 }
1119 }
1120
1121 /***********************************************************************
1122 * GdUnionRegion
1123 */
1124 void
1125 GdUnionRegion(MWCLIPREGION *newReg, MWCLIPREGION *reg1, MWCLIPREGION *reg2)
1126 {
1127 /* checks all the simple cases */
1128
1129 /*
1130 * Region 1 and 2 are the same or region 1 is empty
1131 */
1132 if ( (reg1 == reg2) || (!(reg1->numRects)) )
1133 {
1134 if (newReg != reg2)
1135 GdCopyRegion(newReg, reg2);
1136 return;
1137 }
1138
1139 /*
1140 * if nothing to union (region 2 empty)
1141 */
1142 if (!(reg2->numRects))
1143 {
1144 if (newReg != reg1)
1145 GdCopyRegion(newReg, reg1);
1146 return;
1147 }
1148
1149 /*
1150 * Region 1 completely subsumes region 2
1151 */
1152 if ((reg1->numRects == 1) &&
1153 (reg1->extents.left <= reg2->extents.left) &&
1154 (reg1->extents.top <= reg2->extents.top) &&
1155 (reg1->extents.right >= reg2->extents.right) &&
1156 (reg1->extents.bottom >= reg2->extents.bottom))
1157 {
1158 if (newReg != reg1)
1159 GdCopyRegion(newReg, reg1);
1160 return;
1161 }
1162
1163 /*
1164 * Region 2 completely subsumes region 1
1165 */
1166 if ((reg2->numRects == 1) &&
1167 (reg2->extents.left <= reg1->extents.left) &&
1168 (reg2->extents.top <= reg1->extents.top) &&
1169 (reg2->extents.right >= reg1->extents.right) &&
1170 (reg2->extents.bottom >= reg1->extents.bottom))
1171 {
1172 if (newReg != reg2)
1173 GdCopyRegion(newReg, reg2);
1174 return;
1175 }
1176
1177 REGION_RegionOp (newReg, reg1, reg2, (voidProcp) REGION_UnionO,
1178 (voidProcp) REGION_UnionNonO, (voidProcp) REGION_UnionNonO);
1179
1180 newReg->extents.left = MWMIN(reg1->extents.left, reg2->extents.left);
1181 newReg->extents.top = MWMIN(reg1->extents.top, reg2->extents.top);
1182 newReg->extents.right = MWMAX(reg1->extents.right, reg2->extents.right);
1183 newReg->extents.bottom = MWMAX(reg1->extents.bottom, reg2->extents.bottom);
1184 newReg->type = (newReg->numRects) ? MWREGION_COMPLEX : MWREGION_NULL ;
1185 }
1186
1187 /***********************************************************************
1188 * Region Subtraction
1189 ***********************************************************************/
1190
1191 /***********************************************************************
1192 * REGION_SubtractNonO1
1193 *
1194 * Deal with non-overlapping band for subtraction. Any parts from
1195 * region 2 we discard. Anything from region 1 we add to the region.
1196 *
1197 * Results:
1198 * None.
1199 *
1200 * Side Effects:
1201 * pReg may be affected.
1202 *
1203 */
1204 static void
1205 REGION_SubtractNonO1(MWCLIPREGION *pReg, MWRECT *r, MWRECT *rEnd,
1206 MWCOORD top, MWCOORD bottom)
1207 {
1208 MWRECT *pNextRect;
1209
1210 pNextRect = &pReg->rects[pReg->numRects];
1211
1212 while (r != rEnd)
1213 {
1214 MEMCHECK(pReg, pNextRect, pReg->rects);
1215 pNextRect->left = r->left;
1216 pNextRect->top = top;
1217 pNextRect->right = r->right;
1218 pNextRect->bottom = bottom;
1219 pReg->numRects += 1;
1220 pNextRect++;
1221 r++;
1222 }
1223 }
1224
1225
1226 /***********************************************************************
1227 * REGION_SubtractO
1228 *
1229 * Overlapping band subtraction. x1 is the left-most point not yet
1230 * checked.
1231 *
1232 * Results:
1233 * None.
1234 *
1235 * Side Effects:
1236 * pReg may have rectangles added to it.
1237 *
1238 */
1239 static void
1240 REGION_SubtractO(MWCLIPREGION *pReg, MWRECT *r1, MWRECT *r1End,
1241 MWRECT *r2, MWRECT *r2End, MWCOORD top, MWCOORD bottom)
1242 {
1243 MWRECT *pNextRect;
1244 MWCOORD left;
1245
1246 left = r1->left;
1247 pNextRect = &pReg->rects[pReg->numRects];
1248
1249 while ((r1 != r1End) && (r2 != r2End))
1250 {
1251 if (r2->right <= left)
1252 {
1253 /*
1254 * Subtrahend missed the boat: go to next subtrahend.
1255 */
1256 r2++;
1257 }
1258 else if (r2->left <= left)
1259 {
1260 /*
1261 * Subtrahend preceeds minuend: nuke left edge of minuend.
1262 */
1263 left = r2->right;
1264 if (left >= r1->right)
1265 {
1266 /*
1267 * Minuend completely covered: advance to next minuend and
1268 * reset left fence to edge of new minuend.
1269 */
1270 r1++;
1271 if (r1 != r1End)
1272 left = r1->left;
1273 }
1274 else
1275 {
1276 /*
1277 * Subtrahend now used up since it doesn't extend beyond
1278 * minuend
1279 */
1280 r2++;
1281 }
1282 }
1283 else if (r2->left < r1->right)
1284 {
1285 /*
1286 * Left part of subtrahend covers part of minuend: add uncovered
1287 * part of minuend to region and skip to next subtrahend.
1288 */
1289 MEMCHECK(pReg, pNextRect, pReg->rects);
1290 pNextRect->left = left;
1291 pNextRect->top = top;
1292 pNextRect->right = r2->left;
1293 pNextRect->bottom = bottom;
1294 pReg->numRects += 1;
1295 pNextRect++;
1296 left = r2->right;
1297 if (left >= r1->right)
1298 {
1299 /*
1300 * Minuend used up: advance to new...
1301 */
1302 r1++;
1303 if (r1 != r1End)
1304 left = r1->left;
1305 }
1306 else
1307 {
1308 /*
1309 * Subtrahend used up
1310 */
1311 r2++;
1312 }
1313 }
1314 else
1315 {
1316 /*
1317 * Minuend used up: add any remaining piece before advancing.
1318 */
1319 if (r1->right > left)
1320 {
1321 MEMCHECK(pReg, pNextRect, pReg->rects);
1322 pNextRect->left = left;
1323 pNextRect->top = top;
1324 pNextRect->right = r1->right;
1325 pNextRect->bottom = bottom;
1326 pReg->numRects += 1;
1327 pNextRect++;
1328 }
1329 r1++;
1330 left = r1->left;
1331 }
1332 }
1333
1334 /*
1335 * Add remaining minuend rectangles to region.
1336 */
1337 while (r1 != r1End)
1338 {
1339 MEMCHECK(pReg, pNextRect, pReg->rects);
1340 pNextRect->left = left;
1341 pNextRect->top = top;
1342 pNextRect->right = r1->right;
1343 pNextRect->bottom = bottom;
1344 pReg->numRects += 1;
1345 pNextRect++;
1346 r1++;
1347 if (r1 != r1End)
1348 {
1349 left = r1->left;
1350 }
1351 }
1352 }
1353
1354 /***********************************************************************
1355 * GdSubtractRegion
1356 *
1357 * Subtract regS from regM and leave the result in regD.
1358 * S stands for subtrahend, M for minuend and D for difference.
1359 *
1360 * Results:
1361 * TRUE.
1362 *
1363 * Side Effects:
1364 * regD is overwritten.
1365 *
1366 */
1367 void
1368 GdSubtractRegion(MWCLIPREGION *regD, MWCLIPREGION *regM, MWCLIPREGION *regS )
1369 {
1370 /* check for trivial reject */
1371 if ( (!(regM->numRects)) || (!(regS->numRects)) ||
1372 (!EXTENTCHECK(&regM->extents, &regS->extents)) )
1373 {
1374 GdCopyRegion(regD, regM);
1375 return;
1376 }
1377
1378 REGION_RegionOp (regD, regM, regS, (voidProcp) REGION_SubtractO,
1379 (voidProcp) REGION_SubtractNonO1, (voidProcp) NULL);
1380
1381 /*
1382 * Can't alter newReg's extents before we call miRegionOp because
1383 * it might be one of the source regions and miRegionOp depends
1384 * on the extents of those regions being the unaltered. Besides, this
1385 * way there's no checking against rectangles that will be nuked
1386 * due to coalescing, so we have to examine fewer rectangles.
1387 */
1388 REGION_SetExtents (regD);
1389 regD->type = (regD->numRects) ? MWREGION_COMPLEX : MWREGION_NULL ;
1390 }
1391
1392 /***********************************************************************
1393 * GdXorRegion
1394 */
1395 void
1396 GdXorRegion(MWCLIPREGION *dr, MWCLIPREGION *sra, MWCLIPREGION *srb)
1397 {
1398 MWCLIPREGION *tra, *trb;
1399
1400 if ((! (tra = GdAllocRegion())) || (! (trb = GdAllocRegion())))
1401 return;
1402 GdSubtractRegion(tra,sra,srb);
1403 GdSubtractRegion(trb,srb,sra);
1404 GdUnionRegion(dr,tra,trb);
1405 GdDestroyRegion(tra);
1406 GdDestroyRegion(trb);
1407 }
1408
1409 #if 0
1410 /***********************************************************************
1411 * DumpRegion
1412 * Outputs the contents of a MWCLIPREGION
1413 */
1414 void
1415 DumpRegion(MWCLIPREGION *pReg)
1416 {
1417 MWRECT *pRect, *pRectEnd = pReg->rects + pReg->numRects;
1418
1419 DPRINTF("Region %p: %d,%d - %d,%d %d rects\n", pReg,
1420 pReg->extents.left, pReg->extents.top,
1421 pReg->extents.right, pReg->extents.bottom, pReg->numRects);
1422 for(pRect = pReg->rects; pRect < pRectEnd; pRect++)
1423 DPRINTF("\t%d,%d - %d,%d\n", pRect->left, pRect->top,
1424 pRect->right, pRect->bottom);
1425 }
1426 #endif