We Must Draw the Line

We’ve been using Bresenham’s line algorithm since 1962, but here’s something better!

Jack Elton Bresenham developed the original line drawing algorithm way back in 1962 while working for IBM, as he was developing software for a Calcomp plotter. There’s a great article on the subject on Wikipedia if you want to know more about the history of this algorithm. Search on “Bresenham’s line algorithm”.

Drawing a Line Sounds Like an Easy Thing To Do

So what’s the big deal? Drawing a straight line between two points on a computer screen sounds easy enough — just loop from x1 to x2 and calculate the corresponding values of y to plot at each point along the way, right? Well, yes and no. Here are a few complicating details to ponder.

• Floating point math is not going to be as efficient as integer math. After all, we’re talking about pixels to set along the line, and pixels are inherently located at integer locations in a “raster” covering the display.
• For steep or perfectly vertical lines, how do we calculate multiple values of y corresponding to each value of x along the way between x1 and x2?
• How do we adjust our looping from x1 to x2 when x1 happens to be greater than x2?

Bresenham’s Algorithm to the Rescue