region.c

teamviewer source code vc++

	    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;	/* lint */
}

int
XIntersectRegion(reg1, reg2, newReg)
    Region 	  	reg1;
    Region	  	reg2;          /* source regions     */
    register Region 	newReg;               /* destination Region */
{
   /* check for trivial reject */
    if ( (!(reg1->numRects)) || (!(reg2->numRects))  ||
	(!EXTENTCHECK(&reg1->extents, &reg2->extents)))
        newReg->numRects = 0;
    else
	miRegionOp (newReg, reg1, reg2, 
    		(voidProcp) miIntersectO, (voidProcp) NULL, (voidProcp) 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(dstrgn, rgn)
    register Region dstrgn;
    register Region rgn;

{
    if (dstrgn != rgn) /*  don't want to copy to itself */
    {  
        if (dstrgn->size < rgn->numRects)
        {
            if (dstrgn->rects)
            {
		BOX *prevRects = dstrgn->rects;
		
                if (! (dstrgn->rects = (BOX *)
		       Xrealloc((char *) dstrgn->rects,
				(unsigned) rgn->numRects * (sizeof(BOX))))) {
		    Xfree(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,
	       (int) (rgn->numRects * sizeof(BOX)));
    }
}

#ifdef notdef

/*
 *  combinRegs(newReg, reg1, reg2)
 *    if one region is above or below the other.
*/ 

static void
combineRegs(newReg, reg1, reg2)
    register Region newReg;
    Region reg1;
    Region reg2;
{
    register Region tempReg;
    register BOX *rects;
    register BOX *rects1;
    register BOX *rects2;
    register int total;

    rects1 = reg1->rects;
    rects2 = reg2->rects;

    total = reg1->numRects + reg2->numRects;
    if (! (tempReg = XCreateRegion()))
	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(&reg2->extents, tempReg);  
    miRegionCopy(newReg, tempReg);
    Xfree((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(newReg, reg1, reg2)
    Region newReg, reg1, 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(newReg, rects, reg1, reg2, FirstRect)
    register Region newReg;
    register BOX *rects;
    register Region reg1;
    register Region reg2; 
    BOX *FirstRect;
{
    register BOX *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 Region Operator
 *====================================================================*/

/*-
 *-----------------------------------------------------------------------
 * miCoalesce --
 *	Attempt to merge the boxes 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 (pReg, prevStart, curStart)
    register Region	pReg;	    	/* Region to coalesce */
    int	    	  	prevStart;  	/* Index of start of previous band */
    int	    	  	curStart;   	/* Index of start of current band */
{
    register BoxPtr	pPrevBox;   	/* Current box in previous band */
    register BoxPtr	pCurBox;    	/* Current box in current band */
    register BoxPtr	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];

    pPrevBox = &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.
     */
    pCurBox = &pReg->rects[curStart];
    bandY1 = pCurBox->y1;
    for (curNumRects = 0;
	 (pCurBox != pRegEnd) && (pCurBox->y1 == bandY1);
	 curNumRects++)
    {
	pCurBox++;
    }
    
    if (pCurBox != 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)) {
	pCurBox -= curNumRects;
	/*
	 * The bands may only be coalesced if the bottom of the previous
	 * matches the top scanline of the current.
	 */
	if (pPrevBox->y2 == pCurBox->y1)
	{
	    /*
	     * Make sure the bands have boxes in the same places. This
	     * assumes that boxes have been added in such a way that they
	     * cover the most area possible. I.e. two boxes in a band must
	     * have some horizontal space between them.
	     */
	    do
	    {
		if ((pPrevBox->x1 != pCurBox->x1) ||
		    (pPrevBox->x2 != pCurBox->x2))
		{
		    /*
		     * The bands don't line up so they can't be coalesced.
		     */
		    return (curStart);
		}
		pPrevBox++;
		pCurBox++;
		prevNumRects -= 1;
	    } while (prevNumRects != 0);

	    pReg->numRects -= curNumRects;
	    pCurBox -= curNumRects;
	    pPrevBox -= curNumRects;

	    /*
	     * The bands may be merged, so set the bottom y of each box
	     * in the previous band to that of the corresponding box in
	     * the current band.
	     */
	    do
	    {
		pPrevBox->y2 = pCurBox->y2;
		pPrevBox++;
		pCurBox++;
		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 (pCurBox == pRegEnd)
	    {
		curStart = prevStart;
	    }
	    else
	    {
		do
		{
		    *pPrevBox++ = *pCurBox++;
		} while (pCurBox != 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(newReg, reg1, reg2, overlapFunc,  nonOverlap1Func, nonOverlap2Func)
    register Region 	newReg;	    	    	/* Place to store result */
    Region	  	reg1;	    	    	/* First region in operation */
    Region	  	reg2;	    	    	/* 2d region in operation */
    void    	  	(*overlapFunc)();   	/* Function to call for over-
						 * lapping bands */
    void    	  	(*nonOverlap1Func)();	/* Function to call for non-
						 * overlapping bands in region
						 * 1 */
    void    	  	(*nonOverlap2Func)();	/* Function to call for non-
						 * overlapping bands in region
						 * 2 */
{
    register BoxPtr	r1; 	    	    	/* Pointer into first region */
    register BoxPtr	r2; 	    	    	/* Pointer into 2d region */
    BoxPtr  	  	r1End;	    	    	/* End of 1st region */
    BoxPtr  	  	r2End;	    	    	/* End of 2d region */
    register short  	ybot;	    	    	/* Bottom of intersection */
    register short  	ytop;	    	    	/* Top of intersection */
    BoxPtr  	  	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 BoxPtr 	r1BandEnd;  	    	/* End of current band in r1 */