Something went wrong. Try again.
Reactos
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869// this is a little 'sandbox' application I put together that duplicates// the 'guts' of the Polygon algorithm. It allows for quick turn-around// in testing the algorithm to see what effect your changes have.//// Royce3
// the stuff immediately following is support so that the sandbox code// is nearly identical to the real thing.// search for the _tagFILL_EDGE struct to find the beginning of the// real stuff.
#include <memory.h>#include <malloc.h>#include <stdio.h>#include <string.h>#include <conio.h>#include <assert.h>
#define FASTCALL#define INT int#define CLIPOBJ int#define SURFOBJ int#define PBRUSHOBJ int#define MIX char#define BOOL bool#define TRUE true#define FALSE false#define CONST const#define MmCopyFromCaller memmove#define ALTERNATE 0#define WINDING 1
#define ASSERT assert
typedef struct W{ int polyFillMode;} W;
typedef struct DC{ CLIPOBJ CombinedClip; W w;} DC, *PDC;
typedef struct tagPOINT{ long x, y;} POINT, *PPOINT, *LPPOINT;
typedef struct RECTL{ long left, top, right, bottom;} RECTL, *PRECTL;
#define EngFreeMem free
#define FL_ZERO_MEMORY 1
#define DPRINT1 printf("%i:",__LINE__);printfinline void DPRINT(...){}
#define SCREENX 25#define SCREENY 15char screen[SCREENY][SCREENX];
#define EDGE_CHAR '*'#define FILL_CHAR 'o'
void* EngAllocMem ( int zero, unsigned long size, int tag=0 ){ void* p = malloc ( size ); if ( zero ) memset ( p, 0, size ); return p;}
template <class T>inline T MIN ( T a, T b ){ return a < b ? a : b;}
template <class T>inline T MAX ( T a, T b ){ return a > b ? a : b;}
template <class T>inline T abs ( T t ){ return t < 0 ? -t : t;}
void putpixel ( int x, int y, char c ){ ASSERT( x >= 0 && x < SCREENX && y >= 0 && y < SCREENY ); if ( screen[y][x] == c ) return; if ( screen[y][x] == ' ' ) screen[y][x] = c; else screen[y][x] = '#';}
void IntEngLineTo ( SURFOBJ*, CLIPOBJ, PBRUSHOBJ, int x1, int y1, int x2, int y2, RECTL*, MIX mix ){ int dx = x2 - x1; int dy = y2 - y1; int absdx = abs(dx); int absdy = abs(dy); int EMax = MAX(absdx,absdy); int E = EMax/2; int xinc = dx < 0 ? -1 : 1, yinc = dy < 0 ? -1 : 1; if ( !dy ) { while ( x1 != x2 ) { putpixel ( x1, y1, mix ); x1 += xinc; } return; } if ( !dx ) { while ( y1 != y2 ) { putpixel ( x1, y1, mix ); y1 += yinc; } return; } for ( int i = 0; i < EMax; i++ ) { putpixel ( x1, y1, mix ); if ( absdy > absdx ) { y1 += yinc; E += absdx; if ( E >= EMax ) { E -= absdy; x1 += xinc; } } else { x1 += xinc; E += absdy; if ( E >= EMax ) { E -= absdx; y1 += yinc; } } }}
#define FILL_EDGE_ALLOC_TAG 0x45465044
/*** This struct is used for book keeping during polygon filling routines.*/typedef struct _tagFILL_EDGE{ /*Basic line information*/ int FromX; int FromY; int ToX; int ToY; int dx; int dy; int absdx, absdy; int x, y; int xmajor;
/*Active Edge List information*/ int XIntercept[2]; int Error; int ErrorMax; int XDirection, YDirection;
/* The next edge in the active Edge List*/ struct _tagFILL_EDGE * pNext;} FILL_EDGE;
typedef struct _FILL_EDGE_LIST{ int Count; FILL_EDGE** Edges;} FILL_EDGE_LIST;
#if 0staticvoidDEBUG_PRINT_ACTIVE_EDGELIST ( FILL_EDGE* list ){ FILL_EDGE* pThis = list; if (0 == list) { DPRINT1("List is NULL\n"); return; }
while(0 != pThis) { //DPRINT1("EDGE: (%d, %d) to (%d, %d)\n", pThis->FromX, pThis->FromY, pThis->ToX, pThis->ToY); DPRINT1("EDGE: [%d,%d]\n", pThis->XIntercept[0], pThis->XIntercept[1] ); pThis = pThis->pNext; }}#else#define DEBUG_PRINT_ACTIVE_EDGELIST(x)#endif
/*** Hide memory clean up.*/staticvoidFASTCALLPOLYGONFILL_DestroyEdgeList(FILL_EDGE_LIST* list){ int i; if ( list ) { if ( list->Edges ) { for ( i = 0; i < list->Count; i++ ) { if ( list->Edges[i] ) EngFreeMem ( list->Edges[i] ); } EngFreeMem ( list->Edges ); } EngFreeMem ( list ); }}
/*** This makes and initiaizes an Edge struct for a line between two points.*/staticFILL_EDGE*FASTCALLPOLYGONFILL_MakeEdge(POINT From, POINT To){ 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;}/*** My Edge comparison routine.** This is for scan converting polygon fill.** First sort by MinY, then Minx, then slope.**** This comparison will help us determine which** lines will become active first when scanning from** top (min y) to bottom (max y).**** Return Value Meaning** Negative integer element1 < element2** Zero element1 = element2** Positive integer element1 > element2*/staticINTFASTCALLFILL_EDGE_Compare(FILL_EDGE* Edge1, FILL_EDGE* Edge2){ int e1 = Edge1->XIntercept[0] + Edge1->XIntercept[1]; int e2 = Edge2->XIntercept[0] + Edge2->XIntercept[1];
return e1 - e2;}
/*** Insert an edge into a list keeping the list in order.*/staticvoidFASTCALLPOLYGONFILL_ActiveListInsert(FILL_EDGE** activehead, FILL_EDGE* NewEdge ){ 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);}
/*** Create a list of edges for a list of points.*/staticFILL_EDGE_LIST*FASTCALLPOLYGONFILL_MakeEdgeList(PPOINT Points, int Count){ 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;}
/*** This slow routine uses the data stored in the edge list to** calculate the x intercepts for each line in the edge list** for scanline Scanline.**TODO: Get rid of this floating point arithmetic*/staticvoidFASTCALLPOLYGONFILL_UpdateScanline(FILL_EDGE* pEdge, int Scanline){ 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] );}
/*** This method updates the Active edge collection for the scanline Scanline.*/staticvoidPOLYGONFILL_BuildActiveList ( int Scanline, FILL_EDGE_LIST* list, FILL_EDGE** ActiveHead ){ 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 ); } }}
/*** This method fills the portion of the polygon that intersects with the scanline** Scanline.*/staticvoidPOLYGONFILL_FillScanLineAlternate( PDC dc, int ScanLine, FILL_EDGE* ActiveHead, SURFOBJ *SurfObj, PBRUSHOBJ BrushObj, MIX RopMode ){ 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( SurfObj, dc->CombinedClip, BrushObj, x1, ScanLine, x2, ScanLine, &BoundRect, // Bounding rectangle RopMode); // MIX } pLeft = pRight->pNext; pRight = pLeft ? pLeft->pNext : NULL; }}
staticvoidPOLYGONFILL_FillScanLineWinding( PDC dc, int ScanLine, FILL_EDGE* ActiveHead, SURFOBJ *SurfObj, PBRUSHOBJ BrushObj, MIX RopMode ){ 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( SurfObj, dc->CombinedClip, 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( SurfObj, dc->CombinedClip, BrushObj, x1, ScanLine, x2, ScanLine, &BoundRect, // Bounding rectangle RopMode); // MIX}
//When the fill mode is ALTERNATE, GDI fills the area between odd-numbered and//even-numbered polygon sides on each scan line. That is, GDI fills the area between the//first and second side, between the third and fourth side, and so on.
//WINDING Selects winding mode (fills any region with a nonzero winding value).//When the fill mode is WINDING, GDI fills any region that has a nonzero winding value.//This value is defined as the number of times a pen used to draw the polygon would go around the region.//The direction of each edge of the polygon is important.
BOOLFillPolygon( PDC dc, SURFOBJ *SurfObj, PBRUSHOBJ BrushObj, MIX RopMode, CONST PPOINT Points, int Count, RECTL BoundRect ){ FILL_EDGE_LIST *list = 0; FILL_EDGE *ActiveHead = 0; int ScanLine;
void (*FillScanLine)( PDC dc, int ScanLine, FILL_EDGE* ActiveHead, SURFOBJ *SurfObj, PBRUSHOBJ 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 == dc->w.polyFillMode ) 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, SurfObj, BrushObj, RopMode ); }
/* Free Edge List. If any are left. */ POLYGONFILL_DestroyEdgeList(list);
return TRUE;}
// this is highly hacked from W32kPolygon...BOOLPolygon ( CONST PPOINT UnsafePoints, int Count, int polyFillMode ){ BOOL ret; RECTL DestRect; int CurrentPoint; PPOINT Points; SURFOBJ* SurfObj = 0; DC dc; PBRUSHOBJ OutBrushObj = 0;
dc.CombinedClip = 0; dc.w.polyFillMode = polyFillMode;
DPRINT1("In W32kPolygon()\n");
if ( NULL == UnsafePoints || Count < 2) { DPRINT1("ERROR_INVALID_PARAMETER\n"); return FALSE; }
/* Copy points from userspace to kernelspace */ Points = (PPOINT)EngAllocMem(0, Count * sizeof(POINT)); if (NULL == Points) { DPRINT1("ERROR_NOT_ENOUGH_MEMORY\n"); return FALSE; } MmCopyFromCaller(Points, UnsafePoints, Count * sizeof(POINT)); if ( memcmp ( Points, UnsafePoints, Count * sizeof(POINT) ) ) { free(Points); return FALSE; }
DestRect.left = Points[0].x; DestRect.right = Points[0].x; DestRect.top = Points[0].y; DestRect.bottom = Points[0].y;
for (CurrentPoint = 1; CurrentPoint < Count; ++CurrentPoint) { DestRect.left = MIN(DestRect.left, Points[CurrentPoint].x); DestRect.right = MAX(DestRect.right, Points[CurrentPoint].x); DestRect.top = MIN(DestRect.top, Points[CurrentPoint].y); DestRect.bottom = MAX(DestRect.bottom, Points[CurrentPoint].y); }
// Draw the Polygon Edges with the current pen for (CurrentPoint = 0; CurrentPoint < Count; ++CurrentPoint) { POINT To, From; //, Next;
/* Let CurrentPoint be i * if i+1 > Count, Draw a line from Points[i] to Points[0] * Draw a line from Points[i] to Points[i+1] */ From = Points[CurrentPoint]; if ( CurrentPoint + 1 >= Count) { To = Points[0]; } else { To = Points[CurrentPoint + 1]; }
DPRINT1("Polygon Making line from (%ld,%ld) to (%ld,%ld)\n", From.x, From.y, To.x, To.y ); IntEngLineTo(SurfObj, dc.CombinedClip, OutBrushObj, From.x, From.y, To.x, To.y, &DestRect, EDGE_CHAR); /* MIX */ } /* determine the fill mode to fill the polygon. */ ret = FillPolygon(&dc, SurfObj, OutBrushObj, FILL_CHAR, Points, Count, DestRect ); free(Points);
return ret;}
int main(){ memset ( screen, ' ', sizeof(screen) ); POINT pts[] = {#if 0 { 0, 0 }, { 12, 4 }, { 4, 8 },#elif 0 { 3, 0 }, { 0, 3 }, { 3, 6 },#elif 0 { 1, 1 }, { 3, 1 }, { 3, 3 }, { 1, 3 }#elif 0 { 0, 0 }, { 4, 0 }, { 4, 4 }, { 8, 4 }, { 8, 8 }, { 4, 8 }, { 4, 4 }, { 0, 4 },#else { 4, 12 }, { 12, 0 }, { 18, 12 }, { 4, 4 }, { 20, 4 }#endif }; const int pts_count = sizeof(pts)/sizeof(pts[0]);
// use ALTERNATE or WINDING for 3rd param Polygon ( pts, pts_count, ALTERNATE );
// print out our "screen" for ( int y = 0; y < SCREENY; y++ ) { for ( int x = 0; x < SCREENX; x++ ) { printf("%c", screen[y][x] ); } printf("\n"); } DPRINT1("Done!\n"); (void)_getch();}/* EOF */