I have searched throughout the Internet and found hundreds of implementation of Bresenham's line drawing algorithm. But, one thing I found strange is, only two or three of them can cover all of the eight octets. still, they are being used in many applications.
For example, this lady implemented this version (line 415) of Bresenham's algorithm. But, it doesn't cover the whole 360 degrees. This guy here seems to be developing a library. But still it doesn't work properly.
Can you tell me why?
This guy's implementation works fine. But, I suppose it is not Bresenham's Algorithm. It has a very few similarity with the theory.
Finally, I found the following version of Bresenham's Line Drawing Algorithm that works properly.
#include "utils.h"
void Bresenham(int x1, int y1, int const x2, int const y2, int color)
{
int dx = x2 - x1;
// if x1 == x2, then it does not matter what we set here
int ix((dx > 0) - (dx < 0));
dx = abs(dx) << 1;
int dy = y2 - y1;
// if y1 == y2, then it does not matter what we set here
int iy((dy > 0) - (dy < 0));
dy = abs(dy) << 1;
PlotPixel(x1, y1, color);
if (dx >= dy)
{
// error may go below zero
int error(dy - (dx >> 1));
while (x1 != x2)
{
if ((error >= 0) && (error || (ix > 0)))
{
error -= dx;
y1 += iy;
}
// else do nothing
error += dy;
x1 += ix;
PlotPixel(x1, y1, color);
}
}
else
{
// error may go below zero
int error(dx - (dy >> 1));
while (y1 != y2)
{
if ((error >= 0) && (error || (iy > 0)))
{
error -= dy;
x1 += ix;
}
// else do nothing
error += dx;
y1 += iy;
PlotPixel(x1, y1, color);
}
}
}
int main()
{
int gm = DETECT;
int gd = DETECT;
initgraph(&gm, &gd, "");
double x1 = 0;
double y1 = 0;
double r = 50;
double x2 = 0;
double y2 = 0;
double signx = 0;
double signy = 0;
for(int theta=0 ; theta<=360 ; theta++)
{
x2 = r * cos(DegreeToRad((double) theta));
y2 = r * sin(DegreeToRad((double) theta));
x1 = 5 * cos(DegreeToRad((double) theta));
y1 = 5 * sin(DegreeToRad((double) theta));
Bresenham(x1, y1, x2, y2, YELLOW);
//delay(10);
}
getch();
closegraph();
return 0;
}
The original code is quite strange. So, I need your help to understand that.
Why is he left shifting dx and dy and then, before calculation, again right-shifting them?
Where are the dt and ds that the theory talks about?
According to the theory, dt and ds should have been tested in every step of while loop. But, this code isn't doing so. Why?
The theory seems to have no indication of any error value processing. What is the use of error that the code is calculating? How is he calculating the error? How is he using the error value?
What is the logic behind the test if(dx >= dy)?
Here is an explanation of my own version of Bresenham.
We start with the parametric equation of a line, (X + t.Dx, Y + t.Dy), where t is a parameter in range [0, 1]. The endpoints are obviously (X, Y) and (X + Dx, Y + Dy).
To turn it to a digital line, we want exactly one pixel per row or per column, whichever ensures a continuous line. So defining D = Max(|Dx|, |Dy|), we will draw D+1 points corresponding to fractional t: (X + I.Dx/D, Y + I.Dy/D), with I in [0, D].
Let us assume for a moment 0 <= Dy < Dx = D, and the equation simplifies to (X + I, Y + I.Dy/Dx). As the last term may not be an integer, we will round it with round(I.Dy/Dx) = floor(I.Dy/Dx + 1/2) = floor((I.Dy + Dx/2) / Dx).
The latter expression is the quotient of numbers following an arithmetic progression over a denominator larger than the common difference. Hence, when you increment I, the ratio either stays fixed or increases by 1. For a division-less implementation, we use a trick: keep the quotient and the remainder of the division, let Q and R, and every time you increase I, update these.
Let N = I.Dy + Dx/2, and Q = N / Dx, R = N % Dx. Then increasing I, I' = I + 1, N' = N + Dy, Q' = (N + Dy) / Dx, R' = (N + Dy) % Dx. As you can check, the following rule holds:
if R + Dy >= Dx
Q' = Q + 1; R' = R + Dy - Dx
else
Q' = Q; R' = R + Dy
We now put all elements together, adjust for signs and distinguish the more-horizontal and more-vertical cases (as you will note, there is no need to represent Q explicitly):
# Increments
Sx= Sign(Dx); Sy= Sign(Dy)
# Segment length
Dx= |Dx|; Dy= |Dy|; D= Max(Dx, Dy)
# Initial remainder
R= D / 2
if Dx > Dy:
# Main loop
for I= 0..D:
Set(X, Y)
# Update (X, Y) and R
X+= Sx; R+= Dy # Lateral move
if R >= Dx
Y+= Sy; R-= Dx # Diagonal move
else:
# Main loop
for I= 0..D:
Set(X, Y)
# Update (X, Y) and R
Y+= Sy; R+= Dx # Lateral move
if R >= Dy
X+= Sx; R-= Dy # Diagonal move
C/C++ Implementation (by @anonymous)
void Set(int x, int y, int color)
{
PlotPixel(x, y, color);
}
int Sign(int dxy)
{
if(dxy<0) return -1;
else if(dxy>0) return 1;
else return 0;
}
void Bresenham(int x1, int y1, int x2, int y2, int color)
{
int Dx = x2 - x1;
int Dy = y2 - y1;
//# Increments
int Sx = Sign(Dx);
int Sy = Sign(Dy);
//# Segment length
Dx = abs(Dx);
Dy = abs(Dy);
int D = max(Dx, Dy);
//# Initial remainder
double R = D / 2;
int X = x1;
int Y = y1;
if(Dx > Dy)
{
//# Main loop
for(int I=0; I<D; I++)
{
Set(X, Y, color);
//# Update (X, Y) and R
X+= Sx; R+= Dy; //# Lateral move
if (R >= Dx)
{
Y+= Sy;
R-= Dx; //# Diagonal move
}
}
}
else
{
//# Main loop
for(int I=0; I<D; I++)
{
Set(X, Y, color);
//# Update (X, Y) and R
Y+= Sy;
R+= Dx; //# Lateral move
if(R >= Dy)
{
X+= Sx;
R-= Dy; //# Diagonal move
}
}
}
}