Drawing Line Using Bresenham Algorithm

11 October 2007, 12:01 AM

publicvoidline(intx,inty,intx2,inty2,intcolor) {intw = x2 - x ;inth = y2 - y ;doublem = h/(double)w ;doublej = y ;for(inti=x;i<=x2;i++) { putpixel(i,(int)j,color) ; j += m ; } }

As you can see that is one inefficient code, but it works just fine. Take note however, above is not a full line function, it only draws properly in the second octant region. A full line function is available at the end of this article if you can't be bothered with understanding the algorithm.

If we look at the fraction m = h/w and the addition j += m, the operation is actually increasing the numerator h, and keeping the denominator w constant whenever m is added to j. When the numerator h becomes equal or greater than the denominator w, the numerator is subtracted with the denominator and j is increased by 1. This reasoning is what bresenham algorithm is about, an with this the algorithm is able to replace the division and real number operation with just additions and a simple rule. See code below for the implementation of bresenham algorithm in the second octant.

publicvoidline(intx,inty,intx2,inty2,intcolor) {intw = x2 - x ;inth = y2 - y ;intdy1 = -1 ;intlongest = Math.abs(w) ;intshortest = Math.abs(h) ;intnumerator = longest >> 1;for(inti=0;i<=longest;i++) { putpixel(x,y,color) ; numerator += shortest ;if(!(numerator<longest)) { numerator -= longest ; y += dy1 ; } x++ ; } }

Notice the line

*numerator = longest >> 1*? Technically it means numerator is equal to half of

*longest*, and is important to avoid y from being rounded at every whole number instead of halfway point.

Writing a complete bresenham line function will require consideration of all eight octants and it is easy to imagine to have eight copies of above code. Fortunately the copies are all very similar since they are just mirrors of each other, and it is very easy to write a generic code that takes care of all eight octants. But first let us look on the similarities in different octants.

Drawing a line in the third octant is simply drawing a line in the second octant with mirrored y. This can be reflected by setting dy1 = 1, instead of -1. See below at line number four for the difference.

publicvoidline(intx,inty,intx2,inty2,intcolor) {intw = x2 - x ;inth = y2 - y ;intdy1 = 1 ;intlongest = Math.abs(w) ;intshortest = Math.abs(h) ;intnumerator = longest >> 1;for(inti=0;i<=longest;i++) { putpixel(x,y,color) ; numerator += shortest ;if(!(numerator<longest)) { numerator -= longest ; y += dy1 ; } x++ ; } }

The sixth octant is the same with the third one, except with mirrored x. This can be done by changing the line x++ to x--.

publicvoidline(intx,inty,intx2,inty2,intcolor) {intw = x2 - x ;inth = y2 - y ;intdy1 = 1 ;intlongest = Math.abs(w) ;intshortest = Math.abs(h) ;intnumerator = longest >> 1;for(inti=0;i<=longest;i++) { putpixel(x,y,color) ; numerator += shortest ;if(!(numerator<longest)) { numerator -= longest ; y += dy1 ; } x-- ; } }

The same goes for the seventh octant, it is the same with the second octant except with mirrored x. Again this can be done by changing the line x++ to x--.

publicvoidline(intx,inty,intx2,inty2,intcolor) {intw = x2 - x ;inth = y2 - y ;intdy1 = -1 ;intlongest = Math.abs(w) ;intshortest = Math.abs(h) ;intnumerator = longest >> 1;for(inti=0;i<=longest;i++) { putpixel(x,y,color) ; numerator += shortest ;if(!(numerator<longest)) { numerator -= longest ; y += dy1 ; } x-- ; } }

Looking at all this similarities, we can now devise a more generic function that draws line in the second, third, sixth, and seventh octants. Below is the code just to do that,

publicvoidline(intx,inty,intx2,inty2,intcolor) {intw = x2 - x ;inth = y2 - y ;intdx1 = 0, dy1 = 0, dx2 = 0, dy2 = 0 ;if(w<0) dx1 = -1 ;elseif(w>0) dx1 = 1 ;if(h<0) dy1 = -1 ;elseif(h>0) dy1 = 1 ;if(w<0) dx2 = -1 ;elseif(w>0) dx2 = 1 ;intlongest = Math.abs(w) ;intshortest = Math.abs(h) ;intnumerator = longest >> 1 ;for(inti=0;i<=longest;i++) { putpixel(x,y,color) ; numerator += shortest ;if(!(numerator<longest)) { numerator -= longest ; x += dx1 ; y += dy1 ; }else{ x += dx2 ; y += dy2 ; } } }

At this point we have a function that can draw lines on the second, third, sixth, and seventh octants. However this is still incomplete, we need to consider the others before we can call it a full line function. To do that, we observe that lines that fall in the first, fourth, fifth, and eight octants will have its height longer than its width, unlike in the second, third, sixth, and seventh octant where the lines have widths longer than heights. By including this in the logic, the result will be a full implementation of bresenham algorithm for drawing line on all octants.

Here is the full implementation,

publicvoidline(intx,inty,intx2,inty2,intcolor) {intw = x2 - x ;inth = y2 - y ;intdx1 = 0, dy1 = 0, dx2 = 0, dy2 = 0 ;if(w<0) dx1 = -1 ;elseif(w>0) dx1 = 1 ;if(h<0) dy1 = -1 ;elseif(h>0) dy1 = 1 ;if(w<0) dx2 = -1 ;elseif(w>0) dx2 = 1 ;intlongest = Math.abs(w) ;intshortest = Math.abs(h) ;if(!(longest>shortest)) { longest = Math.abs(h) ; shortest = Math.abs(w) ;if(h<0) dy2 = -1 ;elseif(h>0) dy2 = 1 ; dx2 = 0 ; }intnumerator = longest >> 1 ;for(inti=0;i<=longest;i++) { putpixel(x,y,color) ; numerator += shortest ;if(!(numerator<longest)) { numerator -= longest ; x += dx1 ; y += dy1 ; }else{ x += dx2 ; y += dy2 ; } } }

Last edited on 15 October 2007

### Comments

~

**Marc**, 2 December 2009, 02:37 PMthanks!

greetings form austria :)

greetings form austria :)

~

**loreen**, 26 March 2010, 11:56 AMthanks a lot it is very helpful

~

**Tomas**, 21 October 2010, 04:46 PMNice explanation. Thank you :)

~

**Ron**, 7 April 2011, 09:02 AMThis helps me a lot, thank you :)

~

**salamath**, 27 April 2011, 06:02 AMGreat tutorial! Thanks a lot.

~

**ishwor**, 19 June 2011, 06:57 AMit\'s so helpful

~

**bhatta**, 19 June 2011, 06:59 AMit,s great

~

**gopi**, 1 August 2011, 11:49 AMit is good

~

**sameer gupta**, 22 September 2011, 06:25 AMnice explanation........thanks for this.

~

**Vojtech**, 25 October 2011, 04:05 PMThanks alot, saved my ass in school

~

**sajiK**, 31 October 2011, 12:41 AMThanks, this helped a lot!

~

**sec**, 4 November 2011, 09:25 AMmy JVM does not recognize the function

putpixel (x, y, color)

putpixel (x, y, color)

~

**Arya**, 7 November 2011, 09:28 AMplease provide explanation also!

~

**Dutchman**, 24 November 2011, 12:16 PMWhy does the 3. if test the same thing as the first one ? (w<0)

Couldn\'t you combine the 1. and 3. if query in one ?

Couldn\'t you combine the 1. and 3. if query in one ?

~

**reza nikmaram**, 26 November 2011, 01:27 AMvoid putPixel(Graphics g, int x, int y)

{

g.drawLine( x , y, x, y);

}

{

g.drawLine( x , y, x, y);

}

~

**jayesh seeruthun**, 5 March 2012, 04:50 AMbull shit

~

**Zoharco**, 25 April 2012, 04:51 AMVery helpful. Tnx

~

**Pixelmed**, 9 May 2012, 05:32 AMThanks from algeria ^^

~

**Pixelapp**, 4 June 2012, 03:50 PMMy mind has been blown. Thnx from Santo Domingo and New York City.

~

**Priya**, 23 July 2012, 03:03 AMNice job

~

**DafuQ**, 26 October 2012, 12:03 PMGj, dude ;)

~

**sorubi**, 19 November 2012, 03:23 AMnice

~

**mohsen**, 9 December 2012, 07:20 AMI am looking for an algorithm to draw fat anti-aliased line (I want implement it on C++ and hardware too)

can anyone help me

can anyone help me

~

**aero**, 9 April 2013, 09:13 AMThanks! Awesome! :))

~

**Avi**, 6 May 2013, 02:51 PMFind complete code in C++ to Draw a Line using Bresenham Algorithm at http://www.etechplanet.com/codesnippets/computer-graphics-draw-a-line-using-bresenham-algorithm.aspx

