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 |
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.
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.
nStep
/
nDenominator
? That is, will it help to find the GCF and divide?
Well, calculating
the GCF is O(n^{2}) 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.
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.
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.)
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.
3 # 2 ## 1 ## 0### 01234567 |
6 # 5 ## 4 ## 3 ### 2 ## 1 ## 0### 012345678901234 |
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 |
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; } }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.
Louis K. Thomas <loui sth@hotm ail.co m> | Auth | 2008-05-03 (3344 days ago) |