Thursday, January 3, 2013

Simplified DDA/Bresenham-like algorithm for line drawing in 2D and 3D

Implementing Bresenham's line drawing algorithm is a pain and has some drawbacks for motion control applications. In particular, it relies on swapping endpoints of the line-segments to achieve specific preconditions and has eight configurations (in 2D alone!) that must be implemented to draw arbitrarily oriented lines.  This has big disadvantages for implementation in high dimension (6D in my case) and even bigger disadvantages for motion control, where you want to move from point A to point B, not arbitrarily (and incorrectly) assume you're already at B and then move backward to A because, hey, order doesn't matter!

I recently ran across Cris Luengo's blog post on a Bresenham-equivalent algorithm in arbitrary dimension based on floating point rounding.  This is likely to be faster on modern machines than the integer only version, simply because i) floating point ops and casting are cheap and ii) branches are expensive, which is effectively the opposite of the case when the original Bresenham algorithm was developed.  He claims the method reproduces the original Bresenham algorithm's plotted pixels, although in my tests I seem to get occasional errant pixels even with double precision.  It may well be an error on my part.

Regardless, this post gave me the idea of just implementing Bresenham's algorithm in a parametric form, accumulating error and advancing pixels in both (all) coordinates in the same manner.  This is considerably more costly in 2D, where you double the operations required, but the relative cost decreases as the dimension increases. Since I'm targeting 6D, the relative cost is only 1/5th, and the simplicity of implementation and lack of endpoint switching more than makes up for it.

I've put up simple C++ code for 2D and 3D integer-only line drawing using a test implementation that is freely available for any use.  It draws 50 random lines with the integer only algorithm described above into the green channel and the same 50 lines with the floating point rounding method (in double precision) into the red channel. The results are below, if the algorithms matched exactly, all the lines would be yellow, with no red or green pixels anywhere.

It looks okay at first, but if you zoom in and look carefully you can see a few red and green pixels around. Regardless, they both do a good job of plotting lines, and if my code is off by a step or two occasionally it's not the end of the world.

No comments: