Boost logo

Boost :

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                                                         |

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk