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
Bresenham's line drawing algorithm absolutely positively does not "go off by a few pixels"
NotWhiteRice [OP] 1 points · May 2023
When I implemented the version on Wikipedia it was off by 2-3 pixels.
phord 7 points · May 2023
Your implementation was flawed, possibly because the Wikipedia one is.