region.c

linux下的一款播放器

}

#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(&reg1->extents, &reg2->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(&reg2->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