The aliasing of the line to pixels could be accomplished by comparing the distance of the line from the centers of the pixels and choosing the closer one. This however leads to floating point math that is slower than integer math. Because way to get the height of the line involves division.
To choose which second pixel should be darkened in the case of the above line from (2,2) to (19,9):
y = mx+b
m = 7/17 = 0.41176471
b = 1.1764706
The exact location of the line when x = 3 (the second pixel) is:
y = 0.41176471 * 3 + 1.1764706 = 2.4117647
the distance from the upper pixel is 0.58823527
the distance from the lower pixel is 0.4117647
Thus the lower pixel is chosen, but only after muttiple floating point operations were performed.
Help on the equation of the line
The algorithm below uses only integers to find a solution.
void
draw_line (int x0,int y0,int x1,int y1)
{
int dy, dx, incrE, incrNE, d,x,y;
dx = x1 - x0;
dy = y1 - y0;
d = 2 * dy - dx;
incrE = 2*dy;
incrNE = 2*(dy - dx);
x = x0;
y = y0;
plot_point(x, y);
while(x < x1)
{
if (d <= 0)
{
d += incrE;
x++;
}
else
{
d += incrNE;
x++;
y++;
}
plot_point(x,y);
}
}
draw_line (int x0,int y0,int x1,int y1)
{
The internal variables dy, dx, incrE, incrNE, d, x, y
. dx
is the change in x, dy
the change in y. d
determines if the next pixel is on the same line or rises one. The variables incrE
and incrNE
are used to change the value of d
. x
and y
are the point to be plotted, initially the first point given.
dx = x1 - x0;
dy = y1 - y0;
d = 2 * dy - dx;
incrE = 2*dy;
incrNE = 2*(dy - dx);
x = x0;
y = y0;
plot_point(x, y);
The while loop does the work. x
is incremented each time through the loop. Because the plot happens at the end of the loop, x is incremented before each plot.
while(x < x1)
{
If d is less than one d is increased by incrE
, y
remains the same, and x
is incremented.
if (d <= 0)
{
d += incrE;
x++;
}
Otherwise d is increased by incrNE
, and both x
and y
are incremented.
else
{
d += incrNE;
x++;
y++;
}
plot_point(x,y);
}
}
Here endith the lesson.