Jump to content
  • Advertisement
Sign in to follow this  
kreyszig_rocks

problem with filling polygon using bresenhams algorithm

This topic is 4892 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hi all, i have a very annoying problem when filling a four sided poly using bresenhams algorithm to create an array of scanline end points. Specifically, I'm getting the problem when interpolating vertex colours; the screen coordinates are coming out fine. The problem is that some polygons are getting 'stepped' results - the colours do not blend perfectly smoothly.(ie i have bands of colour) The wierd thing is that an adjacent polygon which (duh) shares the same edge is filled fine (perfectly smooth that is). I can post code if it helps, but thought maybe some of you had come across this before. I thought it may have something to do with rounding, as I cast my rgb values as floats as well as the gradient of each colour wrt the direction i'm moving in to fill the edge array. I then round the values back to ints using this: #define round(x) ((x)>=0?(long)((x)+0.5):(long)((x)-0.5)) when I assign them to the array. Oh, dammit i might as well post the code here now. I'm writing in C and using SDL fyi. Another thing I thought it might be is some difference between the Dx > Dy and Dx < Dy code, but that doesn't really make sense, given that an adjacent polygon fills ok. thanks for any help you can offer, i'm stumped on this one
void fill_edgearray(fill_line *pointarray,edge e, int miny, int maxy)
{
	int x1,y1,x2,y2;
	int bx, by, dx, dy, xsign, ysign, p, const1, const2;
	float dr, dg, db; /*slopes of the rgb parts of a colour*/
	float r,g,b; /*current rgb values */
	colour current_col;
	
	
	x1 = e.points[0].x;
	x2 = e.points[1].x;
	y1 = e.points[0].y;
	y2 = e.points[1].y;

	bx = x1;		/*b represents current value */
	by = y1;
	dx = (x2 - x1);
	dy = (y2 - y1);
	/*initialise colours*/
	r = float(e.points[0].col.red);
	g = float(e.points[0].col.green);
	b = float(e.points[0].col.blue);
	/*set up the intial colour*/
	set_colour(¤t_col,round(r),round(g),round(b));

	if(dy==0) /* horizontal*/
	{
		/* don't do anything at the moment as we don't add horizontal lines to scanline array */
	}
	else if (dx == 0) /* vertical line*/
	{
		dr = float(e.points[1].col.red - e.points[0].col.red)/float(dy);
		dg = float(e.points[1].col.green - e.points[0].col.green)/float(dy);
		db = float(e.points[1].col.blue - e.points[0].col.blue)/float(dy);
		ysign = dy /abs(dy);
		add_fill_line(&pointarray[by-miny], bx,current_col);
		while(by != y2)
		{
			by+=ysign;
			r+=dr;
			g+=dg;
			b+=db;
			set_colour(¤t_col,round(r),round(g),round(b));
			add_fill_line(&pointarray[by-miny], bx,current_col);
		}
	}
	else	/*bresenhal algo starts here*/
	{
		xsign = dx/abs(dx);
		ysign = dy/abs(dy);
		
		dx = abs(dx);
		dy = abs(dy);

		if (by != maxy)
			add_fill_line(&pointarray[by-miny], bx,current_col); /*initial point on line*/
		if (dx < dy) /*more vertical than horizontal*/
		{
			/*initialise color slope variables*/
			dr = float(e.points[1].col.red - e.points[0].col.red)/float(dy);
			dg = float(e.points[1].col.green - e.points[0].col.green)/float(dy);
			db = float(e.points[1].col.blue - e.points[0].col.blue)/float(dy);

			p = 2*dx - dy;
			const1 = 2*dx;
			const2 = 2* (dx - dy);
			while (by != y2)
			{
				by = by + ysign;
				r+=dr;
				g+=dg;
				b+=db;
				if(p < 0){
					p = p + const1;
				}
				else
				{
					p = p + const2;
					bx = bx + xsign;
					set_colour(¤t_col,round(r),round(g),round(b));					
				}
				if (by != maxy)
					add_fill_line(&pointarray[by-miny], bx,current_col);
			}
			
		}
		else /*more horizontal than vertical*/
		{
			/*initialise color slope variables*/
			dr = float(e.points[1].col.red - e.points[0].col.red)/float(dx);
			dg = float(e.points[1].col.green - e.points[0].col.green)/float(dx);
			db = float(e.points[1].col.blue - e.points[0].col.blue)/float(dx);
			
			p = 2*dy - dx;
			const1 = 2*dy;
			const2 = 2*(dy - dx);
			while (bx != x2)
			{
				bx = bx + xsign;
				r+=dr;
				g+=dg;
				b+=db;
				if(p < 0){
					p = p + const1;
				}
				else{
					p = p + const2;
					by = by + ysign;
					set_colour(¤t_col,round(r),round(g),round(b));
				}
				if (by != maxy)
					add_fill_line(&pointarray[by-miny], bx,current_col);
			}
			
		}
	}
}

