|
|
Boost : |
From: Christian Henning (chhenning_at_[hidden])
Date: 2006-10-15 13:29:50
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_at_[hidden]> 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
>
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk