![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to miregion.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi|
Return to miregion.c CVS log | Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi |
1.1 root 1: /***********************************************************
2: Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
3: and the Massachusetts Institute of Technology, Cambridge, Massachusetts.
4:
5: All Rights Reserved
6:
7: Permission to use, copy, modify, and distribute this software and its
8: documentation for any purpose and without fee is hereby granted,
9: provided that the above copyright notice appear in all copies and that
10: both that copyright notice and this permission notice appear in
11: supporting documentation, and that the names of Digital or MIT not be
12: used in advertising or publicity pertaining to distribution of the
13: software without specific, written prior permission.
14:
15: DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
16: ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
17: DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
18: ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
19: WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
20: ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
21: SOFTWARE.
22:
23: ******************************************************************/
24: /* $Header: miregion.c,v 1.27 87/09/03 13:25:15 toddb Exp $ */
25:
26: #include "miscstruct.h"
27: #include "regionstr.h"
28:
29: #ifdef DEBUG
30: #define assert(expr) {if (!(expr)) \
31: FatalError("Assertion failed file %s, line %d: expr\n", \
32: __FILE__, __LINE__); }
33: #else
34: #define assert(expr)
35: #endif
36:
37: /*
38: * The functions in this file implement the Region abstraction used extensively
39: * throughout the X11 sample server. A Region is simply an area, as the name
40: * implies, and is implemented as a "y-x-banded" array of rectangles. To
41: * explain: Each Region is made up of a certain number of rectangles sorted
42: * by y coordinate first, and then by x coordinate.
43: *
44: * Furthermore, the rectangles are banded such that every rectangle with a
45: * given upper-left y coordinate (y1) will have the same lower-right y
46: * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
47: * will span the entire vertical distance of the band. This means that some
48: * areas that could be merged into a taller rectangle will be represented as
49: * several shorter rectangles to account for shorter rectangles to its left
50: * or right but within its "vertical scope".
51: *
52: * An added constraint on the rectangles is that they must cover as much
53: * horizontal area as possible. E.g. no two rectangles in a band are allowed
54: * to touch.
55: *
56: * Whenever possible, bands will be merged together to cover a greater vertical
57: * distance (and thus reduce the number of rectangles). Two bands can be merged
58: * only if the bottom of one touches the top of the other and they have
59: * rectangles in the same places (of the same width, of course). This maintains
60: * the y-x-banding that's so nice to have...
61: */
62:
63: typedef BoxRec BOX; /* this is to cut down on some gratuitous edits */
64:
65: /* 1: if two BOXs overlap.
66: /* 0: if two BOXs do not overlap.
67: * Remember, x2 and y2 are not in the region
68: */
69: #define EXTENTCHECK(r1, r2) \
70: (!( ((r1)->x2 <= (r2)->x1) || \
71: ( ((r1)->x1 >= (r2)->x2)) || \
72: ( ((r1)->y2 <= (r2)->y1)) || \
73: ( ((r1)->y1 >= (r2)->y2)) ) )
74:
75:
76: void
77: miprintRects(rgn)
78: RegionPtr rgn;
79: {
80: register int i;
81:
82: ErrorF( "num: %d size: %d \n", rgn->numRects, rgn->size);
83: ErrorF( " extents: %d %d %d %d\n",rgn->extents.x1,
84: rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
85: for (i = 0; i < rgn->numRects; i++)
86: ErrorF( "%d %d %d %d \n", rgn->rects[i].x1,rgn->rects[i].y1,
87: rgn->rects[i].x2,rgn->rects[i].y2);
88: ErrorF( "\n");
89: }
90:
91: /*****************************************************************
92: * RegionCreate(rect, size)
93: * This routine does a simple malloc to make a structure of
94: * REGION of "size" number of rectangles.
95: *****************************************************************/
96:
97: RegionPtr
98: miRegionCreate(rect, size)
99: register BOX *rect;
100: register int size;
101: {
102: register RegionPtr temp; /* new region */
103:
104: size = max(1, size);
105: temp = (RegionPtr ) Xalloc (sizeof (RegionRec));
106: temp->rects = (BOX *) Xalloc (size * (sizeof(BOX)));
107: if (rect == (BOX *)NULL)
108: {
109: temp->numRects = 0;
110: temp->extents.x1 = 0;
111: temp->extents.y1 = 0;
112: temp->extents.x2 = 0;
113: temp->extents.y2 = 0;
114: }
115: else
116: {
117: temp->extents = *rect;
118: temp->rects[0] = *rect;
119: temp->numRects = 1;
120: }
121: temp->size = size;
122: return(temp);
123: }
124:
125:
126: void
127: miRegionCopy(dstrgn, rgn)
128: register RegionPtr dstrgn;
129: register RegionPtr rgn;
130:
131: {
132: if (dstrgn != rgn) /* don't want to copy to itself */
133: {
134: if (dstrgn->size < rgn->numRects)
135: {
136: if (dstrgn->rects)
137: {
138: dstrgn->rects = (BOX *) Xrealloc(dstrgn->rects,
139: rgn->numRects * (sizeof(BOX)));
140: }
141: else
142: ErrorF( "RC HORRIBLE ERROR...\n");
143: dstrgn->size = rgn->numRects;
144: }
145: dstrgn->numRects = rgn->numRects;
146: dstrgn->extents.x1 = rgn->extents.x1;
147: dstrgn->extents.y1 = rgn->extents.y1;
148: dstrgn->extents.x2 = rgn->extents.x2;
149: dstrgn->extents.y2 = rgn->extents.y2;
150:
151: bcopy(rgn->rects, dstrgn->rects, rgn->numRects * sizeof(BOX));
152: }
153: }
154:
155:
156: /*======================================================================
157: * Generic Region Operator
158: *====================================================================*/
159:
160: /*-
161: *-----------------------------------------------------------------------
162: * miCoalesce --
163: * Attempt to merge the boxes in the current band with those in the
164: * previous one. Used only by miRegionOp.
165: *
166: * Results:
167: * The new index for the previous band.
168: *
169: * Side Effects:
170: * If coalescing takes place:
171: * - rectangles in the previous band will have their y2 fields
172: * altered.
173: * - pReg->numRects will be decreased.
174: *
175: *-----------------------------------------------------------------------
176: */
177: static int
178: miCoalesce (pReg, prevStart, curStart)
179: register RegionPtr pReg; /* Region to coalesce */
180: int prevStart; /* Index of start of previous band */
181: int curStart; /* Index of start of current band */
182: {
183: register BoxPtr pPrevBox; /* Current box in previous band */
184: register BoxPtr pCurBox; /* Current box in current band */
185: register BoxPtr pRegEnd; /* End of region */
186: int curNumRects; /* Number of rectangles in current
187: * band */
188: int prevNumRects; /* Number of rectangles in previous
189: * band */
190: int bandY1; /* Y1 coordinate for current band */
191:
192: pRegEnd = &pReg->rects[pReg->numRects];
193:
194: pPrevBox = &pReg->rects[prevStart];
195: prevNumRects = curStart - prevStart;
196:
197: /*
198: * Figure out how many rectangles are in the current band. Have to do
199: * this because multiple bands could have been added in miRegionOp
200: * at the end when one region has been exhausted.
201: */
202: pCurBox = &pReg->rects[curStart];
203: bandY1 = pCurBox->y1;
204: for (curNumRects = 0;
205: (pCurBox != pRegEnd) && (pCurBox->y1 == bandY1);
206: curNumRects++)
207: {
208: pCurBox++;
209: }
210:
211: if (pCurBox != pRegEnd)
212: {
213: /*
214: * If more than one band was added, we have to find the start
215: * of the last band added so the next coalescing job can start
216: * at the right place... (given when multiple bands are added,
217: * this may be pointless -- see above).
218: */
219: pRegEnd--;
220: while (pRegEnd[-1].y1 == pRegEnd->y1)
221: {
222: pRegEnd--;
223: }
224: curStart = pRegEnd - pReg->rects;
225: pRegEnd = pReg->rects + pReg->numRects;
226: }
227:
228: if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
229: pCurBox -= curNumRects;
230: /*
231: * The bands may only be coalesced if the bottom of the previous
232: * matches the top scanline of the current.
233: */
234: if (pPrevBox->y2 == pCurBox->y1)
235: {
236: /*
237: * Make sure the bands have boxes in the same places. This
238: * assumes that boxes have been added in such a way that they
239: * cover the most area possible. I.e. two boxes in a band must
240: * have some horizontal space between them.
241: */
242: do
243: {
244: if ((pPrevBox->x1 != pCurBox->x1) ||
245: (pPrevBox->x2 != pCurBox->x2))
246: {
247: /*
248: * The bands don't line up so they can't be coalesced.
249: */
250: return (curStart);
251: }
252: pPrevBox++;
253: pCurBox++;
254: prevNumRects -= 1;
255: } while (prevNumRects != 0);
256:
257: pReg->numRects -= curNumRects;
258: pCurBox -= curNumRects;
259: pPrevBox -= curNumRects;
260:
261: /*
262: * The bands may be merged, so set the bottom y of each box
263: * in the previous band to that of the corresponding box in
264: * the current band.
265: */
266: do
267: {
268: pPrevBox->y2 = pCurBox->y2;
269: pPrevBox++;
270: pCurBox++;
271: curNumRects -= 1;
272: } while (curNumRects != 0);
273:
274: /*
275: * If only one band was added to the region, we have to backup
276: * curStart to the start of the previous band.
277: *
278: * If more than one band was added to the region, copy the
279: * other bands down. The assumption here is that the other bands
280: * came from the same region as the current one and no further
281: * coalescing can be done on them since it's all been done
282: * already... curStart is already in the right place.
283: */
284: if (pCurBox == pRegEnd)
285: {
286: curStart = prevStart;
287: }
288: else
289: {
290: do
291: {
292: *pPrevBox++ = *pCurBox++;
293: } while (pCurBox != pRegEnd);
294: }
295:
296: }
297: }
298: return (curStart);
299: }
300:
301: /*-
302: *-----------------------------------------------------------------------
303: * miRegionOp --
304: * Apply an operation to two regions. Called by miUnion, miInverse,
305: * miSubtract, miIntersect...
306: *
307: * Results:
308: * None.
309: *
310: * Side Effects:
311: * The new region is overwritten.
312: *
313: * Notes:
314: * The idea behind this function is to view the two regions as sets.
315: * Together they cover a rectangle of area that this function divides
316: * into horizontal bands where points are covered only by one region
317: * or by both. For the first case, the nonOverlapFunc is called with
318: * each the band and the band's upper and lower extents. For the
319: * second, the overlapFunc is called to process the entire band. It
320: * is responsible for clipping the rectangles in the band, though
321: * this function provides the boundaries.
322: * At the end of each band, the new region is coalesced, if possible,
323: * to reduce the number of rectangles in the region.
324: *
325: *-----------------------------------------------------------------------
326: */
327: static void
328: miRegionOp(newReg, reg1, reg2, overlapFunc, nonOverlap1Func, nonOverlap2Func)
329: register RegionPtr newReg; /* Place to store result */
330: RegionPtr reg1; /* First region in operation */
331: RegionPtr reg2; /* 2d region in operation */
332: void (*overlapFunc)(); /* Function to call for over-
333: * lapping bands */
334: void (*nonOverlap1Func)(); /* Function to call for non-
335: * overlapping bands in region
336: * 1 */
337: void (*nonOverlap2Func)(); /* Function to call for non-
338: * overlapping bands in region
339: * 2 */
340: {
341: register BoxPtr r1; /* Pointer into first region */
342: register BoxPtr r2; /* Pointer into 2d region */
343: BoxPtr r1End; /* End of 1st region */
344: BoxPtr r2End; /* End of 2d region */
345: register short ybot; /* Bottom of intersection */
346: register short ytop; /* Top of intersection */
347: BoxPtr oldRects; /* Old rects for newReg */
348: int oldSize; /* Old size of newReg */
349: int prevBand; /* Index of start of
350: * previous band in newReg */
351: int curBand; /* Index of start of current
352: * band in newReg */
353: register BoxPtr r1BandEnd; /* End of current band in r1 */
354: register BoxPtr r2BandEnd; /* End of current band in r2 */
355: short top; /* Top of non-overlapping
356: * band */
357: short bot; /* Bottom of non-overlapping
358: * band */
359:
360: /*
361: * Initialization:
362: * set r1, r2, r1End and r2End appropriately, preserve the important
363: * parts of the destination region until the end in case it's one of
364: * the two source regions, then mark the "new" region empty, allocating
365: * another array of rectangles for it to use.
366: */
367: r1 = reg1->rects;
368: r2 = reg2->rects;
369: r1End = r1 + reg1->numRects;
370: r2End = r2 + reg2->numRects;
371:
372: oldSize = newReg->size;
373: oldRects = newReg->rects;
374:
375: EMPTY_REGION(newReg);
376:
377: /*
378: * Allocate a reasonable number of rectangles for the new region. The idea
379: * is to allocate enough so the individual functions don't need to
380: * reallocate and copy the array, which is time consuming, yet we don't
381: * have to worry about using too much memory. I hope to be able to
382: * nuke the Xrealloc() at the end of this function eventually.
383: */
384: newReg->size = max(reg1->numRects,reg2->numRects) * 2;
385:
386: newReg->rects = (BoxPtr) Xalloc (sizeof(BoxRec) * newReg->size);
387:
388: /*
389: * Initialize ybot and ytop.
390: * In the upcoming loop, ybot and ytop serve different functions depending
391: * on whether the band being handled is an overlapping or non-overlapping
392: * band.
393: * In the case of a non-overlapping band (only one of the regions
394: * has points in the band), ybot is the bottom of the most recent
395: * intersection and thus clips the top of the rectangles in that band.
396: * ytop is the top of the next intersection between the two regions and
397: * serves to clip the bottom of the rectangles in the current band.
398: * For an overlapping band (where the two regions intersect), ytop clips
399: * the top of the rectangles of both regions and ybot clips the bottoms.
400: */
401: if (reg1->extents.y1 < reg2->extents.y1)
402: {
403: ybot = reg1->extents.y1;
404: ytop = reg2->extents.y1;
405: }
406: else
407: {
408: ybot = reg2->extents.y1;
409: ytop = reg1->extents.y1;
410: }
411:
412: /*
413: * prevBand serves to mark the start of the previous band so rectangles
414: * can be coalesced into larger rectangles. qv. miCoalesce, above.
415: * In the beginning, there is no previous band, so prevBand == curBand
416: * (curBand is set later on, of course, but the first band will always
417: * start at index 0). prevBand and curBand must be indices because of
418: * the possible expansion, and resultant moving, of the new region's
419: * array of rectangles.
420: */
421: prevBand = 0;
422:
423: do
424: {
425: curBand = newReg->numRects;
426:
427: /*
428: * This algorithm proceeds one source-band (as opposed to a
429: * destination band, which is determined by where the two regions
430: * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
431: * rectangle after the last one in the current band for their
432: * respective regions.
433: */
434: r1BandEnd = r1;
435: while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
436: {
437: r1BandEnd++;
438: }
439:
440: r2BandEnd = r2;
441: while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
442: {
443: r2BandEnd++;
444: }
445:
446: /*
447: * First handle the band that doesn't intersect, if any.
448: *
449: * Note that attention is restricted to one band in the
450: * non-intersecting region at once, so if a region has n
451: * bands between the current position and the next place it overlaps
452: * the other, this entire loop will be passed through n times.
453: */
454: if (r1->y1 < r2->y1)
455: {
456: top = max(r1->y1,ybot);
457: bot = min(r1->y2,r2->y1);
458:
459: if ((top != bot) && (nonOverlap1Func != (void (*)())NULL))
460: {
461: (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
462: }
463:
464: ytop = r2->y1;
465: }
466: else if (r2->y1 < r1->y1)
467: {
468: top = max(r2->y1,ybot);
469: bot = min(r2->y2,r1->y1);
470:
471: if ((top != bot) && (nonOverlap2Func != (void (*)())NULL))
472: {
473: (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
474: }
475:
476: ytop = r1->y1;
477: }
478: else
479: {
480: ytop = r1->y1;
481: }
482:
483: /*
484: * If any rectangles got added to the region, try and coalesce them
485: * with rectangles from the previous band. Note we could just do
486: * this test in miCoalesce, but some machines incur a not
487: * inconsiderable cost for function calls, so...
488: */
489: if (newReg->numRects != curBand)
490: {
491: prevBand = miCoalesce (newReg, prevBand, curBand);
492: }
493:
494: /*
495: * Now see if we've hit an intersecting band. The two bands only
496: * intersect if ybot > ytop
497: */
498: ybot = min(r1->y2, r2->y2);
499: curBand = newReg->numRects;
500: if (ybot > ytop)
501: {
502: (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
503:
504: }
505:
506: if (newReg->numRects != curBand)
507: {
508: prevBand = miCoalesce (newReg, prevBand, curBand);
509: }
510:
511: /*
512: * If we've finished with a band (y2 == ybot) we skip forward
513: * in the region to the next band.
514: */
515: if (r1->y2 == ybot)
516: {
517: r1 = r1BandEnd;
518: }
519: if (r2->y2 == ybot)
520: {
521: r2 = r2BandEnd;
522: }
523: } while ((r1 != r1End) && (r2 != r2End));
524:
525: /*
526: * Deal with whichever region still has rectangles left.
527: */
528: curBand = newReg->numRects;
529: if (r1 != r1End)
530: {
531: if (nonOverlap1Func != (void (*)())NULL)
532: {
533: do
534: {
535: r1BandEnd = r1;
536: while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
537: {
538: r1BandEnd++;
539: }
540: (* nonOverlap1Func) (newReg, r1, r1BandEnd,
541: max(r1->y1,ybot), r1->y2);
542: r1 = r1BandEnd;
543: } while (r1 != r1End);
544: }
545: }
546: else if ((r2 != r2End) && (nonOverlap2Func != (void (*)())NULL))
547: {
548: do
549: {
550: r2BandEnd = r2;
551: while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
552: {
553: r2BandEnd++;
554: }
555: (* nonOverlap2Func) (newReg, r2, r2BandEnd,
556: max(r2->y1,ybot), r2->y2);
557: r2 = r2BandEnd;
558: } while (r2 != r2End);
559: }
560:
561: if (newReg->numRects != curBand)
562: {
563: (void) miCoalesce (newReg, prevBand, curBand);
564: }
565:
566: /*
567: * A bit of cleanup. To keep regions from growing without bound,
568: * we shrink the array of rectangles to match the new number of
569: * rectangles in the region. This never goes to 0, however...
570: *
571: * Only do this stuff if the number of rectangles allocated is more than
572: * twice the number of rectangles in the region (a simple optimization...).
573: */
574: if (newReg->numRects < (newReg->size >> 1))
575: {
576: if (REGION_NOT_EMPTY(newReg))
577: {
578: newReg->size = newReg->numRects;
579: newReg->rects = (BoxPtr) Xrealloc (newReg->rects,
580: sizeof(BoxRec) * newReg->size);
581: }
582: else
583: {
584: /*
585: * No point in doing the extra work involved in an Xrealloc if
586: * the region is empty
587: */
588: newReg->size = 1;
589: Xfree(newReg->rects);
590: newReg->rects = (BoxPtr) Xalloc(sizeof(BoxRec));
591: }
592: }
593: Xfree (oldRects);
594: }
595:
596: /*-
597: *-----------------------------------------------------------------------
598: * miSetExtents --
599: * Reset the extents of a region to what they should be. Called by
600: * miSubtract and miIntersect b/c they can't figure it out along the
601: * way or do so easily, as miUnion can.
602: *
603: * Results:
604: * None.
605: *
606: * Side Effects:
607: * The region's 'extents' structure is overwritten.
608: *
609: *-----------------------------------------------------------------------
610: */
611: static void
612: miSetExtents (pReg)
613: RegionPtr pReg;
614: {
615: register BoxPtr pBox,
616: pBoxEnd,
617: pExtents;
618:
619: pExtents = &pReg->extents;
620: pBox = pReg->rects;
621: pBoxEnd = &pBox[pReg->numRects - 1];
622:
623: /*
624: * Since pBox is the first rectangle in the region, it must have the
625: * smallest y1 and since pBoxEnd is the last rectangle in the region,
626: * it must have the largest y2, because of banding. Initialize x1 and
627: * x2 from pBox and pBoxEnd, resp., as good things to initialize them
628: * to...
629: */
630: pExtents->x1 = pBox->x1;
631: pExtents->y1 = pBox->y1;
632: pExtents->x2 = pBoxEnd->x2;
633: pExtents->y2 = pBoxEnd->y2;
634:
635: assert(pExtents->y1 < pExtents->y2);
636: while (pBox <= pBoxEnd)
637: {
638: if (pBox->x1 < pExtents->x1)
639: {
640: pExtents->x1 = pBox->x1;
641: }
642: if (pBox->x2 > pExtents->x2)
643: {
644: pExtents->x2 = pBox->x2;
645: }
646: pBox++;
647: }
648: assert(pExtents->x1 < pExtents->x2);
649: }
650:
651:
652: /*======================================================================
653: * Region Inversion
654: *====================================================================*/
655:
656: /*-
657: *-----------------------------------------------------------------------
658: * miInverse --
659: * Take a region and a box and return a region that is everything
660: * in the box but not in the region. The careful reader will note
661: * that this is the same as subtracting the region from the box...
662: *
663: * Results:
664: * TRUE.
665: *
666: * Side Effects:
667: * newReg is overwritten.
668: *
669: *-----------------------------------------------------------------------
670: */
671: int
672: miInverse(newReg, reg1, invRect)
673: RegionPtr newReg; /* Destination region */
674: RegionPtr reg1; /* Region to invert */
675: BOX *invRect; /* Bounding box for inversion */
676: {
677: RegionRec invReg; /* Quick and dirty region made from the
678: * bounding box */
679:
680: invReg.size = 1;
681: invReg.numRects = 1;
682: invReg.extents = *invRect;
683: invReg.rects = invRect;
684: return (miSubtract (newReg, &invReg, reg1));
685: }
686:
687:
688: /*======================================================================
689: * Region Intersection
690: *====================================================================*/
691: /*-
692: *-----------------------------------------------------------------------
693: * miIntersectO --
694: * Handle an overlapping band for miIntersect.
695: *
696: * Results:
697: * None.
698: *
699: * Side Effects:
700: * Rectangles may be added to the region.
701: *
702: *-----------------------------------------------------------------------
703: */
704: static void
705: miIntersectO (pReg, r1, r1End, r2, r2End, y1, y2)
706: register RegionPtr pReg;
707: register BoxPtr r1;
708: BoxPtr r1End;
709: register BoxPtr r2;
710: BoxPtr r2End;
711: short y1;
712: short y2;
713: {
714: register short x1;
715: register short x2;
716: register BoxPtr pNextRect;
717:
718: pNextRect = &pReg->rects[pReg->numRects];
719:
720: while ((r1 != r1End) && (r2 != r2End))
721: {
722: x1 = max(r1->x1,r2->x1);
723: x2 = min(r1->x2,r2->x2);
724:
725: /*
726: * If there's any overlap between the two rectangles, add that
727: * overlap to the new region.
728: * There's no need to check for subsumption because the only way
729: * such a need could arise is if some region has two rectangles
730: * right next to each other. Since that should never happen...
731: */
732: if (x1 < x2)
733: {
734: assert(y1<y2);
735:
736: MEMCHECK(pReg, pNextRect, pReg->rects);
737: pNextRect->x1 = x1;
738: pNextRect->y1 = y1;
739: pNextRect->x2 = x2;
740: pNextRect->y2 = y2;
741: pReg->numRects += 1;
742: pNextRect++;
743: assert(pReg->numRects <= pReg->size);
744: }
745:
746: /*
747: * Need to advance the pointers. Shift the one that extends
748: * to the right the least, since the other still has a chance to
749: * overlap with that region's next rectangle, if you see what I mean.
750: */
751: if (r1->x2 < r2->x2)
752: {
753: r1++;
754: }
755: else if (r2->x2 < r1->x2)
756: {
757: r2++;
758: }
759: else
760: {
761: r1++;
762: r2++;
763: }
764: }
765: }
766:
767:
768: int
769: miIntersect(newReg, reg1, reg2)
770: register RegionPtr newReg; /* destination Region */
771: RegionPtr reg1;
772: RegionPtr reg2; /* source regions */
773: {
774: /* check for trivial reject */
775: if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
776: (!EXTENTCHECK(®1->extents, ®2->extents)))
777: {
778: newReg->numRects = 0;
779: return(1);
780: }
781:
782: miRegionOp (newReg, reg1, reg2, miIntersectO, NULL, NULL);
783:
784: if (newReg->numRects != 0)
785: {
786: /*
787: * Can't alter newReg's extents before we call miRegionOp because
788: * it might be one of the source regions and miRegionOp depends
789: * on the extents of those regions being the same. Besides, this
790: * way there's no checking against rectangles that will be nuked
791: * due to coalescing, so we have to examine fewer rectangles.
792: */
793: miSetExtents(newReg);
794: }
795: return(1);
796: }
797:
798:
799: /*======================================================================
800: * Region Union
801: *====================================================================*/
802:
803: /*-
804: *-----------------------------------------------------------------------
805: * miUnionNonO --
806: * Handle a non-overlapping band for the union operation. Just
807: * Adds the rectangles into the region. Doesn't have to check for
808: * subsumption or anything.
809: *
810: * Results:
811: * None.
812: *
813: * Side Effects:
814: * pReg->numRects is incremented and the final rectangles overwritten
815: * with the rectangles we're passed.
816: *
817: *-----------------------------------------------------------------------
818: */
819: static void
820: miUnionNonO (pReg, r, rEnd, y1, y2)
821: register RegionPtr pReg;
822: register BoxPtr r;
823: BoxPtr rEnd;
824: register short y1;
825: register short y2;
826: {
827: register BoxPtr pNextRect;
828:
829: pNextRect = &pReg->rects[pReg->numRects];
830:
831: assert(y1 < y2);
832:
833: while (r != rEnd)
834: {
835: assert(r->x1 < r->x2);
836: MEMCHECK(pReg, pNextRect, pReg->rects);
837: pNextRect->x1 = r->x1;
838: pNextRect->y1 = y1;
839: pNextRect->x2 = r->x2;
840: pNextRect->y2 = y2;
841: pReg->numRects += 1;
842: pNextRect++;
843:
844: assert(pReg->numRects<=pReg->size);
845: r++;
846: }
847:
848: }
849:
850: /*-
851: *-----------------------------------------------------------------------
852: * miUnionO --
853: * Handle an overlapping band for the union operation. Picks the
854: * left-most rectangle each time and merges it into the region.
855: *
856: * Results:
857: * None.
858: *
859: * Side Effects:
860: * Rectangles are overwritten in pReg->rects and pReg->numRects will
861: * be changed.
862: *
863: *-----------------------------------------------------------------------
864: */
865: static void
866: miUnionO (pReg, r1, r1End, r2, r2End, y1, y2)
867: register RegionPtr pReg;
868: register BoxPtr r1;
869: BoxPtr r1End;
870: register BoxPtr r2;
871: BoxPtr r2End;
872: register short y1;
873: register short y2;
874: {
875: register BoxPtr pNextRect;
876:
877: pNextRect = &pReg->rects[pReg->numRects];
878:
879: #define MERGERECT(r) \
880: if ((pReg->numRects != 0) && \
881: (pNextRect[-1].y1 == y1) && \
882: (pNextRect[-1].y2 == y2) && \
883: (pNextRect[-1].x2 >= r->x1)) \
884: { \
885: if (pNextRect[-1].x2 < r->x2) \
886: { \
887: pNextRect[-1].x2 = r->x2; \
888: assert(pNextRect[-1].x1<pNextRect[-1].x2); \
889: } \
890: } \
891: else \
892: { \
893: MEMCHECK(pReg, pNextRect, pReg->rects); \
894: pNextRect->y1 = y1; \
895: pNextRect->y2 = y2; \
896: pNextRect->x1 = r->x1; \
897: pNextRect->x2 = r->x2; \
898: pReg->numRects += 1; \
899: pNextRect += 1; \
900: } \
901: assert(pReg->numRects<=pReg->size);\
902: r++;
903:
904: assert (y1<y2);
905: while ((r1 != r1End) && (r2 != r2End))
906: {
907: if (r1->x1 < r2->x1)
908: {
909: MERGERECT(r1);
910: }
911: else
912: {
913: MERGERECT(r2);
914: }
915: }
916:
917: if (r1 != r1End)
918: {
919: do
920: {
921: MERGERECT(r1);
922: } while (r1 != r1End);
923: }
924: else while (r2 != r2End)
925: {
926: MERGERECT(r2);
927: }
928: }
929:
930: int
931: miUnion(newReg, reg1, reg2)
932: RegionPtr newReg; /* destination Region */
933: RegionPtr reg1;
934: RegionPtr reg2; /* source regions */
935: {
936: /* checks all the simple cases */
937:
938: /*
939: * Region 1 and 2 are the same or region 1 is empty
940: */
941: if ( (reg1 == reg2) || (!(reg1->numRects)) )
942: {
943: if (newReg != reg2)
944: miRegionCopy(newReg, reg2);
945: return(TRUE);
946: }
947:
948: /*
949: * if nothing to union (region 2 empty)
950: */
951: if (!(reg2->numRects))
952: {
953: if (newReg != reg1)
954: miRegionCopy(newReg, reg1);
955: return(TRUE);
956: }
957:
958: /*
959: * Region 1 completely subsumes region 2
960: */
961: if ((reg1->numRects == 1) &&
962: (reg1->extents.x1 <= reg2->extents.x1) &&
963: (reg1->extents.y1 <= reg2->extents.y1) &&
964: (reg1->extents.x2 >= reg2->extents.x2) &&
965: (reg1->extents.y2 >= reg2->extents.y2))
966: {
967: if (newReg != reg1)
968: miRegionCopy(newReg, reg1);
969: return(TRUE);
970: }
971:
972: /*
973: * Region 2 completely subsumes region 1
974: */
975: if ((reg2->numRects == 1) &&
976: (reg2->extents.x1 <= reg1->extents.x1) &&
977: (reg2->extents.y1 <= reg1->extents.y1) &&
978: (reg2->extents.x2 >= reg1->extents.x2) &&
979: (reg2->extents.y2 >= reg1->extents.y2))
980: {
981: if (newReg != reg2)
982: miRegionCopy(newReg, reg2);
983: return(TRUE);
984: }
985:
986: miRegionOp (newReg, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO);
987:
988: newReg->extents.x1 = min(reg1->extents.x1, reg2->extents.x1);
989: newReg->extents.y1 = min(reg1->extents.y1, reg2->extents.y1);
990: newReg->extents.x2 = max(reg1->extents.x2, reg2->extents.x2);
991: newReg->extents.y2 = max(reg1->extents.y2, reg2->extents.y2);
992:
993: return(1);
994: }
995:
996:
997:
998: /*======================================================================
999: * Region Subtraction
1000: *====================================================================*/
1001:
1002: /*-
1003: *-----------------------------------------------------------------------
1004: * miSubtractNonO --
1005: * Deal with non-overlapping band for subtraction. Any parts from
1006: * region 2 we discard. Anything from region 1 we add to the region.
1007: *
1008: * Results:
1009: * None.
1010: *
1011: * Side Effects:
1012: * pReg may be affected.
1013: *
1014: *-----------------------------------------------------------------------
1015: */
1016: static void
1017: miSubtractNonO1 (pReg, r, rEnd, y1, y2)
1018: register RegionPtr pReg;
1019: register BoxPtr r;
1020: BoxPtr rEnd;
1021: register short y1;
1022: register short y2;
1023: {
1024: register BoxPtr pNextRect;
1025:
1026: pNextRect = &pReg->rects[pReg->numRects];
1027:
1028: assert(y1<y2);
1029:
1030: while (r != rEnd)
1031: {
1032: assert(r->x1<r->x2);
1033: MEMCHECK(pReg, pNextRect, pReg->rects);
1034: pNextRect->x1 = r->x1;
1035: pNextRect->y1 = y1;
1036: pNextRect->x2 = r->x2;
1037: pNextRect->y2 = y2;
1038: pReg->numRects += 1;
1039: pNextRect++;
1040:
1041: assert(pReg->numRects <= pReg->size);
1042:
1043: r++;
1044: }
1045: }
1046:
1047: /*-
1048: *-----------------------------------------------------------------------
1049: * miSubtractO --
1050: * Overlapping band subtraction. x1 is the left-most point not yet
1051: * checked.
1052: *
1053: * Results:
1054: * None.
1055: *
1056: * Side Effects:
1057: * pReg may have rectangles added to it.
1058: *
1059: *-----------------------------------------------------------------------
1060: */
1061: static void
1062: miSubtractO (pReg, r1, r1End, r2, r2End, y1, y2)
1063: register RegionPtr pReg;
1064: register BoxPtr r1;
1065: BoxPtr r1End;
1066: register BoxPtr r2;
1067: BoxPtr r2End;
1068: register short y1;
1069: register short y2;
1070: {
1071: register BoxPtr pNextRect;
1072: register int x1;
1073:
1074: x1 = r1->x1;
1075:
1076: assert(y1<y2);
1077: pNextRect = &pReg->rects[pReg->numRects];
1078:
1079: while ((r1 != r1End) && (r2 != r2End))
1080: {
1081: if (r2->x2 <= x1)
1082: {
1083: /*
1084: * Subtrahend missed the boat: go to next subtrahend.
1085: */
1086: r2++;
1087: }
1088: else if (r2->x1 <= x1)
1089: {
1090: /*
1091: * Subtrahend preceeds minuend: nuke left edge of minuend.
1092: */
1093: x1 = r2->x2;
1094: if (x1 >= r1->x2)
1095: {
1096: /*
1097: * Minuend completely covered: advance to next minuend and
1098: * reset left fence to edge of new minuend.
1099: */
1100: r1++;
1101: x1 = r1->x1;
1102: }
1103: else
1104: {
1105: /*
1106: * Subtrahend now used up since it doesn't extend beyond
1107: * minuend
1108: */
1109: r2++;
1110: }
1111: }
1112: else if (r2->x1 < r1->x2)
1113: {
1114: /*
1115: * Left part of subtrahend covers part of minuend: add uncovered
1116: * part of minuend to region and skip to next subtrahend.
1117: */
1118: assert(x1<r2->x1);
1119: MEMCHECK(pReg, pNextRect, pReg->rects);
1120: pNextRect->x1 = x1;
1121: pNextRect->y1 = y1;
1122: pNextRect->x2 = r2->x1;
1123: pNextRect->y2 = y2;
1124: pReg->numRects += 1;
1125: pNextRect++;
1126:
1127: assert(pReg->numRects<=pReg->size);
1128:
1129: x1 = r2->x2;
1130: if (x1 >= r1->x2)
1131: {
1132: /*
1133: * Minuend used up: advance to new...
1134: */
1135: r1++;
1136: x1 = r1->x1;
1137: }
1138: else
1139: {
1140: /*
1141: * Subtrahend used up
1142: */
1143: r2++;
1144: }
1145: }
1146: else
1147: {
1148: /*
1149: * Minuend used up: add any remaining piece before advancing.
1150: */
1151: if (r1->x2 > x1)
1152: {
1153: MEMCHECK(pReg, pNextRect, pReg->rects);
1154: pNextRect->x1 = x1;
1155: pNextRect->y1 = y1;
1156: pNextRect->x2 = r1->x2;
1157: pNextRect->y2 = y2;
1158: pReg->numRects += 1;
1159: pNextRect++;
1160: assert(pReg->numRects<=pReg->size);
1161: }
1162: r1++;
1163: x1 = r1->x1;
1164: }
1165: }
1166:
1167: /*
1168: * Add remaining minuend rectangles to region.
1169: */
1170: while (r1 != r1End)
1171: {
1172: assert(x1<r1->x2);
1173: MEMCHECK(pReg, pNextRect, pReg->rects);
1174: pNextRect->x1 = x1;
1175: pNextRect->y1 = y1;
1176: pNextRect->x2 = r1->x2;
1177: pNextRect->y2 = y2;
1178: pReg->numRects += 1;
1179: pNextRect++;
1180:
1181: assert(pReg->numRects<=pReg->size);
1182:
1183: r1++;
1184: if (r1 != r1End)
1185: {
1186: x1 = r1->x1;
1187: }
1188: }
1189: }
1190:
1191: /*-
1192: *-----------------------------------------------------------------------
1193: * miSubtract --
1194: * Subtract regS from regM and leave the result in regD.
1195: * S stands for subtrahend, M for minuend and D for difference.
1196: *
1197: * Results:
1198: * TRUE.
1199: *
1200: * Side Effects:
1201: * regD is overwritten.
1202: *
1203: *-----------------------------------------------------------------------
1204: */
1205: int
1206: miSubtract(regD, regM, regS)
1207: register RegionPtr regD;
1208: RegionPtr regM;
1209: RegionPtr regS;
1210: {
1211: /* check for trivial reject */
1212: if ( (!(regM->numRects)) || (!(regS->numRects)) ||
1213: (!EXTENTCHECK(®M->extents, ®S->extents)) )
1214: {
1215: miRegionCopy(regD, regM);
1216: return(1);
1217: }
1218:
1219: miRegionOp (regD, regM, regS, miSubtractO, miSubtractNonO1, NULL);
1220:
1221: if (regD->numRects != 0)
1222: {
1223: /*
1224: * Can't alter newReg's extents before we call miRegionOp because
1225: * it might be one of the source regions and miRegionOp depends
1226: * on the extents of those regions being the unaltered. Besides, this
1227: * way there's no checking against rectangles that will be nuked
1228: * due to coalescing, so we have to examine fewer rectangles.
1229: */
1230: miSetExtents (regD);
1231: }
1232: return(1);
1233: }
1234:
1235:
1236: /*
1237: * RectIn(region, rect)
1238: * This routine takes a pointer to a region and a pointer to a box
1239: * and determines if the box is outside/inside/partly inside the region.
1240: *
1241: * The idea is to travel through the list of rectangles trying to cover the
1242: * passed box with them. Anytime a piece of the rectangle isn't covered
1243: * by a band of rectangles, partOut is set TRUE. Any time a rectangle in
1244: * the region covers part of the box, partIn is set TRUE. The process ends
1245: * when either the box has been completely covered (we reached a band that
1246: * doesn't overlap the box, partIn is TRUE and partOut is false), the
1247: * box has been partially covered (partIn == partOut == TRUE -- because of
1248: * the banding, the first time this is true we know the box is only
1249: * partially in the region) or is outside the region (we reached a band
1250: * that doesn't overlap the box at all and partIn is false)
1251: */
1252:
1253: int
1254: miRectIn(region, prect)
1255: register RegionPtr region;
1256: register BoxPtr prect;
1257: {
1258: register short x;
1259: register short y;
1260: register BoxPtr pbox;
1261: register BoxPtr pboxEnd;
1262: int partIn, partOut;
1263:
1264: /* this is (just) a useful optimization */
1265: if ((region->numRects == 0) || !EXTENTCHECK(®ion->extents, prect))
1266: return(rgnOUT);
1267:
1268: partOut = FALSE;
1269: partIn = FALSE;
1270:
1271: /* (x,y) starts at upper left of rect, moving to the right and down */
1272: x = prect->x1;
1273: y = prect->y1;
1274:
1275: /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
1276: for (pbox = region->rects, pboxEnd = pbox + region->numRects;
1277: pbox < pboxEnd;
1278: pbox++)
1279: {
1280:
1281: if (pbox->y2 <= y)
1282: continue; /* getting up to speed or skipping remainder of band */
1283:
1284: if (pbox->y1 > y)
1285: {
1286: partOut = TRUE; /* missed part of rectangle above */
1287: if (partIn || (pbox->y1 >= prect->y2))
1288: break;
1289: y = pbox->y1; /* x guaranteed to be == prect->x1 */
1290: }
1291:
1292: if (pbox->x2 <= x)
1293: continue; /* not far enough over yet */
1294:
1295: if (pbox->x1 > x)
1296: {
1297: partOut = TRUE; /* missed part of rectangle to left */
1298: if (partIn)
1299: break;
1300: }
1301:
1302: if (pbox->x1 < prect->x2)
1303: {
1304: partIn = TRUE; /* definitely overlap */
1305: if (partOut)
1306: break;
1307: }
1308:
1309: if (pbox->x2 >= prect->x2)
1310: {
1311: y = pbox->y2; /* finished with this band */
1312: if (y >= prect->y2)
1313: break;
1314: x = prect->x1; /* reset x out to left again */
1315: }
1316: else
1317: {
1318: /*
1319: * Because boxes in a band are maximal width, if the first box
1320: * to overlap the rectangle doesn't completely cover it in that
1321: * band, the rectangle must be partially out, since some of it
1322: * will be uncovered in that band. partIn will have been set true
1323: * by now...
1324: */
1325: partOut = TRUE;
1326: break;
1327: }
1328: }
1329:
1330: return(partIn ? ((y < prect->y2) ? rgnPART : rgnIN) : rgnOUT);
1331: }
1332:
1333: /* TranslateRegion(pRegion, x, y)
1334: translates in place
1335: added by raymond
1336: */
1337:
1338: void
1339: miTranslateRegion(pRegion, x, y)
1340: register RegionPtr pRegion;
1341: register int x;
1342: register int y;
1343: {
1344: register int nbox;
1345: register BOX *pbox;
1346:
1347: pbox = pRegion->rects;
1348: nbox = pRegion->numRects;
1349:
1350: while(nbox--)
1351: {
1352: pbox->x1 += x;
1353: pbox->x2 += x;
1354: pbox->y1 += y;
1355: pbox->y2 += y;
1356: pbox++;
1357: }
1358: pRegion->extents.x1 += x;
1359: pRegion->extents.x2 += x;
1360: pRegion->extents.y1 += y;
1361: pRegion->extents.y2 += y;
1362: }
1363:
1364: void
1365: miRegionDestroy(pRegion)
1366: RegionPtr pRegion;
1367: {
1368: Xfree(pRegion->rects);
1369: Xfree(pRegion);
1370: }
1371:
1372:
1373: void
1374: miRegionReset(pRegion, pBox)
1375: RegionPtr pRegion;
1376: BOX *pBox;
1377: {
1378: assert(pBox->x1<pBox->x2);
1379: assert(pBox->y1<pBox->y2);
1380: pRegion->extents.x1 = pRegion->rects->x1 = pBox->x1;
1381: pRegion->extents.y1 = pRegion->rects->y1 = pBox->y1;
1382: pRegion->extents.x2 = pRegion->rects->x2 = pBox->x2;
1383: pRegion->extents.y2 = pRegion->rects->y2 = pBox->y2;
1384:
1385: pRegion->numRects = 1;
1386: }
1387:
1388: #define INBOX(r, x, y) \
1389: ( ( ((r).x2 > x)) && \
1390: ( ((r).x1 <= x)) && \
1391: ( ((r).y2 > y)) && \
1392: ( ((r).y1 <= y)) )
1393:
1394: Bool
1395: miPointInRegion(pRegion, x, y, box)
1396: register RegionPtr pRegion;
1397: register int x, y;
1398: BOX *box; /* "return" value */
1399: {
1400: register BOX *pbox, *pboxEnd;
1401:
1402: if (pRegion->numRects == 0)
1403: return(FALSE);
1404: if (!INBOX(pRegion->extents, x, y))
1405: return(FALSE);
1406: for (pbox = pRegion->rects, pboxEnd = pbox + pRegion->numRects;
1407: pbox < pboxEnd;
1408: pbox++)
1409: {
1410: if (y >= pbox->y2)
1411: continue; /* not there yet */
1412: if ((y < pbox->y1) || (x < pbox->x1))
1413: break; /* missed it */
1414: if (x >= pbox->x2)
1415: continue; /* not there yet */
1416: *box = *pbox;
1417: return(TRUE);
1418: }
1419: return(FALSE);
1420: }
1421:
1422: Bool
1423: miRegionNotEmpty(pRegion)
1424: RegionPtr pRegion;
1425: {
1426: return(pRegion->numRects != 0);
1427: }
1428:
1429:
1430: void
1431: miRegionEmpty(pRegion)
1432: RegionPtr pRegion;
1433: {
1434: pRegion->numRects = 0;
1435: }
1436:
1437: BoxPtr
1438: miRegionExtents(pReg)
1439: RegionPtr pReg;
1440: {
1441: return((BoxPtr) &pReg->extents);
1442: }
1443:
1444: /*
1445: Clip a list of scanlines to a region. The caller has allocated the
1446: spce. FSorted is non-zero if the scanline origins are in ascending
1447: order.
1448: returns the number of new, clipped scanlines.
1449: */
1450:
1451: int
1452: miClipSpans(prgnDst, ppt, pwidth, nspans, pptNew, pwidthNew, fSorted)
1453: RegionPtr prgnDst;
1454: register DDXPointPtr ppt;
1455: int *pwidth;
1456: int nspans;
1457: register DDXPointPtr pptNew;
1458: int *pwidthNew;
1459: int fSorted;
1460: {
1461: register BoxPtr pbox, pboxLast, pboxTest;
1462: register DDXPointPtr pptLast;
1463: int xStart, xEnd;
1464: int yMax;
1465: int *pwidthNewThatWeWerePassed; /* the vengeance
1466: of Xerox! */
1467:
1468: pptLast = ppt + nspans;
1469:
1470: pbox = prgnDst->rects;
1471: pboxLast = pbox + prgnDst->numRects;
1472: yMax = prgnDst->extents.y2;
1473: pwidthNewThatWeWerePassed = pwidthNew;
1474:
1475: if(fSorted)
1476: {
1477: /* scan lines sorted in ascending order. Because they are sorted, we
1478: * don't have to check each scanline against each clip box. We can be
1479: * sure that this scanline only has to be clipped to boxes at or after the
1480: * beginning of this y-band
1481: */
1482: pboxTest = pbox;
1483: while(ppt < pptLast)
1484: {
1485: pbox = pboxTest;
1486: if(ppt->y >= yMax)
1487: break;
1488: while(pbox < pboxLast)
1489: {
1490: if(*pwidth == 0)
1491: {
1492: /* Null span */
1493: break;
1494: }
1495: else if(pbox->y1 > ppt->y)
1496: {
1497: /* scanline is before clip box */
1498: break;
1499: }
1500: else if(pbox->y2 <= ppt->y)
1501: {
1502: /* clip box is before scanline */
1503: pboxTest = ++pbox;
1504: continue;
1505: }
1506: else if(pbox->x1 > ppt->x + *pwidth)
1507: {
1508: /* clip box is to right of scanline */
1509: break;
1510: }
1511: else if(pbox->x2 <= ppt->x)
1512: {
1513: /* scanline is to right of clip box */
1514: pbox++;
1515: continue;
1516: }
1517:
1518: /* at least some of the scanline is in the current clip box */
1519: xStart = max(pbox->x1, ppt->x);
1520: xEnd = min(ppt->x + *pwidth, pbox->x2);
1521: pptNew->x = xStart;
1522: pptNew++->y = ppt->y;
1523: *pwidthNew++ = xEnd - xStart;
1524:
1525: if(ppt->x + *pwidth <= pbox->x2)
1526: {
1527: /* End of the line, as it were */
1528: break;
1529: }
1530: else
1531: pbox++;
1532: }
1533: /* We've tried this span against every box; it must be outside them
1534: * all. move on to the next span */
1535: ppt++;
1536: pwidth++;
1537: }
1538: }
1539: else
1540: {
1541: /* scan lines not sorted. We must clip each line against all the boxes */
1542: while(ppt < pptLast)
1543: {
1544: if(ppt->y >= 0 && ppt->y < yMax)
1545: {
1546:
1547: for(pbox = prgnDst->rects; pbox< pboxLast; pbox++)
1548: {
1549: if(pbox->y1 > ppt->y)
1550: {
1551: /* rest of clip region is above this scanline,
1552: * skip it */
1553: break;
1554: }
1555: if(pbox->y2 <= ppt->y)
1556: {
1557: /* clip box is below scanline */
1558: pbox++;
1559: break;
1560: }
1561: if(pbox->x1 <= ppt->x + *pwidth &&
1562: pbox->x2 > ppt->x)
1563: {
1564: xStart = max(pbox->x1, ppt->x);
1565: xEnd = min(pbox->x2, ppt->x + *pwidth);
1566: pptNew->x = xStart;
1567: pptNew++->y = ppt->y;
1568: *pwidthNew++ = xEnd - xStart;
1569: }
1570:
1571: }
1572: }
1573: ppt++;
1574: pwidth++;
1575: }
1576: }
1577: return (pwidthNew - pwidthNewThatWeWerePassed);
1578: }
1579:
1580: /* find the band in a region with the most rectangles */
1581: int
1582: miFindMaxBand(prgn)
1583: RegionPtr prgn;
1584: {
1585: register int nbox;
1586: register BoxPtr pbox;
1587: register int nThisBand;
1588: register int nMaxBand = 0;
1589: short yThisBand;
1590:
1591: nbox = prgn->numRects;
1592: pbox = prgn->rects;
1593:
1594: while(nbox > 0)
1595: {
1596: yThisBand = pbox->y1;
1597: nThisBand = 0;
1598: while((nbox--) && (pbox->y1 == yThisBand))
1599: {
1600: pbox++;
1601: nThisBand++;
1602: }
1603: if (nThisBand > nMaxBand)
1604: nMaxBand = nThisBand;
1605: }
1606: return (nMaxBand);
1607: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.