Breshenham’s Line-Drawing Algorithm

July 17, 2012

The algorithm that raster graphics devices use to draw straight lines was invented by Jack Breshenham of IBM in 1962. The algorithm is favored because it uses only simple arithmetic, addition and subtraction and multiplication by 2, making it suitable both for software (graphics libraries, or languages such as PostScript) and for hardware (graphics cards, video displays, plotters).

Assume coordinates with point (0,0) at the top left, increasing down and right, where the first coordinate is the column and the second coordinate is the row, that all pixels have integer coordinates, and the task is to draw a line from (x0, y0) to (x1, y1). Assume for the moment a line that slopes downward from left to right (so both x and y are increasing) at less than a 45 degree angle (so y increases faster than x). For each x from x0 to x1, the algorithm chooses the y between y0 and y1 that is closest to the ideal y for the corresponding x. But instead of computing fractional y, the algorithm keeps track of the error between the current value of y and its idealized value. At each increase in x, the error is increased by the slope of the line, and if the error exceeds half a pixel, y increases by 1 and the error decreases by 1. Similar calculations can be made for other orientations of the line.

Your task is to write a function that implements Breshenham’s line-drawing algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

4 Responses to “Breshenham’s Line-Drawing Algorithm”

  1. madscifi said
    #include <iostream>
    #include <cstdlib>
    #include <functional>
    
    void DrawLine( int x0, int y0, int x1, int y1, std::function<void(int,int)> setpixel )
    {
        int absDx = abs(x1 - x0);
        int absDy = abs(y1 - y0 );
        bool xySwapped = false;
        if( absDy > absDx )
        {
            xySwapped = true;
            std::swap( x0, y0 );
            std::swap( x1, y1 );
            std::swap( absDx, absDy );
        }
        int xStep = ( x0 > x1 ) ? -1 : 1;
        int yStep = ( y0 > y1 ) ? -1 : 1;
        int err = absDx / 2;
        for(;;)
        {
            if( xySwapped ) setpixel(y0,x0);
            else setpixel(x0,y0);
    
            if( x0 == x1 ) break;
    
            err -= absDy;
            if( err < 0 )
            {
                y0 += yStep;
                err += absDx;
            }
            x0 += xStep;
        }
    }
    
    int main( int argc, char**argv )
    {
        std::cout << "DrawLine(0,0,10,12)" << std::endl;
        DrawLine(0,0,10,12,[](int x, int y){ std::cout << x << " " << y << std::endl; } );
        std::cout << std::endl;
        return 0;
    }
    
  2. added this to digg cerkiner.tk

  3. A Python solution using curses library:

    import curses
    
    
    def breshenham(x0, y0, x1, y1, fn):
        dx = abs(x1 - x0)
        dy = abs(y1 - y0)
        sx = 1 if x0 < x1 else -1
        sy = 1 if y0 < y1 else -1
        err = dx - dy
    
        while x0 != x1 and y0 != y1:
            fn(x0, y0)
            err2 = err * 2
            if err2 > -dy:
                err -= dy
                x0 += sx
            if err2 < dx:
                err += dx
                y0 += sy
    
    
    def draw_line(screen, x0, y0, x1, y1):
    
        def putpixel(x, y):
            screen.addch(y, x, '*')
    
        screen.border()
        breshenham(x0, y0, x1, y1, putpixel)
        screen.getch()
    
    curses.wrapper(draw_line, 5, 5, 20, 20)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: