Arduino / Bresenham linear interpolation with ramping

Hello all,

I'll shortly introduce myself since this is my first post on this forum, I'm a graduating graphic design student at the art academy in Amsterdam. As a graduation project I'm building a cnc printer that uses rubber stamps. This is not a RepRap, but since the basic mechanics and logic are the same, and this seems to be a nice and lively user forum, I'd like to ask you a question.

For the x y movement I'm controlling two stepper motors (2,5Nm and 1,0Nm). Since the y-axis (double rail) is carrying the x axis, and this is quite a heavy one, the steppers need to accelerate in order to move the heavy load and build up the speed.

The drivers I am using for the stepper motors are step/direction drivers, therefore, I decrease the delay inbetween the pulses to accelerate the stepper motors.

Now this is where my question pops up: I'd like to move the x and y axis sycnhronized, which I will do using the linear Bresenham algorithm. But I also need to be able to ramp up / down the speed of the steppers, without them affecting each other. And sine the arduino cannot drive two steppers simultaneously (correct me if I'm wrong!) but only sequentially, the delays of the stepper motors will affect each other.

Now is there a solution in which the x and y axis move synchronized but also have their own delays?

Thanks alot for reading the post

I used to work for a graphics card company and we did some interesting things with line drawing algorithms. Steppers have an added complication of needing a specific speed, rather than "as fast as possible" with graphics.

One interesting algorithm I remember was one where each axis had its own accumulator. The idea is that you repeatedly add (or subtract) numbers to the accumulators and move the pixel on an overflow (or underflow) condition. The nice thing about this is that you can run both X and Y simultaneously by repeatedly adding different values to the accumulators. In theory, you could also control the speed by scaling the increment values.

I can see something like this applying to stepper control where you use a fixed (very short) delay to run the accumulators and use the overflow/underflow output to control step and direction. I think it'd be something like:
- an underflow or overflow would cause a single step
- overflow would toggle the direction line to forward
- underflow would toggle the direction line to reverse

The relative values of the X and Y increment specify the slope of the line. The combined values specify the speed.

Not sure how this sort of thing would fit in with the current architecture, though. It's all well and good for me to ramble on about it in theory but applying it to steppers controlled by separate microcontrollers and connect by a serial link is a different story.

I don't know anything about the arduino software but my machine drives two steppers at once with acceleration and deceleration.

With the Bresenham algorithm the stepper going the furthest steps on every step and the other misses out some of the steps to go a shorter distance. The misses are spread out evenly as possible amongst the steps by the algorithm.

I think the arduino does that for up to three axis at once.

I apply the acceleration / deceleration to the step times since that is the rate the faster axis is going at. The other axis is slower so gets correspondingly lower acceleration, which it needs to do to still move along a straight line.

My axes have the same motor but there is much more mass moving on the x-axis. I just chose the acceleration to suit the heavier axis so it is only optimum when moving along x.

To optimise it you would have to work out the component of acceleration along each axis and scale the acceleration along the line so that neither motors exceeded their maximum torque.

Edited 1 time(s). Last edit at 03/31/2008 01:52PM by nophead.

---

[www.hydraraptor.blogspot.com]

... the core-point of the Bresenham algorhythmus for stepper-moving (or in pixelgraphics too) is the fact that you have an inherent synchronisation of two (or three) axes with respect to the longer axis-projection.

This means, you have only to accelerate/deccelerate the motor with the most steps for the specific line and the other motors steps at slower takt-rate but with the ame acceleration ramp.

It's even contraproductive, when you want to desync your motors - then you loose most of the linearisation effect and have much to calculate and steer to resync your motors again to get straight vector-lines ...

Maybe i missed some point - can you please explain more in detail, why you want to desync your axes?

Viktor

Thanks for all your replies, they have been helpful!

nition:

this is actually really easy, but we just havent implemented it with the arduino (yet). the arduino is capable of driving all 3 steppers to draw a direct line. please look through our arduino code for how we do this (look at the GCode_Interpreter code)

Its very simple: we calculate the deltas, then set all counters to an initial value. we then add all the deltas to the counter, and step the the motors if their counter is above 0. the counter gets reset then as well.

the last step is that we then delay a certain amount of time (based on how fast the line is to be drawn)

to add ramping to that, you simply change that delay variable. instead of using the speed passed in (ie: max speed) you keep track of what speed you are, and gradually reduce that timer until you are at the max speed.

ps. if you're using step/direction boards, you can easily use our Arduino software and take advantage of all the work we've put into it =)

hi new here, found this maybe you could make use of it
[hwml.com]

Hello all,

I've been able to implement the bresenham algorithm in the meanwhile, but I found that it slows down my stepper motors enormously, while they should run at their maximum speed.

This is the code I am using now, which is based on the RepRap code for the Arduino. I hope anyone of you is able to tell me if this algorithm is processor intensive

Edited 1 time(s). Last edit at 04/20/2008 01:32PM by nition.

Hi nition,

AFAIR my implementation work in another way: When for example the plotter had to draw a line from 0,0 to 720,120, then i had to pulse the X-motor exactly 720 times and the Y-motor steps synchrone every 6. X-pulse.

For the speed i had to calculate the max-speed per step and the ramp from start to run and from run to stop in respect to the direction-vector.

