Variable Length Bresenham Lines
In my previous ramble, we explored the standard Bresenham algorithm for drawing 2D integerbased 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. Redshaded octants represent horizontal (xdominant) lines wheras greenshaded octants represent vertical (ydominant) lines.
However, there is a clever optimization that the standard algorithm employs so that it must only consider four of the octants:
 Lefttoright, bottomtotop (+x, +y) (horizontal)
 Righttoleft, bottomtotop (x, +y) (horizontal)
 Lefttoright, bottomtotop (+x, +y) (vertical)
 Righttoleft, bottomtotop (x, +y) (vertical)
As you can see, Bresenham considers only the tophalf of the octants and all lines are drawn from bottomtotop. 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 topleft.)
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:


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.


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 variablelength algorithms slightly outperforms the standard implementation in JavaScript performance tests. On my development machine running Chrome v72.0, the results are as follows:
Implementation  Ops/sec  % 

Standard Bresenham  47,432,265  97.35% 
Variable Length Bresenham  48,722,462  100.00% 
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.