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 :

1. Calculating the delta of the two point of the line
2. Deciding whether we should calculate each point relative to X or Y.
3. 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
4. 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.

1. Color is a type which is accepted across the whole library as a color. I use a simply RGB class
2. 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.
3. 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