smiller@wet.UUCP (Gregory Shane Miller) (03/20/91)
Tue 19 March 1991
Re: Bresenham's Linear DDA and Motion Systems
---------------
Everybody knows that Bresenham wrote a paper in 1965 called "Algorithm
for Computer Control of a Digital Plotter". The idea is of course to
generate a line (an approximation of desired line) very quickly.
What I want to call attention to is its application to moving systems.
It seems to me that the algorithm does not work generally with motion
systems especially at high speeds or with high loads. I want to know if
anybody can correct my thinking on this or advise me on an alternative
to linear DDAs.
To illustrate my concern very quickly, assume a XY table is at currently
located at the origin. It is then commanded to move to 100,23. We use Bresen-
hams linear DDA to approximate the true line. So we run through a loop 1 to
100 and then depending on a decision variable, we move horizontally or we
move diagonally ("distribute a step in the 'Y' direction"). Here's my
problem: THE Y STEP (IN MY EXAMPLE) IS SOMETIMES DISTRIBUTED EVERY 5 X STEPS
OR SOMETIMES EVERY 4 X STEPS. I've listed the first 22 iterations of the loop
below. 'X' means make 1 step in the X direction and 'Y' means make on step
in the Y direction.
[1] X [6] X [11] X [16] X [21] X
[2] X [7] X [12] X [17] X [22] X Y
[3] X [8] X [13] X [18] X Y .
[4] X [9] X Y [14] X Y [19] X .
[5] X Y [10] X [15] X [20] X .
You can see that on the 5th iteration 1 Y step was made. You'd expect the
next one at iteration 10 but it comes at 9 (only 4 steps later not 5). The
next Y step comes at 14 (5 steps later). The next two Y steps both come after
4 X steps passes. Shortly, it switch back to 5 ...
When your are (as I am doing) moving stepper motor systems at high speeds
(I'm doing feed rates of 120"/min) this small change in the frequency for
the Y axis causes it to "stick", grind, "freeze", or generally to screw up!
Obviously the whole technique works great in the graphics area ...
After a little more consideration, I concluded any linear DDA will exhibit
this problem (I developed my own DDA and it suffers from the same problem).
What can you do? Am I wrong? Is there a way to make a line nicely even
at high speeds? How could Bresenham title his paper "... for Computer Control
of Digital Plotters"? I tried to get the original article so as see for myself
but somebody stole that issue from my local university (UC Berkeley).
There's 15 billion sevo/stepper driver programs - how do you guys do it (short
of buying hardware for each axis and stuffing each with a distance to move
and velocity to use). What I want is one CPU controlling two outputs; one for
the X axis and one for Y axis. Mabybe that's dreaming :{
HELP PLEASE - thanks - smiller@wet.UUCP
--
G. Shane Miller [ smiller@wet.UUCP (415) 453-4926 ]whit@milton.u.washington.edu (John Whitmore) (03/25/91)
In article <2237@wet.UUCP> smiller@wet.UUCP (Gregory Shane Miller) writes: >Re: Bresenham's Linear DDA and Motion Systems > >Everybody knows that Bresenham wrote a paper in 1965 called "Algorithm >for Computer Control of a Digital Plotter". The idea is of course to >generate a line (an approximation of desired line) very quickly. > >What I want to call attention to is its application to moving systems. >It seems to me that the algorithm does not work generally with motion >systems especially at high speeds or with high loads. ... >problem: THE Y STEP (IN MY EXAMPLE) IS SOMETIMES DISTRIBUTED EVERY 5 X STEPS >OR SOMETIMES EVERY 4 X STEPS. What the Bresenham algorithm does is predicated on the assumption that one wishes to generate the bitmap corresponding to 'nearest the given line'. What YOU want is time-specified; the Bresenham method gives you +/- 1 'tick' time resolution for your motor, and you are complaining that a motor speed variation of plus or minus one step per N ticks (where N is greater than or equal to one, but depends on the slope of the line) is too great. There IS a solution to your problem using Bresenham; you can compute with Bresenham the motor movement to higher accuracy than the physical mechanism (like, 32 virtual steps per motor step), and ignore the five least significant bits of the X/Y positions that Bresenham generates. The motor speed variation would be then plus/minus 1/32 of a step per 'tick'. Also, instead of both the X and Y axis motors updating at the same time, they would generally operate with stepping pulses 'out of step' by a multiple of 1/32 nd of the minimum step time that the motors will accept (considering the required torque...). Of course, this requires the Bresenham inner loop be traversed many times (32 at minimum) per external motor-step event, but the stepping motor will require a millisecond or so per step, and that probably will suffice for the calculation. On a modern ALU. The last plotter I disassembled used microstepping motor controllers, and the shaft position accuracy was on the order of one full microstep, so one would assume the velocity 'irregularity' would not be a major problem. Probably the shaft inertia and its elasticity would combine to smoothe the effect away. John Whitmore