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 ;(