I recently derived a new line drawing function that hasn't ever been off by a few pixels and hasnt ever had gaps

Bresenham's line drawing algorithm always goes off by a few pixels when I implement it, so I derived my own in a similar way.

y=mx+b

y=dy/dx x + b

dx y = dy x + dx b

0 = dy x - dx y + dx b

f(m, n) = dy m - dx n + dx b

N = f(x+t, y+u), f(x,y) = 0
N = dy(x+t) - dx(y+u) + dx b

- 0 = dy x - dx y + dx b

N = dy t - dx u

Let u = v+1/2:
N = dy t - dx (v+1/2)

0 > dy t - dx (v+1/2)
dx(v+1/2) > dy t

dx (2v+1) > 2 dy t

This is the implementation that I be using as of this time.

void drawLine(int x0, int y0, int x1, int y1, rgb color) {
int dx = abs(x1 - x0);
int dy = abs(y1 - y0);
int tilt = dy < dx ? -1 : 1;
int step = tilt == -1 ? x0 < x1 ? -1 : 1 : y0 < y1 ? -1 : 1;
int mode = tilt == -1 ? y1 < y0 ? -1 : 1 : x1 < x0 ? -1 : 1;
int sV = tilt == -1 ? x0 > x1 ? x1 : x0 : y0 > y1 ? y1 : y0;
int eV = tilt == -1 ? x0 > x1 ? x0 : x1 : y0 > y1 ? y0 : y1;
int L = tilt == -1 ? dx : dy;
int R = tilt == -1 ? dy : dx;
for(int i = sV, h = 0, l = L, r = -R, c = tilt == -1 ? x0 > x1 ? y1 : y0 : y0 > y1 ? x1 : x0; i <= eV; i++) {
if(l < (r += 2 * R)) { h++; l += 2 * L; }
if(tilt == -1) plot(i, c - h * step * mode, color);
if(tilt == 1) plot(c - h * step * mode, i, color);

}

}

It hasn't been tested as far as I know, so I'm not sure if changing step and mode would break the function if it were to undergo extensive use, but this is an optimization that could be done:
int hStep = x0 < x1 ? tilt : -tilt;

int vStep = y0 < y1 ? -tilt : tilt;

​

Since line drawing functions are easily called countless times a frame, it would probably go faster due to checking that less, but I'm not sure how messing with the first one, which be more rigorous would affect things after extensive use.

3 comments · 68% upvoted · other discussions

comments

MuForceShoelace

Bresenham's line drawing algorithm absolutely positively does not "go off by a few pixels"

NotWhiteRice [OP]

When I implemented the version on Wikipedia it was off by 2-3 pixels.

phord

Your implementation was flawed, possibly because the Wikipedia one is.