Trapezoid Filling

[A_SN]

Hi,

I have just implemented a simple isometric 3D engine that displays cubes, and in order to fill the sides of cubes, I use a Bresenham line function that I modified so that instead of write pixels everytime it iterates, it calls a simple Bresenham line function to draw lines parallel to the two other sides of the trapezoid. Unfortunately, it leaves some pixels out in certain cases.

I have tried filling by triangles instead, but it's worse. Any ideas?

 

[hal9000]

That is a very, very crazy way to fill a polygon. What you should do is filling triangles row-by-row. Drawing an horizontal line is just filling a segment of memory, which is many times faster than your Bresenham algorithm. And it does not let "holes" everywhere.

Seriously, I don't think you should write such a program anyway. It has been written thousands of times. Find existing code, or better: use existing lib. Learn OpenGL, and use GPU 940, for example. That will be much faster and much more efficient, and will let you more time for the higher level parts.

 

[A_SN]

That is a very, very crazy way to fill a polygon. What you should do is filling triangles row-by-row. Drawing an horizontal line is just filling a segment of memory, which is many times faster than your Bresenham algorithm. And it does not let "holes" everywhere.

Interesting. But how do I do that?

QUOTE

Seriously, I don't think you should write such a program anyway. It has been written thousands of times. Find existing code, or better: use existing lib. Learn OpenGL, and use GPU 940, for example. That will be much faster and much more efficient, and will let you more time for the higher level parts.



No no, I'm not trying to make some engine or anything, I just need a couple of pixel art isometric varying-geometry cubes in my little pong game, I'm not gonna start using OpenGL for that!

 

[hal9000]

Interesting. But how do I do that?

The classical algorithm for this is called scanline algorithm (you can google it). But in your case, if you can already draw your edges, I would say that there is an easier way.

For each polygon, you store for each Y the minimum and maximum values of X such that (X,Y) is a point of one of the edges. You can get all the coordinates of all edge points using your Breseham procedure.

Then you draw all lines (Xmin,Y)-(Xmax,Y).

Of course it will not be extremely efficient, but it should be a minimal effort considering what you've already done.

 

[Lazrhog]

Try this for a description of the algorithm you want

http://www-users.mat.uni.torun.pl/~wrona/3...ri_fillers.html

 

[A_SN]

Try this for a description of the algorithm you want

http://www-users.mat.uni.torun.pl/~wrona/3...ri_fillers.html



Ewww, dude, did you see these divisions in the code? Anyways, the concept presented in this page still helps. So I think I'll just modify my Bresenham line function so that it creates a 1D array which index would represent an offset value for Y, and which contents would be, as hal9000 said, Xmin and Xmax.

Just realized that I just said what hal9000 has said

 

[Exophase]

Try this for a description of the algorithm you want

http://www-users.mat.uni.torun.pl/~wrona/3...ri_fillers.html



Ewww, dude, did you see these divisions in the code? Anyways, the concept presented in this page still helps. So I think I'll just modify my Bresenham line function so that it creates a 1D array which index would represent an offset value for Y, and which contents would be, as hal9000 said, Xmin and Xmax.

Just realized that I just said what hal9000 has said


There's no reason to make arrays, you can just get the endpoints as you go and draw trapezoid incrementially. Just iterate the two edges using Bresenham's and draw a horizontal line between them (you can optimize this easily if you want speed).

 

[A_SN]

Try this for a description of the algorithm you want

http://www-users.mat.uni.torun.pl/~wrona/3...ri_fillers.html



Ewww, dude, did you see these divisions in the code? Anyways, the concept presented in this page still helps. So I think I'll just modify my Bresenham line function so that it creates a 1D array which index would represent an offset value for Y, and which contents would be, as hal9000 said, Xmin and Xmax.

Just realized that I just said what hal9000 has said


There's no reason to make arrays, you can just get the endpoints as you go and draw trapezoid incrementially. Just iterate the two edges using Bresenham's and draw a horizontal line between them (you can optimize this easily if you want speed).


I just don't see how I'm gonna modify a Bresenham function into obtaining Xmin and Xmax at the same time actually..

 

[rokdcasbah]

this might be useful:

http://www.gamedev.net/reference/articles/article663.asp

 

[Daid]

I found this horribly function in a very old test of mine (made over 2 years ago)
It fills triangles in a single color. It's filled with assumptions, like that the surface it draws on is 32bit and that the screen is 640x480.

Might give you a starting point.
CODE
typedef struct
{
int X,Y;
} sScreenPos;

