C Board - Line Drawing Algorithm

C Board (http://cboard.cprogramming.com/)

- Game Programming (http://cboard.cprogramming.com/game-programming/)

- - Line Drawing Algorithm (http://cboard.cprogramming.com/game-programming/67832-line-drawing-algorithm.html)

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 :p, 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 :p.

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

Try Bresenham's Line Algorithm

Exactly. I think this might help.

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

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]

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

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

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.

Paint is probably running at a higher screen resolution than your game, so the line looks better. :)

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

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

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

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

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

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

}