Go Down

Topic: Having trouble with Bresenham's algorithm (Read 3016 times)previous topic - next topic

selbs

Apr 29, 2011, 02:59 pm
Hi everyone.

I am building a sort of x, y axis cnc machine and I'm having trouble implementing bresenham's algorithm.
More specifically I have a question over the 'steep' variable. The code I'm using is based (heavily) on that found in the LCD library source. All the examples I have found are for drawing pixels, and as I understand it, when a line is 'steep' the code swaps the x and y axis controllers before drawing. However, when using motors, each motor can mechanically only control one axis - you can't swap them. How do I edit my code to reflect this?
My general problem is that I don't fully understand what it's doing so when I look at other examples, like the drawbot, I can't get much use out of them.

I'm using arduino Duemilanove, and the adafruit motor shield with windows 7.
My code is below (it's an early version so please excuse the quality) Any advice is much appreciated.

Thanks.

Code: [Select]
`void bresLine( int x0, int y0, int x1, int y1) {  int Dx = x1 - x0;   int Dy = y1 - y0;  int steep = (abs(Dy) >= abs(Dx));    if (steep) {    int a = x0;    int b = y0;    x0=b;    y0=a;    a = x1;    b = y1;    x1=b;    y1=a;    // recompute Dx, Dy after swap    Dx = x1 - x0;    Dy = y1 - y0;  }  int xstep = 1;  if (Dx < 0) {    xstep = -1;    Dx = -Dx;  }  int ystep = 1;  if (Dy < 0) {    ystep = -1;     Dy = -Dy;   }  // not objects - * is pointer to memory store   // location for motor objects defined at top  // 'referencing'  // basically creating a new name for the object that can be played with  AF_Stepper* xMotor = NULL;  AF_Stepper* yMotor = NULL;     int TwoDy = 2*Dy;   int TwoDyTwoDx = TwoDy - 2*Dx; // 2*Dy - 2*Dx  int E = TwoDy - Dx; //2*Dy - Dx  int y = y0;  int xDraw, yDraw;   for (int x = x0; x != x1; x += xstep) {     if (steep) {     yMotor = &motorCO2;     xMotor = &motorTime;      xDraw = y;     yDraw = x;    }     else {       yMotor = &motorTime;      xMotor = &motorCO2; // xmotor can mechanically only control time       xDraw = x;      yDraw = y;    }    (*xMotor).step(1, FORWARD, INTERLEAVE);//ORIGINAL    if (E > 0) {      (*yMotor).step(1, BACKWARD, INTERLEAVE);//ORIGINAL            E += TwoDyTwoDx; //E += 2*Dy - 2*Dx;      y = y + ystep;    }     else {      (*yMotor).step(1, BACKWARD, INTERLEAVE);//ORIGINAL      E += TwoDy; //E += 2*Dy;    }  }}`

johnwasser

#1
Apr 29, 2011, 04:12 pm
The 'steep' flag is a measure of which axis has to move further.  That is the axis that moves once every step time.  The other axis will move fewer steps.  Rather than having separate outer loops stepping from X0 to X1 by 1 if the X axis is longer and Y0 to Y1 by 1 if the Y axis is longer it swaps the axis before the loop and swaps them back when using the values.

If you have enough space you could just duplicate the loop, swap the X and Y names, and run one or the other based on which axis has more travel.  Something like:

Code: [Select]
`oid bresLine( int x0, int y0, int x1, int y1) {  int Dx = x1 - x0;   int Dy = y1 - y0;  int xstep = 1;  if (Dx < 0) {    xstep = -1;    Dx = -Dx;  }  int ystep = 1;  if (Dy < 0) {    ystep = -1;     Dy = -Dy;   }  boolean steep = (Dy >= Dx);    if (steep)     {    for (int y = y0; y != y1; y += ystep)       {       motorTime.step(1, FORWARD, INTERLEAVE);//ORIGINAL      if (E > 0)         {       motorCO2.step(1, BACKWARD, INTERLEAVE);//ORIGINAL              E += TwoDyTwoDx; //E += 2*Dy - 2*Dx;        y = y + ystep;        }       else         {        motorCO2.step(1, BACKWARD, INTERLEAVE);//ORIGINAL        E += TwoDy; //E += 2*Dy;        }      }    }  else    {   for (int x = x0; x != x1; x += xstep)       {       motorCO2.step(1, FORWARD, INTERLEAVE);//ORIGINAL      if (E > 0)         {        motorTime.step(1, BACKWARD, INTERLEAVE);//ORIGINAL              E += TwoDyTwoDx; //E += 2*Dy - 2*Dx;        y = y + ystep;        }       else         {        motorTime.step(1, BACKWARD, INTERLEAVE);//ORIGINAL        E += TwoDy; //E += 2*Dy;        }     }    }`
Send Bitcoin tips to: 1G2qoGwMRXx8az71DVP1E81jShxtbSh5Hp
See who has no social life: https://forum.arduino.cc/index.php?action=stats

selbs

#2
May 11, 2011, 01:26 am
That's great thanks, I understand better what's going on now.
I rewrote the code I had, getting one loop working and duplicating it as you said, which also helped me to grasp what the code is doing.
I'll post my code up soon when it's a little more polished!

Cheers.

Go Up