Thread: Line Drawing Algorithm

  1. #1
    Adamant Programmer Axpen's Avatar
    Join Date
    Jun 2003
    Location
    USA
    Posts
    42

    Lightbulb Line Drawing Algorithm


    Ok i've searched the forums and found little algorithms that support my cause or work in the expected way. My problem is that I want a line drawing algorithm that is as versital as possible, however, being able to accept stuff like
    Code:
    line(12,12,-5,-5);
    really isnt too important cause even I can do the math to make that signed 1 or just decrement using sign -1.

    Anywho the real problem isnt my knowing of what I want it to do, its my lack of math knowledge , what I want is something like this:
    Code:
    void line(const int x1, const int y1, const int x2, const int y2, unsigned char color);
    
    int main(void)
    {
     line(0,0,5,4);
     return 0;
    }
    
    output (it should plot these coordinates):
    X,Y  |  Changed
    0,0  |  =,=
    1,1  |  +,+
    2,2  |  +,+
    3,2  |  +,=
    4,3  |  +,+
    5,4  |  +,+
    
    OR In Graphical Form:
    
      0 1 2 3 4 5
      _ _ _ _ _ _
    0|0|_|_|_|_|_|
    1|_|0|_|_|_|_|
    2|_|_|0|0|_|_|
    3|_|_|_|_|0|_|
    4|_|_|_|_|_|0|
    Just so you know the line drawing algorithm I want is the one from MS Paint. It seems to produce the smoothest cleanest lines. Anyways, it's painfully obvious that half way through the plotting the line changes course from just a straight diagonal line. Its definately got a pattern to it, it seems to figure that half way through it sees that to meet the end it must move over x and not y.

    As I have mentioned before I have seen MANY algorithms on cprogramming.com and other related sites, it just sucks that none of them produce the right results. I dont really have a preference if its following old skool line plotting algorithms or in the new bresenhams line drawing algorithm. I'd actually rather have a psuedo code type response. I'm just really fed up with this line thing so i'll take whatever I can get .

    Well this is my plauge and its been bugging me for 5 days now, I really appriciate any and all algorithm suggestions and thoughts,
    Alex
    The Man With 3 Ears::Oh no better get the huskers

    Download Helppc by David Jurgens, It's a FANTASTIC Reference!!!

    In Case I Forget I Have:
    Windows XP
    For My 32-bit Questions:
    Dev C++ (mainly just use its mingw)
    For My 16-bit Questions:
    Borland Turbo C++ 1.01

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Try Bresenham's Line Algorithm

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Exactly. I think this might help.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Adamant Programmer Axpen's Avatar
    Join Date
    Jun 2003
    Location
    USA
    Posts
    42
    Tried that but it just doesn't produce the right pixels, it makes:
    Code:
    XX****
    ***X**
    ****X*
    *****X
    *****X
    or such, I just wonder how a math algorithm decides the divide by powers or such, cause MSPaints Algorithm seems to figure out in the middle to move over, and its very elegant looking. Any math people that know how this could be accomplished please share your wisdom.

    Thanks for all the replys thus far,
    Alex
    The Man With 3 Ears::Oh no better get the huskers

    Download Helppc by David Jurgens, It's a FANTASTIC Reference!!!

    In Case I Forget I Have:
    Windows XP
    For My 32-bit Questions:
    Dev C++ (mainly just use its mingw)
    For My 16-bit Questions:
    Borland Turbo C++ 1.01

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Give me a second . . . .

    Code:
    void line(int startx, int starty, int endx, int endy, int color) {
        int t, distance;
        int xerr=0, yerr=0, delta_x, delta_y;
        int incx, incy;
    
        /* compute the distances in both directions */
        delta_x=endx-startx;
        delta_y=endy-starty;
    
        /* Compute the direction of the increment,
           an increment of 0 means either a horizontal or vertical
           line.
        */
        if(delta_x>0) incx=1;
        else if(delta_x==0) incx=0;
        else incx=-1;
    
        if(delta_y>0) incy=1;
        else if(delta_y==0) incy=0;
        else incy=-1;
    
        /* determine which distance is greater */
        delta_x=abs(delta_x);
        delta_y=abs(delta_y);
        if(delta_x>delta_y) distance=delta_x;
        else distance=delta_y;
    
        /* draw the line */
        for(t=0; t<=distance+1; t++) {
            wp(startx, starty, color);
            
            xerr+=delta_x;
            yerr+=delta_y;
            if(xerr>distance) {
                xerr-=distance;
                startx+=incx;
            }
            if(yerr>distance) {
                yerr-=distance;
                starty+=incy;
            }
        }
    }
    You need a function called wp() which plots a pixel . . . I can give you the code for a DVA Windows XP compatible wp() if you like.

    [edit]
    I didn't write that code, so don't ask me how it works . . . .
    [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Adamant Programmer Axpen's Avatar
    Join Date
    Jun 2003
    Location
    USA
    Posts
    42
    While still not exactly as elegant as M$ Paint's line drawing algo, I guess i'll just have to live with bresenhams line drawing algorithm.

    Thanks for all your time,
    Alex
    The Man With 3 Ears::Oh no better get the huskers

    Download Helppc by David Jurgens, It's a FANTASTIC Reference!!!

    In Case I Forget I Have:
    Windows XP
    For My 32-bit Questions:
    Dev C++ (mainly just use its mingw)
    For My 16-bit Questions:
    Borland Turbo C++ 1.01

  7. #7
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >>M$ Paint's line drawing algo

    This probably uses some type of anti-aliasing to make the line look smoother. There are many algos around for that too.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Zoom in far enough and you'll see they look the same. You're working with a grid. As such, there is no way to make a "clean" diagonal. The closest thing you get is stair stepping. You'll always get this effect. You can try and hide it (anti-alias) or what not, but it's always going to be the same thing. Since your monitor is always going to be a grid, if you zoom in far enough, you'll always find a stair step.


    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Paint is probably running at a higher screen resolution than your game, so the line looks better.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #10
    Adamant Programmer Axpen's Avatar
    Join Date
    Jun 2003
    Location
    USA
    Posts
    42
    I get the whole resolution thing, so that's why I examined it at a 8:1 ratio using MS Paints magnifing lens thing. The stair step thing is nessacery I know, but its just that MS's method is so much more elegantly laid out when it plots. So do you guys just use the bresenhams line thing and just deal with the sometimes odd lines? It just looks kind of odd when you want a line from 0,0 to 5,4 and the standard bresenham line drawing algo does:
    0,0/1,0/2,1/3,2/4,3/5,4
    MS does the better:
    0,0/1,1/2,2/3,2/4,3/5,4
    It's like it divides the total distance or something cause it knows half way throuh to line it needs to scooch the rest over, but it does so in the middle NOT at the beginning or end like:
    0,0/1,1/2,2/3,3/4,4/5,4
    Anywho I appriciate the response,
    Alex
    The Man With 3 Ears::Oh no better get the huskers

    Download Helppc by David Jurgens, It's a FANTASTIC Reference!!!

    In Case I Forget I Have:
    Windows XP
    For My 32-bit Questions:
    Dev C++ (mainly just use its mingw)
    For My 16-bit Questions:
    Borland Turbo C++ 1.01

  11. #11
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >>So do you guys just use the bresenhams line thing and just deal with the sometimes odd lines?

    Are you sure you implemented the algorithm properly? search the game board for a clock demo i posted a while ago, it has an implementation of Bressenhams line and circle algorithms.

  12. #12
    Adamant Programmer Axpen's Avatar
    Join Date
    Jun 2003
    Location
    USA
    Posts
    42
    Well the link seems to be down, but I found a site that helped me awhile back Direct X Math Line , but it now seems to get all messed up with its y coordinate in my program, it stays at zero cause the division is returning a float converted to and int using casting that will never go past .99 so it will never see the value 1, much less make it to 4.
    in the form (x1,y1,x2,y2) im doing (0,0,5,4)
    it makes it just fine from x1 to x2, just not from y1 to y2, any helps as to why and any more helps on line plotting would be great, this one seems to work, although it's neigh identicle to what i've been trying in the past, I hopefully will also get to see that demo clock thing when the link isnt broke, thanks for all the help thus far,
    Alex
    The Man With 3 Ears::Oh no better get the huskers

    Download Helppc by David Jurgens, It's a FANTASTIC Reference!!!

    In Case I Forget I Have:
    Windows XP
    For My 32-bit Questions:
    Dev C++ (mainly just use its mingw)
    For My 16-bit Questions:
    Borland Turbo C++ 1.01

  13. #13
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    I'm not sure if this is any use to you, but I've attached an implementation of Bresenham's line algo that I recently wrote in Pascal (sorry). Shouldn't be a problem to convert it to C assuming you've already got functions to draw pixels (PutPixel in this case) and horiz/vert lines (PutHLine and PutVLine in this case).
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  14. #14
    Adamant Programmer Axpen's Avatar
    Join Date
    Jun 2003
    Location
    USA
    Posts
    42
    Well I actually did get that program of yours perspective, I guess im just wanting something I cant have, the bresenham line thing does work well enough, its just I was SO curious how to make a line drawing algo like MicroSofts paint, but every direction I go leads to one road, so I suppose ill just use the bresenhams line thing for now and just scrap the MS line thing to the side as a little hobby of mine, thanks guys,
    Alex
    The Man With 3 Ears::Oh no better get the huskers

    Download Helppc by David Jurgens, It's a FANTASTIC Reference!!!

    In Case I Forget I Have:
    Windows XP
    For My 32-bit Questions:
    Dev C++ (mainly just use its mingw)
    For My 16-bit Questions:
    Borland Turbo C++ 1.01

  15. #15
    Registered User joed's Avatar
    Join Date
    Mar 2004
    Posts
    59
    Try this Bresenham, it's identical to MS-Paint except for a slight difference when lines are drawn backwards.

    Code:
    void line(int x1, int y1, int x2, int y2, int color)
    {
    	int dx, dy, inx, iny, e;
    	
    	dx = x2 - x1;
    	dy = y2 - y1;
    	inx = dx > 0 ? 1 : -1;
    	iny = dy > 0 ? 1 : -1;
    
    	dx = ABS(dx);
    	dy = ABS(dy);
    	
    	if(dx >= dy) {
    		dy <<= 1;
    		e = dy - dx;
    		dx <<= 1;
    		while (x1 != x2) {
    			setpixel(x1, y1, color);
    			if(e >= 0) {
    				y1 += iny;
    				e-= dx;
    			}
    			e += dy; x1 += inx;
    		}
    	} else {
    		dx <<= 1;
    		e = dx - dy;
    		dy <<= 1;
    		while (y1 != y2) {
    			setpixel(x1, y1, color);
    			if(e >= 0) {
    				x1 += inx;
    				e -= dy;
    			}
    			e += dx; y1 += iny;
    		}
    	}
    	setpixel(x1, y1, color);
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Algorithm for drawing arc?
    By 6tr6tr in forum C++ Programming
    Replies: 7
    Last Post: 01-09-2009, 02:26 AM
  2. lens drawing algorithm
    By manav in forum Game Programming
    Replies: 6
    Last Post: 05-17-2008, 01:10 AM
  3. GDI Drawing a stupid line!
    By Bajanine in forum Windows Programming
    Replies: 4
    Last Post: 05-08-2003, 09:00 PM
  4. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  5. Question About Line Drawing with Messaging
    By Unregistered in forum Windows Programming
    Replies: 3
    Last Post: 06-06-2002, 11:47 PM