home | news | contact | about
Drawing Line Using Bresenham Algorithm
11 October 2007, 12:01 AM
The Bresenham algorithm is probably the most efficient of all line drawing algorithm. It greatly simplifies line drawing by using only integer variables, and importantly removing that costly division operation for slope. Before we begin impementing the algorithm, it is advisable to revise the method for drawing line in an inefficient way. This can help lay out the fundamentals of line algorithm, and is very useful since bresenham algorithm itself is an extension of the inefficient one anyway. The figure below, is circle showing eight octants of region and in the second region lies a line (x,y,x2,y2). The following java code is the logic for drawing line just in that region.

brline001.png
public void line(int x,int y,int x2, int y2, int color) {
    int w = x2 - x ;
    int h = y2 - y ;
    double m = h/(double)w ;
    double j = y ;
    for (int i=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.

public void line(int x,int y,int x2, int y2, int color) {
    int w = x2 - x ;
    int h = y2 - y ;
    int dy1 = -1 ;
    int longest = Math.abs(w) ;
    int shortest = Math.abs(h) ;
    int numerator = longest >> 1;
    for (int i=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.

public void line(int x,int y,int x2, int y2, int color) {
    int w = x2 - x ;
    int h = y2 - y ;
    int dy1 = 1 ;
    int longest = Math.abs(w) ;
    int shortest = Math.abs(h) ;
    int numerator = longest >> 1;
    for (int i=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--.

public void line(int x,int y,int x2, int y2, int color) {
    int w = x2 - x ;
    int h = y2 - y ;
    int dy1 = 1 ;
    int longest = Math.abs(w) ;
    int shortest = Math.abs(h) ;
    int numerator = longest >> 1;
    for (int i=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--.

public void line(int x,int y,int x2, int y2, int color) {
    int w = x2 - x ;
    int h = y2 - y ;
    int dy1 = -1 ;
    int longest = Math.abs(w) ;
    int shortest = Math.abs(h) ;
    int numerator = longest >> 1;
    for (int i=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,

public void line(int x,int y,int x2, int y2, int color) {
    int w = x2 - x ;
    int h = y2 - y ;
    int dx1 = 0, dy1 = 0, dx2 = 0, dy2 = 0 ;
    if (w<0) dx1 = -1 ; else if (w>0) dx1 = 1 ;
    if (h<0) dy1 = -1 ; else if (h>0) dy1 = 1 ;
    if (w<0) dx2 = -1 ; else if (w>0) dx2 = 1 ;
    int longest = Math.abs(w) ;
    int shortest = Math.abs(h) ;
    int numerator = longest >> 1 ;
    for (int i=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,

public void line(int x,int y,int x2, int y2, int color) {
    int w = x2 - x ;
    int h = y2 - y ;
    int dx1 = 0, dy1 = 0, dx2 = 0, dy2 = 0 ;
    if (w<0) dx1 = -1 ; else if (w>0) dx1 = 1 ;
    if (h<0) dy1 = -1 ; else if (h>0) dy1 = 1 ;
    if (w<0) dx2 = -1 ; else if (w>0) dx2 = 1 ;
    int longest = Math.abs(w) ;
    int shortest = Math.abs(h) ;
    if (!(longest>shortest)) {
        longest = Math.abs(h) ;
        shortest = Math.abs(w) ;
        if (h<0) dy2 = -1 ; else if (h>0) dy2 = 1 ;
        dx2 = 0 ;            
    }
    int numerator = longest >> 1 ;
    for (int i=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

~nminhtai, 7 September 2009, 08:00 AM
Great tutorial! Thanks a lot.
~Marc, 2 December 2009, 02:37 PM
thanks!

greetings form austria :)
~loreen, 26 March 2010, 11:56 AM
thanks a lot it is very helpful
~Tomas, 21 October 2010, 04:46 PM
Nice explanation. Thank you :)
~Ron, 7 April 2011, 09:02 AM
This helps me a lot, thank you :)
~salamath, 27 April 2011, 06:02 AM
Great tutorial! Thanks a lot.
~ishwor, 19 June 2011, 06:57 AM
it\'s so helpful
~bhatta, 19 June 2011, 06:59 AM
it,s great
~gopi, 1 August 2011, 11:49 AM
it is good
~sameer gupta, 22 September 2011, 06:25 AM
nice explanation........thanks for this.
~Vojtech, 25 October 2011, 04:05 PM
Thanks alot, saved my ass in school
~sajiK, 31 October 2011, 12:41 AM
Thanks, this helped a lot!
~sec, 4 November 2011, 09:25 AM
my JVM does not recognize the function
putpixel (x, y, color)
~Arya, 7 November 2011, 09:28 AM
please provide explanation also!
~Dutchman, 24 November 2011, 12:16 PM
Why 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 ?
~reza nikmaram, 26 November 2011, 01:27 AM
void putPixel(Graphics g, int x, int y)
{
g.drawLine( x , y, x, y);
}
~jayesh seeruthun, 5 March 2012, 04:50 AM
bull shit
~Zoharco, 25 April 2012, 04:51 AM
Very helpful. Tnx
~Pixelmed, 9 May 2012, 05:32 AM
Thanks from algeria ^^
~Pixelapp, 4 June 2012, 03:50 PM
My mind has been blown. Thnx from Santo Domingo and New York City.
~Priya, 23 July 2012, 03:03 AM
Nice job
~DafuQ, 26 October 2012, 12:03 PM
Gj, dude ;)
~sorubi, 19 November 2012, 03:23 AM
nice
~mohsen, 9 December 2012, 07:20 AM
I am looking for an algorithm to draw fat anti-aliased line (I want implement it on C++ and hardware too)
can anyone help me
~aero, 9 April 2013, 09:13 AM
Thanks! Awesome! :))
~Avi, 6 May 2013, 02:51 PM
Find 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 AM
Don\'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 PM
I almost understand it all, It certainly works fine for me ( pic32 + ssd1289 ( 240x320 lcd )
Very helpfull was stuck for ages....
many thanks indeed
~Surya Sharma, 18 July 2013, 09:29 AM
its really very nicely explained here...thnx
~Mr SCM, 23 August 2013, 11:47 AM
What if a line is thicker than one pixel?
~Sam Brown, 6 November 2013, 11:42 PM
Hi. 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
~gram, 1 May 2014, 04:00 AM
Line drawing algorithm with example explained here -
http://geeksprogrammings.blogspot.com/2014/02/line-drawing-algorithm-cpp.html
~Rectangle, 5 June 2014, 07:38 AM
If 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.
~Guillem Freixanet, 13 June 2014, 11:35 AM
Great code! thanks!!! it works great in Xmega128a4u.
~Michael Wesp, 22 June 2014, 05:28 PM
Last 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).
~some guy, 26 August 2014, 10:12 PM
Hi. 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 PM
Thank 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
~Chami, 8 February 2015, 04:47 AM
Thanks Soo Much... :) Very Helpfull. From Sri Lanka.
~hilal, 17 March 2015, 05:40 PM
The 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 ?
~Amit, 3 April 2015, 12:58 PM
http://www.techalg.com/
Post a comment~
Name*
An elephant is bigger than a mouse. true or false*
Comment*
Notes: The comment system is moderated.
Meaning your comment will not show until reviewed.