Pages: [1]   Go Down
Author Topic: Having trouble with Bresenham's algorithm  (Read 1620 times)
0 Members and 1 Guest are viewing this topic.
UK
Offline Offline
Newbie
*
Karma: 0
Posts: 6
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
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;
    }
  }
}
Logged

Massachusetts, USA
Offline Offline
Tesla Member
***
Karma: 180
Posts: 8103
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
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;
        }
     }
   }

Logged

Send Bitcoin tips to: 1L3CTDoTgrXNA5WyF77uWqt4gUdye9mezN
Send Litecoin tips to : LVtpaq6JgJAZwvnVq3ftVeHafWkcpmuR1e

UK
Offline Offline
Newbie
*
Karma: 0
Posts: 6
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged

Pages: [1]   Go Up
Jump to: