Algorithm for evenly arranging steps in 2 directions

Question

I am currently programming the controller for a CNC machine, and therefore I need to get the amount of stepper motor steps in each direction when I get from point A to B. For example point A's coordinates are x=0 and y=0 and B's coordinates are x=15 and y=3. So I have to go 15 steps on the x axis and 3 und the y axis. But how do I get those two values mixed up in a way that is smooth (aka not first x and then y, this results in really ugly lines)? In my example with x=15 and y=3 I want it arranged like that:

for 3 times do:    
    x:4 steps  y:0 steps
    x:1 steps  y:1 step

But how can I get these numbers from an algorithm? I hope you get what my problem is, thanks for your time, Luca

Answer 1

there are 2 major issues in here:

1. trajectory

   this can be handled by any interpolation/rasterization like:

   • DDA
   • Bresenham

   the DDA is your best option as it can handle any number of dimensions easily and can be computed on both integer and floating arithmetics. Its also faster (was not true in the x386 days but nowadays CPU architecture changed all)

   and even if you got just 2D machine the interpolation itself will be most likely multidimensional as you will probably add another stuff like: holding force, tool rpm, preasures for what ever, etc... That has to be interpolated along your line in the same way.

2. speed

   This one is much much more complicated. You need to drive your motors smoothly from start position to the end concerning with these:

   • line start/end speeds so you can smoothly connect more lines together
   • top speed (dependent on the manufactoring process usually constant for each tool)
   • motor/mechanics resonance
   • motor speed limits: start/stop and top

   When writing about speed I mean frequency [Hz] for the steps of the motor or physical speed of the tool [m/s] or [mm/2].

   Linear interpolation is not good for this I am using cubics instead as they can be smoothly connected and provide good shape for the speed change. See:

   • How can i produce multi point linear interpolation?

   The interpolation cubic (form of CATMUL ROM) is exactly what I use for tasks like this (and I derived it for this very purpose)

   The main problem is the startup of the motor. You need to drive from 0 Hz to some frequency but usual stepping motor has resonance in the lower frequencies and as they can not be avoided for multidimensional machines you need to spend as small time in such frequencies as possible. There are also another means of handling this shifting resonance of kinematics by adding weights or change of shape, and adding inertial dampeners on the motors itself (rotary motors only)

   So usual speed control for single start/stop line looks like this:

   

   So you should have 2 cubics one per start up and one per stopping dividing your line into 2 joined ones. You have to do it so start and stop frequency is configurable ...

   Now how to merge speed and time? I am using discrete non linear time for this:

   • Find start point (time) of each cycle in a sine wave

   its the same process but instead of time there is angle. The frequency of sinwave is changing linearly so that part you need to change with the cubic. Also You have not a sinwave so instead of that use the resulting time as interpolation parameter for DDA ... or compare it with time of next step and if bigger or equal do step and compute the next one ...

   Here another example of this technique:

   • how to control the speed of animation, using a Bezier curve?

   This one actually does exactly what you should be doing ... interpolate DDA with Speed controled by cubic curve.

When done you need to build another layer on top of this which will configure the speeds for each line of trajectory so the result is as fast as possible and matching your machine speed limits and also matching tool speed if possible. This part is the most complicated one...

In order to show you what is ahead of you when I put all this together mine CNC interpolator has ~166KByte of pure C++ code not counting depending libs like vector math, dynamic lists, communication etc... The whole control code is ~2.2 MByte

Answer 2

Consider Bresenham's line drawing algorithm - he invented it for plotters many years ago. (Also DDA one)

In your case X/Y displacements have common divisor GCD=3 > 1, so steps should change evenly, but in general case they won't distributed so uniformly.

Answer 3

If your controller can issue commands faster than the steppers can actually turn, you probably want to use some kind of event-driven timer-based system. You need to calculate when you trigger each of the motors so that the motion is distributed evenly on both axes.

The longer motion should be programmed as fast as it can go (that is, if the motor can do 100 steps per second, pulse it every 1/100th of a second) and the other motion at longer intervals.

Edit: the paragraph above assumes that you want to move the tool as fast as possible. This is not normally the case. Usually, the tool speed is given, so you need to calculate the speed along X and Y (and maybe also Z) axes separately from that. You also should know what tool travel distance corresponds to one step of the motor. So you can calculate the number of steps you need to do per time unit, and also duration of the entire movement, and thus time intervals between successive stepper pulses along each axis.

So you program your timer to fire after the smallest of the calculated time intervals, pulse the corresponding motor, program the timer for the next pulse, and so on.

This is a simplification because motors, like all physical objects, have inertia and need time to accelerate/decelerate. So you need to take this into account if you want to produce smooth movement. There are more considerations to be taken into account. But this is more about physics than programming. The programming model stays the same. You model your machine as a physical object that reacts to known stimuli (stepper pulses) in some known way. Your program calculates timings for stepper pulses from the model, and sits in an event loop, waiting for the next time event to occur.

Answer 4

You should take the ratio between the distance on each of the coordinates, and then alternate between steps along the coordinate that has the longest distance with steps that do a single unit step on both coordinates.

Here is an implementation in JavaScript -- using only the simplest of its syntax:

function steps(a, b) {
    const dx = Math.abs(b.x - a.x);
    const dy = Math.abs(b.y - a.y);
    const sx = Math.sign(b.x - a.x); // sign = -1, 0, or 1
    const sy = Math.sign(b.y - a.y);
    const longest = Math.max(dx, dy);
    const shortest = Math.min(dx, dy);
    const ratio = shortest / longest;
    const series = [];

    let longDone = 0;
    let remainder = 0;
    for (let shortStep = 0; shortStep < shortest; shortStep++) {
        const steps = Math.ceil((0.5 - remainder) / ratio);
        if (steps > 1) {
            if (dy === longest) {
                series.push( {x: 0, y: (steps-1)*sy} );
            } else {
                series.push( {x: (steps-1)*sx, y: 0} );
            }
        }
        series.push( {x: sx, y: sy} );
        longDone += steps;
        remainder += steps*ratio-1;
    }
    if (longest > longDone) {
        if (dy === longest) {
            series.push( {x: 0, y: longest-longDone} );
        } else {
            series.push( {x: longest-longDone, y: 0} );
        }   
    }
    
    return series;
}

// Demo
console.log(steps({x: 0, y: 0}, {x: 3, y: 15}));

Note that the first segment is shorter than all the others, so that it is more symmetrical with how the sequence ends near the second point. If you don't like that, then replace the occurrence of 0.5 in the code with either 0 or 1.