Bresenham Lines

The Bresenham Line algorithm is an approach to drawing integer-based lines. It comes from a time when real-time rendering on PCs was nearly non-existant, and the drawing of a simple image was measured not in milli- or nano-seconds, but in seconds and minutes. It offered primitive lines at high speed, especially in it’s assembly form, at the cost of fidelity.

Developed in 1962, it was later supplanted by Xiaolin Wu’s Line algorithm in 1992 which boasted fast antialiased lines (though slower then Bresenham). Wu’s arrival was nearly three decades ago, so of what use is Bresenham’s in 2019, 57 years after it’s initial development?

Well, sometimes you just need a simple, integer-based line algorithm. Which is exactly what Bresenham’s is.

The Algorithm

To start, Bresenham uses only the slope of the line, in the form of x and y delta values. That, used in combination with the current position, is sufficient for plotting the line points.

The algorithm takes in a starting point (x0, y0) and an ending point (x1, y1). It calculates the deltas and then begins to step along the line going from the start to the end. For each step, we always move once along the major line axis. If it is a horizontal line we always move along the x-axis, if it is a vertical line we always move along the y-axis.

All points in the plane can be split into two categories: those that lie exactly on the line, and those that are on one side of the line. During each step of the algorithm, we keep a running error value which tracks how far off from the line the last point was.

When the error value is too large (greater or equal to 0), then we move once along our minor axis. The pseudo-code for calculating the error is as follows:

1
2
3
4
5
6

error = (2 * minor delta) - major delta
for each step
    if error >= 0
        error += (2 * minor delta) - (2 * major delta)
    else
        error += (2 * minor delta)

Intuitively this can be thought of as we move once along the minor axis each time the line moves halfway between cells along the minor axis. Or, the error value is large enough that we know the next point on the minor axis is closer to the true line.

The graphic below shows the step-by-step progress of plotting a Bresenham line. Notice that only the first and last points are exactly on the line, and that we plot with an origin in the upper-left corner. Some adaptations have an origin in the center of the cell which misses the point that Bresenham is first and foremost an integer-based line.

As we step along the major x axis we can see the error increasing. Once it is greater or equal to zero, the error is re-adjusted and we move once along the minor y axis. The number of steps taken is always equal to the major delta plus one, so for a horizontal line we take (x1 - x0) + 1 steps.

Hopefully at this point you have an understanding of the Bresenham algorithm. Below is an implementation in C++, which can be easily adapted to any other language.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

void plotBresenham(int32_t x0, int32_t y0, int32_t x1, int32_t y1)
{
    // We always plot with the y-value increasing.
    // So swap y0 and y1 if y0 is above y1.
    if(y0 > y1)
    {
        std::swap(x0, x1);
        std::swap(y0, y1);
    }

    int32_t deltaX = x1 - x0;
    int32_t deltaY = y1 - y0;

    if(deltaX > 0)
    {
        // We are moving right-to-left
        if(deltaX > deltaY)
            plotBresenhamHorizontal(x0, y0, deltaX, deltaY, 1);
        else 
            plotBresenhamVertical(x0, y0, deltaX, deltaY, 1);
    }
    else 
    {
        // We are moving left-to-right
        deltaX = -deltaX;

        if(deltaX > deltaY)
            plotBresenhamHorizontal(x0, y0, deltaX, deltaY, -1);
        else
            plotBresenhamVertical(x0, y0, deltaX, deltaY, -1);
    }
}

void plotBresenhamHorizontal(int32_t x, int32_t y, int32_t deltaX, int32_t const deltaY, int32_t const dir)
{
    const int32_t deltaX2 = deltaX * 2;
    const int32_t deltaY2 = deltaY * 2;
    int32_t error = deltaY2 - deltaX; 

    plot(x, y);

    // Step along the major x axis
    while(deltaX--)
    {
        if(error >= 0)
        {
            // Step along the minor y axis
            y++;
            error -= deltaX2;
        }
        
        error += deltaY2;
        x += dir;

        plot(x, y);
    }
}

void plotBresenhamVertical(int32_t x, int32_t y, int32_t const deltaX, int32_t deltaY, int32_t const dir)
{
    const int32_t deltaX2 = deltaX * 2;
    const int32_t deltaY2 = deltaY * 2;
    int32_t error = deltaX2 - deltaY;

    plot(x, y);

    // Step along the major y axis
    while(deltaY--)
    {
        if(error >= 0)
        {
            // Step along the minor x axis
            x += dir;
            error -= deltaY2;
        }

        error += deltaX2;
        y++;

        plot(x, y);
    }
}

Uses and Adaptations

Cool, now what?

I assume that you came into this post with ideas in mind for what you were going to use Bresenham’s for. That you googled 2d line drawing or something similar, and if that is the case I will leave it to you to go forth and implement the algorithm for your own use.

However, if you stumbled upon this post by accident, or you knew what Bresenham’s was but didn’t have a good use for it, I will share my particular case.

In mid-2018 I began development on a modern Roguelike, Realms. Though it makes use of many newish technologies (Unity 5, C#, ECS programming, etc.) it, as a by-product of being a Roguelike, still has some old-school problems which require old-school solutions.

One such problem is calculating diagonal movement along a tile grid. In short, when traveling in the cardinal directions we can simply move one unit. The distance from (0, 0) to (1, 0) is 1. However moving diagonally from (0, 0) to (1, 1) the distance is √2 which isn’t quite as neat.

In fact, it can quickly start getting messy and you may begin contemplating using hex tiles instead. Plus there are addtional challenges when we want to move further than one space at a time, or we want to shoot a fireball at a far-away target. And that is where Bresenham’s comes in, and it can be seen in use by a multitude of games, including other Roguelikes such as Dungeon Crawl Stone Soup.

There is a follow-up ramble in which an implementation of Variable Length Bresenham Lines is discussed.

References

1. Abrash, Michael. Graphics Programming Black Book. Coriolis, 1997, pp. 654–678. http://downloads.gamedev.net/pdf/gpbb/gpbb35.pdf.