alternatives to current linear Bresenham algorithm

Read this page here.
[blog.cncorbust.com]

This guy seems to know what he is talking about on stepper algorithms.

I agree with him that there is a flaw with the how the other axis follows the lead axis. The steps of the lead axis are smooth, but the other axis's are not.

Soupcup was mentioned to have an alternative approach. I am not sure as to how it is different, so I am ready to be enlightened

SoupCup can be found at [github.com]


What I would like in this topic is a discussion of alternatives to the Bresenham algorithm, or a fix for the non smoothness of the other axis.

Keep it green, don't be mean! Also I would like to keep this discussion firmware generic. meaning discuss alternative algorithms, not specific firmwares. Please!

On microcontrollers that supports 4 or more output capture style hardware units (Pic32 and some ARM, probably others as well) it is possible to generate the leading edge of the step pulse from a hardware comparision of a high resolution timer with a changable value. A similar approach can be used with an XMOS chip by dedicating a thread per step generator.

On such microcontrollers the timing for constant velocity steps becomes a simple matter of division - total amount of time (in whatever timer resolution is used) divided by the number of steps to be taken. Some adjust for any remainder is needed (truncate, distribute evenly over the pulses, or load them at the beginning or end) - no Bresenham algorithm is needed, the timing of every axis is a precise as the timer resolution allows, and jitter due to the interrupt response time is eliminated.

Demitasse was written to use the above approach specifically because I was interested in seeing if the jitter had any observable effect on the printed objects. As far as I can tell, no, it does not. At least not at the speeds that are commonly used today.

Acceleration is something that I've yet to implement so I'm not prepared to discuss it intelligently yet, but thank you for that link because it references some material that I need to read...

Quote

a fix for the non smoothness of the other axis

Why does it need a fix. What problem does it cause for FFF? Remember the steps are actually microsteps and the inertia of the motor smooths out the path anyway.

---

[www.hydraraptor.blogspot.com]

If you scroll back Teacup's repository a month or so, you'll find a thing called ACCELERATION_TEMPORAL in dda.c. This smoothes out all four axes, but it was never found a way to do acceleration. In the still existing branch "ramping_temporal" an approach for this acceleration is sketched, but this has still to receive testing.

So, the nuggets are there, available for you to play with them.

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

I dropped my solution from soupcup, you'll have to scroll back a few commits. Basically, precision loss meant that it was almost impossible to get all the axes to finish moving at the same time. When they moved similar distances it was almost perfect, but with things like eg G1 X143 Y8.1 it was terrible- Y would finish moving at X=85 or so!

I think I wrote somewhere another possibility- the bresenham counters vs the update value give a proportion with which we can calculate the exact correct step time vs the leading axis. This gives us both less jitter and acceleration at a cost of doing more math in interrupt context.

Personally I agree with nophead on this one, the physical systems smooth out the jitter to an acceptable degree.

---

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

I wasn't able to find any link between the non-optimal stepping of the slower axis and lower print quality. The mechanical properties of belts and motors seem to smooth it out to a non-issue as our speeds.

The lag in time between when the extruder stepper turns and the actual plastic comes out and that interaction with lots of acceleration does cause quality issues. Resulting in not enough plastic at the start and too much at the end of a move.

This is just for a thought....


What about approximating the position within resolution limits .1mm and sub sampling and offsetting a line that has a direct correlation? sub sampling is breaking down the steps into several steps, and only one in say 64 of those actually does a stepper move.

here are direct angle evenly divided step angles for x and y. as long as the slave axis does not exceed the maximum stall or start speed of the axis. it is fine. some times interpolation of moves requires a correction. the correction is 2 or 3 steps together and at the same max speed of lead axis.


Is it possible to looking at this range of 1 to 1 and 1:8 speeds of slave axis, come up with a way to ensure that the slave axis speed is constant, and that corrections are by a shift offset before ramping up.


this is a picture of 8:1 and 1:8 x and y axis alternating lead.



this image below shows the same image with green colors for 1 in 8. as long as stall speed is no less than 1/8*max ramp speed, we are good to go. for now it is safe to say the green angles are approachable in between any angle of green without error in steps. the lines drawn are the only angles capable of accelerating linearly to each other. Red areas need to follow an actual maxstartspeed:accelerated speed correlation or need to be carefully sub sampled. note: 1:1 ration is at 45deg. i don't know why it is not showing by 45deg is a 1:1 correlation it would be a line down the middle.


then there is sub sampling. look at this 1/64 sub sampled


sub sampling increases amount of lines that we can linearly accelerate because lead axis only moves forward every 64th step


here is a sample that is 1/32 sub sampled.


not as detailed in the middle, but it is possible to adjust sampling level for lines along the corners.

so you can change sample size on the fly to approximate angles and offset results at beginning to have an even ramp. no need for modifications in green range. also there are a lot of angles that also are very bad, that need to be approximated. those bad angles have not been calculated. Any one who wants to play around with this method and needs a tool to see how angles interact can download it here lines


is it possible to ensure that an angle of direct correlation to sub sampling can occur? Is it possible that the max speed of the slave axis is the stall or start speed of that axis at all times?. Can Arduino do this subsampling at reasonable speeds?

Edited 3 time(s). Last edit at 06/16/2011 03:42PM by jamesdanielv.

I don't entirely understand what you're proposing, but if you're saying that we run a virtual axis faster than any real axis to achieve less jitter, that's what EMC2 does. I think our little atmegas would have trouble keeping up with a decent lead rate, and the resulting aliasing would end up on all moving axes rather than just the lead axis. I think this one can wait for the 32 bit, >60MIPS microcontrollers.

---

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

Triffid_Hunter - yes that is what I'm saying. well said by the way.


i have a arm processor capable of 80mhz and over 120mips with 32bit code, but there is still a little life in the arduino. especially with a couple if mega's laying around.

another option is to use 64bit math,or take advantage of the pins pwm settings to allow for aliasing without that much more processing power.. with 64 bit math we would have some options not available currently.

[www.arduino.cc]


even better is to move gcode processing back to the host and have the arduino execute bare minimum timing of i/o

there are still several options out there. yes i think a bigger better faster processor would make things easier.

I still think we can do something on arduino though..

Currently, Sprinter can achieve about 36KHz step rate by doing the whole move in a tight busy loop. Teacup tops out at about 13KHz because we use a step interrupt and keep everything else running at the same time (serial I/O, temp sensors, heaters, system clock, gcode processing etc).

EMC2's virtual axis runs at 40KHz, and at this rate you would have markedly increased jitter for any fast stepping axes that aren't stepping at a subharmonic of 40KHz, and jitter equally savage as worst case bresenham at around 26.6KHz. With our bresenham implementation, the fastest axis always has close to zero jitter, and the secondary axis may have up to +/-50% jitter (2,1,2,1 pattern).

Since EMC2 can turn out such lovely results, I think jitter is as much of a non-issue in this application as we think. There's no point making things really complex in an effort to avoid it.

The other approach is to run the virtual axis at some multiple of the fastest axis' step rate. This will definitely decrease jitter on slave axes, at the expense of needing a very tight step calculation function that can execute fast enough to run the fastest axis at whatever top speed you're trying to achieve.

If jitter really bugs you, I suggest that using the bresenham error counters to calculate when slave axes step relative to the master and plugging those into your extra timers may be the best compromise- simple, not much more math than we're already doing, and most importantly, geometrically correct. Can be as simple as slave_time_offset = master_step_time * error_numerator / error_denominator.

---

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

I have a modified version of an arduino firmware pushing 92.5khz at o-scope for a y move of G1 Y1000 F400000 . using fast writes, with interrupt redundancy, meaning writing two times to a pin in case first time is interrupted. also i require a 1us delay enabled in configuration for when e axis moves only. that is 1 step every 92.5khz. Without this delay it runs at 134.9khz single axis . these are actual o-scope measurements from frequency counter mode. nothing to scale, other than divisions set to 1us sampling.

is this about normal?

Edited 3 time(s). Last edit at 06/17/2011 03:40AM by jamesdanielv.

jamesdanielv Wrote:
-------------------------------------------------------
> I have a modified version of an arduino firmware
> pushing 92.5khz at o-scope for a y move of G1
> Y1000 F400000 . using fast writes, with interrupt
> redundancy, meaning writing two times to a pin in
> case first time is interrupted. also i require a
> 1us delay enabled in configuration for when e axis
> moves only. that is 1 step every 92.5khz. Without
> this delay it runs at 134.9khz single axis . these
> are actual o-scope measurements from frequency
> counter mode. nothing to scale, other than
> divisions set to 1us sampling.
>
> is this about normal?

yeah that's quite achievable without acceleration.. it's doing accel properly as well that slows things down.

btw, I don't see how a pin write could be interrupted, it's a single instruction operation...

---

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

without knowing the pin in advance it becomes a little more complicated it breaks down to 2 instructions.


with knowing the pin it still takes 2 instructions, although this is prone to its own set of errors. it is better to buffer the known state in a ram location then to find out on the port register what is stored there...

people following this post can find out about bit port manipulation here. [www.arduino.cc]

PORTB=PORTB | 00000001 turn on bit.

PORTB=PORTB & 11111110 turn off bit

it was a little faster with using disable Interrupts instead of repeating the commands. still is 4 commands though, i think disabling interrupts is not correct protocol in this case, because it messes with timers.

I guess i also could code for a pin bit xor change without reading the port first. that probably will shave off a few more cycles. so thanks


i am using acceleration. also using the sprinter firmware modified. just shaving off cycles where i can... i can pm it to you to verify if you would like, but personally I'd like a week or so to do more changes before the community can look at it. Also i don't want to disturb sprinters marketing.

but i think you know what I'm talking about when i say it currently does not matter how much faster a firmware runs.

even at 140.8khz (which is where I'm at now) you still run into the slave axis stall speed as the max speed of that axis because it rarely constantly moves. constant motion allows acceleration that is predictable.

Edited 2 time(s). Last edit at 06/17/2011 05:17AM by jamesdanielv.

jamesdanielv Wrote:
-------------------------------------------------------
> with knowing the pin it still takes 2
> instructions, although this is prone to its own
> set of errors. it is better to buffer the known
> state in a ram location then to find out on the
> port register what is stored there...

Actually gcc uses sbi/cbi for bitwise port I/O, no need to know previous state with those, it's handled by the hardware. They're both single cycle instructions

> it was a little faster with using disable
> Interrupts instead of repeating the commands.
> still is 4 commands though, i think disabling
> interrupts is not correct protocol in this case,
> because it messes with timers.

nope, timers run independent of interrupts, you can just keep adding Tdelta to OCR1A and checking the flags as long as you don't underrun.

> I guess i also could code for a pin bit xor change
> without reading the port first. that probably will
> shave off a few more cycles. so thanks

sbi/cbi still faster than xor. Also writing to PINxy will perform a xor, so that can be handled by hardware too rather than read/modify/write manually

As you can probably tell, I've read the datasheet closely to find out which optimisations are applicable and possible for this architecture

> i am using acceleration. also using the sprinter
> firmware modified. just shaving off cycles where i
> can... i can pm it to you to verify if you would
> like, but personally I'd like a week or so to do
> more changes before the community can look at it.
> Also i don't want to disturb sprinters marketing.

disturb? this is open source in action, when it works send a pull request or create a new branch or something!

> but i think you know what I'm talking about when i
> say it currently does not matter how much faster a
> firmware runs.
>
> even at 140.8khz (which is where I'm at now) you
> still run into the slave axis stall speed as the
> max speed of that axis because it rarely
> constantly moves. constant motion allows
> acceleration that is predictable.

You're saying the jitter causes stalls? Interesting, does the stalling axis stall at higher speeds when it's the master, nothing else changed?

I expect that with full step, maybe half step but at 1/16 microstep, the rotor is always a few steps behind anyway.

If you can get the firmware running reliably at 140KHz, maybe doubling the timer fire rate is more feasible than I thought at first

---

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

yeah your the master.... I'll do a separate firmware branch but i want to change a few more things.

the macro that i do the fast writes with includes pwm disabling... need to get rid of it. then it will run a bit faster

Edited 1 time(s). Last edit at 06/17/2011 08:54AM by jamesdanielv.

almost ready to post an alternative firmware branch/fork. i went backwards i guess and took tonokip original firmware and modified it so it does 176.8khz steps on single axis and with a dual move of x and y it does 121khz. it may be possible though tricky to have x and y move together with a pulse rate of over 160khz.

There is speed room to incorporate a method of sub sampling. Although it would be best to have sub sampling of 64, this version will at least sub sample between 1 and 16. 1 if it does not work and 16 if there is speed to do so.



think this will be called tach_Redline fork/branch. should it be a fork of tonokip, or completely separate? signed up for git account already.

ok a few things, on the atmega some port registers are out of range to do single instructions writes, so the digitalWriteFast with a few cycles is still in use. It is capable of near 180khz being this way. 8 times sub-sampling speed is 17.5khz

a few other things to think about with future firmwares.

whether to accelerate or not to if move shorter than 5mm it is not worth it currently and causes jitter (unless on sd)
provide simple multitasking ability to process char buffer during delays (delays happen often between steps)
curved acceleration - advanced prediction of corners 10-100steps ahead of line segment ending.
some sort of smoothing between line segments. if angle and speed is same, why slow down at all?

Here's an integer bresenham curve interpolator algorithm if you feel like implementing it

EMC2's path planner has some interesting write-ups too, which should go nicely with the above algorithm.

I think a minimum speed and a minimum ramp distance would do far more for corners than having a no accel distance

---

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

I think only Bresenham line has constant velocity along the path. The circle, for example, will be travelling faster when the tangent is 45 than it is when the tangent is 0 or 90.

---

[www.hydraraptor.blogspot.com]

It may be important to know the mass of the tool head,and the direction it is moving in separately for x and y, for every quadrant, there is a slow part, and a brief period of no motion on axis before it switches direction. at very least a delay constant for x,-x,y,-y

also modifying angles to both move at a constant (evenly but different) speed will increase max speed and reduce jitter and resonance of motors.

Changing angle slightly will increase speed, even with 8x sub sampling angles between 43-45 and 45-47 (but not 45 as 45 is evenly accelerated both axis) there is no constant acceleration, so in order to have jitter free motion the max speed between those angles should not be more than stall speed of motors. outside of those angles, as the angle becomes more Perpendicular the max speed eventually can be over 8x the stall speed because the slave axis moves at less than 1/8 the speed of lead axis, or be at an exact angle that causes constant acceleration on each axis. outside of 43-47 degrees the angles can be manipulated slightly enough to be within .1mm even at 100mm distances.

some calculation needs to be done to alter max speeds at certain angles and at other angles more perpendicular modify the angles slightly to increase max speed. with the slave axis not being evenly accelerated the max speed is the lead axis steps/slave axis steps *stall speed