🚀 go-pugleaf

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