Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!rpi!sci.ccny.cuny.edu!jhuang
From: jhuang@sci.ccny.cuny.edu (Jian Huang)
Newsgroups: comp.robotics
Subject: Re: Help with Bresenham line DDA and XY tables: they don't work together!
Keywords: bresenham DDA CNC stepper motor
Message-ID: <1991Mar30.014344.1972@sci.ccny.cuny.edu>
Date: 30 Mar 91 01:43:44 GMT
References: <2237@wet.UUCP>
Organization: City College of New York - Science Computing Facility
Lines: 55


In article <2237@wet.UUCP> smiller@wet.UUCP (Gregory Shane Miller) writes:
>
>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.
>
I did linear interpolation on our MC2 stepper controller by
using this algorithem two years ago. It can run at about
15k pps with some noise. It works much nicer (up to 40K
pps) with DC motor because DC diver has a sort of low filter
function. You are right about the speed limit. The worst
case will happen in situation such as moving table from
{0,0} to {N,N-1}. The shorter axis will have a sudden speed 
change between a certain pair of pulses (50% loss and then 
100% increase) which is enough to cause its stalling when it
is at high speed. A possible improvement is to put a
divider on the output to average the change. A (/N) divider
will smooth the sudden change by factor of N. But you must
run that algorithm N times faster than before. Even with
some high-end microprocessors, this still needs at least
several microseconds. Considering other factors such as
interrupt latency and running background tasks you hardly
can get speed over 50k pps which is not high enough for
most microsteping systems. Therefore, the hardware solution
win again, which ironically was relaced by software several
decades ago. A chip from Toko can do linear interpolation
at 400k and circular interpolation at 200k. You pump a
pulse train into the chip, and its internal logic circuits
do all the algorithm for you. You still need a divider if
you want to get nice output to stepper. The best way to do
interpolation is to use close-loop-controlled frequency
generation in which you got have a high resolution
frequency generator. It usually is a rate multiplier or
self-adder. They need divider too, but CPU will not have to
run algorithm for every pulse output. A sample rate of 1k
is enough in most cases. Of course, new algorithm is axis-
independent and time-based. A PC stepper control board
from Oregon Micro Systems is based on this method by using
some large scale FPGAs. It can do interpolation at 524k
pps. In motion control area, path control (or contouring)
is still somewhat challenging. Maybe that is why I am
getting paid :-)

Hope this helps

-- 
JIAN HUANG                         System Software Engineer
jhuang@sci.ccny.cuny.edu           Klinger Scientific
jhuang@ccnysci.uucp                Garden City, NY 11530
jhuang@ccnysci.bitnet              (516)745-6800