Life After Bresenham
Most books would have you believe that the development of line drawing algorithms
ended with Bresenham's famous algorithm. But there has been some signifcant
work since then.
The following 2-step algorithm, developed by Xiaolin Wu, is a good example. The interesting story of this algorithm's development is discussed in an article that appears in Graphics Gems I by Brian Wyvill.
The two-step algorithm takes the interesting approach of treating line drawing as a automaton, or finite state machine. If one looks at the possible configurations that the next two pixels of a line, it is easy to see that only a finite set of possiblities exist.
The two-step algorithm also exploits the symmetry of line-drawing by simultaneously drawn from both ends towards the midpoint.
The code, which is further down this web page, is a bit long to show an a slide.
public void lineTwoStep(int x0, int y0, int x1, int y1, Color color) {
int pix = color.getRGB();
int dy = y1 - y0;
int dx = x1 - x0;
int stepx, stepy;
if (dy < 0) { dy = -dy; stepy = -1; } else { stepy = 1; }
if (dx < 0) { dx = -dx; stepx = -1; } else { stepx = 1; }
raster.setPixel(pix, x0, y0);
raster.setPixel(pix, x1, y1);
if (dx > dy) {
int length = (dx - 1) >> 2;
int extras = (dx - 1) & 3;
int incr2 = (dy << 2) - (dx << 1);
if (incr2 < 0) {
int c = dy << 1;
int incr1 = c << 1;
int d = incr1 - dx;
for (int i = 0; i < length; i++) {
x0 += stepx;
x1 -= stepx;
if (d < 0) { // Pattern:
raster.setPixel(pix, x0, y0); //
raster.setPixel(pix, x0 += stepx, y0); // x o o
raster.setPixel(pix, x1, y1); //
raster.setPixel(pix, x1 -= stepx, y1);
d += incr1;
} else {
if (d < c) { // Pattern:
raster.setPixel(pix, x0, y0); // o
raster.setPixel(pix, x0 += stepx, y0 += stepy); // x o
raster.setPixel(pix, x1, y1); //
raster.setPixel(pix, x1 -= stepx, y1 -= stepy);
} else {
raster.setPixel(pix, x0, y0 += stepy); // Pattern:
raster.setPixel(pix, x0 += stepx, y0); // o o
raster.setPixel(pix, x1, y1 -= stepy); // x
raster.setPixel(pix, x1 -= stepx, y1); //
}
d += incr2;
}
}
if (extras > 0) {
if (d < 0) {
raster.setPixel(pix, x0 += stepx, y0);
if (extras > 1) raster.setPixel(pix, x0 += stepx, y0);
if (extras > 2) raster.setPixel(pix, x1 -= stepx, y1);
} else
if (d < c) {
raster.setPixel(pix, x0 += stepx, y0);
if (extras > 1) raster.setPixel(pix, x0 += stepx, y0 += stepy);
if (extras > 2) raster.setPixel(pix, x1 -= stepx, y1);
} else {
raster.setPixel(pix, x0 += stepx, y0 += stepy);
if (extras > 1) raster.setPixel(pix, x0 += stepx, y0);
if (extras > 2) raster.setPixel(pix, x1 -= stepx, y1 -= stepy);
}
}
} else {
int c = (dy - dx) << 1;
int incr1 = c << 1;
int d = incr1 + dx;
for (int i = 0; i < length; i++) {
x0 += stepx;
x1 -= stepx;
if (d > 0) {
raster.setPixel(pix, x0, y0 += stepy); // Pattern:
raster.setPixel(pix, x0 += stepx, y0 += stepy); // o
raster.setPixel(pix, x1, y1 -= stepy); // o
raster.setPixel(pix, x1 -= stepx, y1 -= stepy); // x
d += incr1;
} else {
if (d < c) {
raster.setPixel(pix, x0, y0); // Pattern:
raster.setPixel(pix, x0 += stepx, y0 += stepy); // o
raster.setPixel(pix, x1, y1); // x o
raster.setPixel(pix, x1 -= stepx, y1 -= stepy); //
} else {
raster.setPixel(pix, x0, y0 += stepy); // Pattern:
raster.setPixel(pix, x0 += stepx, y0); // o o
raster.setPixel(pix, x1, y1 -= stepy); // x
raster.setPixel(pix, x1 -= stepx, y1); //
}
d += incr2;
}
}
if (extras > 0) {
if (d > 0) {
raster.setPixel(pix, x0 += stepx, y0 += stepy);
if (extras > 1) raster.setPixel(pix, x0 += stepx, y0 += stepy);
if (extras > 2) raster.setPixel(pix, x1 -= stepx, y1 -= stepy);
} else
if (d < c) {
raster.setPixel(pix, x0 += stepx, y0);
if (extras > 1) raster.setPixel(pix, x0 += stepx, y0 += stepy);
if (extras > 2) raster.setPixel(pix, x1 -= stepx, y1);
} else {
raster.setPixel(pix, x0 += stepx, y0 += stepy);
if (extras > 1) raster.setPixel(pix, x0 += stepx, y0);
if (extras > 2) {
if (d > c)
raster.setPixel(pix, x1 -= stepx, y1 -= stepy);
else
raster.setPixel(pix, x1 -= stepx, y1);
}
}
}
}
} else {
int length = (dy - 1) >> 2;
int extras = (dy - 1) & 3;
int incr2 = (dx << 2) - (dy << 1);
if (incr2 < 0) {
int c = dx << 1;
int incr1 = c << 1;
int d = incr1 - dy;
for (int i = 0; i < length; i++) {
y0 += stepy;
y1 -= stepy;
if (d < 0) {
raster.setPixel(pix, x0, y0);
raster.setPixel(pix, x0, y0 += stepy);
raster.setPixel(pix, x1, y1);
raster.setPixel(pix, x1, y1 -= stepy);
d += incr1;
} else {
if (d < c) {
raster.setPixel(pix, x0, y0);
raster.setPixel(pix, x0 += stepx, y0 += stepy);
raster.setPixel(pix, x1, y1);
raster.setPixel(pix, x1 -= stepx, y1 -= stepy);
} else {
raster.setPixel(pix, x0 += stepx, y0);
raster.setPixel(pix, x0, y0 += stepy);
raster.setPixel(pix, x1 -= stepx, y1);
raster.setPixel(pix, x1, y1 -= stepy);
}
d += incr2;
}
}
if (extras > 0) {
if (d < 0) {
raster.setPixel(pix, x0, y0 += stepy);
if (extras > 1) raster.setPixel(pix, x0, y0 += stepy);
if (extras > 2) raster.setPixel(pix, x1, y1 -= stepy);
} else
if (d < c) {
raster.setPixel(pix, stepx, y0 += stepy);
if (extras > 1) raster.setPixel(pix, x0 += stepx, y0 += stepy);
if (extras > 2) raster.setPixel(pix, x1, y1 -= stepy);
} else {
raster.setPixel(pix, x0 += stepx, y0 += stepy);
if (extras > 1) raster.setPixel(pix, x0, y0 += stepy);
if (extras > 2) raster.setPixel(pix, x1 -= stepx, y1 -= stepy);
}
}
} else {
int c = (dx - dy) << 1;
int incr1 = c << 1;
int d = incr1 + dy;
for (int i = 0; i < length; i++) {
y0 += stepy;
y1 -= stepy;
if (d > 0) {
raster.setPixel(pix, x0 += stepx, y0);
raster.setPixel(pix, x0 += stepx, y0 += stepy);
raster.setPixel(pix, x1 -= stepy, y1);
raster.setPixel(pix, x1 -= stepx, y1 -= stepy);
d += incr1;
} else {
if (d < c) {
raster.setPixel(pix, x0, y0);
raster.setPixel(pix, x0 += stepx, y0 += stepy);
raster.setPixel(pix, x1, y1);
raster.setPixel(pix, x1 -= stepx, y1 -= stepy);
} else {
raster.setPixel(pix, x0 += stepx, y0);
raster.setPixel(pix, x0, y0 += stepy);
raster.setPixel(pix, x1 -= stepx, y1);
raster.setPixel(pix, x1, y1 -= stepy);
}
d += incr2;
}
}
if (extras > 0) {
if (d > 0) {
raster.setPixel(pix, x0 += stepx, y0 += stepy);
if (extras > 1) raster.setPixel(pix, x0 += stepx, y0 += stepy);
if (extras > 2) raster.setPixel(pix, x1 -= stepx, y1 -= stepy);
} else
if (d < c) {
raster.setPixel(pix, x0, y0 += stepy);
if (extras > 1) raster.setPixel(pix, x0 += stepx, y0 += stepy);
if (extras > 2) raster.setPixel(pix, x1, y1 -= stepy);
} else {
raster.setPixel(pix, x0 += stepx, y0 += stepy);
if (extras > 1) raster.setPixel(pix, x0, y0 += stepy);
if (extras > 2) {
if (d > c)
raster.setPixel(pix, x1 -= stepx, y1 -= stepy);
else
raster.setPixel(pix, x1, y1 -= stepy);
}
}
}
}
}
}