Bresenham's Line Algorithm in Arduino ( CNC / Plotters )

I've been working off and on with my wall plotter project, and found that it was really difficult to find a good implentation of Bresenham's line-drawing algorithm done in Arduino. The original code I found following a link from Wikipedia, pointing to implementations in a number of languages. This is modified from the original C code. http://rosettacode.org/wiki/Bitmap/Bresenham's_line_algorithm#C

Note that I'm using suspension steppers, so my movement code is somewhat custom. Just replace those sections (noted with comments) to meet whatever movement method you prefer.

The function is called with x,y pairs. For my purposes, the first pair is always the current location and the second is the destination.

void line(int x0, int y0, int x1, int y1) {     /// Bresenham's Line Algorithm
  int md1, md2, s_s1, s_s2, ox, oy;
  int dx = abs(x1-x0), sx = x0<x1 ? 1 : -1;
  int dy = abs(y1-y0), sy = y0<y1 ? 1 : -1;
  int err = (dx>dy ? dx : -dy)/2, e2; 
  for(;;){    
    ox=x0;
    oy=y0;
    if (x0==x1 && y0==y1) break;
    e2 = err;
    if (e2 >-dx) { 
      err -= dy; 
      x0 += sx; 
    }    
    if (e2 < dy) { 
      err += dx; 
      y0 += sy; 
    }
    s_s1=s1;
    s_s2=s2;
    if (y0 < oy) { // Move UP, replace s1/s2 with your own code
      s1=s1-1;
      s2=s2-1;
    };
    if (y0 > oy) { // DOWN, replace s1/s2 with your own code
      s1=s1+1;
      s2=s2+1;
    };
    if (x0 < ox) {  //LEFT, replace s1/s2 with your own code
      s1=s1-1;
      s2=s2+1;
    };
    if (x0 > ox) {  //RIGHT, replace s1/s2 with your own code
      s1=s1+1;
      s2=s2-1;
    };
    md1=s1-s_s1;
    md2=s2-s_s2;
    stepper1.step(md1);  //now do the actual move.
    stepper2.step(md2);
    delay(10);           //delay for settling
  }
}
1 Like

please explain this line:

dx = abs(x1-x0), sx = x0<x1 ? 1 : -1;

I don't understand the abs(x1-x0) part in it as it has no effect or I miss something...
Where does sx comes from?

You are confusing:

  dx = abs(x1-x0), sx = x0<x1 ? 1 : -1;

(which uses the comma operator) with

  int dx = abs(x1-x0), sx = x0<x1 ? 1 : -1;

Which is a declaration of two integers each with an initial value expression. The comma here just separates the declarations.

Off course, makes 100% sense, it is just like int x=0, y=0;

From point of readability I prefer one declaration at a time especially when vars are initialized immediately with formulas.