region.c

ARM9-2410教学实验系统下Linux下minigui程序

/***********************************************************************
 *           REGION_Coalesce
 *
 *      Attempt to merge the rects in the current band with those in the
 *      previous one. Used only by REGION_RegionOp.
 *
 * Results:
 *      The new index for the previous band.
 *
 * Side Effects:
 *      If coalescing takes place:
 *          - rectangles in the previous band will have their bottom fields
 *            altered.
 *          - some clipping rect will be deleted.
 *
 */
static CLIPRECT* REGION_Coalesce (
             CLIPRGN *region,      /* Region to coalesce */
             CLIPRECT *prevStart,  /* start of previous band */
             CLIPRECT *curStart    /* start of current band */
) {
    CLIPRECT *newStart;         /* Start of new band */
    CLIPRECT *pPrevRect;        /* Current rect in previous band */
    CLIPRECT *pCurRect;         /* Current rect in current band */
    CLIPRECT *temp;             /* Temporary clipping rect */
    int curNumRects;            /* Number of rectangles in current band */
    int prevNumRects;           /* Number of rectangles in previous band */
    int bandtop;                /* top coordinate for current band */

    if (prevStart == NULL) prevStart = region->head;
    if (curStart == NULL) curStart = region->head;

    if (prevStart == curStart)
        return prevStart;

    newStart = pCurRect = curStart;

    pPrevRect = prevStart;
    temp = prevStart;
    prevNumRects = 0;
    while (temp != curStart) {
        prevNumRects ++;
        temp = temp->next;
    }

    /*
     * Figure out how many rectangles are in the current band. Have to do
     * this because multiple bands could have been added in REGION_RegionOp
     * at the end when one region has been exhausted.
     */
    pCurRect = curStart;
    bandtop = pCurRect->rc.top;
    curNumRects = 0;
    while (pCurRect && (pCurRect->rc.top == bandtop)) {
        curNumRects ++;
        pCurRect = pCurRect->next;
    }
    
    if (pCurRect) {
        /*
         * 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).
         */
        temp = region->tail;
        while (temp->prev->rc.top == temp->rc.top) {
            temp = temp->prev;
        }
        newStart = temp;
    }

    if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
        pCurRect = curStart;
        /*
         * The bands may only be coalesced if the bottom of the previous
         * matches the top scanline of the current.
         */
        if (pPrevRect->rc.bottom == pCurRect->rc.top) {
            /*
             * Make sure the bands have rects in the same places. This
             * assumes that rects have been added in such a way that they
             * cover the most area possible. I.e. two rects in a band must
             * have some horizontal space between them.
             */
            do {
                if ((pPrevRect->rc.left != pCurRect->rc.left) ||
                    (pPrevRect->rc.right != pCurRect->rc.right))
                {
                    /*
                     * The bands don't line up so they can't be coalesced.
                     */
                    return newStart;
                }
                pPrevRect = pPrevRect->next;
                pCurRect = pCurRect->next;
            } while (--prevNumRects);

            /*
             * If only one band was added to the region, we have to backup
             * newStart to the start of the previous band.
             */
            if (pCurRect == NULL) {
                newStart = prevStart;
            }

            /*
             * The bands may be merged, so set the bottom of each rect
             * in the previous band to that of the corresponding rect in
             * the current band.
             */
            /*
             * for implementation of MiniGUI, we should free 
             * the clipping rects merged.
             */
            pCurRect = curStart;
            pPrevRect = prevStart;
            do {
                pPrevRect->rc.bottom = pCurRect->rc.bottom;
                pPrevRect = pPrevRect->next;

                if (pCurRect->next)
                    pCurRect->next->prev = pCurRect->prev;
                else
                    region->tail = pCurRect->prev;
                if (pCurRect->prev)
                    pCurRect->prev->next = pCurRect->next;
                else
                    region->head = pCurRect->next;

                temp = pCurRect->next;
                FreeClipRect (region->heap, pCurRect);
                pCurRect = temp;
            } while (--curNumRects);

            /*
             *
             * 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... newStart is already in the right place.
             */
            /* no need to copy for implementation of MiniGUI -- they are freed.
            if (temp == regionEnd) {
                newStart = prevStart;
            }

            else {
                do {
                    *pPrevRect++ = *pCurRect++;
                } while (pCurRect != regionEnd);
            }
            */
            
        }
    }
    return (newStart);
}

