Per-Axis acceleration

Required Reading:

* Generate stepper motor speed profiles in real-time
* High-speed cornering by CNC machines under prescribed bounds on axis accelerations and toolpath contour error (pdf)

article (1) discusses speed profile control for one stepper. Repraps and other CNC machines must simultaneously control 3 or more, in lock-step with one another to prevent geometric errors.

In order to preserve geometry, all moving axes must maintain their position relative to other axes on the prescribed line regardless of velocity.

Each axis has its own velocity and acceleration limits.

For any given move, we must first work out the max velocity of each axis given the move velocity. If any of those maximums exceeds the axis maximum, we must scale the move velocity down until it no longer exceeds axis velocities. Thus it is possible to move at ~141mm/s diagonally, if X and Y are limited to 100mm/s.

We cannot accelerate all axes at maximum acceleration, or one axis may reach full speed before another creating a geometric error, a curve or elbow in our "straight" line. That axis may also reach its endpoint before others, creating further geometric errors.

article (1) above allows us to work out the number of steps it takes to accelerate each axis to full speed. We can use this to work out which axis is furthest into the move when it reaches full speed. This axis limits the acceleration of all other axes. We can then use some of the other calculations from (1) to calculate a new acceleration for other axes such that all axes reach full speed at the same time.

I think this will eliminate geometric errors, although precision limits may introduce some slight errors. I would love to see this proven or disproven by someone with stronger math than me.

article (2) shows us that a conic section curve can be created from a sharp corner by overlapping the linear deceleration of one axis with the acceleration of another. I think we can skip most of the complex math by simply overlapping by some fixed amount.

How do we trace our curve without a ton of math in the case where the corner isn't aligned to X and Y axes?

---

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

There's also AVR application note 446, which implements pretty much what ACCELERATION_RAMPING does, but also comes with formulas to calculate the number of acceleration and deceleration steps in advance.

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

AVR446 describes the same math as article (1), and cites it as a literature reference (read: primary source). It's probably another good one to read, just for a slightly different viewpoint on the math involved

---

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

Success!

See attached png for a graph, perl script contains proof of concept and plot is to generate handy png.

to duplicate:

perl alg.pl 2>alg.data && gnuplot alg.plot && display alg.png

Now I just have to expand it to 4 axes then replace most of dda.c with this algorithm and we'll have the awesomest acceleration around

Edited 1 time(s). Last edit at 04/11/2011 11:24AM by Triffid_Hunter.

---

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

Impressive blob of perl, Triffid. As soon as this works, we can drop ACCELERATION_RAMPING.

BTW., where did the Teacup simulator go? I was recently about to experiment with algorithms, too, but there is no longer the equipment to compile the firmware on a generic PC.

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

Traumflug Wrote:
-------------------------------------------------------
> Impressive blob of perl, Triffid. As soon as this
> works, we can drop ACCELERATION_RAMPING.

I vote for dropping /all/ acceleration algorithms and having just this when we've worked out the kinks.

So far in my translation to C it's developing geometric errors from integer precision loss because the axes run totally unsynchronised after the accel values are worked out. Any ideas on that one? Maybe bresenham isn't so bad at the usual precision of reprap machines? How much does the jitter affect top speeds? We could use all this math to work out the proper acceleration for the leading axis given limits of other moving axes then just bresenham the actual stepping..

> BTW., where did the Teacup simulator go? I was
> recently about to experiment with algorithms, too,
> but there is no longer the equipment to compile
> the firmware on a generic PC.

hm, I think it never got properly merged into master, still available in sw's fork but may need some work to bring up to date with latest head. I'd love to have the sim back in place actually, then we could get it to spit out raw data on stderr or something and plot algorithmic stuff like I'm doing with my perl script. Would be amazing to couple it with a blender script and blender model of a mendel and have a 3d simulation of the entire print process

---

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

Quote

I vote for dropping /all/ acceleration algorithms and having just this when we've worked out the kinks.

Now, ACCELERATION_REPRAP has different rules which can't be joined with ramping. Nevertheless you might be right, because the "golden rule" for Skeinforge users is apparently still "disable acceleration". That golden rule exists due to a flaw in FiveD, but might be handy to help moving all acceleration into the Firmware.

Quote

Maybe bresenham isn't so bad at the usual precision of reprap machines?

Bresenham uses additions only, so yes, it's pretty variable overflow safe.

Quote

We could use all this math to work out the proper acceleration for the leading axis given limits of other moving axes then just bresenham the actual stepping.

That's what I thought you wanted to get rid of.

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

Traumflug Wrote:
-------------------------------------------------------
> We could use all this math to work out the proper
> acceleration for the leading axis given limits of
> other moving axes then just bresenham the actual
> stepping.
>
> That's what I thought you wanted to get rid of.

I do, but not at the expense of the geometric errors I'm seeing from only having 32 bit integers everywhere.. maybe my C porting just isn't very good yet; I've pushed it into 'newdda' branch if you want to check it out and give me some help

---

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

Have you looked at GRBL's motion planner [1]? It seems to do exactly what we need.

[1] [github.com]

Had a look at GRBL. This firmware doesn't attempt to smooth out edges, but simply allows some amount of "jerk". So, instead of slowing dow to zero at each junction, it's only slowing down to a speed which doesn't make the mechanics cringe. The jerk is calculated as simple as:

inline double junction_jerk(block_t *before, block_t *after) {
  return(sqrt(
    pow(before->speed_x-after->speed_x, 2)+
    pow(before->speed_y-after->speed_y, 2)+
    pow(before->speed_z-after->speed_z, 2))
  );
}

With that, it calculates the allowable speed in the junction point to:

double jerk = junction_jerk(previous, current);
if (jerk > settings.max_jerk) {
   entry_factor = (settings.max_jerk/jerk);
}

Now, that's drastically simpler than what I had in mind so far. I always thought of inserting a small circle segment in between two straight paths. Circles may be accurate, but the maths is obviously more complex, as you have to move, well, a circle, a non-straight line.

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

If you use that sort of algorithm you will get different results depending on how the vertices of the part align with the axes. I always apply the worst case axis acceleration along the direction of travel so my corners are always consistent.

---

[www.hydraraptor.blogspot.com]

Traumflug Wrote:
-------------------------------------------------------
> Now, that's drastically simpler than what I had in
> mind so far. I always thought of inserting a small
> circle segment in between two straight paths.
> Circles may be accurate, but the maths is
> obviously more complex, as you have to move, well,
> a circle, a non-straight line.

That poses the question what belongs into the firmware and what into the gcode generator.
IMHO the firmware should not modify the toolpath.

As look ahead is pretty pointless without allowing tolerance to the path moved, the path _has_ to be modified to maintain speed between two segments. In EMC2, you can even set this tolerance: [linuxcnc.org]:

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

Markus Amsler Wrote:
-------------------------------------------------------
> That poses the question what belongs into the
> firmware and what into the gcode generator.
> IMHO the firmware should not modify the toolpath.

It's actually in the g-code spec (such as there is one, I was looking at the documentation for EMC2) that the machine modifies the toolpath. Look at the "constant speed" mode, there's a note that says basically that this mode will round off corners to maintain the same speed, while keeping within the permissible per-axis acceleration.

That's basically what we want. I don't know if an arc is the ideal path though.

---

--
I'm building it with Baling Wire

>>Circles may be accurate, but the maths is obviously more complex, as you have to move, well, a circle, a non-straight line.

I didn't look at it yet, but there's a bresenham variation to draw circles:
[www.ecse.rpi.edu]

However I agree with nophead. We cannot afford to have different corners just because they're angled differently with the axes.

This is my blurb on the topic: [github.com]

The simple idea is, calculate ramping as before on the fast axis, but apply the result to all four axes. Timings for a slow axis can be found by a simple comparison with the fast axis.

Try the algorithm by #defining ACCELERATION_RAMPING. The ACCELERATION_TEMPORAL flag is now obsolete.

Totally untested, but I hope you get the idea.

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

Just a minute ago I committed a few patches which precalculates the number of acceleration and deceleration steps. This has two advantages:

- No need to track this number at interrupt time.

- Now it's possible to have a different number of acceleration and deceleration steps. That means, you can go through the queue, compare deceleration of the previous step with acceleration of the next step and reduce both if the amount of jerk is acceptable.

There is no such comparison (aka look-ahead), yet, but it's a step closer.

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

I've found that in terms of accel, all we need to precalculate is start c, minimum c and decel steps for the bresenham master axis. When c <= min_c we have reached our top speed and must stop accelerating. n starts off at 5 so can be set in dda_start. we work out when to start decelerating from the master axis steps remaining counter vs decel steps.

