Variable Length Bresenham Lines

In my previous ramble, we explored the standard Bresenham algorithm for drawing 2D integer-based lines.

This time I will present a deoptimized variation of the Bresenham line. But first lets take a step back and review what exactly the standard algorithm sets out to achieve, which can be summed up as follows:

The Bresenham algorithm efficiently plots a line from an integer point (x0,y0) to (x1,y1).

But what if we want a variable length line? That starts from (x0,y0) but continues on for a specified range? In that case the standard implementation is insufficient due to its highly optimized nature.

The Intentional Limitations of Bresenham

The Bresenham algorithm defines lines based on octants, which is illustrated in the above graphic. Red-shaded octants represent horizontal (x-dominant) lines wheras green-shaded octants represent vertical (y-dominant) lines.

However, there is a clever optimization that the standard algorithm employs so that it must only consider four of the octants:

• Left-to-right, bottom-to-top (+x, +y) (horizontal)
• Right-to-left, bottom-to-top (-x, +y) (horizontal)
• Left-to-right, bottom-to-top (+x, +y) (vertical)
• Right-to-left, bottom-to-top (-x, +y) (vertical)

As you can see, Bresenham considers only the top-half of the octants and all lines are drawn from bottom-to-top. This is achieved by the swaps performed at the very beginning of the plotBresenham function which ensures that the line drawing always begins at the bottom. Regardless of whether the starting point (x0,y0) is the bottom or the top.

Because of this, depending on orientation, the line drawing will sometimes start at the first point (x0,y0) and at other times it will start at the last point (x1,y1). However, if we want to draw a variable length line we must always begin drawing at the starting point. This behavior is demonstrated in the demo below, where the line gets darker as it gets further along the drawing. You can see that depending on the line the starting point is either at the line start (grid center) or at the line end (mouse location).

(Keep in mind that HTML5 canvas elements have their origin at the top-left.)

If we attempt to draw a variable length line starting at the end then it will result in a line that is moving opposite of the intended direction, overshooting the starting point. So how can we overcome this deliberate behavior?

Creating a Variable Length Line

Fortunately, drawing a variable length line with Bresenham requires only a few modifications. Primarily we have to unwind our implementation and explicitly handle lines from all octants, and not just the four comprising the top half.

Once we handle all octants we then need to update the horizontal and vertical functions to iterate over the specified distance and not just from (x0,y0) to (x1,y1).

So to start, we first modify the plotBresenham function to remove the starting point swap and we also check against all octants:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void plotBresenham(int32_t const x0, int32_t const y0, int32_t const x1, int32_t const y1, int32_t const range = 0)
{
    const int32_t dx   = x1 - x0;
    const int32_t dy   = y1 - y0;
    const int32_t absX = std::abs(dx);
    const int32_t absY = std::abs(dy);
    const int32_t dirX = (dx > 0) ? 1 : -1;
    const int32_t dirY = (dy > 0) ? 1 : -1;
    
    if(absX > absY)
        plotBresenhamHorizontal(x0, y0, absX, absY, dirX, dirY, (range <= 0) ? absX : range);
    else
        plotBresenhamVertical(x0, y0, absX, absY, dirX, dirY, (range <= 0) ? absY : range);
}

Wait, thats it? Checking against all eight octants is less than half the code of checking only four of them? This is primarily possible since we use the absolute of the delta to determine whether its a horizontal or vertical line, instead of the original implementation which must check if the delta is negative.

The other two functions, plotBresenhamHorizontal and plotBresenhamVertical, receive only minor adjustments as well to handle variable length lines.

 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

void plotBresenhamHorizontal(int32_t x, int32_t y, int32_t const dx, int32_t const dy, int32_t const xdir, int32_t const ydir, int32_t range)
{
    const int32_t dx2 = dx * 2;
    const int32_t dy2 = dy * 2;
    int32_t err = dy2 - dx;
    
    plot(x, y);
    
    while(range--)
    {
        if(err >= 0)
        {
            y += ydir;
            err -= dx2;
        }
        
        err += dy2;
        x += xdir;
        
        plot(x, y);
    }
}

void plotBresenhamVertical(int32_t x, int32_t y, int32_t const dx, int32_t const dy, int32_t const xdir, int32_t const ydir, int32_t range)
{
    const int32_t dx2 = dx * 2;
    const int32_t dy2 = dy * 2;
    int32_t err = dx2 - dy;
    
    plot(x, y);
    
    while(range--)
    {
        if(err >= 0)
        {
            x += xdir;
            err -= dy2;
        }
        
        err += dx2;
        y += ydir;
        
        plot(x, y);
    }
}

And thats all there is. We can now draw variable length Bresenham lines starting from (x0,y0), we can also continue to draw only to (x1,y1) if the range parameter is set to zero. In either case, the lines are always drawn from start to finish.

Performance Comparison

At this point we can compare the performance of both implementations, as Bresenham was originally designed to be fast.

Surprisingly, however, the variable-length algorithms slightly outperforms the standard implementation in JavaScript performance tests. On my development machine running Chrome v72.0, the results are as follows:

Much could probably be said about the advancements in the past several decades that have allowed for the intentionally unoptimized version to outperform the optimized one, but all that we need to know is that the difference in performance when using the variable length algorithm is at worst negligible.

References

None this time.