Journal: 2008-05-02

There once was a man, who was faced with a decision. "What shall I do?" he wondered. "I know! I shall integrate over all space!" Then he realized, this was not really his strong suit. "I know! I shall rasterize over all space instead." And so he did.

˜ ™

Bresenham's Algorithm

Bresenham's algorithm is a brilliantly simple algorithm that every CS geek should know. It is usually used for figuring out what pixels to turn on to draw a line on the screen. However, once you understand the insight, you can use it for other purposes as well.

Most derivations are very complicated and seem to miss the point, which is why I'm witing my own explaination. For example, this derivation pretty much takes the cake! :) Even Wikipedia's explaination isn't that clear.

The Problem: We want to draw a line, as efficiently as possible.

To start off, let's simplify the problem. First, let's assume the first endpoint is (0, 0) - if it is not, we just add an offset to the calculated coordinates. Second, let's assume that the line is going upward and rightward (that the end point has positive X and Y coordinates) - if not, we just flip some signs. Third, let's assume that we only want to plot one point per column (that the line is shallow, with a slope between 0 and 1; that endpoint X coordiante > endpoint Y coordiante) - if not, we just transpose the coordinates. All this can be handled with a few 'if's at the beginning of the code and otherwise is just a distraction.

Now, let's consider a concrete example. Let's say we want to draw a line from (0, 0) to (7, 3). The slope of this line is rise over run, so 3/7. We have to stick to the grid lines, so we can just add 1 to the X coordinate each time. The first point is easy - it's (0, 0). Now the next point: X is 1, so Y is 3/7. Next: (2, 6/7) Next: (3, 9/7 = 1 2/7) Next: (4, 12/7 = 1 5/7) Next: (5, 15/7 = 2 1/7) Next: (6, 18/7 = 2 4/7) Next: (7, 21/7 = 3) Well, that's good, we reached our desired end point exactly.

Now the obvious problem is we can't plot (1, 3/7). We can only plot (1, 0) or (1, 1). Now, it might seem like you should plot the nearest point (0 for 3/7, 1 for 6/7) but that's kind of tricky. Let's take the easy road for now and always round down (truncate). So, our points are (0, 0), (1, 0), (2, 0), (3, 1), (4, 1), (5, 2), (6, 2), (7, 3). Notice that the Y coordinate is the whole part of the fraction.

Back to the problem: to plot a line, all we need to do is calculate this sequence of fractions. Obviously you could calculate the slope (m) as a double and use Y=m*X, multiplying each time, but multiplication is expensive (in this context), and there is probably rounding error. You could use cumulative additions instead of multiplication, but you will accumulate rounding errors and the error will get worse and worse.

Why not use integers to maintain the exact value of the fraction? Let's say we keep the numerator in one variable. The denominator never changes; it's always the end X coordinate (7 in our example). Every step, we always add to the numerator the same increment, which is the end Y coordinate (3 in our example). Whenever the numerator exceeds the denominator, we move our point up one and bring the numerator back in to range (subtracting the denominator).

Look at those fractional coordinates again, compared to the truncated coordinates.
X
           
Y
(fractional)
Y
(truncated)
0 0 0/7 0
1 0 3/7 0
2 0 6/7 0
3 1 2/7 1
4 1 5/7 1
5 2 1/7 2
6 2 4/7 2
7 3 0/7 3
The fractional part is just the error between where the point is supposed to be and where we can actually put it.

Gee, Bresenham's algorithm is just using an integer to track the fractional error during repeated addition of a fraction.

Here's some code to
make it more concrete:
Here's the same program again
with different variable names,
suggesting a different point of view:
int nX=0; int nY=0;
int nNumerator=0;
int nLastX=nDenominator=7;
int nStep=3;

plot(nX, nY);
while (nX<nLastX) {
  nX++;
  nNumerator+=nStep;
  if (nNumerator>=nDenominator) {
    nY++;
    nNumerator-=nDenominator;
  }
  plot(nX, nY);
}
int nX=0; int nY=0;
int nError=0;
int nLastX=nLarge=7;
int nSmall=3;

plot(nX, nY);
while (nX<nLastX) {
  nX++;
  nError+=nSmall;
  if (nError>=nLarge) {
    nY++;
    nError-=nLarge;
  }
  plot(nX, nY);
}

Now that we understand the algorithm, we can look for problems.

I mentioned at the beginning that this could be used for doing other things besides drawing lines. What else could you use it for? Well, you can use it any time you want to do any sort of fraction interpolation.

For example, I used it to generate a "fillet" of a log for reporting purposes. I had a log with possibly tens of thousands of lines. I wanted to generate a report, but I wanted to make sure the report was no longer than 1000 lines long. However, I also wanted the chosen 1000 lines to be representative of the entire souce log - some from the start, some from the middle, some from the end. I wanted every 1000/Nth line. Here's how I did it:

// using a variation on Bresenham's algorithm, print nSmall items evently distributed out of nLarge items.
int nSmall=1000;
int nLarge=logLines.size();
int nError=nLarge-nSmall;
if (nError<=0) {
    // There are fewer items to print than the max, so print them all
    nError=0;
    nSmall=0;
    nLarge=0;
}
int nIndex=0;
for (String sLogLine : logLines) {
    nIndex++;
    nError+=nSmall;
    if (nError>=nLarge) {
        outPrintStream.println("<Div><NoBr>"+nIndex+". "+sLogLine+"</NoBr></Div>");
        nError-=nLarge;
    }
}
See? Very useful! In this case, I only wanted to "plot" the first point of every run, so I moved the "plot" (println in this case) inside the if. (Yes, this is where I came up with the nError / nLarge / nSmall nomenclature.)

For those who are curious, here is the original paper. I've been a bit cavalier regrding accuracy and the choice of initial nError, but I think my description provides a simple mental model and a good basis for further exploration.

[ < Prev | Calendar | Next > ]
C o m m e n t s :    
(nothing yet)
Edit