Polygon filling

Anybody know of a library that handles arbitrary polygon filling? I
have only found them for lines, triangles, circles etc. and I really
don’t want to write my own. :slight_smile:

Thanks

p

well, each polygon can be broken into a series of triangles. Software
implementations of 3d engines do it this way so id be fairly confident
saying that is the most efficient way to do it. You might consider doing
that (:

other than that…no i dont :P> ----- Original Message -----

From: pchans@wm.edu ()
To:
Sent: Saturday, September 21, 2002 7:53 PM
Subject: [SDL] polygon filling

Anybody know of a library that handles arbitrary polygon filling? I
have only found them for lines, triangles, circles etc. and I really
don’t want to write my own. :slight_smile:

Thanks

p


SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl

Anybody know of a library that handles arbitrary polygon filling? I
have only found them for lines, triangles, circles etc. and I really
don’t want to write my own. :slight_smile:

Basically you do the same thing as for lines or circles. You iterate
over the edge-pixels and draw a horizontal line from one pixel to the
other. Well - this works for konvex Polygons, but not for concav
(S-Shape) or intersecting polygons (5-edged star).
To write this on your own would be rather tricky (I did once - scaaary
thing =) and I guess the way Alan suggested is probably one of the
smoothest, because triangles are always convex. Anyways finding the
triangles is still a bit tricky, too.

Search google for “polygon filling” - there are quite many tutorials on it.

Ciao
Arne

You wrote:

Anybody know of a library that handles arbitrary polygon filling? I
have only found them for lines, triangles, circles etc. and I really
don’t want to write my own. :slight_smile:

You can try this:

#define MaxPoints 50

void FilledPolygon(int NumPoints,int Pointsx[],int Pointsy[])
{
struct all_edges{
int ymin;
int ymax;
float x;
float m;
} *Edges[MaxPoints];

if (NumPoints > 0) {
int i,succ;
for(i=0;(i<NumPoints);i++) {
if (i == (NumPoints-1)) succ = 0;
else succ = i+1;
if ((Pointsy[succ]-Pointsy[i]) != 0) {
Edges[i] = (all_edges *) malloc(sizeof(all_edges));
Edges[i]->ymin=Mini(Pointsy[i],Pointsy[succ]);
Edges[i]->ymax=Maxi(Pointsy[i],Pointsy[succ]);
if (Edges[i]->ymin == Pointsy[i]) Edges[i]->x=Pointsx[i];
else Edges[i]->x=Pointsx[succ];
Edges[i]->m=((float)(Pointsx[succ]-Pointsx[i]))/
(Pointsy[succ]-Pointsy[i]);
}
else Edges[i]=NULL;
}
int j,t,m;
bool found;
all_edges *Global[MaxPoints];
for(i=t=0;(i<NumPoints);i++) {
if (Edges[i]!=NULL) {
found = false;
Global[t] = Edges[i];
for(j=0;((j<t) && (!found));j++) {
if ((Global[t]->ymin < Global[j]->ymin) ||
((Global[t]->ymin == Global[j]->ymin) &&
(Global[t]->x < Global[j]->x)) ||
((Global[t]->ymin == Global[j]->ymin) &&
(((int)Global[t]->x) == ((int)Global[j]->x))
&& (Global[t]->ymax < Global[j]->ymax)))
found = true;
}
if (found) {
all_edges *TempEdges = (all_edges *) malloc(sizeof(all_edges));
TempEdges->ymin = Global[t]->ymin;
TempEdges->ymax = Global[t]->ymax;
TempEdges->x = Global[t]->x;
TempEdges->m = Global[t]->m;
for(m=t;(m>=j);m–) {
Global[m]->ymin = Global[m-1]->ymin;
Global[m]->ymax = Global[m-1]->ymax;
Global[m]->x = Global[m-1]->x;
Global[m]->m = Global[m-1]->m;
}
Global[m]->ymin = TempEdges->ymin;
Global[m]->ymax = TempEdges->ymax;
Global[m]->x = TempEdges->x;
Global[m]->m = TempEdges->m;
free(TempEdges);
}
t++;
}
}
int NumEdges = t;
if (NumEdges > 0) {
int ScanLine = Global[0]->ymin;
int MaxScanLine = ScanLine;
for(i=1;i<NumEdges;i++) {
if (Global[i]->ymax > MaxScanLine) MaxScanLine = Global[i]->ymax;
}
int xmin,xmax;
xmin = xmax = (int) Global[0]->x;
for(i=1;i<NumEdges;i++) {
if (Global[i]->x < xmin) xmin = (int) Global[i]->x;
if (Global[i]->x > xmax) xmax = (int) Global[i]->x;
}
for(i=0;i<NumPoints;i++) Edges[i] = NULL;
t = 0;
while((t<NumEdges) && (Global[t]->ymin == ScanLine)) {
Edges[t] = Global[t];
Global[t] = NULL;
t++;
}
int NumActive = t;
while(ScanLine<MaxScanLine) {
for(j=0;j<NumActive;j++) {
if (j != (NumActive-1))
Line ((int)(Edges[j]->x),ScanLine,
(int)(Edges[j+1]->x),ScanLine);
j++;
}
ScanLine++;
for(j=0;j<NumActive;j++) {
if (Edges[j]->ymax == ScanLine) {
free(Edges[j]);
Edges[j] = NULL;
}
}
for(j=t=0;j<NumActive;j++) {
if (Edges[j] != NULL) {
if (t != j) {
Edges[t] = Edges[j];
Edges[j] = NULL;
}
t++;
}
}
NumActive = t;
for(j=0;j<NumActive;j++)
Edges[j]->x += Edges[j]->m;
for(j=0;j<NumEdges;j++) {
if (Global[j] != NULL) {
if (Global[j]->ymin == ScanLine) {
Edges[NumActive] = Global[j];
Global[j] = NULL;
NumActive++;
}
}
}
for(i=0;(i<NumActive);i++) {
found = false;
for(j=0;((j<i) && (!found));j++) {
if ((Edges[i]->x < Edges[j]->x) ||
((Edges[i]->x == Edges[j]->x) &&
(Edges[i]->ymax < Edges[i]->ymax)))
found = true;
}
if (found) {
all_edges *TempEdges = (all_edges *) malloc(sizeof(all_edges));
TempEdges->ymin = Edges[i]->ymin;
TempEdges->ymax = Edges[i]->ymax;
TempEdges->x = Edges[i]->x;
TempEdges->m = Edges[i]->m;
for(m=i;(m>=j);m–) {
Edges[m]->ymin = Edges[m-1]->ymin;
Edges[m]->ymax = Edges[m-1]->ymax;
Edges[m]->x = Edges[m-1]->x;
Edges[m]->m = Edges[m-1]->m;
}
Edges[m]->ymin = TempEdges->ymin;
Edges[m]->ymax = TempEdges->ymax;
Edges[m]->x = TempEdges->x;
Edges[m]->m = TempEdges->m;
free(TempEdges);
}
}
}
}
}
}