Bresenham's line-drawing algorithm

You are here: HomeMathematicsComputer Graphics → Bresenham's line-drawing algorithm

About

Bresenham's algorithm is an algorithm for drawing straight lines (and optionally performing antialiasing) using only integer arithmetic. In other words, given the coordinates of both ends of a line, the algorithm tells you which pixels to fill in to make a straight line between those points.

Derivation

Lines

The mathematical definition of a straight line is

P = Dt + S

For a line passing through two particular points, you can calculate D and S from the coordines the line is supposed to pass through, and then perform the calculation for every value of t from 0 to 1. That then gives you the coordinates of the pixels to fill in to make the line.

The trouble is the “for every value of t”. Since t is a fractional number, how big a step to we increase it by each time? Well, that depends on how long the line is, what angle it's at… and it's generally awkward and fiddly to calculate. There is a much easier way.

The Digital Differential Algorithm

For our next trick, we start by imagining then an invisible “pen” is sitting at the start coordinates for the line. What we're going to do is move the pen one pixel right at each stage, and we may or may not also move it up one pixel. In other words, each step is either straight right, or diagonally up and right. The trick now is simply figuring out when to do a diagonal instead of a straight. And then depends on the slope of the line we want to draw

So, the pen starts at (x0,y0) and finishes at (x1,y1), and we have to figure out how to move it from one to the other. The total number of pixels to move right is equal to x1 − x0, and the total number of pixels to move up is y1 − y0. Let's call these numbers dx and dy. We assume for now that dx ≥ dy — that is, the line slope is 45° or less.

Some simple maths tells us that for each 1 pixel step right, we should also move dy / dx pixels up. That number will usually be fractional; obviously we can only move in whole numbers of pixels! But here is what we will do: we will keep a counter named e which measures the ideal, fractional position to put the next pixel. When e > 0.5, we will actually move the pen up 1 pixel, and decrease e by 1 also. And each time we move 1 pixel right, we increase e by dy / dx.

And that, in short, is the DDA:

  1. Calculate dx = x1 − x0.
  2. Calculate dy = y1 − y0.
  3. Set e to exactly 0.
  4. Put the “pen” at (x0,y0).
  5. Draw a pixel at the current pen position.
  6. If the pen is at (x1,y1) then exit.
  7. Move the pen 1 pixel right.
  8. Increase e by dy / dx.
  9. If e > 0.5 then move the pen 1 pixel up and decrease e by 1.
  10. Go back to step 5.

In other words, repeat steps 5–10 until we get to the end, where step 6 makes us stop. (In practice, you would probably calculate dy / dx before the start of the loop, so you only have to calculate it once.)

Why Bresenham?

At this point, we have a way to draw straight lines. It works just fine. However, there is one last modification to be made: in a moment we will modify the algorithm so that it only uses whole numbers. That makes the algorithm look a fair bit more complicated. Why bother?

Well, because whole number calculations are easier, put simply. Whole numbers take up less space, there's no rounding errors to worry about (only overflows), and integer arithmetic is usually faster for computers to calculate. Vastly faster. And if you're building, say, a graphics card with build-in line-drawing hardware, it means you don't have to waste space on the silicon chip building a complicated floating-point arithmetic unit; you can use a much simpler integer one.

Introducing Bresenham's algorithm

And so at last, we come to Bresenham's algorithm itself. The idea is basically to take all the fractional quantities and multiply them by something so they all end up being whole numbers. The only really fractional values turn out to be e and dy / dx. Now, if we keep a counter named E who's value is “equivilent” to the real e multiplied by dx, then we can incriment it by dy at each step, and move the pen up when E is greater than half of dx.

Minor glitch: what if dx is an odd number? Then half of dx would still be fractional. This is easy to fix though; instead of testing E > dx / 2, we can perform the equivilent test 2*E > dx. Even better: computers can do multiplication by 2 very easily, so this extra calculation isn't much of a problem.

The end result of all this is Bresenham's line algorithm:

  1. Calculate dx = x1 − x0.
  2. Calculate dy = y1 − y0.
  3. Set E to exactly 0.
  4. Put the “pen” at (x0,y0).
  5. Draw a pixel at the current pen position.
  6. If the pen is at (x1,y1) then exit.
  7. Move the pen 1 pixel right.
  8. Increase W by dy.
  9. If 2*E > dx then move the pen 1 pixel up and decrease e by 1.
  10. Go back to step 5.

Final Adjustments

There is a small amount of extra fiddly stuff to make the algorithm work. The algorithm, as described above, assumes that the end point is to the right and above the start point, and the line slope is between 0° and 45°. What if that's not the case?

Well, if the end point is to the left and below the start point, you can just swap the ends round. The real problem is if the line is nearer to vertical than 45°, or if the line slopes down from left-to-right instead of up. If the line is nearly vertical, you can swap the X and Y coordinates and run the algorithm just the same. Similarly, if the line slopes downward, you just move the pen down instead of up at the appropriate steps.

So, the final algorithm is a little bit tricky to get right, but in principle it's merely a souped-up version of the DDA.

Next time you draw a bording old straight line, spare a thought for how much effort your computer is going through just to do that!

Antialiasing

It is possible to enhance the algorithm further to perform antialiasing. That is, instead of filling pixels in pure black, we fill then with shades of grey to indicate how near each pixel is to the “true” position of the line. Well, in the DDA, this is simplicity itself; the colour of the pixel under the pen is set to e, and the pixel above it is set to 1 − e.

The only complication in Bresenham's algorithm is that we don't have e, only E. But it's quite easy to take the number of possible shades of grey, divide that by dx, and then multiply E by the answer at each state to get a whole-number grey level.

Other Algorithms

Using a similar technique to the above, it's possible (though mildly more complicated) to draw circles as well. Starting at the bottom of the circle, we always move 1 pixel right, and sometimes move 1 pixel up. To decide whether to move up, we calculate (in integers) the distance from the pen position to the center, and if it's more than 1 pixel out, we move up.

(Unlike a line, a circle's equation is quadratic. That is, it involves squaring variables. However, since x incriments in steps of 1, it's quite easy to compute the new x2 from the old one without performing any costly multiplications (except by 2). Similarly for y. If the square of the radius is computes at the start of the loop, no (extremely expensive) square root operations are required.)


Valid XHTML 1.0 Strict Valid CSS 2

Generated by Indoculate Release #2b (17-Feb-2007) [Compiled by GHC 6.6]. Document generated on 2007-03-23 20:40:32.