How can I draw a "line" in a 2-D array (simulacrum for a screen)

Question

Hello! I'm working on a project that's going to print out to a bitmap(more specifically a RAW, but that's not important to the question), but I'm working in a 2-D array in-program.

I want to be able to draw a line from point (a,b) to point (x,y) for any arbitrary values of a,b,x, and y. I don't need anything fancy like anti-aliasing; at this point nearest-neighbor is fine. for the sake of example, let's assume I've got a 5x5 2d array, like so:

00,10,20,30,40
01,11,21,31,41
02,12,22,32,42
03,13,23,33,43
04,14,24,34,44

now, lets assume I want to draw a line between 04 and 42. I want a way of reliably coming up with something like this:

0,0,0,0,0
0,0,0,0,0
0,0,0,1,1
0,1,1,1,0
1,1,0,0,0

I'm sure there's someone thinking "guh, is this guy retarded? did he fail here?", but humor me, please!

I'm working in C++, but that should be secondary to the actual question.

Answer 1

Like Simucal said, Bresenham is the way to go. Here is a naive implementation.

Not perfect C code, and you have to do some magic if you want thickness on the line segments. Also, you should traverse along x, instead of y like I do here. It is more cache-friendly. If you want anti-aliasing, search for "Wu-lines". It's a clever trick to use the fraction from the positions as a gradient.

Tips for line thickness: Calculate the normalized vector V(-y,x) from v1 - v0 if your vertices are in counter-clockwise order, or V(y,-x) if your vertices are in clockwise order. Then you have four points defined by: v0, v0 + V * linewidth, v1 and v1 + V * linewidth. Rasterize that quadrangle by interpolating along the edges. But if you already want to go that far, you would probably code a triangle rasterizer instead.

typedef struct Point 
{
    int x, y;
} Point;

typedef struct Color {
    unsigned char r,g,b;
} Color;

#define RGB(x) (x->r << 16) | (x->g << 8) | (x->b)

int DrawLinestrip(int width, int height, unsigned int* buffer,
    Color* color, Point* verts, int count)
{
    int i, x,y,xbegin, xdelta, ydelta, xdiff, ydiff, accum, sign;
    Point *p1, *p2;
    if(!verts || count < 2)
        return -1;

    for(i=1; i<count; ++i){
        if(verts[i].y > verts[i-1].y){ /* sort by y */
            p1 = &verts[i-1];
            p2 = &verts[i];
        } else {
            p1 = &verts[i];
            p2 = &verts[i-1];
        }

        xdelta = p2->x - p1->x;
        ydelta = p2->y - p1->y;
        accum = 0;
        sign = 0;

        if(!xdelta && !ydelta)
            continue;
        else if(!xdelta && ydelta){ /* Special case: straight vertical line */
            x = p1->x;
            for(y=p1->y; y<(p1->y + ydelta); ++y){
                buffer[x + y*width] = RGB(color);
            }
        }
        else if(xdelta && !ydelta){ /* Special case: straight horisontal line */
            y = p1->y;
            xbegin = (p1->x < p2->x ? p1->x : p2->x);
            for(x=xbegin; x<=xbegin+abs(xdelta); ++x){
                buffer[x + y*width] = RGB(color);
            }
        }
        else {
            xdiff = (xdelta << 16) / ydelta;
            ydiff = (ydelta << 16) / xdelta;

            if( abs(xdiff) > abs(ydiff) ){ /* horizontal-major */
                y = p1->y;
                if(xdelta < 0){ /* traversing negative x */
                    for(x=p1->x; x >= p2->x; --x){
                        buffer[x + y*width] = RGB(color);
                        accum += abs(ydiff);
                        while(accum >= (1<<16)){
                            ++y;
                            accum -= (1<<16);
                        }
                    }
                } else { /* traversing positive x */
                    for(x=p1->x; x <= p2->x; ++x){
                        buffer[x + y*width] = RGB(color);
                        accum += abs(ydiff);
                        while(accum >= (1<<16)){
                            ++y;
                            accum -= (1<<16);
                        }
                    }
                }
            } else if( abs(ydiff) > abs(xdiff) ){ /* vertical major */
                sign = (xdelta > 0 ? 1 : -1);
                x = p1->x;
                for(y=p1->y; y <= p2->y; ++y){
                    buffer[x + y*width] = RGB(color);
                    accum += abs(xdiff);
                    while(accum >= (1<<16)){
                        x += sign;
                        accum -= (1<<16);
                    }
                }            
            } else if( abs(ydiff) == abs(xdiff) ){ /* 45 degrees */
                sign = (xdelta > 0 ? 1 : -1);
                x = p1->x;
                for(y=p1->y; y <= p2->y; ++y){
                    buffer[x + y*width] = RGB(color);
                    x+= sign;
                }
            }
        }
    }
    return 0;
}