polyfill.c File Reference

#include <win32k.h>
#include <debug.h>

Include dependency graph for polyfill.c:

Go to the source code of this file.

Classes
struct	_tagFILL_EDGE
struct	_FILL_EDGE_LIST

Macros
#define	NDEBUG
#define	FILL_EDGE_ALLOC_TAG   0x45465044
#define	DEBUG_PRINT_ACTIVE_EDGELIST(x)

Typedefs
typedef struct _tagFILL_EDGE	FILL_EDGE
typedef struct _FILL_EDGE_LIST	FILL_EDGE_LIST

Functions
static void FASTCALL	POLYGONFILL_DestroyEdgeList (FILL_EDGE_LIST *list)
static FILL_EDGE *FASTCALL	POLYGONFILL_MakeEdge (POINT From, POINT To)
static INT FASTCALL	FILL_EDGE_Compare (FILL_EDGE *Edge1, FILL_EDGE *Edge2)
static void FASTCALL	POLYGONFILL_ActiveListInsert (FILL_EDGE **activehead, FILL_EDGE *NewEdge)
static FILL_EDGE_LIST *FASTCALL	POLYGONFILL_MakeEdgeList (PPOINT Points, int Count)
static void FASTCALL	POLYGONFILL_UpdateScanline (FILL_EDGE *pEdge, int Scanline)
static void APIENTRY	POLYGONFILL_BuildActiveList (int Scanline, FILL_EDGE_LIST *list, FILL_EDGE **ActiveHead)
static void APIENTRY	POLYGONFILL_FillScanLineAlternate (PDC dc, int ScanLine, FILL_EDGE *ActiveHead, SURFACE *psurf, BRUSHOBJ *BrushObj, MIX RopMode)
static void APIENTRY	POLYGONFILL_FillScanLineWinding (PDC dc, int ScanLine, FILL_EDGE *ActiveHead, SURFACE *psurf, BRUSHOBJ *BrushObj, MIX RopMode)
BOOL APIENTRY	FillPolygon (PDC dc, SURFACE *psurf, BRUSHOBJ *BrushObj, MIX RopMode, CONST PPOINT Points, int Count, RECTL BoundRect)
BOOL FASTCALL	IntFillPolygon (PDC dc, SURFACE *psurf, BRUSHOBJ *BrushObj, CONST PPOINT Points, int Count, RECTL DestRect, POINTL *BrushOrigin)

Macro Definition Documentation

DEBUG_PRINT_ACTIVE_EDGELIST

#define DEBUG_PRINT_ACTIVE_EDGELIST

(

x

)

Definition at line 68 of file polyfill.c.

FILL_EDGE_ALLOC_TAG

#define FILL_EDGE_ALLOC_TAG   0x45465044

Definition at line 14 of file polyfill.c.

NDEBUG

#define NDEBUG

Definition at line 11 of file polyfill.c.

Typedef Documentation

FILL_EDGE

typedef struct _tagFILL_EDGE FILL_EDGE

FILL_EDGE_LIST

typedef struct _FILL_EDGE_LIST FILL_EDGE_LIST

Function Documentation

FILL_EDGE_Compare()

static INT FASTCALL FILL_EDGE_Compare ( FILL_EDGE *  Edge1, FILL_EDGE *  Edge2  )

static

Definition at line 176 of file polyfill.c.

{
    int e1 = Edge1->XIntercept[0] + Edge1->XIntercept[1];
    int e2 = Edge2->XIntercept[0] + Edge2->XIntercept[1];
 
    return e1 - e2;
}

Referenced by POLYGONFILL_ActiveListInsert().

FillPolygon()

BOOL APIENTRY FillPolygon	(	PDC	dc,
		SURFACE *	psurf,
		BRUSHOBJ *	BrushObj,
		MIX	RopMode,
		CONST PPOINT	Points,
		int	Count,
		RECTL	BoundRect
	)

Definition at line 538 of file polyfill.c.

