polyreg.c

linux下的一款播放器

    register EdgeTableEntry *pWETE;
    register int inside = 1;
    register 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;
}

/*
 *     InsertionSort
 *
 *     Just a simple insertion sort using
 *     pointers and back pointers to sort the Active
 *     Edge Table.
 *
 */

static int InsertionSort(register EdgeTableEntry *AET )
{
    register EdgeTableEntry *pETEchase;
    register EdgeTableEntry *pETEinsert;
    register EdgeTableEntry *pETEchaseBackTMP;
    register int changed = 0;

    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 = 1;
        }
    }
    return(changed);
}

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

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

/*
 *     Create an array of rectangles from a list of points.
 *     If indeed these things (POINTS, RECTS) are the same,
 *     then this proc is still needed, because it allocates
 *     storage for the array, which was allocated on the
 *     stack by the calling procedure.
 *
 */
static int PtsToRegion( register int numFullPtBlocks,
                        register int iCurPtBlock,
                        POINTBLOCK *FirstPtBlock,
                        HXREGION *reg
                        )
{
    HXBOX  *rects;
    HXxPoint *pts;
    POINTBLOCK *CurPtBlock;
    int i;
    HXBOX *extents;
    int numRects;
    HXBOX *prevRects = reg->rects;

    extents = &reg->extents;
 
    numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
 
    if (!(reg->rects = (HXBOX *)realloc((char *)reg->rects, 
            (unsigned) (sizeof(HXBOX) * numRects))))  {
        free(prevRects);
        return(0);
    }
 
    reg->size = numRects;
    CurPtBlock = FirstPtBlock;
    rects = reg->rects - 1;
    numRects = 0;
    extents->x1 = MAXSHORT,  extents->x2 = MINSHORT;
 
    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->x1 && pts->y == rects->y2 &&
                pts[1].x == rects->x2 &&
                (numRects == 1 || rects[-1].y1 != rects->y1) &&
                (i && pts[2].y > pts[1].y)) {
                rects->y2 = pts[1].y + 1;
                continue;
            }
            numRects++;
            rects++;
            rects->x1 = (short) pts->x;  
            rects->y1 = (short) pts->y;
            rects->x2 = (short) pts[1].x;  
            rects->y2 = (short) pts[1].y + 1;
            if (rects->x1 < extents->x1)
                extents->x1 = rects->x1;
            if (rects->x2 > extents->x2)
                extents->x2 = rects->x2;
        }
        CurPtBlock = CurPtBlock->next;
    }

    if (numRects) {
        extents->y1 = reg->rects->y1;
        extents->y2 = rects->y2;
    } else {
        extents->x1 = 0;
        extents->y1 = 0;
        extents->x2 = 0;
        extents->y2 = 0;
    }
    reg->numRects = numRects;
 
    return(TRUE);
}

/*
 *     polytoregion
 *
 *     Scan converts a polygon by returning a run-length
 *     encoding of the resultant bitmap -- the run-length
 *     encoding is in the form of an array of rectangles.
 */
_HXRegion HXPolygonRegion( HXxPoint* Pts,   /* the pts */
                           int       Count, /* number of pts */
                           int       rule   /* winding rule */
                           )
{
    _HXRegion region;
    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    */
    HXxPoint *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;
 
    if( !(region = HXCreateRegion()) )
        return (_HXRegion) NULL;

    /* special case a rectangle */
    pts = Pts;
    if (((Count == 4) ||
         ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
        (((pts[0].y == pts[1].y) &&
          (pts[1].x == pts[2].x) &&
          (pts[2].y == pts[3].y) &&
          (pts[3].x == pts[0].x)) ||
         ((pts[0].x == pts[1].x) &&
          (pts[1].y == pts[2].y) &&
          (pts[2].x == pts[3].x) &&
          (pts[3].y == pts[0].y)))) {
        region->extents.x1 = (short) min(pts[0].x, pts[2].x);
        region->extents.y1 = (short) min(pts[0].y, pts[2].y);
        region->extents.x2 = (short) max(pts[0].x, pts[2].x);
        region->extents.y2 = (short) max(pts[0].y, pts[2].y);
        if ((region->extents.x1 != region->extents.x2) &&
            (region->extents.y1 != region->extents.y2)) {
            region->numRects = 1;
            *(region->rects) = region->extents;
        }
        return(region);
    }

    if (! (pETEs = (EdgeTableEntry *)
           malloc((unsigned) (sizeof(EdgeTableEntry) * Count))))
        return (_HXRegion) NULL;

    pts = FirstPtBlock.pts;
    CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);

        if (ET.ymin > ET.ymax)
        {
                // this is not a valid region. Chances are all the
                // points are equivalent
                free((char *)pETEs);
                return(region);
        }

    pSLL = ET.scanlines.next;
    curPtBlock = &FirstPtBlock;
 
    if (rule == EvenOddRule) {
        /*
         *  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) {
                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 = (POINTBLOCK *)malloc(sizeof(POINTBLOCK));
                    curPtBlock->next = tmpPtBlock;
                    curPtBlock = tmpPtBlock;
                    pts = curPtBlock->pts;
                    numFullPtBlocks++;
                    iPts = 0;
                }
                EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
            }
            (void) 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) {
                loadAET(&AET, pSLL->edgelist);
                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 = (POINTBLOCK *)malloc(sizeof(POINTBLOCK));
                        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 (InsertionSort(&AET) || fixWAET) {
                computeWAET(&AET);
                fixWAET = FALSE;
            }
        }
    }
    FreeStorage(SLLBlock.next); 
    (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
    for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
        tmpPtBlock = curPtBlock->next;
        free((char *)curPtBlock);
        curPtBlock = tmpPtBlock;
    }
    free((char *)pETEs);
    return(region);
}