Drawing Line Bresenhem midpoint algorithm

Hey guys, I’ve spend way too much time trying to make Bresenhem’s midpoint line algorithm to work in every octant. Can someone pleaseee edit my code so it work on all 8 octants. Right now it only work in octant 1,2,4,5, and 8. I count the octants from 1 - 8 counter-clockwise starting right above the positive X-axis. I think i’ve complicated things!!! helpppp!! You can even completely switch up my code if you want to, I’ve 30 hours on something that shouldn’t take me more than 5 hours.

void drawLine(int Ax, int Ay, int Bx, int By)
{
int y,x, dy, dx, slope, decision, incE, incNE;

int temp;


if (Ax > Bx)
{
	temp = Ax;

	Ax = Bx;
	Bx = temp;
	temp = Ay;
	Ay = By;
	By = temp;	 

}
	
 dx = Bx - Ax;
       dy = By - Ay;

 if (dy < 0)
       {
           slope = -1;
           dy = -dy;
       }
       else
       {
           slope = 1;
       }

	
if(Ay == By)
{	
	y = Ay;	
	   for (x = Ax; x != Bx; x++)	
		setCell(x,y,0.4,0.7,1.0);
	return;
			 
	
}
    
 if(Ax == Bx)
{	
	x = Ax;
	if(Ay > By)
	{
		temp = Ay;
		Ay = By;
		By = temp;
	}
	
	for (y = Ay; y<= By; y++)
		setCell(x,y,0.4,0.7,1.0);
	return;
	
}	 



       incE = 2 * dy;
       incNE = 2 * dy - 2 * dx;
       decision = 2 * dy - dx;


  
if( dy > dx)
{	
	
	incE = 2*dx;
	incNE = 2*dx - 2 *dy;
	x = Ax;
	printf("test1

");
for (y = Ay; y <= By; y++)
{
setCell(x,y, 0.4, 0.7, 1.0);
if (decision <= 0)
decision += incE;

           		else
          		 {
				
				decision += incNE;
				x++;	

         		  }
    	   }
	return;
}	




    
y = Ay;
for (x = Ax; x &lt;= Bx; x++)
       {
           setCell(x,y, 0.4, 0.7, 1.0);
           if (decision &lt;= 0)
           {
               decision += incE;
           }
           else
           {
               decision += incNE;
               y += slope;
           }
       }

HI…

I’m not sure but i think this logic should work out…

for a given point (x,y), you can obtain four points in four quadrants by changing signs… i.e.
(x,y)
(-x,y)
(-x,-y), and
(x,-y)

to get other four points u can use
_x = x/2;
_y = y*2;

now again by changing sign as shown above, you can obtain other four points…

so all together u’ll obtain eight points in eight octants… I may be wrong also… dont rely on me… wait for some senior person’s suggestions…

Good luck


#define ABS(x)	(x < 0 ? -x : x)
#define SIGN	(x < 0 ? -1 : (x > 0 ? 1 : 0))

void DrawLine(int x1,int y1,int x2,int y2)
{
	int	dx,dy,sx,sy;
	int	accum;

	dx = x2 - x1;
	dy = y2 - y1;

	sx = SIGN(dx);
	sy = SIGN(dy);

	dx = ABS(dx);
	dy = ABS(dy);

	x2 += sx;
	y2 += sy;

	if(dx > dy)
	{
		accum = dx >> 1;
		do{
			setCell(x1,y1, 0.4, 0.7, 1.0);

			accum -= dy;
			if(accum < 0)
			{
				accum += dx;
				y1 += sy;
			}

			x1 += sx;
		}while(x1 != x2);
	}else{
		accum = dy >> 1;
		do{
			setCell(x1,y1, 0.4, 0.7, 1.0);

			accum -= dx;
			if(accum < 0)
			{
				accum += dy;
				x1 += sx;
			}

			y1 += sy;
		}while(y1 != y2);
	}
}

And, in case you ever get the need or desire to draw general ellipses…


void DrawEllipse(int left,int top,int right,int bottom)
{
	int		a,b;
	int		x,y,a2,b2,S,T;
	int		two_a2,two_b2;
	int		four_a2,four_b2;
	int		temp;

	if(right < left)
	{
		temp = left;
		left = right;
		right = temp;
	}
	if(bottom < top)
	{
		temp = top;
		top = bottom;
		bottom = temp;
	}

	a = (right - left + 1) / 2;
	b = (bottom - top + 1) / 2;

	if(!a && !b)
	{
		setCell(left,top, 0.4, 0.7, 1.0); // Draw a single pixel
		return;
	}

	if(!b)
	{
		DrawLine(top,left,top,right); // Draw a horizontal line
		return;
	}

	if(!a)
	{
		DrawLine(left,top,left,bottom); // Draw a vertical line
		return;
	}

	a2 = a * a;
	b2 = b * b;
	two_a2 = a2 << 1;
	two_b2 = b2 << 1;
	four_a2 = a2 << 2;
	four_b2 = b2 << 2;
	x = 0;
	y = b;
	S = a2 * (1 - (b << 1)) + two_b2;
	T = b2 - two_a2 * ((b << 1) - 1);

	setCell(right + x - a,bottom + y - b, 0.4, 0.7, 1.0); 
	setCell(left - x + a,bottom + y - b, 0.4, 0.7, 1.0); 
	setCell(left - x + a,top - y + b, 0.4, 0.7, 1.0); 
	setCell(right + x - a,top - y + b, 0.4, 0.7, 1.0); 

	do{
		if(S < 0)
		{
			S += two_b2 * ((x << 1) + 3);
			T += four_b2 * (x + 1);
			x++;
		}else if(T < 0){
			S += two_b2 * ((x << 1) + 3) - four_a2 * (y - 1);
			T += four_b2 * (x + 1) - two_a2 * ((y << 1) - 3);
			x++;
			y--;
		}else{
			S -= four_a2 * (y - 1);
			T -= two_a2 * ((y << 1) - 3);
			y--;
		}
		setCell(right + x - a,bottom + y - b, 0.4, 0.7, 1.0); 
		setCell(left - x + a,bottom + y - b, 0.4, 0.7, 1.0); 
		setCell(left - x + a,top - y + b, 0.4, 0.7, 1.0); 
		setCell(right + x - a,top - y + b, 0.4, 0.7, 1.0); 
	}while(y > 0);
}

I have to generalize drawing a line using Bresenhem’s midpoint alogrithm, not just any algorithm.

Right…

:confused:

That IS Bresenham’s algorithm, or rather, a highly optimized variation of his algorithm.

Is this a homework thing?

No it’s extra credit, a lot of work for 5 points which is half a percent. I don’t have to do it but it’s killing me not to finish it because I’ve spend so much time on it already, know what I mean? Can I ask you to fix my algorithm instead? I have a real project due in a week and I can’t let go of this stupid simple one. Pleassee help!!!

void drawLine(int Ax, int Ay, int Bx, int By)
{
int y,x, dy, dx, slope, decision, incE, incNE;

int temp;


if (Ax &gt; Bx)
{
	temp = Ax;

	Ax = Bx;
	Bx = temp;
	temp = Ay;
	Ay = By;
	By = temp;	 

}
	
 dx = Bx - Ax;
       dy = By - Ay;

 if (dy &lt; 0)
       {
           slope = -1;
           dy = -dy;
       }
       else
       {
           slope = 1;
       }

	
if(Ay == By) //draw vertical line
{	
	y = Ay;	
	   for (x = Ax; x != Bx; x++)	
		setCell(x,y,0.4,0.7,1.0);
	return;
			 
	
}
    
 if(Ax == Bx) //draw diagonal line
{	
	x = Ax;
	if(Ay &gt; By)
	{
		temp = Ay;
		Ay = By;
		By = temp;
	}
	
	for (y = Ay; y&lt;= By; y++)
		setCell(x,y,0.4,0.7,1.0);
	return;
	
}	 



       incE = 2 * dy;
       incNE = 2 * dy - 2 * dx;
       decision = 2 * dy - dx;

//trying to draw line that is with slope >1 and <-1, only successful with slopes greater 1 on the first quadrand

if( dy &gt; dx)
{	
	
	incE = 2*dx;
	incNE = 2*dx - 2 *dy;
	x = Ax;
	printf("test1

");
for (y = Ay; y <= By; y++)
{
setCell(x,y, 0.4, 0.7, 1.0);
if (decision <= 0)
decision += incE;

           		else
          		 {
				
				decision += incNE;
				x++;	

         		  }
    	   }
	return;
}	

//draw the rest of possible lines, works just fine
y = Ay;
for (x = Ax; x <= Bx; x++)
{
setCell(x,y, 0.4, 0.7, 1.0);
if (decision <= 0)
{
decision += incE;
}
else
{
decision += incNE;
y += slope;
}
}

}

OK, here is your code with some minor changes.

Notice the use of the ABS macro. This is all that it took to get it to work in all octants. Now, if you work through the decision variable, you’ll find that it degenerates to what I posted above. I’ll leave that up to you to figure out. If you turn in an optimized version of this algorithm, it is more than likely going to raise some eyebrows. You’ll need to be able to explain what you are doing and why, step by step.

You’ll also notice that all of the swapping of the end points has been eliminated as it is no longer necessary. The slope variable is gone and instead of adding one to the x variable and slope to the y, the sign of dx and dy is used as an increment. If dx or dx < 0, sx or sy will be -1, > 0 = 1. I also removed the for loops. Just personal taste.

This has been tested and it works. Since you did not fully code this and you are expecting it to be graded, I strongly suggest you familiarize yourself with it to the point of being able to explain each and every line of code with confidence. Your five point bonus could turn into a failing grade quite easily.


void drawLine(int Ax,int Ay,int Bx,int By)
{
	int	y,x,dy,dx,sx,sy;
	int	decision,incE,incNE;

	dx = Bx - Ax;
	dy = By - Ay;

	sx = SIGN(dx);
	sy = SIGN(dy);

	dx = ABS(dx);
	dy = ABS(dy);

	if(dy > dx)
	{	
		incE = 2 * dx;
		incNE = 2 * dx - 2 * dy;
		decision = 2 * dy - dx;

		x = Ax;
		y = Ay;
		do{
			setCell(x,y,0.4,0.7,1.0);
			if(decision <= 0)
				decision += incE;
			else{
				decision += incNE;
				x += sx;	
			}
			y += sy;
		}while(y != By);
	}else{
		incE = 2 * dy;
		incNE = 2 * dy - 2 * dx;
		decision = 2 * dy - dx;

		x = Ax;
		y = Ay;
		do{
			setCell(x,y,0.4,0.7,1.0);
			if(decision <= 0)
				decision += incE;
			else{
				decision += incNE;
				y += sy;
			}
			x += sx;
		}while(x != Bx);
	}
}

Slight correction. The decision variable was incorrect in this case:


	if(dy > dx)
	{	
		incE = 2 * dx;
		incNE = 2 * dx - 2 * dy;
		decision = 2 * dy - dx;

It should be:

decision = 2 * dx - dy;

Also, if you want to draw the last pixel in the line, add this before “if(dy > dx)”:

Bx += sx;
By += sy;