Not sure how that fits with your plans for look-ahead though- accel steps would probably be a handy value to hang on to, as would the actual resultant acceleration as capped by other moving axes. we don't want to make giant curves at corners if the lines are neither 45 degree nor parallel to an axis. I think if we're blending moves, we may also need to store n_decel so we're not calculating to stop at the end of the move when we shrink decel_steps to match the start of the next move. We'll also need an n_start to complement the adjusted c_start.

SO, how do we do the blend? I'm thinking we simply have a blend distance. We work out each axis' speed at end-blend and start+blend and work out relevant accelerations. If any axes accelerate too fast, we cut down blend distance until they all fit, then doctor the queue variables n_decel, decel_steps, c_start, n_start to match what we've worked out. Do we need another n value for the blend stage? Do we need to let the dda know that we're blending, or is that implicit from doctoring the variables? How do we lift bresenham's lockstep for the duration of the blend?

---

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

Quote

I've found that in terms of accel, all we need to precalculate is start c, minimum c and decel steps for the bresenham master axis. When c <= min_c we have reached our top speed and must stop accelerating. n starts off at 5 so can be set in dda_start. we work out when to start decelerating from the master axis steps remaining counter vs decel steps.

This is what we had before.

Quote

I think if we're blending moves, we may also need to store n_decel so we're not calculating to stop at the end of the move when we shrink decel_steps to match the start of the next move. We'll also need an n_start to complement the adjusted c_start.

Effectively, we have this now. If we don't slow down to a halt, n and c are left with values just right for starting the next movement. So we get what sou describe without precaclulating c_start and n_start[1].

So, assume your first movement has 500 steps acceleration and accordingly 500 steps deceleration. The next movement counts just the same. Now you can reduce the number of deceleration steps by 100 on the first movement and the number of acceleration steps by the same amount and speed will smooth out. It won't go down all to speed zero, instead it will stay at top speed for 100 steps longer, slow down 400 steps only and accelerate again from there.

Currently, this works with two not-so-good assumptions:

- acceleration is relative to the direction of the fast axis

- the fast axis is both times the same

In other words: "guess what, it isn't perfect yet *grin*"

Quote

SO, how do we do the blend? I'm thinking we simply have a blend distance. We work out each axis' speed at end-blend and start+blend and work out relevant accelerations. If any axes accelerate too fast, we cut down blend distance until they all fit, then doctor the queue variables n_decel, decel_steps, c_start, n_start to match what we've worked out. Do we need another n value for the blend stage? Do we need to let the dda know that we're blending, or is that implicit from doctoring the variables? How do we lift bresenham's lockstep for the duration of the blend?

Exactly these questions dance in my head

First of all, as we all know, EMC2 & Co. do smoothing just fine. But this doesn't help us. EMC uses a constant clock which calculates the required position every few microseconds and commands the motors to step the difference. So this constant clock must run at least at the highest possible step rate and do position calculations just that often. Likely, an ATmega can't keep up with this.

Second approach whould be to calculate acceleration steps & co. for each axis individually and run them more or less independent of each other. ACCELERATION_TEMPORAL worked in this direction. The tricky part here is geometric accuracy, as not even the number of acceleration steps matches. Also the processing load is probably high, as acceleration calculation is required four times (interrupt time!). It might work out, though. Bonus is, there is no master axis, so the problem of a changing master axis between two lines simply disappears.

Third approach whould be to introduce another (mathematical) axis, which always runs along the direction of movement. This axis does the acceleration stuff and all real axes follow with a bresenham factor < 1. Simple, effective, at the cost of uneven step intervals.


Markus


[1] Edit: c and n are no longer stored in the queue, but in a global variable, so this works out.

Edited 1 time(s). Last edit at 05/16/2011 03:29AM by Traumflug.

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

Traumflug Wrote:
-------------------------------------------------------
> - acceleration is relative to the direction of the
> fast axis
>
> - the fast axis is both times the same

so we need to calculate and keep the results for all axes, as if we were doing per-axis, but then do bresenham within the move itself for geometric precision. That'll boost the ram usage a bit - is it worth it?

> Second approach whould be to calculate
> acceleration steps & co. for each axis
> individually and run them more or less independent
> of each other. ACCELERATION_TEMPORAL worked in
> this direction. The tricky part here is geometric
> accuracy, as not even the number of acceleration
> steps matches. Also the processing load is
> probably high, as acceleration calculation is
> required four times (interrupt time!). It might
> work out, though. Bonus is, there is no master
> axis, so the problem of a changing master axis
> between two lines simply disappears.
>
> Third approach whould be to introduce another
> (mathematical) axis, which always runs along the
> direction of movement. This axis does the
> acceleration stuff and all real axes follow with a
> bresenham factor < 1. Simple, effective, at the
> cost of uneven step intervals.

I've been thinking that if we can get E to be the master axis during moves with extrusion, we can solve two birds with one stone. It's becoming clear that we need E to lead the other axes to build up pressure in the melt zone. I had the idea of doubling up on bresenhams- have E_steps vs E_extruded as one bresenham, then slave the other axes to E_extruded.

Then we just need to work out how to cross from one move to the next keeping E_velocity as high as possible given other constraints. This would require all the math for per-axis be kept so we can work out appropriate move blending.


I've been wondering about the bresenham stuff too.. All the information is there to work out how far between master axis steps other axes should step, can we extract it with a minimum of math and use it for jitter reduction to emulate per-axis? This could give us the best of both worlds. Basically it goes like this:
usually, counter -= delta; if counter < 0 { step, counter += ts }, my idea is counter -= delta; if (counter < delta) { /* slave step happens before next master step! */ set_slave_timer(counter * c / delta); }; slave_step() { step(); counter += ts; }

so can we somehow work out counter * c / delta quickly?

---

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

Quote

so we need to calculate and keep the results for all axes, as if we were doing per-axis, but then do bresenham within the move itself for geometric precision. That'll boost the ram usage a bit - is it worth it?

To be honest, this sounds like it quickly becomes very complex. Think about that smoothing curve between two straight lines which crosses a 45 deg boundary ...

Quote

I've been thinking that if we can get E to be the master axis during moves with extrusion

Yes, using E as this master axis is an excellent idea. The extruder often does less or no steps (e.g. rapid move), but coupling these two whould be possible.

Quote

so can we somehow work out counter * c / delta quickly?

200 cycles? I fear I can't follow where the big improvement is. Perhaps because I don't care much about jitter as long as there is no look-ahead

BTW., why did you remove ACCELERATION_TEMPORAL? Wasn't hat meant to be the algorithm of the future? The code looked good! Except for the missing acceleration, of course.

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

Traumflug Wrote:
-------------------------------------------------------
> BTW., why did you remove ACCELERATION_TEMPORAL?
> Wasn't hat meant to be the algorithm of the
> future? The code looked good! Except for the
> missing acceleration, of course.

that's why- I couldn't work out how to get the acceleration in there, so I scrapped it. There comes a time in every project's life where it's easier to rewrite from scratch than fix the existing codebase. After scrapping temporal, I did work out the per-axis algorithm which is basically temporal with accel, but the geometric errors were too high even with floating point math- eg on a move of X140 Y3, the Y axis would reach its endpoint at around X=90!

Without acceleration, it's a mere novelty to me.

I have written a blend algorithm- one that does all the per-axis math so we can choose appropriate acceleration and deceleration profiles for the move that obey axis limits but then uses bresenham in the actual move interrupt itself to maintain geometry. It appears in my experimental SoupCup codebase due to heavy use of floating point if you're curious.

Not sure if it's suitable for backporting due to all the floating point math. I don't think it translates well to integer math at all.

---

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

Could this aditional level of complexity be more than AVR's can do realtime? Moving to a 2-pass strategy may be the answer. Either feed the code thru a PC side preprocesor, send to firmware and it responds with the prepeocessed moves and host send them back to firmware to print, or even better firmware stores the preproocessed data on SD to do the print.

Quote

Could this aditional level of complexity be more than AVR's can do realtime?

Maybe, but we're nowhere near that ceiling yet. The required algorithms are missing, so even a 8-core Xeon whouldn't help.

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

jv4779 Wrote:
-------------------------------------------------------
> send to firmware and
> it responds with the prepeocessed moves and host
> send them back to firmware to print, or even
> better firmware stores the preproocessed data on
> SD to do the print.

soupcup does this. It takes too much ram and flash to fit on a '328, especially since the SD/FAT code alone takes about 18k of flash!

Don't worry, I'm not abandoning teacup, I'm just seeing what's possible when we drop '168 and '328 support as design requirements. I plan to run development of both in parallel once my printer is working which is what I'm actually focusing on at the moment!

---

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

here it is!

Well, it's a start anyway.. looks like it would spit out E steps /way/ too fast in some situations. I think that double layer bresenham will turn out to be really handy. I'm thinking that we may have to ignore acceleration and speed limits on E axis to implement this initially which I'm not particularly keen on, but I think most (all?) current machines can handle it as long as E-only moves (extruder dump) still obey them.

---

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