A common algorithm for turning lines into pixels.

A few posts ago I wrote about problems with rasters and used drawing a line as one of my examples. In this post I present one of the most common families of line drawing algorithms for rasters. There is no discussion in this post beyond the algorithm itself.

Divided Differences

Given a line from point p1 = (x1, y1) to point p2 = (x2, yy), we want to fill an 8-connected line (pixels can touch along edges or corners) that lies as close to the mathematical line as possible. To do this, we’ll use the DDA algorithm. This stands for “‍Digital Differential Analyzer‍” and works by computing the difference between the endpoints and dividing it by the number of pixels we’ll need. That number of pixels is the larger of |x2 – x1| and |y2 – y1|.

In the above diagram the red arrow is the vector p2 – p1 and the blue arrow is the red arrow divided by |x2 – x1|. We’ll use the blue arrow to move from one pixel to the next as we draw. But before we can do that we need to find where to start; this will be close to p1, but we want to move forward to the center of the column of pixels. We find that initial move by computing how much we need to move in x and then scaling the blue arrow to have an x component that large.

Now we repeatedly check whether the current location is closer to the pixel above or below it, fill that pixel, and move one blue arrow forward.

…

Without Division

There is one step in the DDA algorithm that is problematic: we divide the red arrow by a number to get the blue arrow. Division is rarely exact, so this can cause rounding error; rounding error, in turn, can change which pixels we color which can cause adjacent shapes to not longer touch.

Fortunately, we can draw lines without division using a small modification of DDA called the Bresenham algorithm. Observe that each time we go to a new pixel we either do not change y, or we change it by 1. This is because we are adding

y2 – y1

|x2 – x1|

, a value between –1 and 1. So in mixed number form, we either go from pixelY

n

|x2 – x1|

to pixelY

n + y2 – y1

|x2 – x1|

or we go to (pixelY ± 1)

n + y2 – y1 ∓ |x2 – x1|

|x2 – x1|

. All we really need to track, then, is the numerator n and change y when it gets outside of the interval [0, |x2 – x1|).

4-connected Lines

The DDA/Bresenham algorithms can easily be modified to make 4-connected lines by filling one of the two corners each time they advance in y (or x for more vertical lines). The pixel to fill depends on which is closer to the boundary, the old point or the new one.

Interpolation and Polygons

If you have more coordinates per point that just x and y—say, for example, color—then it interpolates linearly with no additional work.

A simple way to fill polygons is to use DDA or Bresenham in y along the edges and then for each pair of points with the same y use it again in x between the pair. Of course, the horizontal lines are even easier because the y never changes, but we use the algorithm anyway so we can interpolate across the face of the polygon. This simple process is the core of just about every video game graphics engine and implemented in hardware on most graphics cards.

Say what you will about the problems of rasters, they do make for very simple drawing algorithms.