Share this post


Link to post
Share on other sites
Advertisement
well isn't that funny, asking for help can be the best kind of help itself. silly me, I wasn't assigning the colour values to my colour struct unless the Y/X value had changed. sorry for wasting your time!

Share this post


Link to post
Share on other sites
for future reference, use the source tags instead of code tags for that much code.

#define round(x) ((x)&gt;=0?(long)((x)+0.5):(long)((x)-0.5))

void fill_edgearray(fill_line *pointarray,edge e, int miny, int maxy)
{
int x1,y1,x2,y2;
int bx, by, dx, dy, xsign, ysign, p, const1, const2;
float dr, dg, db; /*slopes of the rgb parts of a colour*/
float r,g,b; /*current rgb values */
colour current_col;


x1 = e.points[0].x;
x2 = e.points[1].x;
y1 = e.points[0].y;
y2 = e.points[1].y;

bx = x1; /*b represents current value */
by = y1;
dx = (x2 - x1);
dy = (y2 - y1);
/*initialise colours*/
r = float(e.points[0].col.red);
g = float(e.points[0].col.green);
b = float(e.points[0].col.blue);
/*set up the intial colour*/
set_colour(&current_col,round(r),round(g),round(b));

if(dy==0) /* horizontal*/
{
/* don't do anything at the moment as we don't add horizontal lines to scanline array */
}
else if (dx == 0) /* vertical line*/
{
dr = float(e.points[1].col.red - e.points[0].col.red)/float(dy);
dg = float(e.points[1].col.green - e.points[0].col.green)/float(dy);
db = float(e.points[1].col.blue - e.points[0].col.blue)/float(dy);
ysign = dy /abs(dy);
add_fill_line(&pointarray[by-miny], bx,current_col);
while(by != y2)
{
by+=ysign;
r+=dr;
g+=dg;
b+=db;
set_colour(&current_col,round(r),round(g),round(b));
add_fill_line(&pointarray[by-miny], bx,current_col);
}
}
else /*bresenhal algo starts here*/
{
xsign = dx/abs(dx);
ysign = dy/abs(dy);

dx = abs(dx);
dy = abs(dy);

if (by != maxy)
add_fill_line(&pointarray[by-miny], bx,current_col); /*initial point on line*/
if (dx &lt; dy) /*more vertical than horizontal*/
{
/*initialise color slope variables*/
dr = float(e.points[1].col.red - e.points[0].col.red)/float(dy);
dg = float(e.points[1].col.green - e.points[0].col.green)/float(dy);
db = float(e.points[1].col.blue - e.points[0].col.blue)/float(dy);

p = 2*dx - dy;
const1 = 2*dx;
const2 = 2* (dx - dy);
while (by != y2)
{
by = by + ysign;
r+=dr;
g+=dg;
b+=db;
if(p &lt; 0){
p = p + const1;
}
else
{
p = p + const2;
bx = bx + xsign;
set_colour(&current_col,round(r),round(g),round(b));
}
if (by != maxy)
add_fill_line(&pointarray[by-miny], bx,current_col);
}

}
else /*more horizontal than vertical*/
{
/*initialise color slope variables*/
dr = float(e.points[1].col.red - e.points[0].col.red)/float(dx);
dg = float(e.points[1].col.green - e.points[0].col.green)/float(dx);
db = float(e.points[1].col.blue - e.points[0].col.blue)/float(dx);

p = 2*dy - dx;
const1 = 2*dy;
const2 = 2*(dy - dx);
while (bx != x2)
{
bx = bx + xsign;
r+=dr;
g+=dg;
b+=db;
if(p &lt; 0){
p = p + const1;
}
else{
p = p + const2;
by = by + ysign;
set_colour(&current_col,round(r),round(g),round(b));
}
if (by != maxy)
add_fill_line(&pointarray[by-miny], bx,current_col);
}

}
}
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!