/***********************************************************************
 *           REGION_RegionOp
 *
 *      Apply an operation to two regions. Called by Union,
 *      Xor, Subtract, Intersect...
 *
 * 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 rcBound. 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
REGION_RegionOp(
            CLIPRGN *newReg, /* Place to store result */
            const CLIPRGN *reg1,   /* First region in operation */
            const CLIPRGN *reg2,   /* 2nd region in operation */
            voidProcp1 overlapFunc,     /* Function to call for over-lapping bands */
            voidProcp2 nonOverlap1Func, /* Function to call for non-overlapping bands in region 1 */
            voidProcp2 nonOverlap2Func  /* Function to call for non-overlapping bands in region 2 */
) {
    CLIPRGN my_dst;
    CLIPRGN* pdst;
    const CLIPRECT *r1;                 /* Pointer into first region */
    const CLIPRECT *r2;                 /* Pointer into 2d region */
    const CLIPRECT *r1BandEnd;          /* End of current band in r1 */
    const CLIPRECT *r2BandEnd;          /* End of current band in r2 */
    int ybot;                           /* Bottom of intersection */
    int ytop;                           /* Top of intersection */
    CLIPRECT* prevBand;                 /* start of previous band in newReg */
    CLIPRECT* curBand;                  /* start of current band in newReg */
    int top;                            /* Top of non-overlapping band */
    int 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->head;
    r2 = reg2->head;

    /*
     * newReg may be one of the src regions so we can't empty it. We keep a 
     * note of its rects pointer (so that we can free them later), preserve its
     * rcBound and simply set numRects to zero. 
     */
    /*
    oldRects = newReg->rects;
    newReg->numRects = 0;
     */

    /* 
     * for implementation of MiniGUI, we create an empty region.
     */
    if (newReg == reg1 || newReg == reg2) {
        InitClipRgn (&my_dst, newReg->heap);
        pdst = &my_dst;
    }
    else {
        EmptyClipRgn (newReg);
        pdst = 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.
     */

    /* for implementation of MiniGUI, dst always is an empty region.
    newReg->size = MAX(reg1->numRects,reg2->numRects) * 2;

    if (! (newReg->rects = malloc( sizeof(CLIPRECT) * 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->rcBound.top < reg2->rcBound.top)
        ybot = reg1->rcBound.top;
    else
        ybot = reg2->rcBound.top;
    
    /*
     * 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 = pdst->head;
    
    do {
        curBand = pdst->tail;

        /*
         * 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 && (r1BandEnd->rc.top == r1->rc.top))
            r1BandEnd = r1BandEnd->next;
        
        r2BandEnd = r2;
        while (r2BandEnd && (r2BandEnd->rc.top == r2->rc.top))
            r2BandEnd = r2BandEnd->next;
        
        /*
         * 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->rc.top < r2->rc.top) {
            top = MAX (r1->rc.top, ybot);
            bot = MIN (r1->rc.bottom, r2->rc.top);

            if ((top != bot) && (nonOverlap1Func != NULL))
                (* nonOverlap1Func) (pdst, r1, r1BandEnd, top, bot);

            ytop = r2->rc.top;
        }
        else if (r2->rc.top < r1->rc.top) {
            top = MAX (r2->rc.top, ybot);
            bot = MIN (r2->rc.bottom, r1->rc.top);

            if ((top != bot) && (nonOverlap2Func != NULL))
                (* nonOverlap2Func) (pdst, r2, r2BandEnd, top, bot);

            ytop = r1->rc.top;
        }
        else {
            ytop = r1->rc.top;
        }

        /*
         * 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 (pdst->tail != curBand) {
            prevBand = REGION_Coalesce (pdst, prevBand, curBand);
        }

        /*
         * Now see if we've hit an intersecting band. The two bands only
         * intersect if ybot > ytop
         */
        ybot = MIN (r1->rc.bottom, r2->rc.bottom);
        curBand = pdst->tail;
        if (ybot > ytop)
            (* overlapFunc) (pdst, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
        
        if (pdst->tail != curBand)
            prevBand = REGION_Coalesce (pdst, prevBand, curBand);

        /*
         * If we've finished with a band (bottom == ybot) we skip forward
         * in the region to the next band.
         */
        if (r1->rc.bottom == ybot)
            r1 = r1BandEnd;
        if (r2->rc.bottom == ybot)
            r2 = r2BandEnd;
    } while (r1 && r2);

    /*
     * Deal with whichever region still has rectangles left.
     */
    curBand = pdst->tail;
    if (r1) {
        if (nonOverlap1Func != NULL) {
            do {
                r1BandEnd = r1;
                while ((r1BandEnd) && (r1BandEnd->rc.top == r1->rc.top)) {
                    r1BandEnd = r1BandEnd->next;
                }
                (* nonOverlap1Func) (pdst, r1, r1BandEnd,
                                     MAX (r1->rc.top, ybot), r1->rc.bottom);
                r1 = r1BandEnd;
            } while (r1);
        }
    }
    else if ((r2) && (nonOverlap2Func != NULL))
    {
        do {
            r2BandEnd = r2;
            while ((r2BandEnd) && (r2BandEnd->rc.top == r2->rc.top)) {
                 r2BandEnd = r2BandEnd->next;
            }
            (* nonOverlap2Func) (pdst, r2, r2BandEnd,
                                MAX (r2->rc.top, ybot), r2->rc.bottom);
            r2 = r2BandEnd;
        } while (r2);
    }

    if (pdst->tail != curBand)
        (void) REGION_Coalesce (pdst, 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 0 // MiniGUI implementation does not need to do this
    if (newReg->numRects < (newReg->size >> 1))