PDA

View Full Version : Drawing Line Bresenhem midpoint algorithm

The_Thinker
10-01-2009, 02:01 AM
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\n");
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 <= Bx; x++)
{
setCell(x,y, 0.4, 0.7, 1.0);
if (decision <= 0)
{
decision += incE;
}
else
{
decision += incNE;
y += slope;
}
}

rakesh_thp
10-01-2009, 04:21 AM
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

MarkS
10-01-2009, 10:49 PM
#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 &amp;&amp; !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);
}

The_Thinker
10-02-2009, 05:51 PM
I have to generalize drawing a line using Bresenhem's midpoint alogrithm, not just any algorithm.

MarkS
10-02-2009, 06:39 PM
Right...

:confused:

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

Is this a homework thing?

The_Thinker
10-02-2009, 08:26 PM
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 > 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) //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 > 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;

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

if( dy > dx)
{

incE = 2*dx;
incNE = 2*dx - 2 *dy;
x = Ax;
printf("test1\n");
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;
}
}

}

MarkS
10-02-2009, 10:02 PM
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);
}
}

MarkS
10-03-2009, 11:19 AM
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;