{
    FILL_EDGE_LIST *list = 0;
    FILL_EDGE *ActiveHead = 0;
    int ScanLine;
    PDC_ATTR pdcattr = dc->pdcattr;
    void
    (APIENTRY *FillScanLine)(
        PDC dc,
        int ScanLine,
        FILL_EDGE* ActiveHead,
        SURFACE *psurf,
        BRUSHOBJ *BrushObj,
        MIX RopMode);
 
    //DPRINT("FillPolygon\n");
 
    /* Create Edge List. */
    list = POLYGONFILL_MakeEdgeList(Points, Count);
    /* DEBUG_PRINT_EDGELIST(list); */
    if (NULL == list)
        return FALSE;
 
    if (WINDING == pdcattr->jFillMode)
        FillScanLine = POLYGONFILL_FillScanLineWinding;
    else /* Default */
        FillScanLine = POLYGONFILL_FillScanLineAlternate;
 
    /* For each Scanline from BoundRect.bottom to BoundRect.top,
     * determine line segments to draw
     */
    for (ScanLine = BoundRect.top; ScanLine < BoundRect.bottom; ++ScanLine)
    {
        POLYGONFILL_BuildActiveList(ScanLine, list, &ActiveHead);
        //DEBUG_PRINT_ACTIVE_EDGELIST(ActiveHead);
        FillScanLine(dc, ScanLine, ActiveHead, psurf, BrushObj, RopMode);
    }
 
    /* Free Edge List. If any are left. */
    POLYGONFILL_DestroyEdgeList(list);
 
    return TRUE;
}

IntFillPolygon()

BOOL FASTCALL IntFillPolygon	(	PDC	dc,
		SURFACE *	psurf,
		BRUSHOBJ *	BrushObj,
		CONST PPOINT	Points,
		int	Count,
		RECTL	DestRect,
		POINTL *	BrushOrigin
	)

Definition at line 590 of file polyfill.c.

{
    FILL_EDGE_LIST *list = 0;
    FILL_EDGE *ActiveHead = 0;
    FILL_EDGE *pLeft, *pRight;
    int ScanLine;
 
    //DPRINT("IntFillPolygon\n");
 
    /* Create Edge List. */
    list = POLYGONFILL_MakeEdgeList(Points, Count);
    /* DEBUG_PRINT_EDGELIST(list); */
    if (NULL == list)
        return FALSE;
 
    /* For each Scanline from DestRect.top to DestRect.bottom, determine line segments to draw */
    for (ScanLine = DestRect.top; ScanLine < DestRect.bottom; ++ScanLine)
    {
        POLYGONFILL_BuildActiveList(ScanLine, list, &ActiveHead);
        //DEBUG_PRINT_ACTIVE_EDGELIST(ActiveHead);
 
        if (!ActiveHead)
        {
            POLYGONFILL_DestroyEdgeList(list);
            return FALSE;
        }
 
        pLeft = ActiveHead;
        pRight = pLeft->pNext;
        ASSERT(pRight);
 
        while (NULL != pRight)
        {
            int x1 = pLeft->XIntercept[0];
            int x2 = pRight->XIntercept[1];
 
            if (x2 > x1)
            {
                RECTL LineRect;
                LineRect.top = ScanLine;
                LineRect.bottom = ScanLine + 1;
                LineRect.left = x1;
                LineRect.right = x2;
 
                IntEngBitBlt(&psurf->SurfObj,
                             NULL,
                             NULL,
                             (CLIPOBJ *)&dc->co,
                             NULL,
                             &LineRect,
                             NULL,
                             NULL,
                             BrushObj,
                             BrushOrigin,
                             ROP4_FROM_INDEX(R3_OPINDEX_PATCOPY));
            }
 
            pLeft = pRight->pNext;
            pRight = pLeft ? pLeft->pNext : NULL;
        }
    }
 
    /* Free Edge List. If any are left. */
    POLYGONFILL_DestroyEdgeList(list);
 
    return TRUE;
}

Referenced by IntEngFillPolygon(), and IntGdiPolygon().

POLYGONFILL_ActiveListInsert()

static void FASTCALL POLYGONFILL_ActiveListInsert ( FILL_EDGE **  activehead, FILL_EDGE *  NewEdge  )

static

Definition at line 191 of file polyfill.c.

