Bresenham’s line algorithm

On the main page I describe line-drawing using linear interpolation. It’s simple. It’s fast. It generalizes to 3D, hexagons, colors, and other types of spaces. But Bresenham’s line algorithm^[1] is the famous one. The original paper says:

The algorithm may be programmed without multiplication or division instructions and is efficient with respect to speed of execution and memory utilization.

and Wikipedia says “it uses only integer addition, subtraction, and bit shifting, all of which are very cheap operations in historically common computer architectures”.

The label “Bresenham” is used today for a family of algorithms extending or modifying Bresenham’s original algorithm.

This bothered me a little bit because there’s the original algorithm with separate code for each of eight octants, and there are also simplified versions that collapse some of the octants together. There’s a collection of these simplified versions on rosettacode^[2] and also on roguebasin^[3] (a site for roguelike-games). These are the things I was curious about:

I decided to look at Bresenham’s 1965 paper^[4] (mirror). The description at the top is:

and … there isn’t separate code for the eight octants. I’ve been wrong all this time. In fact there isn’t any code at all. But there’s a table of eight octants and how to use that to set up the equations, and then from the equations how to construct an algorithm. So that makes me think it was intended to be eight separate loops. Some of those loops might be combinable. Also, the original paper wasn’t about graphics on a screen. It was about how to draw lines on a pen plotter. I think it would be a few more years before people would be drawing raster graphics on screens, although I’m not able to find a reference right now.

Also, Bresenham’s 1965 paper says:

This paper is based on “An incremental algorithm for digital plotting,” presented by the author at the ACM National Conference at Denver, Colorado, on August 30, 1963.

However I can’t find that 1963 paper.

 1  Output#

Let’s start with the linear interpolation algorithm from the main page.

function diagonal_distance(p0, p1) {
    let dx = p1.x - p0.x, dy = p1.y - p0.y;
    return Math.max(Math.abs(dx), Math.abs(dy));
}

function lerp(start, end, t) {
    return start * (1.0 - t) + t * end;
}

function lerp_line(p0, p1) {
    let points = [];
    let N = diagonal_distance(p0, p1);
    for (let step = 0; step <= N; step++) {
        let t = N === 0? 0.0 : step / N;
        let x = Math.round(lerp(p0.x, p1.x, t));
        let y = Math.round(lerp(p0.y, p1.y, t));
        points.push({x, y});
    }
    return points;
}

And let’s compare to DDA line drawing^[5], which is a version of the above code transformed with inlining and unrolling optimizations:

function dda_line(p0, p1) {
    let points = [];
    let dx = p1.x - p0.x;
    let dy = p1.y - p0.y;
    let N = Math.max(Math.abs(dx), Math.abs(dy));
    dx /= N;
    dy /= N;
    let {x, y} = p0;
    for (let step = 0; step <= N; step++) {
        points.push({x: Math.round(x), y: Math.round(y)});
        x += dx;
        y += dy;
    }
    return points;
}

Since DDA is an optimized version of linear interpolation lines, we should get the same results. Do we?

The answer is … no. That’s interesting. They mostly match but DDA uses repeated addition, and that means the floating point error accumulates more than using the original multiplication.

TODO: test variants of bresenham that use >= instead of > or vice versa

TODO: splom to show all comparisons at once, maybe just a summary of the count; probably should generate this offline

TODO: visualization that compares each one algorithm to the majority output from all the algorithms? not sure this is interesting

 2  Property: order#

For some applications all we care about is the set of points on the line. Drawing a line from A to B can return the points in any order.

For some applications we also care about the order of those points. Drawing a line from A to B should return A first and B last.

 3  Property: symmetry#

Take a line from P to Q and calculate the line from Q to P, and see if they hit the same points. Flag the ones that don’t. Count how many mismatches there are for each algorithm.

The algorithms that flip P and Q naturally won’t have any mismatches.

I’m curious whether adding an ε value like 1e-6 will make a difference here. I should test that.

 4  Property: rotation#

An extension of left/right symmetry is that the line should be rotateable 90°, and then left/right symmetry is 180°

How about reflection?

 5  Property: translation#

I’ve assumed that the line drawing algorithms behave identically if both points are translated by a fixed amount. This may not be the case. I can take some lines and translate them and see if they produce the same output.

Notes:

1. Linear interpolation has minor changes at different offsets.
2. DDA has a lot of changes at higher offsets. It’s losing precision.
3. Bresenham has no changes at any offsets. This is good.

 6  Performance#

In my brief tests, I found optimized linear interpolation (called DDA^[6]) to be as fast as Bresenham’s line algorithm, but benchmarking is tricky and I don’t have high confidence in this. I can believe it to be as fast though, since Bresenham’s algorithm was designed for the computers of the 1960s. Floating point was slow and branches were fast. Today’s CPUs are different. Floating point is fast and branches are slow. The linear interpolation algorithm has a much tighter inner loop, with no branches. There are other algorithms that claim to be faster than Bresenham’s^[7]; I can’t get their benchmark code to run properly though.

Bresenham also made a second line drawing algorithm, described by demofox^[8] and tomforsyth^[9].

 7  More#