Bresenham’s line drawing algorithm in any number of dimensions

edit: I should have called this “an algorithm that produces the same output as Bresenham’s algorithm, generalised to arbitrary dimensions” (see discussion below)

J.E. Bresenham published an algorithm in 1965, which is used to draw 2D digital lines. Many people have extended the algorithm to work in 3D, and I’ve even found a website with code for 4D, 5D and 6D versions of the algorithm. However, all the code I come across is way more complex that it needs to be, giving the impression that this is a complicated algorithm. Nothing is further from the truth! Drawing digital lines is the most simple and straight-forward task. I’m going to deviate from the classical thinking that an efficient algorithm should use only integer values. This will make our task trivial.

The first thing we need to realize is that, when walking from the start pixel to the end pixel, there is always one dimension along which we take integer steps. Along the other dimensions sometimes we’ll have to step, ans sometimes we won’t. This is, to me, the key finding in the Bresenham algorithm. This tells us how many pixels will compose the line. If we use more pixels, the line will be thickened at some points, or we’ll use some pixels more than once. If we use fewer pixels, the line will not appear continuous. Based on this 1-pixel step size in one dimension, we can easily calculate the sub-pixel step sizes we have to take in the other dimensions. We will then take these steps, computing floating-point coordinates, until we reach the end point. Each of the points we compute we’ll round to integer pixel coordinates for output. In the original algorithm, instead of computing a floating-point coordinate, an integer coordinate is computed, and an additional integer value accumulates the fractional error. These two approaches are equivalent, except that, when using floating-point values, everything becomes easier to understand.

Let’s write some MATLAB code. We’ll start with two random points to draw a line between (I’m using 3D points here, but you can use any number of dimensions):

p1 = round(rand(1,3)*20);
p2 = round(rand(1,3)*20);

Next, we take a floating-point vector variable, p, which will contain the sub-pixel coordinates of the line. We also compute the step size, s, which is the total distance travelled in each dimension divided by the longest distance. Thus, the vector s contains one element with value 1 (or -1), and other values that are smaller.

p = p1;
d = p2-p1;
N = max(abs(d));
s = d/N;

We need to take N steps of size s, then round each of the floating-point positions found:

disp(p1)
for ii=1:N
   p = p+s;
   disp(round(p))
end
    14     6    19
    13     6    18
    12     6    17
    11     7    16
    10     7    16
     9     7    15
     8     7    14
     7     8    13
     6     8    12
     5     8    11
     4     8    11
     3     9    10
     2     9     9
     1     9     8

There it is! Bresenham’s algorithm, for any number of dimensions, in 9 lines of code.