So i had (in Simons-Basic on C64 didn't know it exactly) something as:

...
STEPS=720 // longest line-count
YCOUNT=6 // Bresenham-divider ( 720 / 120 )

FOR X=0 TO STEPS STEP 1
(PULSEX)
Y=Y+1
IF Y=YCOUNT THEN
Y=0: (PULSEY)
ENDIF
(WAIT [STIME]) // - The time-var STIME will be decremented and incremented as needed for the actual speed
NEXT X
...

Viktor

Thanks for your reply, Viktor. Is this algorithm faster you think? And what happens when the bresenham divider results in a floating point number? Say the point (500,316)?

Hi nition,

... should work faster (or smoother), as you calculate all timing and divisions before plotting the line.

When plotting, then you only have to select the right step-delay-time from your ramp (increasing in the start-phase, decreasing before stop).

You have to convert the floating numbers in nearest integer e.g. INT(DIV + 0.5), the stepping is INT anymore.

Search for Bresenham in Wikipedia, there should be a nice description ...

Viktor

Thanks again for the reply, Viktor. I did look into the wikipedia entry before, and to me it seems that the code I had been using before, which is based on the reprap arduino code is actually an implementation of that algorithm, the problem still is, this calculating slows the arduino down so bad that the steppers speed is extremely low, while I need them to run at full speed. Does anybody know if there is a way of having a decent line drawing algorithm while not sacrificing the speed you pulse your stepper motors?

Thanks again, and I'm thinking now, is the microcontroller just not powerful enough? But is there a way to pulse stepper motors directly from a mac? Since it has no parallel port?

That is roughly the correct algorithm. I can code it about twice as fast but you should be getting 10 of thousands of steps per second as it is. Are you using a microstepping driver with a big divide ratio?

I will post the faster version tomorrow.

---

[www.hydraraptor.blogspot.com]

Thanks for your reply, nophead. I am using a microstep driver, but the divide ratio is not too big I think, I have it set at 10 microsteps, and 10.000+ steps a second would be fine. Thanks alot for posting a faster version, I can imagine incrementing the axis with the largest travel by 1 anyway without having to perform the calculations you do for the axis with the smaller travel.

Is there anyway in which I can check how many steps per second the arduino is actually generating? Maybe with the millis() function I'm thinking now.

I've checked it using the millis() function, a travel of 10.000 x steps (with 6000 y steps) takes 6 seconds to perform! And it would be really really nice if this could be done in one second.

looking forward to see your code!

Yes that is basically the optimisation I had in mind. Split it into two loops one for when x goes furthest and the other for y. In each loop you just pulse one axis always and the other conditionally. Ideally you overlap the pulses so you turn them on delay and turn them off then delay to give 50% duty cycle.

if(count) do { ... } while (--count) is the fastest type of loop in C.

I don't know anything about Arduino but it is a 16MHz RISC processor so it should do adds and subtracts very quickly. Unless digitalWrite() is very slow I can't see why you have a problem. You could try replacing it with direct writes to the port.

---

[www.hydraraptor.blogspot.com]

So each step takes 600us which is 9600 instructions. Something doesn't make sense here.

---

[www.hydraraptor.blogspot.com]

Indeed, I debugged my program and there was a delay somewhere causing... the delay. It works very well now. Kind of a silly mistake, but I was hoping for one instead of a real issue!

Thanks again for the help, nophead, I did learn some things here.

awesome! i'm glad you got it to work.

the bresenham algo is pretty darn fast... its all ints.

Hello all,

I've discovered this site by searching information about interpolation application to stepper motor controlling domain. Sorry for my bad English but I'm French! It's rare to be in touch with people experienced on this domain. I have some theoretical information about the motion control but no idea to how to code it. Such a code is never free and that's why I've some difficulties to find examples. I'd like to continue on your conversation and try with your help and participation to improve the above code on different aspects like supplementary improvements if existing or acceleration and deceleration management...
If you are interested, we can work on that. Lets start with my questions :

1- Nition, in your code, you have x_counter = -max_delta/2 but in Wikipedia, the error value is (delta + 1 ) / 2 in order to have (delta/2) + 1/2. Isn't it ?

2 - Nophead, you

I think I see what both you are saying here. Let's say we're moving 10,000 steps on X and 9,900 steps on Y with a step interval of 1 msec (1,000 steps per second). The X axis will move along nicely taking a step every millisecond for 10 seconds but the Y axis will take 99 steps, skip a step, take 99 more, etc. Inertia is going to cause overshoot on those "skipped" steps

Let's say we decrease the calculation interval to 100 microseconds (0.1 msec, 10,000 checks per second) and increase the overflow counters by a factor of 10. The X axis will take a step every 10 calculation intervals (once per millisecond as before) so that's no different. The Y axis will, however, take a step every 10 or 11 calculation intervals (100,000/9,900 = 10.1010...). A step every 1.0 or 1.1 milliseconds is considerably smoother than 8,000 steps of 1 millisecond interspersed with 1,000 steps of 2 milliseconds,

The degree in variation in step interval depends directly on the degree we increase the calculation rate. If we double the calculation rate the "long" intervals will be 50% longer then the "short" intervals. If we increase the calculation rate by a factor of 4 ten the "long" intervals will be 25% longer than the "short" intervals.

The upper limit on calculation rate is how fast the Arduino can churn out the calculations.

> 2 - Nophead, you

Bottom line. Have you implemented BResenham 3D with ramping ? or simple constant speed?
I was considering to write a test on a microcontroller and I am little confused about situation when motors from 3 axes have different maximum speed and different accelerations.

Any hint would be wellcome.

REgards,
Daniel

Edited 1 time(s). Last edit at 06/17/2010 08:15AM by dandumit.

dunno about different accelerations, but the way I've done the bresenham and acceleration in my code is that all motors complete their moves in the same period of time and are moving at the specified speed at that time. The software which tells them how fast to move (skeinforge in my case) must cater for their respective maximum speeds and accelerations.

---

-----------------------------------------------
Wooden Mendel
Teacup Firmware

Actually inside/beside of interpolation algorithm should taken care of ramping for steppers.
So this it should be done in microcontroller.
What I deducted it's that the laziest motor would affect the performance on other axes just because those movements must be synchronized. If the main movement it's made by the "major" axis it's on the fastest motor , than the laziest may not draw back the fastest motor.
Following this thread I have now a better understanding of picture.

Thank you all !
Daniel