~

**me**, 10 June 2013, 04:53 AMDon\'t bullshit this post, it was very helpfull and it realy work. I implemented it in hardware and on vga the lines were very well drawn.

~

**spanner**, 29 June 2013, 10:35 PMI almost understand it all, It certainly works fine for me ( pic32 + ssd1289 ( 240x320 lcd )

Very helpfull was stuck for ages....

many thanks indeed

Very helpfull was stuck for ages....

many thanks indeed

~

**Surya Sharma**, 18 July 2013, 09:29 AMits really very nicely explained here...thnx

~

**Mr SCM**, 23 August 2013, 11:47 AMWhat if a line is thicker than one pixel?

~

**Sam Brown**, 6 November 2013, 11:42 PMHi. Great explanation, thanks.

Having trouble getting it to work on Casio graphing calculator. The bitshitfting is confusing me. What is the difference between \"longest >> 1\" and \"longest / 2\" ?

My current implementation seems to work but is inaccurate reaching the end points. Sometimes misses by quite a few pixels off to the side, or a few pixels past the end point. Although the line is generally going in the right direction. Accumulated error due to >> missing on calc?

Thanks again

Sam

Having trouble getting it to work on Casio graphing calculator. The bitshitfting is confusing me. What is the difference between \"longest >> 1\" and \"longest / 2\" ?

My current implementation seems to work but is inaccurate reaching the end points. Sometimes misses by quite a few pixels off to the side, or a few pixels past the end point. Although the line is generally going in the right direction. Accumulated error due to >> missing on calc?

Thanks again

Sam

~

**gram**, 1 May 2014, 04:00 AMLine drawing algorithm with example explained here -

http://geeksprogrammings.blogspot.com/2014/02/line-drawing-algorithm-cpp.html

http://geeksprogrammings.blogspot.com/2014/02/line-drawing-algorithm-cpp.html

~

**Rectangle**, 5 June 2014, 07:38 AMIf you require a line with a width greater than one pixel, just draw two or more lines side-by-side...

As for anti-aliasing, the easiest way would be to do the same thing, but with slightly shorter outer lines, and the color of the outer lines would need to be linearly interpolated into a darker color from the color of the line in the center. For better anti-aliasing, use google.

As for anti-aliasing, the easiest way would be to do the same thing, but with slightly shorter outer lines, and the color of the outer lines would need to be linearly interpolated into a darker color from the color of the line in the center. For better anti-aliasing, use google.

~

**Guillem Freixanet**, 13 June 2014, 11:35 AMGreat code! thanks!!! it works great in Xmega128a4u.

~

**Michael Wesp**, 22 June 2014, 05:28 PMLast one works great. Best I have found. Thanks Dude.

~

**Nalvin**, 13 August 2014, 05:30 AM@Avi : Il n\'y a pas besoin d\'autant de code en C, le miens prend 33 lignes en à la norme de 42 (une école sur Paris).

Translate : There is no need as much code in C, the mine takes 33 lines to the standard of 42 (a school of Paris).

Translate : There is no need as much code in C, the mine takes 33 lines to the standard of 42 (a school of Paris).

~

**some guy**, 26 August 2014, 10:12 PMHi. Just wanted to ask if it\'s OK with you to use your implementation of this algorithm in a commercial application. Would you like to be credited in any way?

~

**BigSmile**, 19 January 2015, 02:25 PMThank you for explaining. It gave me an idea where to start thinking when implementing this Algorithm.

Some Parts can be simplified though.

Anyway. Big Thumbs up for you

Some Parts can be simplified though.

Anyway. Big Thumbs up for you

~

**Chami**, 8 February 2015, 04:47 AMThanks Soo Much... :) Very Helpfull. From Sri Lanka.

~

**hilal**, 17 March 2015, 05:40 PMThe function putpixel(int,int,int) does not exist.

void putPixel(Graphics g, int x, int y)

{

g.drawLine( x , y, x, y);

}

it is not enough because \"putpixel(i,(int)j,colorV);\" is not matching with the function ?

void putPixel(Graphics g, int x, int y)

{

g.drawLine( x , y, x, y);

}

it is not enough because \"putpixel(i,(int)j,colorV);\" is not matching with the function ?

~

**Amit**, 3 April 2015, 12:58 PMhttp://www.techalg.com/

Post a comment~

nminhtai, 7 September 2009, 08:00 AM