I've always been interested in how things work, not just how they are applied. When I first heard about some special techniques used to draw rasterized lines and other mathematical shapes, I was curious. But it wasn't until some time later that I learned what one of these methods is called and still later before I was finally able to actually read about some of the details.

If you don't already know what a rasterized line is, it's just what happens when you try to draw a line on graph paper by only using completely filled squares of the grid. Instead of drawing the line with a ruler, you are forced to instead select and fill in entire squares in a way that gives the better appearance of the line that you intended to illustrate. This is the same problem faced when drawing lines by setting pixels on an IBM PC graphics screen, for example.

My first contact with digital differential analysis, applied to lines, was frustrating. The information was sparse and didn't make sense to me. The writer seemed to skip around and jump to conclusions I just couldn't reach and, finally, left me without an algorithm I could use to test the ideas. When I was finally able to understand how to do these things on my own, I discovered that the information in that article was also wrong. I guess I shouldn't be surprised.

A goal here is to present the reasoning behind the use of digital differential analysis to draw lines and to develop an algorithm you can use to test the ideas. Another goal is to do this clearly and in a fashion that can appeal to folks with only two years of high school algebra and an interest in computer programming. Finally, I'd like to shine some light in the direction of applying this kind of analysis in drawing circles, ellipses and other mathematical shapes.

Let's start by looking at the mathematical line.

If you've had to do any graphing in algebra, you've probably encountered the following general equation for a line:

This equation shows an exact relationship between x and y values. The value of m is often called the "slope" of the line because larger values generate steeper lines. And the value of b is called the y-intercept because it is the place along the y-axis where the line intersects it (when x is zero.) This style of expressing the line, when m and b are given specific values, helps to quickly picture what the line might look like.

But this form of a line is rarely used in computer graphics. When drawing lines segments as rasters, you are usually given a starting point and an ending point, instead of a slope and y-intercept. Let's call the starting point, , and the ending point, .

We can calculate the slope and y-intercept from these points and modify equation [1], accordingly. To start, recall that the slope of a line is rate of change-in-y versus change-in-x. Expressed this way:

Now that we know how to compute m, we can replace m in equation [1] and reorganize it to solve for the value of b:

