From: Janek Kozicki (janek_listy_at_[hidden])
Date: 2006-10-15 02:28:21
Christian Henning said: (by the date of Sat, 14 Oct 2006 21:39:41 -0400)
> > The next question is, can we make draw_line more generic, and how much
> > more generic (i.e. what kinds of images are possible)
> >
> I'm suggesting an iterator since one might to some extra work at each
> line's pixel. Think about antialiased lines.
Hi, some time ago I have written a small graphical library for simple
use under X, I needed to draw a line. But in X libraries I only found
drawing a line on the screen, while I wanted to draw it in the memory. I
was too lazy to dig manuals for more. Instead I started searching for a
nice line drawing algorithm. I have found some benchmarks, etc.. So Here
I copy/paste the algorithm that according to those benchmarks is the
fastest one..
// screw this, I'm too lazy to dig xlib manual to find line
// drawing function different than
// XDrawLine(display, d, gc, x1, y1, x2, y2)
// which draws on the Display when I *need* to draw on XImage.
//
// Xaolin Wu's (public domain) algorithm
void lix::line(int x0, int y0, int x1, int y1, int color)
{
// cout << "Xaolin Wu's alghoritm\n";
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; }
putpixel( x0, y0, color);
putpixel( x1, y1, color);
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:
putpixel( x0, y0, color); //
putpixel( x0 += stepx, y0, color); // x o o
putpixel( x1, y1, color); //
putpixel( x1 -= stepx, y1, color);
d += incr1;
} else {
if (d < c) { // Pattern:
putpixel( x0, y0, color); // o
putpixel( x0 += stepx, y0 += stepy, color);// x o
putpixel( x1, y1, color); //
putpixel( x1 -= stepx, y1 -= stepy, color);
} else {
putpixel( x0, y0 += stepy, color); // Pattern:
putpixel( x0 += stepx, y0, color); // o o
putpixel( x1, y1 -= stepy, color); // x
putpixel( x1 -= stepx, y1, color); //
}
d += incr2;
}
}
if (extras > 0) {
if (d < 0) {
putpixel( x0 += stepx, y0, color);
if (extras > 1) putpixel( x0 += stepx, y0, color);
if (extras > 2) putpixel( x1 -= stepx, y1, color);
} else
if (d < c) {
putpixel( x0 += stepx, y0, color);
if (extras > 1) putpixel( x0 += stepx, y0 += stepy, color);
if (extras > 2) putpixel( x1 -= stepx, y1, color);
} else {
putpixel( x0 += stepx, y0 += stepy, color);
if (extras > 1) putpixel( x0 += stepx, y0, color);
if (extras > 2) putpixel( x1 -= stepx, y1 -= stepy, color);
}
}
} 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) {
putpixel( x0, y0 += stepy, color); // Pattern:
putpixel( x0 += stepx, y0 += stepy, color); // o
putpixel( x1, y1 -= stepy, color); // o
putpixel( x1 -= stepx, y1 -= stepy, color); // x
d += incr1;
} else {
if (d < c) {
putpixel( x0, y0, color); // Pattern:
putpixel( x0 += stepx, y0 += stepy, color); // o
putpixel( x1, y1, color); // x o
putpixel( x1 -= stepx, y1 -= stepy, color); //
} else {
putpixel( x0, y0 += stepy, color); // Pattern:
putpixel( x0 += stepx, y0, color); // o o
putpixel( x1, y1 -= stepy, color); // x
putpixel( x1 -= stepx, y1, color); //
}
d += incr2;
}
}
if (extras > 0) {
if (d > 0) {
putpixel( x0 += stepx, y0 += stepy, color);
if (extras > 1) putpixel( x0 += stepx, y0 += stepy, color);
if (extras > 2) putpixel( x1 -= stepx, y1 -= stepy, color);
} else
if (d < c) {
putpixel( x0 += stepx, y0, color);
if (extras > 1) putpixel( x0 += stepx, y0 += stepy, color);
if (extras > 2) putpixel( x1 -= stepx, y1, color);
} else {
putpixel( x0 += stepx, y0 += stepy, color);
if (extras > 1) putpixel( x0 += stepx, y0, color);
if (extras > 2) {
if (d > c)
putpixel( x1 -= stepx, y1 -= stepy, color);
else
putpixel( x1 -= stepx, y1, color);
}
}
}
}
} 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) {
putpixel( x0, y0, color);
putpixel( x0, y0 += stepy, color);
putpixel( x1, y1, color);
putpixel( x1, y1 -= stepy, color);
d += incr1;
} else {
if (d < c) {
putpixel( x0, y0, color);
putpixel( x0 += stepx, y0 += stepy, color);
putpixel( x1, y1, color);
putpixel( x1 -= stepx, y1 -= stepy, color);
} else {
putpixel( x0 += stepx, y0, color);
putpixel( x0, y0 += stepy, color);
putpixel( x1 -= stepx, y1, color);
putpixel( x1, y1 -= stepy, color);
}
d += incr2;
}
}
if (extras > 0) {
if (d < 0) {
putpixel( x0, y0 += stepy, color);
if (extras > 1) putpixel( x0, y0 += stepy, color);
if (extras > 2) putpixel( x1, y1 -= stepy, color);
} else
if (d < c) {
putpixel( stepx, y0 += stepy, color);
if (extras > 1) putpixel( x0 += stepx, y0 += stepy, color);
if (extras > 2) putpixel( x1, y1 -= stepy, color);
} else {
putpixel( x0 += stepx, y0 += stepy, color);
if (extras > 1) putpixel( x0, y0 += stepy, color);
if (extras > 2) putpixel( x1 -= stepx, y1 -= stepy, color);
}
}
} 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) {
putpixel( x0 += stepx, y0, color);
putpixel( x0 += stepx, y0 += stepy, color);
putpixel( x1 -= stepx, y1, color);
putpixel( x1 -= stepx, y1 -= stepy, color);
d += incr1;
} else {
if (d < c) {
putpixel( x0, y0, color);
putpixel( x0 += stepx, y0 += stepy, color);
putpixel( x1, y1, color);
putpixel( x1 -= stepx, y1 -= stepy, color);
} else {
putpixel( x0 += stepx, y0, color);
putpixel( x0, y0 += stepy, color);
putpixel( x1 -= stepx, y1, color);
putpixel( x1, y1 -= stepy, color);
}
d += incr2;
}
}
if (extras > 0) {
if (d > 0) {
putpixel( x0 += stepx, y0 += stepy, color);
if (extras > 1) putpixel( x0 += stepx, y0 += stepy, color);
if (extras > 2) putpixel( x1 -= stepx, y1 -= stepy, color);
} else
if (d < c) {
putpixel( x0, y0 += stepy, color);
if (extras > 1) putpixel( x0 += stepx, y0 += stepy, color);
if (extras > 2) putpixel( x1, y1 -= stepy, color);
} else {
putpixel( x0 += stepx, y0 += stepy, color);
if (extras > 1) putpixel( x0, y0 += stepy, color);
if (extras > 2) {
if (d > c)
putpixel( x1 -= stepx, y1 -= stepy, color);
else
putpixel( x1, y1 -= stepy, color);
}
}
}
}
}
}
-- Janek Kozicki |