6th-order jerk-controlled motion planning

dc42

@rcarlyle, I agree with all of that. The fact that the Marlin algorithm forces zero acceleration at the segment boundaries was bothering me too.

I expect to start work on this in July. Using a 6th order Bezier curve, I think there are enough parameters to match target accelerations at the segment start and and as well as target speeds, but the maths to work out the parameters may be difficult. If it turns out to be too hard then I can try implementing classic 7-phase motion instead of the current 3-phase.

Any solution also needs to eliminate commands to change velocity instantaneously ("jerk" in the 3D printer sense), by planning a deliberate deviation from the commanded path instead of commanding instantaneous speed changes and getting an unplanned deviation as a result.

JoergS5

Dear @carlosspr , thanks for explaining part of the firmware source files. If you want, I can help you checking your changes.

My proposal:

isolate the formulas so they can be tested independently (unit testing)
take real world examples of parameters
calculate the values with your formulas
test plausibility by differential time slices, e.g. V-t diagram. E.g. the S curve should show up
if the formula are correct, at least some sums must be correct, like total distance in given time

It is possible to use mathematical simulation programs for the task, but to start easy you can use a spreadsheet program, each row a diff t. The lower diff t, the more exact the results.

RCarlyle

@dc42 I think you need to decide whether to work on addressing corner jerks or work on nth-order straight-line motion, because the solutions strike me as more or less mutually exclusive. Deviating from corners means your paths are no longer exclusively a series of straight lines and corners, so from what I understand the entire motion planner and step interpolation scheme have to be reworked. For long segments you can just clip off the start and end, insert a new radius-arc motion to replace the corner, and keep the segment-middles as straight-line paths like normal. But with short segments, I think there's some complexity around deciding when/how to merge multiple gcode commands into a single radius'd arc or what have you. (Maybe you have something in mind.)

Personally, I'm fine with corner velocity jumps for this application, and am even fine with position jumps on extruder axis (eg pressure advance motions), because they work just fine with real steppers and servos when you stop ignoring driver+motor behavior. I would prefer to see a better cornering-speed-determination algorithm invented rather than eliminate them entirely. You probably know this, but here's what I've seen done:

Limit speed change for each motor (Sailfish)
Limit nozzle velocity vector delta magnitude (older Marlin, Repetier)
Limit "junction deviation" which is some arbitrary hocus with no real physical significance, but gives pretty good results... the CONCEPT is combining a radial acceleration limit with an error tolerance to round off corners, but it doesn't actually follow the trajectory required to implement that; it just uses the derived speed you WOULD use if you did it

My opinion, what we really ought to do is take the motor's behavior into account. For example, 3d printers are typically built with utterly ridiculous torque safety factors (like 50:1 on nominal acceleration), and what really limits cornering speed is the force:error relationship for the printer versus acceptable print quality. (IE the sum of motor following error and drivetrain deflections.) So we should be using a calculation connected to how velocity jumps exert forces on the mechanism. If those forces are comparable to the desired acceleration forces, there's no issue whatsoever with the corner velocity jump. I think that can be reasonably approximated as an elastic impact model, ie the change in kinetic energy due to the velocity jump is converted into elastic energy stored in the drivetrain as a spring deflection. You can thus turn the velocity jump into a peak force and predicted error. The trick here -- what nobody has brought together yet to my knowledge -- is that a lot of the drivetrain inertia is in the rotor, and a lot is in the extruder/bed, so on printers like deltas where the drivetrain ratio is variable, you need to check BOTH the rotor delta-V and the nozzle delta-V and either limit both separately or limit some kind of summing function of the two.

Ideally you'd calculate the total system inertia (moving mass reflected through drivetrain ratio, plus rotor) and velocity changes at each corner to get an actual delta-Ke value, and also calculate the total drivetrain elasticity at each corner according to the machine position, and use those to model a corner error due to the jump, but I doubt that's worth all the trouble. There's probably a simplified approach that captures the various factors with an empirically-tuned limit parameter like we use today. For example, combine a junction-deviation type calculation with a Sailfish-style motor speed change limit. Or convert the cornering jump into an equivalent acceleration based on some heuristic. Etc.

Changing gears. Deviating from the path according to a defined tolerance is a viable and reasonable approach as long as the max error is user-configured. MachineKit has a 3-axis trajectory planner mode that does this. (People use velocity extrusion to slave extruder motion to the 3-axis planner for 3d printing, although I personally think this violates a Stratasys patent.) However, it's a huge change from the GRBL ancestry all the major 3d printer firmwares use. You also probably want to be able to switch the allowed error mid-print so you can run infill rougher and perimeters finer, for example. (There's no fundamental reason for infill to use higher nominal feedrates than perimeters -- we just don't have good motion planners for complex perimeter geometry yet, so we drop perimeter speed to compensate for GRBL sucking.)

What I would suggest with corner-rounding is apply either a RADIAL nozzle acceleration cap and an acceptable path deviation, or PER-AXIS acceleration caps (cartesian axis or motor) and position errors. The path and rounded-cornering speed is then whatever trajectory achieves those max accels and errors. You get different corner-rounding shapes with the different approaches -- circle arcs from a radial acceleration cap, elipses for cartesian axis acceleration caps, and who-the-hell-knows-what from delta motor acceleration caps.

This gets more complicated when the segment size is small enough (ie similar magnitude as allowable error) such that the rounded trajectory spans more than two segments. Machinekit starts by merging small segments wherever the merged path results in less path-following error than the defined limit. That helps a lot. But it's another source of lost path-following fidelity. Then you have to do some iterative work over a queue to generate the overall rounded path, but I'm fuzzy on the details of how that's done.

If you really want to get complicated, you corner more like a car does, and combine centripetal acceleration with radial acceleration along a conic profile or something to achieve a constant combined acceleration. But that seems like too much to try to tackle.

RCarlyle

Oh, I also want to point out that GRBL's biggest speed control shortcoming is that it only looks at corners, and not radial acceleration across lots of segments. Finely-faceted smooth curves are basically ignored by all the mainstream 3d printer firmwares (except MachineKit). We really ought to be checking radial acceleration through arcs so the printer doesn't overspeed through them. The challenge there is how the firmware identifies an arc and determines what run of segments to check for radial acceleration...

JoergS5

Somebody wrote above that it's not possible to test different methods easily without a new firmware version and uploading.

But there is a possibility of scripting inside a program: you can script on the fly and test different possible functions, like the jerk functions above. A true evolutionary approach would be script variations - print and measure - take best of the variations. Print + measure could be a laser or led through the nozzle and photodiodes instead of real filament.

burtoogle

Really interesting thread this but the detail is somewhat over my head. Nonetheless, here's an idea to consider:

If some of the calculations that you maybe would like to do during printing are too complex to do in real-time, how about pre-processing the gcode into an intermediate form that can be interpreted quickly. So arcs/curves and other features of interest could be identified and replaced/augmented with mcodes or comments (or whatever) so that the subsequent gcode++(tm) file could then be printed using simpler realtime calculations.

The pre-processing could be done by the Duet, it would not need to be done before uploading the gcode.

JoergS5

@burtoogle the information whether it's a circle is in the original 3d object*), so transfering this information parallel to the gcode would be probably easier. Because calculating 3d objects from g-code or stl is not trivial. Your idea would allow printing a circle if the printer is capable of this, while another printer prints linear segments.

*) in this case, 2d objects at every layer

burtoogle

@joergs5 said in 6th-order jerk-controlled motion planning:

@burtoogle the information whether it's a circle is in the original 3d object, so transfering this information parallel to the gcode would be probably easier. Because calculating 3d objects from g-code or stl is not trivial. Your idea would allow printing a circle if the printer is capable of this, while another printer prints linear segments.

Sure, but that requires the slicer to play a part and it would be nice to have a solution that doesn't require help from the slicer.

@RCarlyle said

This gets more complicated when the segment size is small enough (ie similar magnitude as allowable error) such that the rounded trajectory spans more than two segments. Machinekit starts by merging small segments wherever the merged path results in less path-following error than the defined limit. That helps a lot. But it's another source of lost path-following fidelity. Then you have to do some iterative work over a queue to generate the overall rounded path, but I'm fuzzy on the details of how that's done.

Some of that could be a candidate for being pre-processed.

I'm really out of my depth with this stuff, so I can't pursue this any further.

wilriker

@joergs5 said in 6th-order jerk-controlled motion planning:

Because calculating 3d objects from g-code or stl is not trivial.

It's not but there is some promising progress made in that area right now: https://github.com/slic3r/Slic3r/issues/23#issuecomment-385288531

Of course this would again make it more slicer-dependent but still an awesome feature if it works as good as described.

Anyway, I think this is a little derailing in the regard that we are now discussing about corner-to-curves-conversion instead of the original discussion about acceleration-types, isn't it?

alranel created this issue in slic3r/Slic3r

open Detect arcs and generate G2/G3 #23

JoergS5

@wilriker wow, that's really interesting, thank you for the link!!

wilriker

@joergs5 Yeah, I was really excited when I found this myself.

RCarlyle

The reason why this arc stuff struggles to go anywhere is that there's a chicken-vs-egg problem with the slicer and firmware needing to change at the same time. Implementing G2/G3 arcs in the slicer is borderline pointless when the firmware handles arc commands by breaking them back into facets and running normal straight-line-and-corner motion control on the re-segmented path. (There's some benefit in gcode file size and command stream processing overhead but that's kinda "meh.")

STLs are faceted, and firmwares do everything faceted, so there's no point in slicers making up arcs when the upstream and downstream toolchains don't cooperate.

If you're going to make up arcs, you might as well do it in firmware. The Klipper model (RasPi does slicing AND trajectory planning, RAMPS does step pulses) is probably the easiest way to go on that front, but there are other things you can potentially do, like run a post-processing script between the slicer and firmware to do whatever conversion work you want.

Given the complexity of rounding off corners, I think working on straight-line motion and corner speed determination is pretty low-hanging fruit in comparison. That's my two cents.

Phaedrux

@rcarlyle I've been wanting to try playing around with Klipper using the duet as the MCU. Best of both worlds if you will. Best in class electronics and very high steps rates. If klipper succeeds in implementing s curve motion planning before the duet I will probably give it a shot.

wilriker

@rcarlyle Regarding whether arcs are making sense or not I was also torn between yes and no but I am now at "yes, they are useful". Let me explain why:

You are right that it seems to be pointless to have a command that defines an arc but the firmware will break it back into lots of linear movements. But there are at least three advantages of this approach I can see

Gcode files are smaller (more of a minor side-effect but still there)
The firmware usually knows on what hardware is running and it can optimize the breaking the arcs apart based on the capabilities of the processor, i.e. slower processors will have fewer segments compared to faster ones (this is already the case comparing Marlin vs. RRF where RRF uses a significantly smaller segment-size by default)
It cannot happen this way that the slicer is doing something strange in the middle of an arc (there are multiple posts in this forum where this happened) preventing the segmented arc being one fluid move. This can lead to lots of shaking, rattling, vibrations that can have a negative effect on print quality

So in my view having the slicer produce G2/G3 commands is desirable even though it seems absurd to have a total workflow where you design arcs in CAD, export them to STL which does not have arcs only to have them being reconstructed in the slicer be broken apart again inside the firmware.

This could in theory also be done in firmware (I mean reconstructing the arcs) but in the most cases the slicer runs on a much more powerful machine and that makes it a much better candidate for this step.

JoergS5

@wilriker I see a forth advantage

there are 3d printers being able to print arcs directly like printers with robot arms, they can print perfectly with arc g-code if the radius of the arm matches the radius of the g-code arc.

(I happen to be building a scara printer with variable radius.;-))

dc42

If G2/G3 arc printing becomes commonplace then I might find a way to generate arc movements without segmenting them.

Catalin_RO

@dc42 I use them extensively for CNC milling and all the motion related issues that I have (detailed in other threads!) are related to G2/G3, more specific, to G2/G3 movements followed by a G1. Maybe for 3D printing G2/G3 is not that important as the slicers usually start from a STL model, but CNC usually milling starts from a STEP model or something like that.

I will give just a simple example: if I want a 5mm hole, when made out of segments it will be slightly smaller!

I use extensively FreeCAD and CamBam. While FreeCAD can export both STL and STEP, CamBam really supports only STL. For complex items I tend to extract the edges and do simple profile and pocket operation based on them instead of an actual 3D milling - sometimes it requires less than half of the machining time! But for simple items I just draw 2D shapes in CamBam and then do operations on them with different Z start/stop heights. Either case, CamBam issues a lot of G2/G3 commands.

JoergS5

@catalin_ro As Cura 3.4 integrates FreeCad, Openscad etc. (thanks, David!), circles can be translated to g-code directly now, without STL.

wilriker

@joergs5 said in 6th-order jerk-controlled motion planning:

@catalin_ro As Cura 3.4 integrates FreeCad, Openscad etc. (thanks, David!), circles can be translated to g-code directly now, without STL.

That sounds great but the problem I see here is that CuraEngine which actually does the slicing part, does nowhere have code to write G2/G3 commands, only G1 and G0.
But maybe that will follow later.

burtoogle

@joergs5 said in 6th-order jerk-controlled motion planning:

@catalin_ro As Cura 3.4 integrates FreeCad, Openscad etc. (thanks, David!), circles can be translated to g-code directly now, without STL.

Except that the Cura plugins that provide this function do so by converting the source object to STL and reading that just like any other STL file. So the STL is still there, it's just hidden from the user.

Sorry to say that, at the moment, Cura can only work using polygons made from points and lines and does not have any support for models defined as arcs.