LateNightHacking Louis Journal

Auth

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 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.

• Watch out for the fence post problem. You can use a for loop, a while loop, or whatever is convenient, but don't forget to plot both the first and the last points (unless you can come up with some good excuse why you can leave one off ;). (After all, OpenGL did!)
• What about overflow? Well, the algorithm is pretty overflow resistent. The maximum value of nError is nSmall+nLarge-1. If nLarge<=MAX_INT/2 you are fine, and you can work around that if you want to be tricky.
• Do you need to worry about reducing the fraction nStep/ nDenominator? That is, will it help to find the GCF and divide? Well, calculating the GCF is O(n²) in the number of digits. Reducing won't affect the speed of adding and subtracting, and isn't even guaranteed to prevent overflow. It's a waste of time.
• Back to our assumptions: What if nStep>nDenominator? This is the case of a steep line, with slope > 1. Consider (0, 0) to (3, 7). After the first step, we have (1, 7/3 = 2 1/3). We've gone more than one step up! One solution is to swap the nStep and the nDenominator. Another solution is to subtract the nDenominator in a loop, plotting once for every subtraction, until the nNumerator is less than the nDenominator. Similar options are available if nStep or nDenominator is negative.
• Note that nX and nY don't have to start out at zero, and they don't have to be increased by one. For example, you might choose to increment nY by the stride when using direct access to a linear image buffer. (Or you might not use nX and nY, but just a single offset that is increased by one or by stride depending on the case.)
• Continuing in that vein, you could solve the multiple orientations problem by incrementing both nX and nY by pre-calculated constants in both the step and the overflow cases. If you are really plotting a line, you will probably prefer the speed of having a separate piece of code for each possible orientation. However, if you are using your fractional interpolation for some other purpose, you might find it convenient to write one code path that handles all cases.
• What about truncation versus rounding? Let's look at the line produced by our simple code:

  3 # 2 ## 1 ## 0### 01234567

  "Kinda ugly. We should have rounded the other way." OK, but what if the endpoint was (14, 6)?

  6 # 5 ## 4 ## 3 ### 2 ## 1 ## 0### 012345678901234

  The line now looks fine around (7, 3). Also, notice the repeated pattern of runs of 3-2-2. No matter how we round, the line will be some combination of pixels in this 3-2-2 pattern. However, if we don't like the line starting with a run of three and ending with a run of one, we can vary the initial value assigned to nError. In fact, we can pick any number we want from 0 to nDenominator-1. (nError takes on all those values at some point while drawing the line, so they're all reasonable values.) The value we pick for the initial value of nError specifies where in the 3-2-2 pattern we start. Picking 0 will start us at the beginning of the longest run. Picking nDenominator/2 will put us right in the middle of a run. It's also equivalent to rounding instead of truncating, since rounding is the equivalent of adding 0.5 and truncating. Picking nDenominator-nStep will guarantee that we move up on the next step. Here's an example starting with nError = 3.

  6 ## 5 ## 4 ## 3 ### 2 ## 1 ## 0## 012345678901234

  Notice that this also means that a clever choice of nError will guarantee that lines drawn left-to-right produce the same result as lines drawn right-to-left (the "mid point" problem"), and in general that overlapping co-linear lines will turn on the same pixels (but they have to be truly co-linear even though they have integer coordinates). (I'm not sure how you would choose nError though. Sounds like an interesting problem for later investigation.)

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/N^th 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;
    }
}

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.