region.c
上传用户:zhongxx05
上传日期:2007-06-06
资源大小:33641k
文件大小:56k
- /* ***** BEGIN LICENSE BLOCK *****
- * Version: RCSL 1.0/RPSL 1.0
- *
- * Portions Copyright (c) 1995-2002 RealNetworks, Inc. All Rights Reserved.
- *
- * The contents of this file, and the files included with this file, are
- * subject to the current version of the RealNetworks Public Source License
- * Version 1.0 (the "RPSL") available at
- * http://www.helixcommunity.org/content/rpsl unless you have licensed
- * the file under the RealNetworks Community Source License Version 1.0
- * (the "RCSL") available at http://www.helixcommunity.org/content/rcsl,
- * in which case the RCSL will apply. You may also obtain the license terms
- * directly from RealNetworks. You may not use this file except in
- * compliance with the RPSL or, if you have a valid RCSL with RealNetworks
- * applicable to this file, the RCSL. Please see the applicable RPSL or
- * RCSL for the rights, obligations and limitations governing use of the
- * contents of the file.
- *
- * This file is part of the Helix DNA Technology. RealNetworks is the
- * developer and/or licensor of the Original Code and owns the copyrights
- * in the portions it created.
- *
- * This file, and the files included with this file, is distributed and made
- * available on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
- * EXPRESS OR IMPLIED, AND REALNETWORKS HEREBY DISCLAIMS ALL SUCH WARRANTIES,
- * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS
- * FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
- *
- * Technology Compatibility Kit Test Suite(s) Location:
- * http://www.helixcommunity.org/content/tck
- *
- * Contributor(s):
- *
- * ***** END LICENSE BLOCK ***** */
- /************************************************************************
- Copyright (c) 1987, 1988 X Consortium
- Permission is hereby granted, free of charge, to any person obtaining a copy
- of this software and associated documentation files (the "Software"), to deal
- in the Software without restriction, including without limitation the rights
- to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- copies of the Software, and to permit persons to whom the Software is
- furnished to do so, subject to the following conditions:
- The above copyright notice and this permission notice shall be included in
- all copies or substantial portions of the Software.
-
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
- AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
- CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
- Except as contained in this notice, the name of the X Consortium shall not be
- used in advertising or otherwise to promote the sale, use or other dealings
- in this Software without prior written authorization from the X Consortium.
- Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
- All Rights Reserved
- Permission to use, copy, modify, and distribute this software and its
- documentation for any purpose and without fee is hereby granted,
- provided that the above copyright notice appear in all copies and that
- both that copyright notice and this permission notice appear in
- supporting documentation, and that the name of Digital not be
- used in advertising or publicity pertaining to distribution of the
- software without specific, written prior permission.
- DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
- ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
- DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
- ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
- WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
- ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
- SOFTWARE.
- ************************************************************************/
- /*
- * The functions in this file implement the _Region abstraction, similar to one
- * used in the X11 sample server. A _Region is simply an area, as the name
- * implies, and is implemented as a "y-x-banded" array of rectangles. To
- * explain: Each _Region is made up of a certain number of rectangles sorted
- * by y coordinate first, and then by x coordinate.
- *
- * Furthermore, the rectangles are banded such that every rectangle with a
- * given upper-left y coordinate (y1) will have the same lower-right y
- * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
- * will span the entire vertical distance of the band. This means that some
- * areas that could be merged into a taller rectangle will be represented as
- * several shorter rectangles to account for shorter rectangles to its left
- * or right but within its "vertical scope".
- *
- * An added constraint on the rectangles is that they must cover as much
- * horizontal area as possible. E.g. no two rectangles in a band are allowed
- * to touch.
- *
- * Whenever possible, bands will be merged together to cover a greater vertical
- * distance (and thus reduce the number of rectangles). Two bands can be merged
- * only if the bottom of one touches the top of the other and they have
- * rectangles in the same places (of the same width, of course). This maintains
- * the y-x-banding that's so nice to have...
- */
- /* $XFree86: xc/lib/X11/_Region.c,v 1.1.1.2.2.2 1998/10/04 15:22:50 hohndel Exp $ */
- #include "region.h"
- #include "hlxclib/stdlib.h"
- #include "hlxclib/memory.h"
- #ifdef _DEBUG
- #include <hlxclib/stdio.h> /* for _DumpRegion() */
- #ifdef _WINDOWS
- #include "windows.h"
- #endif
- #endif
- #include <hlxclib/string.h>
- typedef void (*voidProcp)();
-
- typedef int (*overlapFunc)( register _HXRegion pReg,
- register HXBoxPtr r1,
- HXBoxPtr r1End,
- register HXBoxPtr r2,
- HXBoxPtr r2End,
- register short y1,
- register short y2
- );
- typedef int (*nonOverlapFunc)( register _HXRegion pReg,
- register HXBoxPtr r,
- HXBoxPtr rEnd,
- register short y1,
- register short y2
- );
- static void miRegionOp( _HXRegion newReg,
- _HXRegion reg1,
- _HXRegion reg2,
- overlapFunc overlap,
- nonOverlapFunc nonoverlap,
- nonOverlapFunc nonoverlap2
- );
- /* Create a new empty region */
- _HXRegion HXCreateRegion()
- {
- _HXRegion temp;
- if (! (temp = ( _HXRegion )malloc( (unsigned) sizeof( HXREGION ))))
- return (_HXRegion) NULL;
- if (! (temp->rects = ( HXBOX * )malloc( (unsigned) sizeof( HXBOX )))) {
- free((char *) temp);
- return (_HXRegion) NULL;
- }
- temp->numRects = 0;
- temp->extents.x1 = 0;
- temp->extents.y1 = 0;
- temp->extents.x2 = 0;
- temp->extents.y2 = 0;
- temp->size = 1;
- return( temp );
- }
- int HXClipRBox( _HXRegion r, HXRECTANGLE* rect)
- {
- rect->x = r->extents.x1;
- rect->y = r->extents.y1;
- rect->width = r->extents.x2 - r->extents.x1;
- rect->height = r->extents.y2 - r->extents.y1;
- return 1;
- }
- _HXRegion HXCreateRectRegion(int left, int top, int width, int height)
- {
- _HXRegion pRegion = HXCreateRegion();
-
- /*
- too scared to put this code in. Will have to check to see if everything
- works with it later.
-
- pRegion->numRects++;
- temp->rects.x1 = pRegion->extents.x1 = left;
- temp->rects.y1 = pRegion->extents.y1 = top;
- temp->rects.x2 = pRegion->extents.x2 = right;
- temp->rects.y2 = pRegion->extents.y2 = bottom;
- */
-
- HXRECTANGLE tempRECT;
- tempRECT.x = left;
- tempRECT.y = top;
- tempRECT.width = width;
- tempRECT.height = height;
- HXUnionRectWithRegion(&tempRECT, pRegion, pRegion);
- return pRegion;
- }
- //=======================================================================
- //=======================================================================
- // New methods to act on regions
- //=======================================================================
- //=======================================================================
- int HXCombineRgn( _HXRegion destRgn,
- _HXRegion srcRgn1,
- _HXRegion srcRgn2,
- HXRegionArithmetic rgnOperation)
- {
- // HX_ASSERT( destRgn && srcRgn1 && srcRgn2);
- switch (rgnOperation)
- {
- case HX_RGN_DIFF:
- HXSubtractRegion( srcRgn1, srcRgn2, destRgn );
- break;
-
- case HX_RGN_AND:
- HXIntersectRegion( srcRgn1, srcRgn2, destRgn );
- break;
-
- case HX_RGN_OR:
- HXUnionRegion(srcRgn1, srcRgn2, destRgn );
- break;
-
- case HX_RGN_XOR:
- HXXorRegion( srcRgn1, srcRgn2, destRgn );
- break;
-
- default:
- // HX_ASSERT(!"Egads! Unknown HXCombineRgn Operation!");
- break;
- }
- return 0;
- }
- //=======================================================================
- //=======================================================================
- // END: New methods to act on regions
- //=======================================================================
- //=======================================================================
- int HXUnionRectWithRegion(HXRECTANGLE* rect, _HXRegion source, _HXRegion dest)
- {
- HXREGION region;
- if (!rect->width || !rect->height)
- return 0;
- region.rects = ®ion.extents;
- region.numRects = 1;
- region.extents.x1 = rect->x;
- region.extents.y1 = rect->y;
- region.extents.x2 = rect->x + rect->width;
- region.extents.y2 = rect->y + rect->height;
- region.size = 1;
- return HXUnionRegion(®ion, source, dest);
- }
- /*-
- *-----------------------------------------------------------------------
- * miSetExtents --
- * Reset the extents of a region to what they should be. Called by
- * miSubtract and miIntersect b/c they can't figure it out along the
- * way or do so easily, as miUnion can.
- *
- * Results:
- * None.
- *
- * Side Effects:
- * The region's 'extents' structure is overwritten.
- *
- *-----------------------------------------------------------------------
- */
- static void
- miSetExtents (_HXRegion pReg)
- {
- register HXBoxPtr pHXBox,
- pHXBoxEnd,
- pExtents;
- if (pReg->numRects == 0)
- {
- pReg->extents.x1 = 0;
- pReg->extents.y1 = 0;
- pReg->extents.x2 = 0;
- pReg->extents.y2 = 0;
- return;
- }
- pExtents = &pReg->extents;
- pHXBox = pReg->rects;
- pHXBoxEnd = &pHXBox[pReg->numRects - 1];
- /*
- * Since pHXBox is the first rectangle in the region, it must have the
- * smallest y1 and since pHXBoxEnd is the last rectangle in the region,
- * it must have the largest y2, because of banding. Initialize x1 and
- * x2 from pHXBox and pHXBoxEnd, resp., as good things to initialize them
- * to...
- */
- pExtents->x1 = pHXBox->x1;
- pExtents->y1 = pHXBox->y1;
- pExtents->x2 = pHXBoxEnd->x2;
- pExtents->y2 = pHXBoxEnd->y2;
- /* assert(pExtents->y1 < pExtents->y2); */
- while (pHXBox <= pHXBoxEnd)
- {
- if (pHXBox->x1 < pExtents->x1)
- {
- pExtents->x1 = pHXBox->x1;
- }
- if (pHXBox->x2 > pExtents->x2)
- {
- pExtents->x2 = pHXBox->x2;
- }
- pHXBox++;
- }
- /* assert(pExtents->x1 < pExtents->x2); */
- }
- int HXZeroOutRegion(_HXRegion r)
- {
- if (!r)
- {
- return 0;
- }
-
- if( r->rects )
- free( (char *) r->rects );
-
- if( !(r->rects = ( HXBOX * )malloc( (unsigned) sizeof( HXBOX ))) )
- {
- return 0;
- }
-
- r->numRects = 0;
- r->extents.x1 = 0;
- r->extents.y1 = 0;
- r->extents.x2 = 0;
- r->extents.y2 = 0;
- r->size = 1;
-
- return 1;
- }
- int HXDestroyRegion(_HXRegion r)
- {
- if (!r)
- {
- return 0;
- }
- free( (char *) r->rects );
- free( (char *) r );
- return 1;
- }
- /* TranslateRegion(pRegion, x, y)
- translates in place
- added by raymond
- */
- int HXOffsetRegion(_HXRegion pRegion, int x, int y)
- {
- register int nHXBox;
- register HXBOX *pHXBox;
- pHXBox = pRegion->rects;
- nHXBox = pRegion->numRects;
- while(nHXBox--)
- {
- pHXBox->x1 += x;
- pHXBox->x2 += x;
- pHXBox->y1 += y;
- pHXBox->y2 += y;
- pHXBox++;
- }
- pRegion->extents.x1 += x;
- pRegion->extents.x2 += x;
- pRegion->extents.y1 += y;
- pRegion->extents.y2 += y;
- return 1;
- }
- /*
- Utility procedure Compress:
- Replace r by the region r', where
- p in r' iff (Quantifer m <= dx) (p + m in r), and
- Quantifier is Exists if grow is TRUE, For all if grow is FALSE, and
- (x,y) + m = (x+m,y) if xdir is TRUE; (x,y+m) if xdir is FALSE.
- Thus, if xdir is TRUE and grow is FALSE, r is replaced by the region
- of all points p such that p and the next dx points on the same
- horizontal scan line are all in r. We do this using by noting
- that p is the head of a run of length 2^i + k iff p is the head
- of a run of length 2^i and p+2^i is the head of a run of length
- k. Thus, the loop invariant: s contains the region corresponding
- to the runs of length shift. r contains the region corresponding
- to the runs of length 1 + dxo & (shift-1), where dxo is the original
- value of dx. dx = dxo & ~(shift-1). As parameters, s and t are
- scratch regions, so that we don't have to allocate them on every
- call.
- */
- #define ZOpRegion(a,b,c) if (grow) HXUnionRegion(a,b,c);
- else HXIntersectRegion(a,b,c)
- #define ZShiftRegion(a,b) if (xdir) HXOffsetRegion(a,b,0);
- else HXOffsetRegion(a,0,b)
- #define ZCopyRegion(a,b) HXUnionRegion(a,a,b)
- static void
- Compress(_HXRegion r, _HXRegion s, _HXRegion t, unsigned dx, int xdir, int grow)
- {
- register unsigned shift = 1;
- ZCopyRegion(r, s);
- while (dx) {
- if (dx & shift) {
- ZShiftRegion(r, -(int)shift);
- ZOpRegion(r, s, r);
- dx -= shift;
- if (!dx) break;
- }
- ZCopyRegion(s, t);
- ZShiftRegion(s, -(int)shift);
- ZOpRegion(s, t, s);
- shift <<= 1;
- }
- }
- #undef ZOpRegion
- #undef ZShiftRegion
- #undef ZCopyRegion
- int HXShrinkRegion(_HXRegion r, int dx, int dy)
- {
- _HXRegion s, t;
- int grow;
- if (!dx && !dy) return 0;
- if ((! (s = HXCreateRegion())) || (! (t = HXCreateRegion()))) return 0;
- if ((grow = (dx < 0)) != 0) dx = -dx;
- if (dx) Compress(r, s, t, (unsigned) 2*dx, TRUE, grow);
- if ((grow = (dy < 0)) != 0) dy = -dy;
- if (dy) Compress(r, s, t, (unsigned) 2*dy, FALSE, grow);
- HXOffsetRegion(r, dx, dy);
- HXDestroyRegion(s);
- HXDestroyRegion(t);
- return 0;
- }
- #ifdef notdef
- /***********************************************************
- * Bop down the array of rects until we have passed
- * scanline y. numRects is the size of the array.
- ***********************************************************/
- static HXBOX *IndexRects(HXBOX *rects, int numRects, int y)
- {
- while ((numRects--) && (rects->y2 <= y))
- rects++;
- return(rects);
- }
- #endif
- /*======================================================================
- * _HXRegion Intersection
- *====================================================================*/
- /*-
- *-----------------------------------------------------------------------
- * miIntersectO --
- * Handle an overlapping band for miIntersect.
- *
- * Results:
- * None.
- *
- * Side Effects:
- * Rectangles may be added to the region.
- *
- *-----------------------------------------------------------------------
- */
- /* static void*/
- static int
- miIntersectO (_HXRegion pReg,
- HXBoxPtr r1,
- HXBoxPtr r1End,
- HXBoxPtr r2,
- HXBoxPtr r2End,
- short y1,
- short y2)
- {
- register short x1;
- register short x2;
- register HXBoxPtr pNextRect;
- pNextRect = &pReg->rects[pReg->numRects];
- while ((r1 != r1End) && (r2 != r2End))
- {
- x1 = max(r1->x1,r2->x1);
- x2 = min(r1->x2,r2->x2);
- /*
- * If there's any overlap between the two rectangles, add that
- * overlap to the new region.
- * There's no need to check for subsumption because the only way
- * such a need could arise is if some region has two rectangles
- * right next to each other. Since that should never happen...
- */
- if (x1 < x2)
- {
- /* assert(y1<y2); */
- MEMCHECK(pReg, pNextRect, pReg->rects);
- pNextRect->x1 = x1;
- pNextRect->y1 = y1;
- pNextRect->x2 = x2;
- pNextRect->y2 = y2;
- pReg->numRects += 1;
- pNextRect++;
- /* assert(pReg->numRects <= pReg->size); */
- }
- /*
- * Need to advance the pointers. Shift the one that extends
- * to the right the least, since the other still has a chance to
- * overlap with that region's next rectangle, if you see what I mean.
- */
- if (r1->x2 < r2->x2)
- {
- r1++;
- }
- else if (r2->x2 < r1->x2)
- {
- r2++;
- }
- else
- {
- r1++;
- r2++;
- }
- }
- return 0;
- }
- int HXIntersectRegion(_HXRegion reg1, _HXRegion reg2, _HXRegion newReg)
- {
- /* check for trivial reject */
- if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
- (!EXTENTCHECK(®1->extents, ®2->extents)))
- newReg->numRects = 0;
- else
- miRegionOp(newReg,
- reg1,
- reg2,
- miIntersectO,
- NULL,
- NULL);
-
- /*
- * Can't alter newReg's extents before we call miRegionOp because
- * it might be one of the source regions and miRegionOp depends
- * on the extents of those regions being the same. Besides, this
- * way there's no checking against rectangles that will be nuked
- * due to coalescing, so we have to examine fewer rectangles.
- */
- miSetExtents(newReg);
- return 1;
- }
- static void
- miRegionCopy(_HXRegion dstrgn, _HXRegion rgn)
- {
- if (dstrgn != rgn) /* don't want to copy to itself */
- {
- if (dstrgn->size < rgn->numRects)
- {
- if (dstrgn->rects)
- {
- HXBOX *prevRects = dstrgn->rects;
-
- if (! (dstrgn->rects = (HXBOX *)
- realloc((char *) dstrgn->rects,
- (unsigned) rgn->numRects * (sizeof(HXBOX))))) {
- free(prevRects);
- return;
- }
- }
- dstrgn->size = rgn->numRects;
- }
- dstrgn->numRects = rgn->numRects;
- dstrgn->extents.x1 = rgn->extents.x1;
- dstrgn->extents.y1 = rgn->extents.y1;
- dstrgn->extents.x2 = rgn->extents.x2;
- dstrgn->extents.y2 = rgn->extents.y2;
- memcpy((char *) dstrgn->rects, (char *) rgn->rects, /* Flawfinder: ignore */
- (int) (rgn->numRects * sizeof(HXBOX)));
- }
- }
- #ifdef notdef
- /*
- * combinRegs(newReg, reg1, reg2)
- * if one region is above or below the other.
- */
- static void CombineRegs(_HXRegion newReg, _HXRegion reg1, _HXRegion reg2)
- {
- register _HXRegion tempReg;
- register HXBOX *rects;
- register HXBOX *rects1;
- register HXBOX *rects2;
- register int total;
- rects1 = reg1->rects;
- rects2 = reg2->rects;
- total = reg1->numRects + reg2->numRects;
- if (! (tempReg = HXCreateRegion()))
- return;
- tempReg->size = total;
- /* region 1 is below region 2 */
- if (reg1->extents.y1 > reg2->extents.y1)
- {
- miRegionCopy(tempReg, reg2);
- rects = &tempReg->rects[tempReg->numRects];
- total -= tempReg->numRects;
- while (total--)
- *rects++ = *rects1++;
- }
- else
- {
- miRegionCopy(tempReg, reg1);
- rects = &tempReg->rects[tempReg->numRects];
- total -= tempReg->numRects;
- while (total--)
- *rects++ = *rects2++;
- }
- tempReg->extents = reg1->extents;
- tempReg->numRects = reg1->numRects + reg2->numRects;
- EXTENTS(®2->extents, tempReg);
- miRegionCopy(newReg, tempReg);
- free((char *)tempReg);
- }
- /*
- * QuickCheck checks to see if it does not have to go through all the
- * the ugly code for the region call. It returns 1 if it did all
- * the work for Union, otherwise 0 - still work to be done.
- */
- static int
- QuickCheck(_HXRegion newReg, _HXRegion reg1, _HXRegion reg2)
- {
- /* if unioning with itself or no rects to union with */
- if ( (reg1 == reg2) || (!(reg1->numRects)) )
- {
- miRegionCopy(newReg, reg2);
- return TRUE;
- }
- /* if nothing to union */
- if (!(reg2->numRects))
- {
- miRegionCopy(newReg, reg1);
- return TRUE;
- }
- /* could put an extent check to see if add above or below */
- if ((reg1->extents.y1 >= reg2->extents.y2) ||
- (reg2->extents.y1 >= reg1->extents.y2) )
- {
- CombineRegs(newReg, reg1, reg2);
- return TRUE;
- }
- return FALSE;
- }
- /* TopRects(rects, reg1, reg2)
- * N.B. We now assume that reg1 and reg2 intersect. Therefore we are
- * NOT checking in the two while loops for stepping off the end of the
- * region.
- */
- static int
- TopRects(_HXRegion newReg, HXBOX *rects, _HXRegion reg1, _HXRegion reg2, HXBOX *FirstRect)
- {
- register HXBOX *tempRects;
- /* need to add some rects from region 1 */
- if (reg1->extents.y1 < reg2->extents.y1)
- {
- tempRects = reg1->rects;
- while(tempRects->y1 < reg2->extents.y1)
- {
- MEMCHECK(newReg, rects, FirstRect);
- ADDRECTNOX(newReg,rects, tempRects->x1, tempRects->y1,
- tempRects->x2, MIN(tempRects->y2, reg2->extents.y1));
- tempRects++;
- }
- }
- /* need to add some rects from region 2 */
- if (reg2->extents.y1 < reg1->extents.y1)
- {
- tempRects = reg2->rects;
- while (tempRects->y1 < reg1->extents.y1)
- {
- MEMCHECK(newReg, rects, FirstRect);
- ADDRECTNOX(newReg, rects, tempRects->x1,tempRects->y1,
- tempRects->x2, MIN(tempRects->y2, reg1->extents.y1));
- tempRects++;
- }
- }
- return 1;
- }
- #endif
- /*======================================================================
- * Generic _HXRegion Operator
- *====================================================================*/
- /*-
- *-----------------------------------------------------------------------
- * miCoalesce --
- * Attempt to merge the HXBoxes in the current band with those in the
- * previous one. Used only by miRegionOp.
- *
- * Results:
- * The new index for the previous band.
- *
- * Side Effects:
- * If coalescing takes place:
- * - rectangles in the previous band will have their y2 fields
- * altered.
- * - pReg->numRects will be decreased.
- *
- *-----------------------------------------------------------------------
- */
- /* static int*/
- static int
- miCoalesce (_HXRegion pReg, int prevStart, int curStart)
- {
- register HXBoxPtr pPrevHXBox; /* Current HXBox in previous band */
- register HXBoxPtr pCurHXBox; /* Current HXBox in current band */
- register HXBoxPtr pRegEnd; /* End of region */
- int curNumRects; /* Number of rectangles in current
- * band */
- int prevNumRects; /* Number of rectangles in previous
- * band */
- int bandY1; /* Y1 coordinate for current band */
- pRegEnd = &pReg->rects[pReg->numRects];
- pPrevHXBox = &pReg->rects[prevStart];
- prevNumRects = curStart - prevStart;
- /*
- * Figure out how many rectangles are in the current band. Have to do
- * this because multiple bands could have been added in miRegionOp
- * at the end when one region has been exhausted.
- */
- pCurHXBox = &pReg->rects[curStart];
- bandY1 = pCurHXBox->y1;
- for (curNumRects = 0;
- (pCurHXBox != pRegEnd) && (pCurHXBox->y1 == bandY1);
- curNumRects++)
- {
- pCurHXBox++;
- }
-
- if (pCurHXBox != pRegEnd)
- {
- /*
- * If more than one band was added, we have to find the start
- * of the last band added so the next coalescing job can start
- * at the right place... (given when multiple bands are added,
- * this may be pointless -- see above).
- */
- pRegEnd--;
- while (pRegEnd[-1].y1 == pRegEnd->y1)
- {
- pRegEnd--;
- }
- curStart = pRegEnd - pReg->rects;
- pRegEnd = pReg->rects + pReg->numRects;
- }
-
- if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
- pCurHXBox -= curNumRects;
- /*
- * The bands may only be coalesced if the bottom of the previous
- * matches the top scanline of the current.
- */
- if (pPrevHXBox->y2 == pCurHXBox->y1)
- {
- /*
- * Make sure the bands have HXBoxes in the same places. This
- * assumes that HXBoxes have been added in such a way that they
- * cover the most area possible. I.e. two HXBoxes in a band must
- * have some horizontal space between them.
- */
- do
- {
- if ((pPrevHXBox->x1 != pCurHXBox->x1) ||
- (pPrevHXBox->x2 != pCurHXBox->x2))
- {
- /*
- * The bands don't line up so they can't be coalesced.
- */
- return (curStart);
- }
- pPrevHXBox++;
- pCurHXBox++;
- prevNumRects -= 1;
- } while (prevNumRects != 0);
- pReg->numRects -= curNumRects;
- pCurHXBox -= curNumRects;
- pPrevHXBox -= curNumRects;
- /*
- * The bands may be merged, so set the bottom y of each HXBox
- * in the previous band to that of the corresponding HXBox in
- * the current band.
- */
- do
- {
- pPrevHXBox->y2 = pCurHXBox->y2;
- pPrevHXBox++;
- pCurHXBox++;
- curNumRects -= 1;
- } while (curNumRects != 0);
- /*
- * If only one band was added to the region, we have to backup
- * curStart to the start of the previous band.
- *
- * If more than one band was added to the region, copy the
- * other bands down. The assumption here is that the other bands
- * came from the same region as the current one and no further
- * coalescing can be done on them since it's all been done
- * already... curStart is already in the right place.
- */
- if (pCurHXBox == pRegEnd)
- {
- curStart = prevStart;
- }
- else
- {
- do
- {
- *pPrevHXBox++ = *pCurHXBox++;
- } while (pCurHXBox != pRegEnd);
- }
-
- }
- }
- return (curStart);
- }
- /*-
- *-----------------------------------------------------------------------
- * miRegionOp --
- * Apply an operation to two regions. Called by miUnion, miInverse,
- * miSubtract, miIntersect...
- *
- * Results:
- * None.
- *
- * Side Effects:
- * The new region is overwritten.
- *
- * Notes:
- * The idea behind this function is to view the two regions as sets.
- * Together they cover a rectangle of area that this function divides
- * into horizontal bands where points are covered only by one region
- * or by both. For the first case, the nonOverlapFunc is called with
- * each the band and the band's upper and lower extents. For the
- * second, the overlapFunc is called to process the entire band. It
- * is responsible for clipping the rectangles in the band, though
- * this function provides the boundaries.
- * At the end of each band, the new region is coalesced, if possible,
- * to reduce the number of rectangles in the region.
- *
- *-----------------------------------------------------------------------
- */
- /* static void*/
- static void miRegionOp(
- register _HXRegion newReg, /* Place to store result */
- _HXRegion reg1, /* First region in operation */
- _HXRegion reg2, /* 2d region in operation */
- overlapFunc fpOverlapFunc, /* Function to call for over-
- * lapping bands */
- nonOverlapFunc nonOverlap1Func, /* Function to call for non-
- * overlapping bands in region
- * 1 */
- nonOverlapFunc nonOverlap2Func /* Function to call for non-
- * overlapping bands in region
- * 2 */
- )
- {
- register HXBoxPtr r1; /* Pointer into first region */
- register HXBoxPtr r2; /* Pointer into 2d region */
- HXBoxPtr r1End; /* End of 1st region */
- HXBoxPtr r2End; /* End of 2d region */
- register short ybot; /* Bottom of intersection */
- register short ytop; /* Top of intersection */
- HXBoxPtr oldRects; /* Old rects for newReg */
- int prevBand; /* Index of start of
- * previous band in newReg */
- int curBand; /* Index of start of current
- * band in newReg */
- register HXBoxPtr r1BandEnd; /* End of current band in r1 */
- register HXBoxPtr r2BandEnd; /* End of current band in r2 */
- short top; /* Top of non-overlapping
- * band */
- short bot; /* Bottom of non-overlapping
- * band */
-
- /*
- * Initialization:
- * set r1, r2, r1End and r2End appropriately, preserve the important
- * parts of the destination region until the end in case it's one of
- * the two source regions, then mark the "new" region empty, allocating
- * another array of rectangles for it to use.
- */
- r1 = reg1->rects;
- r2 = reg2->rects;
- r1End = r1 + reg1->numRects;
- r2End = r2 + reg2->numRects;
-
- oldRects = newReg->rects;
-
- EMPTY_REGION(newReg);
- /*
- * Allocate a reasonable number of rectangles for the new region. The idea
- * is to allocate enough so the individual functions don't need to
- * reallocate and copy the array, which is time consuming, yet we don't
- * have to worry about using too much memory. I hope to be able to
- * nuke the Xrealloc() at the end of this function eventually.
- */
- newReg->size = max(reg1->numRects,reg2->numRects) * 2;
- if (! (newReg->rects = (HXBoxPtr)
- malloc ((unsigned) (sizeof(HXBOX) * newReg->size)))) {
- newReg->size = 0;
- return;
- }
-
- /*
- * Initialize ybot and ytop.
- * In the upcoming loop, ybot and ytop serve different functions depending
- * on whether the band being handled is an overlapping or non-overlapping
- * band.
- * In the case of a non-overlapping band (only one of the regions
- * has points in the band), ybot is the bottom of the most recent
- * intersection and thus clips the top of the rectangles in that band.
- * ytop is the top of the next intersection between the two regions and
- * serves to clip the bottom of the rectangles in the current band.
- * For an overlapping band (where the two regions intersect), ytop clips
- * the top of the rectangles of both regions and ybot clips the bottoms.
- */
- if (reg1->extents.y1 < reg2->extents.y1)
- ybot = reg1->extents.y1;
- else
- ybot = reg2->extents.y1;
-
- /*
- * prevBand serves to mark the start of the previous band so rectangles
- * can be coalesced into larger rectangles. qv. miCoalesce, above.
- * In the beginning, there is no previous band, so prevBand == curBand
- * (curBand is set later on, of course, but the first band will always
- * start at index 0). prevBand and curBand must be indices because of
- * the possible expansion, and resultant moving, of the new region's
- * array of rectangles.
- */
- prevBand = 0;
-
- do
- {
- curBand = newReg->numRects;
- /*
- * This algorithm proceeds one source-band (as opposed to a
- * destination band, which is determined by where the two regions
- * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
- * rectangle after the last one in the current band for their
- * respective regions.
- */
- r1BandEnd = r1;
- while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
- {
- r1BandEnd++;
- }
-
- r2BandEnd = r2;
- while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
- {
- r2BandEnd++;
- }
-
- /*
- * First handle the band that doesn't intersect, if any.
- *
- * Note that attention is restricted to one band in the
- * non-intersecting region at once, so if a region has n
- * bands between the current position and the next place it overlaps
- * the other, this entire loop will be passed through n times.
- */
- if (r1->y1 < r2->y1)
- {
- top = max(r1->y1,ybot);
- bot = min(r1->y2,r2->y1);
- if ((top != bot) && (nonOverlap1Func != NULL))
- {
- (*nonOverlap1Func)(newReg, r1, r1BandEnd, top, bot);
- }
- ytop = r2->y1;
- }
- else if (r2->y1 < r1->y1)
- {
- top = max(r2->y1,ybot);
- bot = min(r2->y2,r1->y1);
- if ((top != bot) && (nonOverlap2Func != NULL ))
- {
- (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
- }
- ytop = r1->y1;
- }
- else
- {
- ytop = r1->y1;
- }
- /*
- * If any rectangles got added to the region, try and coalesce them
- * with rectangles from the previous band. Note we could just do
- * this test in miCoalesce, but some machines incur a not
- * inconsiderable cost for function calls, so...
- */
- if (newReg->numRects != curBand)
- {
- prevBand = miCoalesce (newReg, prevBand, curBand);
- }
- /*
- * Now see if we've hit an intersecting band. The two bands only
- * intersect if ybot > ytop
- */
- ybot = min(r1->y2, r2->y2);
- curBand = newReg->numRects;
- if (ybot > ytop)
- {
- (* fpOverlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
- }
-
- if (newReg->numRects != curBand)
- {
- prevBand = miCoalesce (newReg, prevBand, curBand);
- }
- /*
- * If we've finished with a band (y2 == ybot) we skip forward
- * in the region to the next band.
- */
- if (r1->y2 == ybot)
- {
- r1 = r1BandEnd;
- }
- if (r2->y2 == ybot)
- {
- r2 = r2BandEnd;
- }
- } while ((r1 != r1End) && (r2 != r2End));
- /*
- * Deal with whichever region still has rectangles left.
- */
- curBand = newReg->numRects;
- if (r1 != r1End)
- {
- if (nonOverlap1Func != NULL)
- {
- do
- {
- r1BandEnd = r1;
- while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
- {
- r1BandEnd++;
- }
- (* nonOverlap1Func) (newReg, r1, r1BandEnd,
- max(r1->y1,ybot), r1->y2);
- r1 = r1BandEnd;
- } while (r1 != r1End);
- }
- }
- else if ((r2 != r2End) && (nonOverlap2Func != NULL))
- {
- do
- {
- r2BandEnd = r2;
- while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
- {
- r2BandEnd++;
- }
- (* nonOverlap2Func) (newReg, r2, r2BandEnd,
- max(r2->y1,ybot), r2->y2);
- r2 = r2BandEnd;
- } while (r2 != r2End);
- }
- if (newReg->numRects != curBand)
- {
- (void) miCoalesce (newReg, prevBand, curBand);
- }
- /*
- * A bit of cleanup. To keep regions from growing without bound,
- * we shrink the array of rectangles to match the new number of
- * rectangles in the region. This never goes to 0, however...
- *
- * Only do this stuff if the number of rectangles allocated is more than
- * twice the number of rectangles in the region (a simple optimization...).
- */
- if (newReg->numRects < (newReg->size >> 1))
- {
- if (REGION_NOT_EMPTY(newReg))
- {
- HXBoxPtr prev_rects = newReg->rects;
- newReg->size = newReg->numRects;
- newReg->rects = (HXBoxPtr) realloc ((char *) newReg->rects,
- (unsigned) (sizeof(HXBOX) * newReg->size));
- if (! newReg->rects)
- newReg->rects = prev_rects;
- }
- else
- {
- /*
- * No point in doing the extra work involved in an Xrealloc if
- * the region is empty
- */
- newReg->size = 1;
- free((char *) newReg->rects);
- newReg->rects = (HXBoxPtr) malloc(sizeof(HXBOX));
- }
- }
- free ((char *) oldRects);
- return;
- }
- /*======================================================================
- * _HXRegion Union
- *====================================================================*/
- /*-
- *-----------------------------------------------------------------------
- * miUnionNonO --
- * Handle a non-overlapping band for the union operation. Just
- * Adds the rectangles into the region. Doesn't have to check for
- * subsumption or anything.
- *
- * Results:
- * None.
- *
- * Side Effects:
- * pReg->numRects is incremented and the final rectangles overwritten
- * with the rectangles we're passed.
- *
- *-----------------------------------------------------------------------
- */
- /* static void*/
- static int
- miUnionNonO( register _HXRegion pReg,
- register HXBoxPtr r,
- HXBoxPtr rEnd,
- register short y1,
- register short y2
- )
- {
- register HXBoxPtr pNextRect;
- pNextRect = &pReg->rects[pReg->numRects];
- /* assert(y1 < y2); */
- while (r != rEnd)
- {
- /* assert(r->x1 < r->x2); */
- MEMCHECK(pReg, pNextRect, pReg->rects);
- pNextRect->x1 = r->x1;
- pNextRect->y1 = y1;
- pNextRect->x2 = r->x2;
- pNextRect->y2 = y2;
- pReg->numRects += 1;
- pNextRect++;
- /* assert(pReg->numRects<=pReg->size); */
- r++;
- }
- return 0;
- }
- /*-
- *-----------------------------------------------------------------------
- * miUnionO --
- * Handle an overlapping band for the union operation. Picks the
- * left-most rectangle each time and merges it into the region.
- *
- * Results:
- * None.
- *
- * Side Effects:
- * Rectangles are overwritten in pReg->rects and pReg->numRects will
- * be changed.
- *
- *-----------------------------------------------------------------------
- */
- /* static void*/
- static int miUnionO( register _HXRegion pReg,
- register HXBoxPtr r1,
- HXBoxPtr r1End,
- register HXBoxPtr r2,
- HXBoxPtr r2End,
- register short y1,
- register short y2
- )
- {
- register HXBoxPtr pNextRect;
-
- pNextRect = &pReg->rects[pReg->numRects];
- #define MERGERECT(r)
- if ((pReg->numRects != 0) &&
- (pNextRect[-1].y1 == y1) &&
- (pNextRect[-1].y2 == y2) &&
- (pNextRect[-1].x2 >= r->x1))
- {
- if (pNextRect[-1].x2 < r->x2)
- {
- pNextRect[-1].x2 = r->x2;
- /* assert(pNextRect[-1].x1<pNextRect[-1].x2); */
- }
- }
- else
- {
- MEMCHECK(pReg, pNextRect, pReg->rects);
- pNextRect->y1 = y1;
- pNextRect->y2 = y2;
- pNextRect->x1 = r->x1;
- pNextRect->x2 = r->x2;
- pReg->numRects += 1;
- pNextRect += 1;
- }
- /* assert(pReg->numRects<=pReg->size); */
- r++;
-
- /* assert (y1<y2); */
- while ((r1 != r1End) && (r2 != r2End))
- {
- if (r1->x1 < r2->x1)
- {
- MERGERECT(r1);
- }
- else
- {
- MERGERECT(r2);
- }
- }
-
- if (r1 != r1End)
- {
- do
- {
- MERGERECT(r1);
- } while (r1 != r1End);
- }
- else while (r2 != r2End)
- {
- MERGERECT(r2);
- }
- return 0; /* lint */
- }
- int HXUnionRegion(_HXRegion reg1, _HXRegion reg2, _HXRegion newReg)
- {
- /* checks all the simple cases */
- /*
- * _HXRegion 1 and 2 are the same or region 1 is empty
- */
- if ( (reg1 == reg2) || (!(reg1->numRects)) )
- {
- if (newReg != reg2)
- miRegionCopy(newReg, reg2);
- return 1;
- }
- /*
- * if nothing to union (region 2 empty)
- */
- if (!(reg2->numRects))
- {
- if (newReg != reg1)
- miRegionCopy(newReg, reg1);
- return 1;
- }
- /*
- * _HXRegion 1 completely subsumes region 2
- */
- if ((reg1->numRects == 1) &&
- (reg1->extents.x1 <= reg2->extents.x1) &&
- (reg1->extents.y1 <= reg2->extents.y1) &&
- (reg1->extents.x2 >= reg2->extents.x2) &&
- (reg1->extents.y2 >= reg2->extents.y2))
- {
- if (newReg != reg1)
- miRegionCopy(newReg, reg1);
- return 1;
- }
- /*
- * _HXRegion 2 completely subsumes region 1
- */
- if ((reg2->numRects == 1) &&
- (reg2->extents.x1 <= reg1->extents.x1) &&
- (reg2->extents.y1 <= reg1->extents.y1) &&
- (reg2->extents.x2 >= reg1->extents.x2) &&
- (reg2->extents.y2 >= reg1->extents.y2))
- {
- if (newReg != reg2)
- miRegionCopy(newReg, reg2);
- return 1;
- }
- miRegionOp( newReg,
- reg1,
- reg2,
- miUnionO,
- miUnionNonO,
- miUnionNonO);
- newReg->extents.x1 = min(reg1->extents.x1, reg2->extents.x1);
- newReg->extents.y1 = min(reg1->extents.y1, reg2->extents.y1);
- newReg->extents.x2 = max(reg1->extents.x2, reg2->extents.x2);
- newReg->extents.y2 = max(reg1->extents.y2, reg2->extents.y2);
- return 1;
- }
- /*======================================================================
- * _HXRegion Subtraction
- *====================================================================*/
- /*-
- *-----------------------------------------------------------------------
- * miSubtractNonO --
- * Deal with non-overlapping band for subtraction. Any parts from
- * region 2 we discard. Anything from region 1 we add to the region.
- *
- * Results:
- * None.
- *
- * Side Effects:
- * pReg may be affected.
- *
- *-----------------------------------------------------------------------
- */
- /* static void*/
- static int miSubtractNonO1( register _HXRegion pReg,
- register HXBoxPtr r,
- HXBoxPtr rEnd,
- register short y1,
- register short y2
- )
- {
- register HXBoxPtr pNextRect;
-
- pNextRect = &pReg->rects[pReg->numRects];
-
- /* assert(y1<y2); */
- while (r != rEnd)
- {
- /* assert(r->x1<r->x2); */
- MEMCHECK(pReg, pNextRect, pReg->rects);
- pNextRect->x1 = r->x1;
- pNextRect->y1 = y1;
- pNextRect->x2 = r->x2;
- pNextRect->y2 = y2;
- pReg->numRects += 1;
- pNextRect++;
- /* assert(pReg->numRects <= pReg->size); */
- r++;
- }
- return 0; /* lint */
- }
- /*-
- *-----------------------------------------------------------------------
- * miSubtractO --
- * Overlapping band subtraction. x1 is the left-most point not yet
- * checked.
- *
- * Results:
- * None.
- *
- * Side Effects:
- * pReg may have rectangles added to it.
- *
- *-----------------------------------------------------------------------
- */
- /* static void*/
- static int miSubtractO( register _HXRegion pReg,
- register HXBoxPtr r1,
- HXBoxPtr r1End,
- register HXBoxPtr r2,
- HXBoxPtr r2End,
- register short y1,
- register short y2
- )
- {
- register HXBoxPtr pNextRect;
- register int x1;
-
- x1 = r1->x1;
-
- /* assert(y1<y2); */
- pNextRect = &pReg->rects[pReg->numRects];
- while ((r1 != r1End) && (r2 != r2End))
- {
- if (r2->x2 <= x1)
- {
- /*
- * Subtrahend missed the boat: go to next subtrahend.
- */
- r2++;
- }
- else if (r2->x1 <= x1)
- {
- /*
- * Subtrahend preceeds minuend: nuke left edge of minuend.
- */
- x1 = r2->x2;
- if (x1 >= r1->x2)
- {
- /*
- * Minuend completely covered: advance to next minuend and
- * reset left fence to edge of new minuend.
- */
- r1++;
- if (r1 != r1End)
- x1 = r1->x1;
- }
- else
- {
- /*
- * Subtrahend now used up since it doesn't extend beyond
- * minuend
- */
- r2++;
- }
- }
- else if (r2->x1 < r1->x2)
- {
- /*
- * Left part of subtrahend covers part of minuend: add uncovered
- * part of minuend to region and skip to next subtrahend.
- */
- /* assert(x1<r2->x1); */
- MEMCHECK(pReg, pNextRect, pReg->rects);
- pNextRect->x1 = x1;
- pNextRect->y1 = y1;
- pNextRect->x2 = r2->x1;
- pNextRect->y2 = y2;
- pReg->numRects += 1;
- pNextRect++;
- /* assert(pReg->numRects<=pReg->size); */
- x1 = r2->x2;
- if (x1 >= r1->x2)
- {
- /*
- * Minuend used up: advance to new...
- */
- r1++;
- if (r1 != r1End)
- x1 = r1->x1;
- }
- else
- {
- /*
- * Subtrahend used up
- */
- r2++;
- }
- }
- else
- {
- /*
- * Minuend used up: add any remaining piece before advancing.
- */
- if (r1->x2 > x1)
- {
- MEMCHECK(pReg, pNextRect, pReg->rects);
- pNextRect->x1 = x1;
- pNextRect->y1 = y1;
- pNextRect->x2 = r1->x2;
- pNextRect->y2 = y2;
- pReg->numRects += 1;
- pNextRect++;
- /* assert(pReg->numRects<=pReg->size); */
- }
- r1++;
- if (!(((r1 != r1End) && (r2 != r2End))))
- {
- break;
- }
- x1 = r1->x1;
- }
- }
- /*
- * Add remaining minuend rectangles to region.
- */
- while (r1 != r1End)
- {
- /* assert(x1<r1->x2); */
- MEMCHECK(pReg, pNextRect, pReg->rects);
- pNextRect->x1 = x1;
- pNextRect->y1 = y1;
- pNextRect->x2 = r1->x2;
- pNextRect->y2 = y2;
- pReg->numRects += 1;
- pNextRect++;
- /* assert(pReg->numRects<=pReg->size); */
- r1++;
- if (r1 != r1End)
- {
- x1 = r1->x1;
- }
- }
- return 0; /* lint */
- }
-
- /*-
- *-----------------------------------------------------------------------
- * miSubtract --
- * Subtract regS from regM and leave the result in regD.
- * S stands for subtrahend, M for minuend and D for difference.
- *
- * Results:
- * TRUE.
- *
- * Side Effects:
- * regD is overwritten.
- *
- *-----------------------------------------------------------------------
- */
- int HXSubtractRegion(_HXRegion regM, _HXRegion regS, _HXRegion regD)
- {
- /* check for trivial reject */
- if ( (!(regM->numRects)) || (!(regS->numRects)) ||
- (!EXTENTCHECK(®M->extents, ®S->extents)) )
- {
- miRegionCopy(regD, regM);
- return 1;
- }
-
- miRegionOp (regD, regM, regS, miSubtractO, miSubtractNonO1, NULL);
- /*
- * Can't alter newReg's extents before we call miRegionOp because
- * it might be one of the source regions and miRegionOp depends
- * on the extents of those regions being the unaltered. Besides, this
- * way there's no checking against rectangles that will be nuked
- * due to coalescing, so we have to examine fewer rectangles.
- */
- miSetExtents (regD);
- return 1;
- }
- int HXXorRegion( _HXRegion sra, _HXRegion srb, _HXRegion dr )
- {
- _HXRegion tra, trb;
- if ((! (tra = HXCreateRegion())) || (! (trb = HXCreateRegion())))
- return 0;
- (void) HXSubtractRegion(sra,srb,tra);
- (void) HXSubtractRegion(srb,sra,trb);
- (void) HXUnionRegion(tra,trb,dr);
- HXDestroyRegion(tra);
- HXDestroyRegion(trb);
- return 0;
- }
- /*
- * Check to see if the region is empty. Assumes a region is passed
- * as a parameter
- */
- int HXEmptyRegion( _HXRegion r)
- {
-
- if( !r || r->numRects == 0 ) return TRUE;
- else return FALSE;
- }
- /*
- * Check to see if two regions are equal
- */
- int
- HXEqualRegion( _HXRegion r1, _HXRegion r2)
- {
- int i;
- if( r1->numRects != r2->numRects ) return FALSE;
- else if( r1->numRects == 0 ) return TRUE;
- else if ( r1->extents.x1 != r2->extents.x1 ) return FALSE;
- else if ( r1->extents.x2 != r2->extents.x2 ) return FALSE;
- else if ( r1->extents.y1 != r2->extents.y1 ) return FALSE;
- else if ( r1->extents.y2 != r2->extents.y2 ) return FALSE;
- else for( i=0; i < r1->numRects; i++ ) {
- if ( r1->rects[i].x1 != r2->rects[i].x1 ) return FALSE;
- else if ( r1->rects[i].x2 != r2->rects[i].x2 ) return FALSE;
- else if ( r1->rects[i].y1 != r2->rects[i].y1 ) return FALSE;
- else if ( r1->rects[i].y2 != r2->rects[i].y2 ) return FALSE;
- }
- return TRUE;
- }
- int HXPointInRegion( _HXRegion pRegion, int x, int y )
- {
- int i;
- if (pRegion->numRects == 0)
- return FALSE;
- if (!INHXBOX(pRegion->extents, x, y))
- return FALSE;
- for (i=0; i<pRegion->numRects; i++)
- {
- if (INHXBOX (pRegion->rects[i], x, y))
- return TRUE;
- }
- return FALSE;
- }
- int HXDetermineBestRect( _HXRegion srcReg, _HXRegion newReg )
- {
- return 0;
- }
- int HXRectInRegion(_HXRegion region, int rx, int ry, unsigned int rwidth, unsigned int rheight)
- {
- register HXBoxPtr pHXBox;
- register HXBoxPtr pHXBoxEnd;
- HXBOX rect;
- register HXBoxPtr prect = ▭
- int partIn, partOut;
- prect->x1 = rx;
- prect->y1 = ry;
- prect->x2 = rwidth + rx;
- prect->y2 = rheight + ry;
-
- /* this is (just) a useful optimization */
- if ((region->numRects == 0) || !EXTENTCHECK(®ion->extents, prect))
- return(HXRectangleOut);
- partOut = FALSE;
- partIn = FALSE;
- /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
- for (pHXBox = region->rects, pHXBoxEnd = pHXBox + region->numRects;
- pHXBox < pHXBoxEnd;
- pHXBox++)
- {
- if (pHXBox->y2 <= ry)
- continue; /* getting up to speed or skipping remainder of band */
- if (pHXBox->y1 > ry)
- {
- partOut = TRUE; /* missed part of rectangle above */
- if (partIn || (pHXBox->y1 >= prect->y2))
- break;
- ry = pHXBox->y1; /* x guaranteed to be == prect->x1 */
- }
- if (pHXBox->x2 <= rx)
- continue; /* not far enough over yet */
- if (pHXBox->x1 > rx)
- {
- partOut = TRUE; /* missed part of rectangle to left */
- if (partIn)
- break;
- }
- if (pHXBox->x1 < prect->x2)
- {
- partIn = TRUE; /* definitely overlap */
- if (partOut)
- break;
- }
- if (pHXBox->x2 >= prect->x2)
- {
- ry = pHXBox->y2; /* finished with this band */
- if (ry >= prect->y2)
- break;
- rx = prect->x1; /* reset x out to left again */
- } else
- {
- /*
- * Because HXBoxes in a band are maximal width, if the first HXBox
- * to overlap the rectangle doesn't completely cover it in that
- * band, the rectangle must be partially out, since some of it
- * will be uncovered in that band. partIn will have been set true
- * by now...
- */
- break;
- }
- }
- return(partIn ? ((ry < prect->y2) ? HXRectanglePart : HXRectangleIn) :
- HXRectangleOut);
- }
- #ifdef _DEBUG
- void _DumpRegion(_HXRegion pRegion )
- {
- int i=0;
- char szBuff[256]; /* Flawfinder: ignore */
- sprintf( szBuff, "Region(%p): %d rectsn", pRegion, pRegion->numRects ); /* Flawfinder: ignore */
- _DumpString(szBuff);
- for(i=0 ; i<pRegion->numRects ; i++)
- {
- sprintf( szBuff, "Rect# %d (%d,%d)-(%d,%d)n", /* Flawfinder: ignore */
- i,
- pRegion->rects[i].x1, pRegion->rects[i].y1,
- pRegion->rects[i].x2, pRegion->rects[i].y2
- );
- _DumpString(szBuff);
- }
- }
- void _DumpString(const char* pszString )
- {
- #if defined(_WIN32)
- OutputDebugString(pszString);
- #elif defined(_UNIX)
- FILE* pFP=fopen("/tmp/pnvideo.txt", "a+"); /* Flawfinder: ignore */
- if( pFP )
- {
- fprintf( pFP, "%s", pszString);
- fclose( pFP );
- }
- #else
- fprintf( stderr, "%s", pszString );
- #endif
- }
- #endif