{
    FILL_EDGE *pPrev, *pThis;
    //DPRINT1("In POLYGONFILL_ActiveListInsert()\n");
    ASSERT(activehead && NewEdge);
 
    if (!*activehead)
    {
        NewEdge->pNext = NULL;
        *activehead = NewEdge;
        return;
    }
    /*
    ** First lets check to see if we have a new smallest value.
    */
    if (FILL_EDGE_Compare(NewEdge, *activehead) <= 0)
    {
        NewEdge->pNext = *activehead;
        *activehead = NewEdge;
        return;
    }
 
    /*
    ** Ok, now scan to the next spot to put this item.
    */
    pThis = *activehead;
    pPrev = NULL;
    while ( pThis && FILL_EDGE_Compare(pThis, NewEdge) < 0 )
    {
        pPrev = pThis;
        pThis = pThis->pNext;
    }
 
    ASSERT(pPrev);
    NewEdge->pNext = pPrev->pNext;
    pPrev->pNext = NewEdge;
    //DEBUG_PRINT_ACTIVE_EDGELIST(*activehead);
}

Referenced by POLYGONFILL_BuildActiveList().

POLYGONFILL_BuildActiveList()

static void APIENTRY POLYGONFILL_BuildActiveList ( int  Scanline, FILL_EDGE_LIST *  list, FILL_EDGE **  ActiveHead  )

static

Definition at line 361 of file polyfill.c.

{
    int i;
 
    ASSERT(list && ActiveHead);
    *ActiveHead = 0;
    for (i = 0; i < list->Count; i++)
    {
        FILL_EDGE* pEdge = list->Edges[i];
        ASSERT(pEdge);
        if (pEdge->FromY <= Scanline && pEdge->ToY > Scanline)
        {
            POLYGONFILL_UpdateScanline(pEdge, Scanline);
            POLYGONFILL_ActiveListInsert(ActiveHead, pEdge);
        }
    }
}

Referenced by FillPolygon(), and IntFillPolygon().

POLYGONFILL_DestroyEdgeList()

static void FASTCALL POLYGONFILL_DestroyEdgeList ( FILL_EDGE_LIST *  list )

static

Definition at line 77 of file polyfill.c.

{
    int i;
 
    if (list)
    {
        if (list->Edges)
        {
            for (i = 0; i < list->Count; i++)
            {
                _PRAGMA_WARNING_SUPPRESS(__WARNING_USING_UNINIT_VAR)
                if (list->Edges[i])
                    EngFreeMem(list->Edges[i]);
            }
 
            EngFreeMem(list->Edges);
        }
 
        EngFreeMem(list);
    }
}

Referenced by FillPolygon(), IntFillPolygon(), and POLYGONFILL_MakeEdgeList().

POLYGONFILL_FillScanLineAlternate()

static void APIENTRY POLYGONFILL_FillScanLineAlternate ( PDC  dc, int  ScanLine, FILL_EDGE *  ActiveHead, SURFACE *  psurf, BRUSHOBJ *  BrushObj, MIX  RopMode  )

static

Definition at line 389 of file polyfill.c.

{
    FILL_EDGE *pLeft, *pRight;
 
    if (!ActiveHead)
        return;
 
    pLeft = ActiveHead;
    pRight = pLeft->pNext;
    ASSERT(pRight);
 
    while (NULL != pRight)
    {
        int x1 = pLeft->XIntercept[0];
        int x2 = pRight->XIntercept[1];
        if (x2 > x1)
        {
            RECTL BoundRect;
            BoundRect.top = ScanLine;
            BoundRect.bottom = ScanLine + 1;
            BoundRect.left = x1;
            BoundRect.right = x2;
 
            //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
            IntEngLineTo(&psurf->SurfObj,
                         (CLIPOBJ *)&dc->co,
                         BrushObj,
                         x1,
                         ScanLine,
                         x2,
                         ScanLine,
                         &BoundRect,  // Bounding rectangle
                         RopMode);    // MIX
        }
        pLeft = pRight->pNext;
        pRight = pLeft ? pLeft->pNext : NULL;
    }
}

Referenced by FillPolygon().

POLYGONFILL_FillScanLineWinding()

static void APIENTRY POLYGONFILL_FillScanLineWinding ( PDC  dc, int  ScanLine, FILL_EDGE *  ActiveHead, SURFACE *  psurf, BRUSHOBJ *  BrushObj, MIX  RopMode  )

static

Definition at line 437 of file polyfill.c.

