devrgn2.c

开放源码实时操作系统源码.

    EndPt = pts - 1;
    for(poly = 0; poly < nbpolygons; poly++)
    {
        count = Count[poly];
        EndPt += count;
        if(count < 2)
            continue;

        PrevPt = EndPt;

    /*
     *  for each vertex in the array of points.
     *  In this loop we are dealing with two vertices at
     *  a time -- these make up one edge of the polygon.
     */
        while (count--)
        {
            CurrPt = pts++;
        /*
         *  find out which point is above and which is below.
         */
            if (PrevPt->y > CurrPt->y)
            {
                bottom = PrevPt, top = CurrPt;
                pETEs->ClockWise = 0;
            }
            else
            {
                bottom = CurrPt, top = PrevPt;
                pETEs->ClockWise = 1;
            }

        /*
         * don't add horizontal edges to the Edge table.
         */
            if (bottom->y != top->y)
            {
                pETEs->ymax = bottom->y-1;
                                /* -1 so we don't get last scanline */

            /*
             *  initialize integer edge algorithm
             */
                dy = bottom->y - top->y;
                
                BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);

                REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
                                                                &iSLLBlock);

                if (PrevPt->y > ET->ymax)
                  ET->ymax = PrevPt->y;
                if (PrevPt->y < ET->ymin)
                  ET->ymin = PrevPt->y;
                pETEs++;
            }

            PrevPt = CurrPt;
        }
    }
}

/*
 *     REGION_loadAET
 *
 *     This routine moves EdgeTableEntries from the
 *     EdgeTable into the Active Edge Table,
 *     leaving them sorted by smaller x coordinate.
 *
 */
static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
{
    EdgeTableEntry *pPrevAET;
    EdgeTableEntry *tmp;

    pPrevAET = AET;
    AET = AET->next;
    while (ETEs)
    {
        while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
        {
            pPrevAET = AET;
            AET = AET->next;
        }
        tmp = ETEs->next;
        ETEs->next = AET;
        if (AET)
            AET->back = ETEs;
        ETEs->back = pPrevAET;
        pPrevAET->next = ETEs;
        pPrevAET = ETEs;

        ETEs = tmp;
    }
}

/*
 *     REGION_computeWAET
 *
 *     This routine links the AET by the
 *     nextWETE (winding EdgeTableEntry) link for
 *     use by the winding number rule.  The final
 *     Active Edge Table (AET) might look something
 *     like:
 *
 *     AET
 *     ----------  ---------   ---------
 *     |ymax    |  |ymax    |  |ymax    |
 *     | ...    |  |...     |  |...     |
 *     |next    |->|next    |->|next    |->...
 *     |nextWETE|  |nextWETE|  |nextWETE|
 *     ---------   ---------   ^--------
 *         |                   |       |
 *         V------------------->       V---> ...
 *
 */
static void REGION_computeWAET(EdgeTableEntry *AET)
{
    EdgeTableEntry *pWETE;
    int inside = 1;
    int isInside = 0;

    AET->nextWETE = (EdgeTableEntry *)NULL;
    pWETE = AET;
    AET = AET->next;
    while (AET)
    {
        if (AET->ClockWise)
            isInside++;
        else
            isInside--;

        if ((!inside && !isInside) ||
            ( inside &&  isInside))
        {
            pWETE->nextWETE = AET;
            pWETE = AET;
            inside = !inside;
        }
        AET = AET->next;
    }
    pWETE->nextWETE = (EdgeTableEntry *)NULL;
}

/*
 *     REGION_InsertionSort
 *
 *     Just a simple insertion sort using
 *     pointers and back pointers to sort the Active
 *     Edge Table.
 *
 */
static MWBOOL REGION_InsertionSort(EdgeTableEntry *AET)
{
    EdgeTableEntry *pETEchase;
    EdgeTableEntry *pETEinsert;
    EdgeTableEntry *pETEchaseBackTMP;
    MWBOOL changed = FALSE;

    AET = AET->next;
    while (AET)
    {
        pETEinsert = AET;
        pETEchase = AET;
        while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
            pETEchase = pETEchase->back;

        AET = AET->next;
        if (pETEchase != pETEinsert)
        {
            pETEchaseBackTMP = pETEchase->back;
            pETEinsert->back->next = AET;
            if (AET)
                AET->back = pETEinsert->back;
            pETEinsert->next = pETEchase;
            pETEchase->back->next = pETEinsert;
            pETEchase->back = pETEinsert;
            pETEinsert->back = pETEchaseBackTMP;
            changed = TRUE;
        }
    }
    return changed;
}

