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 ]