How to Draw a Line (Bresenham's Algorithm)

The line equation represented by y = mx + b, is one of the most basic formulas in plotting a line. Where m represents the slope, x represents the value in horizontal coordinate and b represents the offset from y.

Suppose we have a line segment (x₁, y₁) to (x₂, y₂), the slope can be easily computed as (y₂ - y₁) / (x₂ - x₁) or to understand it better, we can read it as an increment in y for every step in x.

In computer graphics, the very popular Bresenham's Algorithm for drawing a line to represent the closest approximation of a line in pixels can be derived by understanding the following:

• A pixel is represented as an integral data type, meaning that applying a fraction in either x or y would always be rounded down. So if the absolute value of | x₂ - x₁ | >= | y₂ - y₁ | then we can say that we can increment/decrement x by one (1) pixel as we draw the line segment from (x₁, y₁) then increment y by the computed slope (where absolute value is between 0 and 1) then converting y to an integral type before plotting the pixel. We can do the reverse if | x₂ - x₁ | < | y₂ - y₁ |.
• The increment/decrement of x and y depends on the difference of x₂ - x₁ and y₂ - y₁ for x and y respectively. If you think about it, if x₂ - x₁ > 0 then you need to increment if you're starting with x₁, if x₂ - x₁ = 0, do not increment/decrement x, else decrement x. The same can be said for y₂ - y₁ with respect to y.
• We can ignore the offset b and set it to 0 since we're starting to plot at (x₁, y₁).

The implementation of this line function using C/C++ and SDL is shown below. 

void drawLineSlope(SDL_Surface* surface, short x1, short y1, short x2, short y2, Uint32 rgba)
{
    short dx = x2 - x1;
    short dy = y2 - y1;
    short t = 0;
    short sdx = dx < 0 ? -1 : 1;
    short sdy = dy < 0 ? -surface->w : surface->w;
    short adx = dx < 0 ? dx * -1 : dx;
    short ady = dy < 0 ? dy * -1 : dy;

    float m;

    Uint32* pixel = (Uint32*)surface->pixels + (y1 * surface->w) + x1;

    if (adx >= ady)
    {
        if (dx == 0)
        {
            m = 0;
        }
        else
        {
            m = ((float)ady / adx);
        }

        float t = 0.0f;
        for (short i = 0; i < adx; ++i)
        {
            *(pixel + (i * sdx) + ((short)t * sdy)) = rgba;
            t += m;
        }
    }
    else
    {
        if (dy == 0)
        {
            m = 0;
        }
        else
        {
            m = ((float)adx / ady);
        }
        
        float t = 0.0f;
        for (short i = 0; i < ady; ++i)
        {
            *(pixel + ((short)t * sdx) + ((short)i * sdy)) = rgba;
            t += m;
        }
    }
}

The problem with this implementation is we're dealing with floating-point numbers and type conversions from float to integral data type.

As we've learned from my previous article (click here), floating-point computations are much slower than integral types (not to mention the typecasting). A detailed conversion of floating-point increments to integral data types is also discussed in the aforementioned article.

Below is the converted line function from floating-point to short data type:

void drawLine(SDL_Surface* surface, short x1, short y1, short x2, short y2, Uint32 rgba)
{
    short dx = x2 - x1;
    short dy = y2 - y1;
    short t = 0;
    short sdx = dx < 0 ? -1 : 1;
    short sdy = dy < 0 ? -surface->w : surface->w;
    short adx = dx < 0 ? dx * -1 : dx;
    short ady = dy < 0 ? dy * -1 : dy;

    // Position the cursor to x1, y1
    Uint32* pixel = (Uint32*)surface->pixels + (y1 * surface->w) + x1;

    if (adx >= ady)
    {
        for (int i = 0; i <= adx; ++i)
        {
            *pixel = rgba;
            t += ady;
            if (t >= adx)
            {
                pixel += sdy;
                t -= adx;
            }
            pixel +=sdx;
        }
    }
    else
    {
        for (int i = 0; i <= ady; ++i)
        {
            *pixel = rgba;
            t += adx;
            if (t >= ady)
            {
                pixel += sdx;
                t -= ady;
            }
            pixel += sdy;
        }
    }
}

This article is not intended to discuss how to install and use the SDL graphics library. It will be discussed in a separate article. But here some important notes you have to know when reading the code so it doesn't confuse you:

• The top-left most of the screen is (0, 0), as we move to the right, x increases, and as we move downwards, y increases. The program does not follow the cartesian plane but rather the default plane of the screen.
• The pixel pointer is pointed to the memory location of size surface->w and surface->h x pixel size which is unsigned int of 32-bits (or 4 bytes).
• The pixel pointer is unsigned int 32-bits, which means if you increment the pixel address by one, you will be pointed to the next pixel.
• y is incremented/decremented by surface->w instead of the slope or one (1), as the x and y coordinates are represented as one single stream of pixels in the memory buffer (surface). The size of each row in pixel memory is surface->w, hence to get pixel in coordinates (x, y) you do *(pixel + x + (y * surface->w)). 

Feel free to download and play around with the codes and/or to convert it to the programming language of your choice.