I've found this Generalized Bresenham's Line Drawing Algorithm and I'm having a hard time understanding what the while
is doing here.
Any help is greatly appreciated.
the code:
#define sign(x) ((x > 0)? 1 : ((x < 0)? -1: 0))
x = x1;
y = y1;
dx = abs(x2 - x1);
dy = abs(y2 - y1);
s1 = sign(x2 - x1);
s2 = sign(y2 - y1);
swap = 0;
if (dy > dx) {
temp = dx;
dx = dy;
dy = temp;
swap = 1;
}
D = 2*dy - dx;
for (i = 0; i < dx; i++) {
display_pixel (x, y);
while (D >= 0) {
D = D - 2*dx;
if (swap)
x += s1;
else
y += s2;
}
D = D + 2*dy;
if (swap)
y += s2;
else
x += s1;
}
D
is the scaled distance from the line to the candidate x, y
coordinate.
Better: D
is scaled difference of the distance from the line to the candidates x+1, y+0
and x+1, y+1
.
That is, as x
increments, the sign of D
indicates should the closer y
increment by 0 or 1?
(The role of x, y
interchanges depending on which octant the algorithm is applied.)
I expected while (D >= 0) {
as if (D >= 0) {
. Bresenham's line algorithm
Note that OP's code is subject to overflow in abs(x2 - x1)
and 2*dy - dx
. Alternates exist that do not rely on wider math.