## 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.

MathLab has its own functions.

What would the complete code in C++?

Thack You.

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.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

Hi Elhassan,

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

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

thanks in advance

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

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.

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. π

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

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.

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);

}

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.

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.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

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.

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

[…] 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 […]

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.

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.

This is wonderful! Excellent post. The simplicity of your version is staggering.

This describes the original 8-connected version of the Bresenham algorithm. Any idea how you’d get the 4-connected version, i.e. avoiding moving along the diagonal? I’ve found some implementations of a 2d 4-connected version elsewhere

Best,

Dylan

Dylan,

I never thought of a 4-connected version. I don’t see, off the top of my head, how to do that in a simple, general way. I’ll give it a thought.