Bresenham's line algorithm

## Bresenham's line algorithm

Bresenham's line algorithm is a pretty standard implementation of line drawing in computer science. In math we're taught to use y = mx + b and calculate the value of y for each value of x, this works terribly for vertical lines as they don't have a valid value of m (the slope).

Instead, we use a computationally friendly version of line drawing. We start by :

- Calculating the delta of the two point of the line
- Deciding whether we should calculate each point relative to X or Y.
- Decide how many X steps to take before altering the value of Y or how many Y steps to take before altering the value of X
- Draw the pixels

Wikipedia declares Bresenham's algorithm in terms of pseudo-code which is pleasant enough to read, but not terribly useful in C++ as follows :

function line(x0, x1, y0, y1) boolean steep := abs(y1 - y0) > abs(x1 - x0) if steep then swap(x0, y0) swap(x1, y1) if x0 > x1 then swap(x0, x1) swap(y0, y1) int deltax := x1 - x0 int deltay := abs(y1 - y0) int error := deltax / 2 int ystep int y := y0 if y0 < y1 then ystep := 1 else ystep := -1 for x from x0 to x1 if steep then plot(y,x) else plot(x,y) error := error - deltay if error < 0 then y := y + ystep error := error + deltax

A C++ programmer on the other hand needs something a little more well suited for plugging into their program, so here's my version.

/// Draws a line from point (x0, y0) to point (x1, y1) with the given color /// /// \param x0 first point's x coordinate /// \param y0 first point's y coordinate /// \param x1 second point's x coordinate /// \param y1 second point's y coordinate /// \param color the color to draw the line void line(int32_t x0, int32_t y0, int32_t x1, int32_t y1, Color color) { bool steep = abs(y1 - y0) > abs(x1 - x0); if(steep) { int32_t temp = x0; x0 = y0; y0 = temp; temp = x1; x1 = y1; y1 = temp; } if(x0 > x1) { int32_t temp = x0; x0 = x1; x1 = temp; temp = y0; y0 = y1; y1 = temp; } int32_t deltaX = x1 - x0; int32_t deltaY = y1 - y0; int32_t error = deltaX >> 1; int32_t y = y0; int32_t yStep = -1; if(y0 < y1) yStep = 1; if(steep) { for(int32_t x=x0; x<=x1; x++) { setPixel(y, x, color); error -= deltaY; if(error < 0) { y += yStep; error += deltaY; } } } else { for(int32_t x=x0; x<=x1; x++) { setPixel(x, y, color); error -= deltaY; if(error < 0) { y += yStep; error += deltaX; } } } }

The code above is dependent on a few different items.

- Color is a type which is accepted across the whole library as a color. I use a simply RGB class
- setPixel() is a function for setting a pixel within the drawing context. It is possible to make this function faster by eliminating calls to a function and pushing the data directly to a buffer, but for cleanliness, I decided on this method.
- abs() which is a function that is defined in the standard C library but for some reason I always re-implement on my own as I don't trust the compiler I'm using ;(

page revision: 4, last edited: 05 Oct 2010 06:42