Bresenham Line Drawing Algorithm

int Octet(double m, int Ax, int Ay, int Bx, int By)
{
int octetNo = -1;
double dx = Bx - Ax;
double dy = By - Ay;

//m = dy / dx;

if(0<=m && m<=1)
{
if(Ax<Bx) octetNo = 1;
else if(Bx<Ax) octetNo = 5;
}
else if(0>=m && m>=-1)
{
if(Bx<Ax)
octetNo = 4;
else if(Ax<Bx) octetNo = 8;
}
else if(m>1)
{
if(Ay<By) octetNo = 2;
else if(By<Ay) octetNo = 6;
}
else if(-1>m)
{
if(Ay<By) octetNo = 3;
else if(By<Ay) octetNo = 7;
}

return octetNo;
}

int NextDiIfDiIsGreaterThanOrEqualtoZero(double m, int di, int x1, int y1, int x2, int y2)
{
int di_plus_1 = -1;
int dx = x2 - x1;
int dy = y2 - y1;

int octet = Octet(m, x1, y1, x2, y2);

switch(octet)
{
case 1:
case 5:
di_plus_1 = di - 2 * (dx - dy);
break;
case 2:
case 6:
di_plus_1 = di + 2 * (dx - dy);
break;
case 3:
case 7:
di_plus_1 = di - 2 * (dx + dy);
break;
case 4:
case 8:
di_plus_1 = di + 2 * (dx + dy);
break;
}

return di_plus_1;
}

int NextDiIfDiIsSmallerThanZero(double m, int di, int x1, int y1, int x2, int y2)
{
int di_plus_1 = -1;
int dx = x2 - x1;
int dy = y2 - y1;

int octet = Octet(m, x1, y1, x2, y2);

switch(octet)
{
case 1:
case 5:
di_plus_1 = di - 2 * dy;
break;
case 2:
case 6:
di_plus_1 = di + 2 * dx;
break;
case 3:
case 7:
di_plus_1 = di - 2 * dx;
break;
case 4:
case 8:
di_plus_1 = di + 2 * dy;
break;
}

return di_plus_1;
}

int InitialValueOfDi(double m, int x1, int y1, int x2, int y2)
{
int init_di = -1;
int dx = x2 - x1;
int dy = y2 - y1;

int octet = Octet(m, x1, y1, x2, y2);

switch(octet)
{
case 1:
case 5:
init_di = dx - 2 * dy;
break;
case 2:
case 6:
init_di = 2 * dx - dy;
break;
case 3:
case 7:
init_di = (-2) * dx - dy;
break;
case 4:
case 8:
init_di = 2 * dy + dx;
break;
}

return init_di;
}

void BresLine(int x1, int y1, int x2, int y2, int color)
{
int dy = y2 - y1;
int dx = x2 - x1;
double m = (double)dy/(double)dx;
int di = InitialValueOfDi(m, x1, y1, x2, y2);
int limit = ((abs(dx)>abs(dy))?abs(dx):abs(dy))/2;
int x = x1;
int y = y1;

for(int i=0 ; i<=limit; i++)
{
PlotPixel(x, y, color);

if(di>=0)
{
di = NextDiIfDiIsGreaterThanOrEqualtoZero(m, di, x1, y1, x2, y2);
y++;
}
else
{
di = NextDiIfDiIsSmallerThanZero(m, di, x1, y1, x2, y2);
}
x++;
}
}


Disclaimer: I know nothing of C++, but I'll help you as much as I can.

Overall, your code looks good. A+ for readability! Probably a missing spot somewhere, but no biggy. Still, your code is easy to read and follow.

On your BresLine(), you have this:

int dy = y2 - y1;
int dx = x2 - x1;
double m = (double)dy/(double)dx;
[...]
int limit = ((abs(dx)>abs(dy))?abs(dx):abs(dy))/2;


You could try to store that abs() somewhere, to shave on re-calling it.

You have the functions NextDiIfDiIsGreaterThanOrEqualtoZero() and NextDiIfDiIsSmallerThanZero(). They have giant names. And the code is almost the same. I suggest the following:

int NextDi(double m, int di, int x1, int y1, int x2, int y2)
{
int di_plus_1 = -1;
int dx = x2 - x1;
int dy = y2 - y1;

int octet = Octet(m, x1, y1, x2, y2);

switch(octet)
{
case 1:
case 5:
di_plus_1 = di - 2 * (di > 0 ? dx - dy : dy);
break;
case 2:
case 6:
di_plus_1 = di + 2 * (di > 0 ? dx - dy : dx);
break;
case 3:
case 7:
di_plus_1 = di - 2 * (di > 0 ? dx - dy : dx);
break;
case 4:
case 8:
di_plus_1 = di + 2 * (di > 0 ? dx - dy : dy);
break;
}

return di_plus_1;
}


It isn't the prettiest thing on Earth, but may work for you. To call it, you don't have to change anything! Just remove that if on BresLine. With some bitwise operations, you can cut down this code by a lot!

If you see something innacurate, please tell me. I haven't touched on the remaining functions, but I'm specially worried about the Octet function.

• just now I found that my implementation doesn't work properly.
– user3804
Aug 25, 2015 at 19:30
• @anonymous finding bugs is part of what's possible to find in a peer review. Feel free to post a self-review to point out the bug. The "broken code is off-topic" rule is only there to avoid "please help me debug my code" questions; every now and then reviewers do find bugs in OP's code; answers don't make a question off-topic. Aug 25, 2015 at 19:37

Bugs

Given these lines:

int limit = ((abs(dx)>abs(dy))?abs(dx):abs(dy))/2;
int x = x1;
int y = y1;
for(int i=0 ; i<=limit; i++)
{
PlotPixel(x, y, color);
if(di>=0)
{
di = something;
y++;
}
else
{
di = something;
}
x++;
}


I can immediately deduce the following problems:

1. Your program will only draw about half of the line requested because it draws limit+1 number of pixels, and limit is half the length of the longest dimension.

2. Your program can't draw vertical lines because each loop increments x unconditionally. This also means that it can't possibly draw any line steeper than 45 degrees.

3. Your program only has x++ and not x--. But if x2 is smaller than x1, then you are drawing in the wrong direction. Same thing for y.

Further investigation showed that the program doesn't handle horizontal lines correctly either (y gets incremented on the first iteration).

These bugs seem like they should have been pretty obvious if you actually ran the code and plotted the results. I suggest spending a lot more time testing.