19 Responses to “Bresenham’s line drawing algorithm in any number of dimensions”

  1. On August 22nd, 2011, at 16:35, Sean O'Conor said:

    MathLab has its own functions.
    What would the complete code in C++?
    Thack You.

  2. On August 22nd, 2011, at 17:32, Cris Luengo said:

    Sean,

    The code in C or C++ would be identical, except you’d need to perform the operations separately on each of the components of the vectors. In the code above, p1, p2, p, d and s are all vectors with 3 components (or however many dimensions you want). All the operations performed on them (addition, subtraction, division, abs, round, etc.) are identical in C/C++, except they work on all the components of the vectors at once. In C/C++ you’d write a little loop for each of these operations (for (jj=0; jj<3; jj++) s(ii)=d(ii)/N), or spell them out if you want to fix how many dimensions you use.

  3. On November 16th, 2011, at 10:07, Elhassan said:

    Hi Cris

    What if I have a volume and I need to put a line between two point inside it. The volume has different sample size in each dimension, i.e the spacing between voxels are (0.5,0.5,2). how will this affect the algorithm.

    Regards
    Elhassan

  4. On November 16th, 2011, at 13:57, Cris Luengo said:

    Hi Elhassan,

    The voxel spacing should not at all affect the algorithm. A straight line stays straight after scaling one dimension.

  5. On December 10th, 2011, at 19:12, neam sal. said:

    please,how can i drive a 3D bresenham from 2d ???

    thanks in advance

  6. On December 12th, 2011, at 11:20, Cris Luengo said:

    Neam, I’m not sure what you are asking… Please clarify your question!

  7. On March 2nd, 2012, at 16:23, Howard said:

    Sorry to say, but this is NOT Bresenham. Bresenham is inherently based on integral type, hence the name DDA (Digital Differential Analyzer). Your deviation from the integral type is henceforth invalid and to call it even Bresenham-like is plainly wrong. I strongly suggest to read some Wiki pages on the topic to get the idea of what the whole story is about.

  8. On March 2nd, 2012, at 17:34, Cris Luengo said:

    Hi Howard,

    Technically you are absolutely right, but unless you’re forced to work on some antiquated equipment, there is no longer a speed advantage in avoiding floating-point calculations. In my experience, 99.9% of people wanting to draw “Bresenham lines” in their images don’t need to use integer types. They just want to draw a straight line. The algorithm above produces the exact same output as the Bresenham algorithm, and is much, much simpler. I’m pretty sure that people looking for integer-only calculations know what they’re doing, and don’t need my help. :)

  9. On March 5th, 2012, at 9:21, Howard said:

    Hi Chris,

    from the point what people need when doing some simple line drawing plus the point you made regarding speed of computation that’s perfectly valid. Also your output is quite the same as that of Bresenham’s algorithm which is a nice feature compared to simply “sampling” a line at arbitrary locations.
    Nevertheless, (at least imho) Bresenham is famous for doing all that in pure integer (though floating point was well known) and should be credited for that. Perhaps rephrasing to “drawing *lines* with Bresenham-like *quality*” makes everything perfect (even for naggers like me) ;)

    Best, Howard

  10. On March 5th, 2012, at 9:58, Cris Luengo said:

    Hi Howard,

    I think the most important innovation in Bresenham’s algorithm is the observation that you need to make integer steps in one direction, while updating the position in the other direction only once every few steps. This sounds obvious, but it’s not. It might be complicated to implement this with the integer-only restriction, but for me, that part is irrelevant today. But of course, we all get something different out of reading a paper, no?
    Anyway, I’ve added a comment at the top, hopefully now this post won’t be as offensive anymore. :)

    Cheers,
    Cris.

  11. On November 8th, 2012, at 10:44, Adrian said:

    Hello Chris,

    i am working on a localization problem where estimate my current pose using a particle filter. In each cycle there are created ~700 particles and each particle has to handle ~700 sensor points (laser scans). I have to calculate the pixels which the line crosses, starting on the position of one particle and ending at one senser point. This given i need to calculate the pixels for 49.000 lines within one cycle and i only have 80ms for that. It is hard to stick to this constraint, so i execute on graphic cards. But using the original Bresenham-Algorithm with its integer steps, it takes me twice the time for each cycle than using your implementation. : ) So, i just want to give you credit for that.

    Here a simple C implementation:

    #include

    int PointA_X, PointA_Y;

    int DX = PointB_X - PointA_X;
    int DY = PointB_Y - PointA_Y;

    int N = 0;

    if(abs(DX) > abs(DY)) N = abs(DX);
    else N = abs(DY);

    float SX = (float)DX/(float)N;
    float SY = (float)DY/(float)N;

    for(int jj=0; jj<N; jj++)
    {
    PX += SX;
    PY += SY;
    setPixel(PX,PY);
    }

  12. On December 12th, 2012, at 9:52, Sabrina said:

    Dear Chris,
    I dont understand how lucas kanade algorithm works to find motion vectors between frames in video. I also want to implement lucas kanade algorithm in matlab. please help me in this regard…. thanks in advance.

  13. On December 12th, 2012, at 14:17, Cris Luengo said:

    Dear Sabrina,

    I don’t have time right now to explain the algorithm in detail, but if you download DIPimage (there’s a link on the right column), you should look for a function called opticflow, which implements the Lucas and Kanade algorithm. It is an M-file, so you can see how it works.

  14. On February 26th, 2013, at 18:42, Prajwal Acharya said:

    Hi Chris, I need C++ code for line drawing algorithm in 3d, Here’s Matlab code but I really dont get it.., so would you please help me to get completed with my project..,
    Thanks,
    Cheers,
    Prajwal

  15. On February 27th, 2013, at 10:48, Cris Luengo said:

    Hi Parjawal,

    Look at the comment a few positions above yours, in it Adrian posted the C code for the algorithm as described on this post. Sorry I cannot help you personally with code, I really don’t have the time to do so.

  16. On June 12th, 2013, at 19:07, Calculate n-dimensional arc path - Tech Forum Network said:

    [...] found a nice multidimensional equivalent of Bresenham’s line drawing algo using floating point operations. Maybe a similar thing exists for drawing an [...]

  17. On June 20th, 2013, at 8:28, Bresenham’s Line Algorithm | nightowl.cc said:

    [...] interested in learning more about N-Dimensional Bresenham Line Algorithms, make sure to check out this post on Cris’s Image Analysis Blog. Why you’d need a Bresenham algorithm in 4, 5 or [...]

  18. On July 21st, 2013, at 23:53, Arpit Singh said:

    Codes on the internet give you the impression that this is a complicated algorithm. I agree with you on that, and you have busted that myth, thank you.

  19. On July 31st, 2013, at 17:15, Tim said:

    I’m sure you’re tired of the Brensham’s/not Brensham’s thing but to me there is an important difference: your algorithm does not produce the same result as the integer based line drawing algorithm described by Brensham. Floating point is inherently imprecise wheras the integer arithmatic used in Brensham’s is exact and avoids the rounding errors and approximations of floating point.

    Great blog btw! I’m glad I stumbled on it.

Leave a Reply

You can use these HTML tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Note: I moderate all comments. Comments without a clear relation to the text above will not be published.