/*
 *     REGION_FreeStorage
 *
 *     Clean up our act.
 */
static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
{
    ScanLineListBlock   *tmpSLLBlock;

    while (pSLLBlock)
    {
        tmpSLLBlock = pSLLBlock->next;
        free( pSLLBlock );
        pSLLBlock = tmpSLLBlock;
    }
}


/*
 *     REGION_PtsToRegion
 *
 *     Create an array of rectangles from a list of points.
 */
static int REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
                       POINTBLOCK *FirstPtBlock, MWCLIPREGION *reg)
{
    MWRECT *rects;
    MWPOINT *pts;
    POINTBLOCK *CurPtBlock;
    int i;
    MWRECT *extents;
    int numRects;

    extents = &reg->extents;

    numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;

    if (!(reg->rects = realloc( reg->rects, sizeof(MWRECT) * numRects )))
        return(0);

    reg->size = numRects;
    CurPtBlock = FirstPtBlock;
    rects = reg->rects - 1;
    numRects = 0;
    extents->left = LARGE_COORDINATE,  extents->right = SMALL_COORDINATE;

    for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
        /* the loop uses 2 points per iteration */
        i = NUMPTSTOBUFFER >> 1;
        if (!numFullPtBlocks)
            i = iCurPtBlock >> 1;
        for (pts = CurPtBlock->pts; i--; pts += 2) {
            if (pts->x == pts[1].x)
                continue;
            if (numRects && pts->x == rects->left && pts->y == rects->bottom && 
                pts[1].x == rects->right &&
                (numRects == 1 || rects[-1].top != rects->top) &&
                (i && pts[2].y > pts[1].y)) {
                rects->bottom = pts[1].y + 1;
                continue;
            }
            numRects++;
            rects++;
            rects->left = pts->x;  rects->top = pts->y;
            rects->right = pts[1].x;  rects->bottom = pts[1].y + 1;
            if (rects->left < extents->left)
                extents->left = rects->left;
            if (rects->right > extents->right)
                extents->right = rects->right;
        }
        CurPtBlock = CurPtBlock->next;
    }

    if (numRects) {
        extents->top = reg->rects->top;
        extents->bottom = rects->bottom;
    } else {
        extents->left = 0;
        extents->top = 0;
        extents->right = 0;
        extents->bottom = 0;
    }
    reg->numRects = numRects;

    return(TRUE);
}

/*
 *           GdAllocPolygonRegion
 */
MWCLIPREGION *
GdAllocPolygonRegion(MWPOINT *points, int count, int mode)
{
    return GdAllocPolyPolygonRegion(points, &count, 1, mode );
}

/*
 *           GdAllocPolyPolygonRegion
 */
MWCLIPREGION *
GdAllocPolyPolygonRegion(MWPOINT *points, int *count, int nbpolygons, int mode)
{
    MWCLIPREGION *rgn;
    EdgeTableEntry *pAET;   /* Active Edge Table       */
    int y;                  /* current scanline        */
    int iPts = 0;           /* number of pts in buffer */
    EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
    ScanLineList *pSLL;     /* current scanLineList    */
    MWPOINT *pts;           /* output buffer           */
    EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
    EdgeTable ET;                    /* header node for ET      */
    EdgeTableEntry AET;              /* header node for AET     */
    EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
    ScanLineListBlock SLLBlock;      /* header for scanlinelist */
    int fixWAET = FALSE;
    POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
    POINTBLOCK *tmpPtBlock;                              
    int numFullPtBlocks = 0;
    int poly, total;

    if(!(rgn = GdAllocRegion()))
        return NULL;
    
    /* special case a rectangle */

    if (((nbpolygons == 1) && ((*count == 4) ||
       ((*count == 5) && (points[4].x == points[0].x)
        && (points[4].y == points[0].y)))) && 
        (((points[0].y == points[1].y) &&
          (points[1].x == points[2].x) &&
          (points[2].y == points[3].y) &&
          (points[3].x == points[0].x)) ||
         ((points[0].x == points[1].x) &&
          (points[1].y == points[2].y) &&
          (points[2].x == points[3].x) &&
          (points[3].y == points[0].y))))
    {
        GdSetRectRegion( rgn, 
	    MWMIN(points[0].x, points[2].x), MWMIN(points[0].y, points[2].y),
	    MWMAX(points[0].x, points[2].x), MWMAX(points[0].y, points[2].y) );
        return rgn;
    }

    for(poly = total = 0; poly < nbpolygons; poly++)
        total += count[poly];
    if (! (pETEs = malloc( sizeof(EdgeTableEntry) * total ))) 
    {
        GdDestroyRegion( rgn );
        return 0;
    }
    pts = FirstPtBlock.pts;
    REGION_CreateETandAET(count, nbpolygons, points, &ET, &AET,
        pETEs, &SLLBlock); 
    pSLL = ET.scanlines.next;
    curPtBlock = &FirstPtBlock;

    if (mode != MWPOLY_WINDING) {
        /*
         *  for each scanline
         */
        for (y = ET.ymin; y < ET.ymax; y++) {
            /*
             *  Add a new edge to the active edge table when we
             *  get to the next edge.
             */
            if (pSLL != NULL && y == pSLL->scanline) {
                REGION_loadAET(&AET, pSLL->edgelist);
                pSLL = pSLL->next;
            }
            pPrevAET = &AET;
            pAET = AET.next;

            /*
             *  for each active edge
             */
            while (pAET) {
                pts->x = pAET->bres.minor_axis,  pts->y = y;
                pts++, iPts++;

                /*
                 *  send out the buffer
                 */
                if (iPts == NUMPTSTOBUFFER) {
                    tmpPtBlock = malloc( sizeof(POINTBLOCK)); 
                    if(!tmpPtBlock) {
                        return 0;
                    }
                    curPtBlock->next = tmpPtBlock;
                    curPtBlock = tmpPtBlock;
                    pts = curPtBlock->pts;
                    numFullPtBlocks++;
                    iPts = 0;
                }
                EVALUATEEDGEEVENODD(pAET, pPrevAET, y);

            }
            REGION_InsertionSort(&AET);
        }
    }
    else {
        /*
         *  for each scanline
         */
        for (y = ET.ymin; y < ET.ymax; y++) {
            /*
             *  Add a new edge to the active edge table when we
             *  get to the next edge.
             */
            if (pSLL != NULL && y == pSLL->scanline) { 
                REGION_loadAET(&AET, pSLL->edgelist);
                REGION_computeWAET(&AET);
                pSLL = pSLL->next;
            }
            pPrevAET = &AET;
            pAET = AET.next;
            pWETE = pAET;

            /*
             *  for each active edge
             */
            while (pAET) {
                /*
                 *  add to the buffer only those edges that
                 *  are in the Winding active edge table.
                 */
                if (pWETE == pAET) {
                    pts->x = pAET->bres.minor_axis,  pts->y = y;
                    pts++, iPts++;

                    /*
                     *  send out the buffer
                     */                        
                    if (iPts == NUMPTSTOBUFFER) {
                        tmpPtBlock = malloc( sizeof(POINTBLOCK) );
                        if(!tmpPtBlock) {
                            return 0;
                        }
                        curPtBlock->next = tmpPtBlock;
                        curPtBlock = tmpPtBlock;
                        pts = curPtBlock->pts;
                        numFullPtBlocks++;    iPts = 0;
                    }
                    pWETE = pWETE->nextWETE;
                }
                EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
            }

            /*
             *  recompute the winding active edge table if
             *  we just resorted or have exited an edge.
             */
            if (REGION_InsertionSort(&AET) || fixWAET) {
                REGION_computeWAET(&AET); 
                fixWAET = FALSE;
            }
        }
    }
    REGION_FreeStorage(SLLBlock.next);
    REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, rgn);
    for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
        tmpPtBlock = curPtBlock->next;
        free( curPtBlock );
        curPtBlock = tmpPtBlock;
    }
    free( pETEs );
    return rgn;
}

#endif /* POLYREGIONS*/