{
    FILL_EDGE *pLeft, *pRight;
    int x1, x2, winding = 0;
    RECTL BoundRect;
 
    if (!ActiveHead)
        return;
 
    BoundRect.top = ScanLine;
    BoundRect.bottom = ScanLine + 1;
 
    pLeft = ActiveHead;
    winding = pLeft->YDirection;
    pRight = pLeft->pNext;
    ASSERT(pRight);
 
    // Setup first line...
    x1 = pLeft->XIntercept[0];
    x2 = pRight->XIntercept[1];
 
    pLeft = pRight;
    pRight = pLeft->pNext;
    winding += pLeft->YDirection;
 
    while ( NULL != pRight )
    {
        int newx1 = pLeft->XIntercept[0];
        int newx2 = pRight->XIntercept[1];
        if ( winding )
        {
            // Check and see if this new line touches the previous...
            if ((newx1 >= x1 && newx1 <= x2) ||
                (newx2 >= x1 && newx2 <= x2) ||
                (x1 >= newx1 && x1 <= newx2) ||
                (x2 >= newx2 && x2 <= newx2))
            {
                // Yup, just tack it on to our existing line
                x1 = min(x1,newx1);
                x2 = max(x2,newx2);
            }
            else
            {
                // Nope - render the old line..
                BoundRect.left = x1;
                BoundRect.right = x2;
 
                //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
                IntEngLineTo(&psurf->SurfObj,
                             (CLIPOBJ *)&dc->co,
                             BrushObj,
                             x1,
                             ScanLine,
                             x2,
                             ScanLine,
                             &BoundRect,  // Bounding rectangle
                             RopMode);    // MIX
 
                x1 = newx1;
                x2 = newx2;
            }
        }
 
        pLeft = pRight;
        pRight = pLeft->pNext;
        winding += pLeft->YDirection;
    }
 
    // There will always be a line left-over, render it now...
    BoundRect.left = x1;
    BoundRect.right = x2;
 
    //DPRINT("Fill Line (%d, %d) to (%d, %d)\n",x1, ScanLine, x2, ScanLine);
    IntEngLineTo(&psurf->SurfObj,
                 (CLIPOBJ *)&dc->co,
                 BrushObj,
                 x1,
                 ScanLine,
                 x2,
                 ScanLine,
                 &BoundRect,  // Bounding rectangle
                 RopMode);    // MIX
}

Referenced by FillPolygon().

POLYGONFILL_MakeEdge()

static FILL_EDGE *FASTCALL POLYGONFILL_MakeEdge ( POINT  From, POINT  To  )

static

Definition at line 105 of file polyfill.c.

{
    FILL_EDGE* rc = (FILL_EDGE*)EngAllocMem(FL_ZERO_MEMORY, sizeof(FILL_EDGE), FILL_EDGE_ALLOC_TAG);
 
    if (0 == rc)
        return NULL;
 
    //DPRINT1("Making Edge: (%d, %d) to (%d, %d)\n", From.x, From.y, To.x, To.y);
    // Now fill the struct.
    if ( To.y < From.y )
    {
        rc->FromX = To.x;
        rc->FromY = To.y;
        rc->ToX = From.x;
        rc->ToY = From.y;
        rc->YDirection = -1;
 
        // Lines that go up get walked backwards, so need to be offset
        // by -1 in order to make the walk identically on a pixel-level
        rc->Error = -1;
    }
    else
    {
        rc->FromX = From.x;
        rc->FromY = From.y;
        rc->ToX = To.x;
        rc->ToY = To.y;
        rc->YDirection = 1;
 
        rc->Error = 0;
    }
 
    rc->x = rc->FromX;
    rc->y = rc->FromY;
    rc->dx   = rc->ToX - rc->FromX;
    rc->dy   = rc->ToY - rc->FromY;
    rc->absdx = abs(rc->dx);
    rc->absdy = abs(rc->dy);
 
    rc->xmajor = rc->absdx > rc->absdy;
 
    rc->ErrorMax = max(rc->absdx,rc->absdy);
 
    rc->Error += rc->ErrorMax / 2;
 
    rc->XDirection = (rc->dx < 0)?(-1):(1);
 
    rc->pNext = 0;
 
    //DPRINT("MakeEdge (%i,%i)->(%i,%i) d=(%i,%i) dir=(%i,%i) err=%i max=%i\n",
    //  From.x, From.y, To.x, To.y, rc->dx, rc->dy, rc->XDirection, rc->YDirection, rc->Error, rc->ErrorMax );
 
    return rc;
}

Referenced by POLYGONFILL_MakeEdgeList().

POLYGONFILL_MakeEdgeList()

