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 |