void DrawPoly(sScreenPos P1, sScreenPos P2, sScreenPos P3, Uint32 Color)
{
sScreenPos TmpPos;

if (P2.Y < P1.Y)
{
TmpPos = P1;
P1 = P2;
P2 = TmpPos;
}
if (P3.Y < P1.Y)
{
TmpPos = P1;
P1 = P3;
P3 = TmpPos;
}
if (P3.Y < P2.Y)
{
TmpPos = P2;
P2 = P3;
P3 = TmpPos;
}

int X;
int From;
int To;
int i;
Uint8 *p;

for(int Y=(P1.Y < 0 ? 0 : P1.Y); Y<P2.Y && Y<480; Y++)
{
From = (Y-P1.Y)*(P2.X-P1.X)/(P2.Y-P1.Y)+P1.X;

if (P3.Y == P1.Y)
To = P3.X;
else
To = (Y-P1.Y)*(P3.X-P1.X)/(P3.Y-P1.Y)+P1.X;

if (From > To)
{
i = To;
To = From;
From = i;
}
if (From < 0)
From = 0;
if (To > 639)
To = 639;

p = (Uint8 *)Screen->pixels + Y * Screen->pitch + From*4;

for(X=From;X<=To;X++)
{
*(Uint32 *)p = Color;
p += 4;
}
}

int XatP2 = (P3.Y == P1.Y ? P1.X : (Y-P1.Y)*(P3.X-P1.X)/(P3.Y-P1.Y)+P1.X);

for(Y=(P2.Y<0 ? 0 : P2.Y); Y<P3.Y && Y<480; Y++)
{
if (P3.Y == P2.Y)
From = P2.X;
else
From = (Y-P2.Y)*(P3.X-P2.X)/(P3.Y-P2.Y)+P2.X;

if (P3.Y == P2.Y)
To = P3.X;
else
To = (Y-P2.Y)*(P3.X-XatP2)/(P3.Y-P2.Y)+XatP2;

if (From > To)
{
i = To;
To = From;
From = i;
}
if (From < 0)
From = 0;
if (To > 639)
To = 639;

p = (Uint8 *)Screen->pixels + Y * Screen->pitch + From*4;

for(X=From;X<=To;X++)
{
*(Uint32 *)p = Color;
p += 4;
}
}
}

 

[A_SN]

I found this horribly function in a very old test of mine (made over 2 years ago)
It fills triangles in a single color. It's filled with assumptions, like that the surface it draws on is 32bit and that the screen is 640x480.

Might give you a starting point.
CODE
typedef struct
{
int X,Y;
} sScreenPos;

void DrawPoly(sScreenPos P1, sScreenPos P2, sScreenPos P3, Uint32 Color)
{
sScreenPos TmpPos;

if (P2.Y < P1.Y)
{
TmpPos = P1;
P1 = P2;
P2 = TmpPos;
}
if (P3.Y < P1.Y)
{
TmpPos = P1;
P1 = P3;
P3 = TmpPos;
}
if (P3.Y < P2.Y)
{
TmpPos = P2;
P2 = P3;
P3 = TmpPos;
}

int X;
int From;
int To;
int i;
Uint8 *p;

for(int Y=(P1.Y < 0 ? 0 : P1.Y); Y<P2.Y && Y<480; Y++)
{
From = (Y-P1.Y)*(P2.X-P1.X)/(P2.Y-P1.Y)+P1.X;

if (P3.Y == P1.Y)
To = P3.X;
else
To = (Y-P1.Y)*(P3.X-P1.X)/(P3.Y-P1.Y)+P1.X;

if (From > To)
{
i = To;
To = From;
From = i;
}
if (From < 0)
From = 0;
if (To > 639)
To = 639;

p = (Uint8 *)Screen->pixels + Y * Screen->pitch + From*4;

for(X=From;X<=To;X++)
{
*(Uint32 *)p = Color;
p += 4;
}
}

int XatP2 = (P3.Y == P1.Y ? P1.X : (Y-P1.Y)*(P3.X-P1.X)/(P3.Y-P1.Y)+P1.X);

for(Y=(P2.Y<0 ? 0 : P2.Y); Y<P3.Y && Y<480; Y++)
{
if (P3.Y == P2.Y)
From = P2.X;
else
From = (Y-P2.Y)*(P3.X-P2.X)/(P3.Y-P2.Y)+P2.X;

if (P3.Y == P2.Y)
To = P3.X;
else
To = (Y-P2.Y)*(P3.X-XatP2)/(P3.Y-P2.Y)+XatP2;

if (From > To)
{
i = To;
To = From;
From = i;
}
if (From < 0)
From = 0;
if (To > 639)
To = 639;

p = (Uint8 *)Screen->pixels + Y * Screen->pitch + From*4;

for(X=From;X<=To;X++)
{
*(Uint32 *)p = Color;
p += 4;
}
}
}

Thanks but I'm done . And ewww, divisions..