Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!emory!gatech!prism!jm59 From: jm59@prism.gatech.EDU (MILLS,JOHN M.) 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: <24879@hydra.gatech.EDU> Date: 22 Mar 91 16:32:17 GMT References: <2237@wet.UUCP> <1991Mar22.120627.14537@bohra.cpg.oz> Organization: Georgia Institute of Technology Lines: 145 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