static FILL_EDGE_LIST *FASTCALL POLYGONFILL_MakeEdgeList ( PPOINT  Points, int  Count  )

static

Definition at line 236 of file polyfill.c.

{
    int CurPt = 0;
    FILL_EDGE_LIST* list = 0;
    FILL_EDGE* e = 0;
 
    if (0 == Points || 2 > Count)
        return 0;
 
    list = (FILL_EDGE_LIST*)EngAllocMem(FL_ZERO_MEMORY, sizeof(FILL_EDGE_LIST), FILL_EDGE_ALLOC_TAG);
    if ( 0 == list )
        goto fail;
    list->Count = 0;
    list->Edges = (FILL_EDGE**)EngAllocMem(FL_ZERO_MEMORY, Count*sizeof(FILL_EDGE*), FILL_EDGE_ALLOC_TAG);
    if ( !list->Edges )
        goto fail;
 
    memset(list->Edges, 0, Count * sizeof(FILL_EDGE*));
 
    for (CurPt = 1; CurPt < Count; ++CurPt)
    {
        e = POLYGONFILL_MakeEdge ( Points[CurPt-1], Points[CurPt] );
        if (!e)
            goto fail;
 
        // If a straight horizontal line - who cares?
        if (!e->absdy)
            EngFreeMem(e);
        else
            list->Edges[list->Count++] = e;
    }
    e = POLYGONFILL_MakeEdge ( Points[CurPt-1], Points[0] );
    if ( !e )
        goto fail;
 
    if (!e->absdy)
        EngFreeMem(e);
    else
        list->Edges[list->Count++] = e;
    return list;
 
fail:
 
    DPRINT1("Out Of MEMORY!!\n");
    POLYGONFILL_DestroyEdgeList ( list );
    return 0;
}

Referenced by FillPolygon(), and IntFillPolygon().

POLYGONFILL_UpdateScanline()

static void FASTCALL POLYGONFILL_UpdateScanline ( FILL_EDGE *  pEdge, int  Scanline  )

static

Definition at line 294 of file polyfill.c.

{
    if (0 == pEdge->dy)
        return;
 
    ASSERT(pEdge->FromY <= Scanline && pEdge->ToY > Scanline);
 
    if (pEdge->xmajor)
    {
        int steps;
 
        ASSERT(pEdge->y == Scanline);
 
        // Now shoot to end of scanline collision
        steps = (pEdge->ErrorMax-pEdge->Error-1)/pEdge->absdy;
        if (steps)
        {
            // Record first collision with scanline
            int x1 = pEdge->x;
            pEdge->x += steps * pEdge->XDirection;
            pEdge->Error += steps * pEdge->absdy;
            ASSERT ( pEdge->Error < pEdge->ErrorMax );
            pEdge->XIntercept[0] = min(x1,pEdge->x);
            pEdge->XIntercept[1] = max(x1,pEdge->x);
        }
        else
        {
            pEdge->XIntercept[0] = pEdge->x;
            pEdge->XIntercept[1] = pEdge->x;
        }
 
        // We should require exactly 1 step to step onto next scanline...
        ASSERT((pEdge->ErrorMax-pEdge->Error-1) / pEdge->absdy == 0);
        pEdge->x += pEdge->XDirection;
        pEdge->Error += pEdge->absdy;
        ASSERT(pEdge->Error >= pEdge->ErrorMax);
 
        // Now step onto next scanline...
        pEdge->Error -= pEdge->absdx;
        pEdge->y++;
    }
    else // Then this is a y-major line
    {
        pEdge->XIntercept[0] = pEdge->x;
        pEdge->XIntercept[1] = pEdge->x;
 
        pEdge->Error += pEdge->absdx;
        pEdge->y++;
 
        if (pEdge->Error >= pEdge->ErrorMax)
        {
            pEdge->Error -= pEdge->ErrorMax;
            pEdge->x += pEdge->XDirection;
            ASSERT ( pEdge->Error < pEdge->ErrorMax );
        }
    }
 
    //DPRINT("Line (%d, %d) to (%d, %d) intersects scanline %d at (%d,%d)\n",
    //        pEdge->FromX, pEdge->FromY, pEdge->ToX, pEdge->ToY, Scanline, pEdge->XIntercept[0], pEdge->XIntercept[1] );
}

Referenced by POLYGONFILL_BuildActiveList().