The only problem with equation [3] is that we still have the general variables, x and y. We can fix that by replacing them with the values from the first or second point, our choice. (I'll use the first point):

Now, let's take equations [3] and [4] and apply them to equation [1], to get:

That last part isn't too bad. It simply says that y can be computed from x by taking the y-value of the starting point and adding a portion of the span between the y-values of the two points. The portion here is the ratio of how far x is from the x-value of the starting point and the span between the x-values of the two points. Makes sense?

Our version of the general line equation, specified by two points, is:

That's the basics. Now I plan to ticker with this equation a bit to gain some more familiarity with lines. If this is already well understood to you, you might skip to the end of the next section.

There's a minor "difficulty" with equation [6]. What if the two points are arranged vertically, so that their x-values are equal? The zero in the divisor will cause some nasty problems. It turns out that there is another way to express a line, which handles this problem. Just multiply both sides by :

Looks worse? Well, let me move a piece of it to the other side and combine terms:

Do you see the symmetry in this? Let's stop for a moment and imagine that these two products each represent some kind of area. Before we go on, it's time for a bit of geometry.

The above chart shows an example to illustrate the areas suggested by equation [8]. The left hand side of the equation is the area covered by the horizontal lines. The right side of the equation is the area covered by the vertical lines. These two areas overlap in the cross-hatched area.

The line shown divides the large rectangle into two triangles with equal areas. The lower left and upper right quadrant rectangles are similarly divided by the line, so we can safely remove their respective areas from the larger triangles and still know that the remaining smaller rectangles are still equal. If we now add the area in the lower left hand corner to both, we get back the two areas described in equation [8]. That's it for the geometry side-bar. It's just good to pause a moment and see how that works out.

Equation [8] removes the possibility of dividing by zero. But it does something else, too. With integer coordinates, we can now perform all of the calculations with integers. This means we are probably on the right track.

Equation [8] is still a bit quirky, in spite of it's balance. If you know what x is, it's kind of hard to figure out y, and visa versa. But before we make any more adjustments to equation [8], we need to decide whether it's more important to calculate x from y or to calculate y from x.

When plotting rasterized lines between two points, you are faced with two choices. You can move x around independently between the x-values of your two points and compute the value of y from this value of x or you can move y around independently between the y-values of your two points and compute the value of x from that. Either way works, mathematically. As a practical matter though, you need to make a choice.

When the equation is set up so that you are free to adjust the value of x and where the value of y depends on this setting, such as in equation [1], then x is considered the independent variable and y is considered the dependent variable. Of course, you can switch this around in order to reverse the roles. (Notice that equation [8] doesn't show a preference for either variable as independent or dependent.)

It turns out that when you are plotting rasterized lines (and most anything else, too) that it's important to make the right choice. The goal is to select the axis that forms the long side of your rectangle between the two points as your independent variable. In other words, you'd pick x as your independent variable when is larger than , and you'd pick y as your independent variable and when the opposite holds. When equal, you can go either way. But why is this true?

Well, let's look at this simple equation and imagine plotting it using x as the independent variable, going from a point at (2,20) to a point at (5,50). Let's recall equation [6] and use it for this purpose:

The points would be (2,20), (3,30), (4,40), and (5,50). But this is only four points and if you tried plotting them, your line would look very sparse. What we'd rather plot is (2,20), (2,21), (2,22), (2,23), (2,24), (3,25), (3,26), (3,27), and so on. This way, the line will look properly solid. In this case, we should have reorganized the equation so that y was the independent variable and x was the dependent one, like this:

That will give us enough points to make a reasonable line. Of course, this argument depends on whether the range along one axis is more or less than it is on the other axis.

Keep this in mind as we continue. The algorithm to follow will have to worry about such things.

We've covered the general equation for lines, given two points, in equation [6]. We've suggested an approach to help avoid dividing by zero in equation [8], although it may still be a mystery how to make much use of it. And we've discussed independent and dependent variables and how to choose which should be which, in and around equations [9] and [10].

I think you are about ready. It's time to develop something useful.

Let's rearrange equation [8] like this:

I'm also going to create two new terms that are pretty easy to understand and will help us when it comes time to make an algorithm. These two terms are simply the height and width of the rectangle formed by the two points between which we are supposed to draw a line. But I'll use a mathematically inclined name, if you don't mind:

Using these two, we can rewrite equation [11] into our golden rule of lines:

This equation isn't just another way of looking at the same old line. It's the key to developing a fast algorithm for drawing lines.

This is the point where we are going to convert the general equations above into specific and detailed rules to use in drawing lines. I've glossed over some of the details, but now that I'm ready to take a narrower focus I need to cover a few definitions I've neglected.

I'll be using the convention of x and y axes, where the x axis is horizontal the positive x direction is to the right, the y axis is vertical, and the positive y direction is up. This isn't always the case, in practice, since both computer screens and printers often have the positive y direction going down. But for the discussion to follow, I'm sticking with the usual mathematical convention and leaving it to you to apply it to particular circumstances.

There are eight possible categories of lines, for drawing purposes. If you imagine that , is located in the center of the adjacent diagram and that the point we'll draw to, . is located somewhere in the surrounding vicinity, then this destination will fall into one of the octants shown.

The table shown below the diagram illustrates the eight different octants and the important criteria that differentiates them. The independent variables are always stepped by +1 or -1, as the line is plotted. The dependent variable will then vary by a fractional value, for each of these independent variable steps.

Take a careful look at this table and make sure that you understand it. If you need to, refer back to the discussion on independent and dependent variables and how to choose between them.

Next, we're going to focus on the details of plotting lines where the destination is in octant 1. Once we've determined how to handle one of these, we can see what's different for the other cases and figure out how to adapt the algorithm to them.

Let's return to our infamous equation, the seed corn we'll use for the algorithm to follow:

Equation [14] is zero for any point that is exactly on the line. If we take any given x and y pair, we can use equation [14] to see where the point is. If the value is zero, the point is on the line; if the value is positive, the point is below the line; and if the value is negative, the point is above the line. (You should test yourself to see if you can spot the exact reason why this is true.) We're going to use these facts to help us plot our points.

Plotting the first point of our line is rather easy. We just plot the first point we were given, . It's the next point that makes us think.

For endpoints in octant 1, x is the independent variable with a +1 increment between adjacent points along the line that we'll plot. Since y is the dependent variable, it will have a positive fractional change between adjacent points along the line, so the next point we need to plot will be either at or at , depending on whether that fractional amount is less or more than 0.5. And, no matter which one we choose, it will probably not fall exactly on the line we'd like to be drawing. So we'll need to keep track of our errors as we proceed, too.

So which of the next two points do we choose? What we'd really like is the answer to, is:

Which next point does the line come closer to, or ?

If we knew the answer to that, we'd know which one to plot. Before we could answer that, we'd need to measure how closely the line went by each of the two possible points and then we'd need to compare them to see which was the smaller distance.

But another way of asking the same question more directly would be something like this:

Does the line cross above or below the halfway point at ?

Notice that the point used in the above question is halfway between the two points we are considering. If the line crosses over this point, then it must be closer to and that's the point we should use. If the line crosses below this point, then it must be closer to and that's the point to use, instead. If you are having any difficulty seeing why this is a good choice, take out a piece of graph paper and check it out. I think you'll see how it works.

Let's define a new equation. We'll use it to help us decide between the two possible choices, as each step in plotting a line in octant 1:

For lines plotted in octant 1, this equation answers the question, "What is the value of the line, at the next x value just to the right of the current point we've plotted and halfway between the current value of y and the next possible value of y?" If the value is positive, then the line must be passing above our halfway point and this means we should plot as the next point. If the value is negative, then the line must be passing under our halfway point and this means we should plot as the next point. An exact zero would suggest that we could pick either one as our next point to plot.

Our remaining problem now is to find a way to efficiently calculate the successive values of . It turns out that we can do this by ignoring for a moment and thinking about how it changes as we plot points in octant 1, instead.

The first value will be . The next value will depend on that value, because we use it to decide which of the two points we will plot next. This means we have two cases to consider:

You will have this same pair of cases to choose between, after each plotted point. And the result, which ever one is picked, will determine the following point to plot. The will repeat over and over again until the line is drawn.

Repeating sequences like this, with an initial boundary condition and repeating logic, are called recurrences. Mathematically, [16] can be generally expressed better as the following recurrence:

We've just used something called mathematical deduction to describe the "local" effects of the function, . It loses sight of the big picture, but tells us a lot about what is going on near our point of interest. Recurrences are ripe for mathematical induction, which reverses this process. But that's for another day.

To compute successive values of , let's expand on its recurrence in [17]:

Now we need to do some algebra to see if this can be simplified. This is detailed, but not hard to follow. So, let's start with the first case listed in [18]. Going back to equations [14] and [15] and substituting:

Now, let's do the same thing for the second case:

Now we can restate [18] in a more concrete form:

Take a quick breath for a moment, because this problem just got a lot easier! Notice that the change in our condition function, used to decide which point to plot in case you've already forgotten, only depends on the original some very simple values that we can pre-compute before starting out. This is good news for drawing lines.

We've one more detail to take care of, the initial value:

That fraction will causes us some slight trouble if we plan to use integers throughout. For that reason alone, we will just multiply everything by 2. That will clear up the problem completely.

Let's fix up recursion [17] with this new information:

Heck. The code in any language will practically write itself from that!

I'll bet you were thinking that there can't be any more, right? Hehe. Well, that just covered cases where we are plotting a line in octant 1. There are seven more of them, you know. I'm not the least bit tired, so shall we continue?

Let's take a look at all the octants for a moment. The following table shows each of the decision functions to use when selecting between two alternate points along the line. There are four with x as the independent variable and four with y. Of each of these four, two are positive directed and two are negative. Look it over and verify in your own mind that these make sense.

Now it also turns out that the eight equations can be cut down to four by recognizing that all octant 3 lines can be converted to octant 7 lines by just swapping the starting and ending points. Similarly, octant 4 becomes octant 8, octant 5 becomes octant 1, and octant 6 becomes octant 2. You can take any octant drawing direction and convert it to the diametrically opposite octant this way, in fact. So you can convert eight situations into just four. That's a bit better.

Actually, it's lots better. Intuitively, you might notice that all these patterns amount to simple reflections of each other and that you probably need just one basic piece of logic. It turns out that the pattern of selecting between the two possible points as the line is drawn varies based on the magnitudes, and . It's the selection of the independent variable and the dependent variable and their respective directions that then tell the full story. Two possible independent variables, two directions for the independent variable, and two possible directions for the dependent variable: 2*2*2=8.

I won't tabulate the eight recurrences for you. You can do those as an exercise, if you like. Just for fun, here's the recurrence for octant 8:

The details start getting pretty tedious at this point, as if they haven't already been that way. It turns out that you can use a single routine to handle drawing all eight octants, if you think of the DDA routine as manipulating the variables as independent and dependent, rather than as x and y.

There are two basic orientations for drawing the lines. One when the dependent variable increases as the independent variable increases and one when the opposite occurs, when the dependent variable decreases as the independent variable increases. So the DDA routine will need the starting and ending points for the independent variable, the starting point for the dependent variable and its orientation to the independent variable, and the magnitude of the spans between the points. With that in place, you can use a single piece of DDA logic to get the whole job done.

Even though the DDA algorithm can handle vertical and horizontal lines quite well, it's often better to handle a few situations as special cases in your code for better efficiency. Horizontal and vertical lines are simple and don't need decision variables. In fact, you can cover both vertical and horizontal lines in a single routine, if you like. Or to take advantage of special capabilities on the hardware, you may prefer to keep these separate. Similarly, lines exactly along 45-degree lines can use special code and can be all handled in a single routine, too.

Now let's see some code.

I'm using the C language to illustrate the routines that follow. The code does not deal with pixel colors or clipping. Although most practical routines have to deal with such things, they aren't always needed and they are beyond the scope here. Also, the SetPixel routine isn't shown. You'll need to provide it, if you plan to test these routines.

Finally, I don't show the special case code I mentioned earlier, to handle vertical, horizontal, 45-degree lines, and isolated points. The code below copes with those special cases just fine without any special handling and I figure you will have little problem adding such code, if you want it. The point here is to showcase the DDA algorithm.

    extern void SetPixel (int x, int y);

    typedef void SetPixelFunc (int a, int b);

    void xySetPixel (int x, int y) { SetPixel (x, y); }

    void yxSetPixel (int y, int x) { SetPixel (x, y); }

    void PlotLineDDA (SetPixelFunc* pfPlot, int a1, int a2, int b, int da, int db, int bc) {
        int g1= db + db;
        int g2= g1 - da - da;
        int g= g1 - da;
        for (int a= a1; a < a2; ++a) {
            pfPlot (a, b);
            if (g < 0)
                g= g + g1;
            else {
                g= g + g2;
                b= b + bc;
            }
        }
        pfPlot (a, b);
    }

    void PlotLine (int x1, int y1, int x2, int y2) {
        int dxabs= abs (x2 - x1);
        int dyabs= abs (y2 - y1);
        if (dxabs >= dyabs) {
            if (x1 < x2)
                PlotLineDDA (xySetPixel, x1, x2, y1, dxabs, dyabs, y1 < y2? 1:-1);
            else
                PlotLineDDA (xySetPixel, x2, x1, y2, dxabs, dyabs, y2 < y1? 1:-1);
        } else {
            if (y1 < y2)
                PlotLineDDA (yxSetPixel, y1, y2, x1, dyabs, dxabs, x1 < x2? 1:-1);
            else
                PlotLineDDA (yxSetPixel, y2, y1, x2, dyabs, dxabs, x2 < x1? 1:-1);
        }
    }

Ok. Ok. I know. Ten pages of nasty math and all you get for it is that short bit of code?! About ready to kill me for dragging you through that mine field when there was a short cut through a soft clover field?

Well, it was good for you. Isn't a brisk bit of algebra just what it takes to get your heart pumping in the morning, anyway? And imagine – now you can tackle my article on that circle-drawing code! (Just don't spoil the plot by jumping to the end, skipping all that thrilling mathematics.)

Yours truly,
Jon