Bresenham's, at least as implemented there is not the most efficient algorithm.
There are 4 checks per loop in that version. The faster impl recognizes that in 1 direction or the other one coordinate will always increment or decrement by 1 while the other coordinate will or will not increment on each iteration.
That will remove 2 of the 4 checks. The loop just becomes N where N is max(abs(dx), abs(dy))
I don't know if that's still considered Bresenham's or not.
int sign(int v) {
return v > 0 ? 1 : ((v < 0) ? -1 : 0);
}
int abs(int x) {
return x > 0 ? x : -x;
}
int max(int a, b) {
return a > b ? a : b;
}
void drawLine(int x1, int y1, int x2, int y2) {
int deltaX = x2 - x1;
int deltaRow = abs(deltaX);
int rowInc = sign(deltaX);
int deltaY = y2 - y1;
int deltaCol = abs(deltaY);
int colInc = sign(deltaY);
int rowAccum = 0;
int colAccum = 0;
int rowCursor = x1;
int colCursor = y1;
int counter = max(deltaCol, deltaRow);
int endPnt = counter;
if (counter == deltaCol) {
rowAccum = endPnt / 2;
for (; counter > 0; --counter) {
rowAccum += deltaRow;
if (rowAccum >= endPnt) {
rowAccum -= endPnt;
rowCursor += rowInc;
}
colCursor += colInc;
setPixel(rowCursor, colCursor);
}
} else {
colAccum = endPnt / 2;
for (; counter > 0; --counter) {
colAccum += deltaCol;
if (colAccum > endPnt) {
colAccum -= endPnt;
colCursor += colInc;
}
rowCursor += rowInc;
setPixel(rowCursor, colCursor);
}
}
}
This is an optimized version of an algorithm I found in the Atari 400/800 Technical Reference Manual page 218.
There are 4 checks per loop in that version. The faster impl recognizes that in 1 direction or the other one coordinate will always increment or decrement by 1 while the other coordinate will or will not increment on each iteration.
That will remove 2 of the 4 checks. The loop just becomes N where N is max(abs(dx), abs(dy))
I don't know if that's still considered Bresenham's or not.
This is an optimized version of an algorithm I found in the Atari 400/800 Technical Reference Manual page 218.