Xref: utzoo comp.robotics:755 comp.realtime:1216 sci.electronics:18763
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!decwrl!ogicse!milton!whit
From: whit@milton.u.washington.edu (John Whitmore)
Newsgroups: comp.robotics,comp.realtime,sci.electronics
Subject: Re: Help with Bresenham line DDA and XY tables: they don't work together!
Keywords: bresenham DDA CNC stepper motor
Message-ID: <18986@milton.u.washington.edu>
Date: 25 Mar 91 02:53:45 GMT
References: <2237@wet.UUCP>
Organization: University of Washington, Seattle
Lines: 45


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