Hi Janek, I was talking about how you might want to design line drawing algorithms into GIL. I like the line iterator idea, since it gives you some flexibility for doing processing while you are stepping over the line. Anti aliasing is just one example. Stepping over a line does not necessarily mean stepping in single pixel steps. But you can also do step over a collection of pixels that are consecutive. Just take a nearly horizontal line. There you have a long runs of pixels that one can drawn or processed in one step. Even more interesting is that you can not only combine single pixels into a run of pixels, you can even combine runs of pixel into runs of runs of pixels, and so forth. I did that during my thesis. If you're interested I can send you a paper of where this algorithm is being described. Cool stuff. The papers name is: "Why Step When You Can Run? Iterative Line Digitization Algorithms Based On Hierarchies Of Runs" by Peter Stephenson, etc... On 10/15/06, Janek Kozicki <janek_listy@wp.pl> wrote:
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 | _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost