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 ]als@bohra.cpg.oz (Anthony Shipman) (03/22/91)
I think what you want is to have the X and the Y motors run at constant speeds during the table motion. Then the path of the table will be a straight line (to within the resolution of the steppers). The ratio of the motor speeds determines the angle of the table's path. If you want to be able to move it at any angle you will need continuous speed control, i.e. an analogue speed controller. If the motor speeds are discrete then the path angle can in general only approximate the desired angle on average. This means the motor speeds will have to keep changing as the path angle is corrected. You can correct the angle frequently like the DDA algorithm does to get a smooth line but then your motor speed flutters. You can correct less often to go easier on the motors but then the path has greater deviations and corrections. I think you can only get what you want with continuously variable speed control on your motors. The equivalent of this in the graphics world is the vector graphics display. The DDA is a discrete approximation for raster graphics. -- Anthony Shipman ACSnet: als@bohra.cpg.oz.au Computer Power Group 19 Cato St., East Hawthorn, Melbourne, Australia D
jm59@prism.gatech.EDU (MILLS,JOHN M.) (03/23/91)
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. Actually, I didn't. Thanks. >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 In my dim memory (c.1968), DDA approaches have the quality that they easily generate polynomial trajectories (including sinusoids), and can be expected to converge on terminal points, subject to your word length (in contrast to binary rate-multiplier --BRM -- generators), but the _big_ disadvantage that their computation load depends on the speed of travel _and_ on the length of move _if_ you don't scale a straight segment up to nearly fill the accumulation registers. (That means multiply the segment lengths by the (same) largest integer than won't make either overflow. If you already knew that, excuse me. I don't know what you've tried.) It is possible to guarantee at least a 50% output rate for a DDA generator. If you time your steps explicitly (instead of letting the DDA cycle do so) you can spin the algorithm till you get one output, then cycle it once more. You can have three results: (1) no output -- send what you have; (2) output on the same axis -- send it next time; (3) output on the _other axis_ -- send both out and adjust the delay for the next iteration. I thought that a DDA straight-line generator could always guarantee being in the best available grid point with respect to your path, but your experience sounds like I'm wrong. Another class of algorithms which is popular in rasterizing applications, I call "discriminant based." There was an article in Byte a few years ago on raster graphics or laser-printer drivers which mentioned some of these, but the only reference I have to hand is a paper by the developer of Fujitsu's 10-phase electro-hydraulic steppers. It is: "Contouring NC Featuring Cutter Radius Full Size Offset and Direct Digital ...," S. Inaba, ASTME Tech. Paper (MS?) 68-218. Unfortunately, I only have a microfiche. It is not obvious until you spend some time on it, but Inaba has a scheme which fell beautifully into simple logic generators (not so important now), and, _if_ it starts in the right spot will _automatically_ generate a conjugate trajectory to implicitly generate the right cutter path when you have programmed the part outline. Remember that he pulled this off with almost no logic (by today's standards). Lots of shortcuts and remappings are possible, but the paper rather leads you _away_ from them. (He builds the controller, remember |8*>). I hope that will bring some others' experience out of the woods. Mine is somewhat dated. -- MILLS,JOHN M. Georgia Institute of Technology, Atlanta Georgia, 30332 uucp: ...!{decvax,hplabs,ncar,purdue,rutgers}!gatech!prism!jm59 Internet: jm59@prism.gatech.edu Newsgroups: comp.robitics Subject: Re: Help with Bresenham line DDA and XY tables: they don't work together! Summary: Expires: References: <2237@wet.UUCP> Sender: Followup-To: Distribution: Organization: Georgia Institute of Technology Keywords: bresenham DDA CNC stepper motor 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. Actually, I didn't. Thanks. >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 In my dim memory (c.1968), DDA approaches have the quality that they easily generate polynomial trajectories (including sinusoids), and can be expected to converge on terminal points, subject to your word length (in contrast to binary rate-multiplier --BRM -- generators), but the _big_ disadvantage that their computation load depends on the speed of travel _and_ on the length of move _if_ you don't scale a straight segment up to nearly fill the accumulation registers. (That means multiply the segment lengths by the (same) largest integer than won't make either overflow. If you already knew that, excuse me. I don't know what you've tried.) It is possible to guarantee at least a 50% output rate for a DDA generator. If you time your steps explicitly (instead of letting the DDA cycle do so) you can spin the algorithm till you get one output, then cycle it once more. You can have three results: (1) no output -- send what you have; (2) output on the same axis -- send it next time; (3) output on the _other axis_ -- send both out and adjust the delay for the next iteration. I thought that a DDA straight-line generator could always guarantee being in the best available grid point with respect to your path, but your experience sounds like I'm wrong. Another class of algorithms which is popular in rasterizing applications, I call "discriminant based." There was an article in Byte a few years ago on raster graphics or laser-printer drivers which mentioned some of these, but the only reference I have to hand is a paper by the developer of Fujitsu's 10-phase electro-hydraulic steppers. It is: "Contouring NC Featuring Cutter Radius Full Size Offset and Direct Digital ...," S. Inaba, ASTME Tech. Paper (MS?) 68-218. Unfortunately, I only have a microfiche. It is not obvious until you spend some time on it, but Inaba has a scheme which fell beautifully into simple logic generators (not so important now), and, _if_ it starts in the right spot will _automatically_ generate a conjugate trajectory to implicitly generate the right cutter path when you have programmed the part outline. Remember that he pulled this off with almost no logic (by today's standards). Lots of shortcuts and remappings are possible, but the paper rather leads you _away_ from them. (He builds the controller, remember |8*>). I hope that will bring some others' experience out of the woods. Mine is somewhat dated. Newsgroups: comp.robitics Subject: Re: Help with Bresenham line DDA and XY tables: they don't work together! Summary: Expires: References: <2237@wet.UUCP> Sender: Followup-To: Distribution: Organization: Georgia Institute of Technology Keywords: bresenham DDA CNC stepper motor -- MILLS,JOHN M. Georgia Institute of Technology, Atlanta Georgia, 30332 uucp: ...!{decvax,hplabs,ncar,purdue,rutgers}!gatech!prism!jm59 Internet: jm59@prism.gatech.edu
megauthi@watcgl.waterloo.edu (Marc E. Gauthier) (03/25/91)
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". (well, I wasn't aware of the paper) >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 >[...detailed description of using bresenham to increment X and Y of a > plotter pen, with all movements synchronised with the increment of the > "longer" axis... deleted...] > >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). >[...] >HELP PLEASE - thanks - smiller@wet.UUCP You were right in saying (somewhere in the deleted text?) that you need to control both axis independently, so they each move as uniformly as possible. In controlling this timing however, it occurred to me that precision is usually of finite granularity, e.g. you usually have a timer which can signal your program in "ticks"; the question is, then, at which tick shall I increment X, and at which tick shall I increment Y? So what you have is really two bresenham lines being drawn simultaneously, one on the X-vs-time plane, the other on the Y-vs-time plane (where on the time axis you have ticks instead of pixels). Is this clear? Was this in the Bresenham paper? -Marc -- Marc E. Gauthier megauthier@watcgl.waterloo.edu University of Waterloo 129.97.128.64 885-1211 x3469 or x4548
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
jhuang@sci.ccny.cuny.edu (Jian Huang) (03/30/91)
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