Bresenham circle algorithm
ManAtWork
Posts: 2,176
StefanL38 has posted an article about the Bresenham algorithms for lines and circles here. I already knew that an algorithm existed for circle and arc drawing on raster screens (pixel based) that only used simple integer math. But as far as I can see this algorithm has a serious drawback which make it kind of useless for CNC applications: it doesn't give constant (angle) speed. Instead, one of the coordinates (x or y) is incremented with a constant step size and the other coordinate is calculated to fullfill the circle equation. If I understand correcly, this way the combined vector speed of both coordinates is sqrt(2) times higher in the 45/135/225/315 degree sections as at the 0/90/180/270 degree sections (near the coordinate axes). On the screen this doesn't matter, but in a milling machine a 41% higher speed can break the cutter or overload the motor.
Does anybody know how to fix this? The only solution I've found so far is incrementing the angle and calculating the x/y coordinates by use of the sin/cos functions. Fortunatelly, the propeller has a built in sine table, so that's not a big problem. But if the starting point of the arc is not at the zero crossings the starting angle value has to be calculated with the arctan function. There should be some more clever algorithm, I think.
Does anybody know how to fix this? The only solution I've found so far is incrementing the angle and calculating the x/y coordinates by use of the sin/cos functions. Fortunatelly, the propeller has a built in sine table, so that's not a big problem. But if the starting point of the arc is not at the zero crossings the starting angle value has to be calculated with the arctan function. There should be some more clever algorithm, I think.
Comments
did you already have a look at the "cordic" method?
Good luck,
Christof
Yes it can be fixed. One way I've tried is to compute a running average (digtially filtered) of the proportion of diagonal to orthogonal moves (lets stick to 2D for
this description), which is then put into a lookup table to determine the average distance per step. This value is used to advance an accumulator on every step
which is decremented according to the speed variable in the DDA that inserts null steps. Microstepping is assumed so that a little jitter in step rates is allowable.
3D would really require using a DDA to track the actual distance I believe. This has to be reset regularly as the track curves, but you can keep a buffer of past steps
and move both end points of the segment under consideration, so it becomes a running average again.
CORDIC solutions are linear in angle (and far more suited to helices for instance). A little known fact is that CORDIC can be used to directly rotate a 3D vector around an
arbitrary axis - well I haven't found any reference to this in the literature. It can also be made incremental (although the details are messy) to reduce cycle counts
for repeated small angle steps.
In fact its what I've been working on recently... Do prod me for proof-of-concept code in a week or two.
Wow ! You are diving deep into practical aspects of CNC. I have thought about expanding your STEP-DIR generate demo-code for circular moves.
Then I discovered Don's CNC-code which represents a (almost) running solution. So I could use this code.
If I understood right Don uses the bresenham-algorithm. You already explained that bresenham causes frequency-variation
if the X/Y-ration has certain values. Do I conclude right that this also happens at circular motions?
I know that your buissenes benezan electronics earns money by selling motion-controls and motordrivers. So I do understand that you are not sharing all code and all know how.
But I would like to ask: will you share some circular-motion-code that has constant speed and constant pulse-frequencies?
best regards
Stefan
Hi Stefan,
yes, I have to, it's my job.;) And it's also true that I can't share all code I write because I work for customers that pay me for developping products. So they own the results of my work and posting it to the public would not only upset them but would also be against the forum rules.
But of course, this doesn't mean I'm not willing to help people. The forum has helped me a lot so not to do something in return and sharing knowledge would be selfish.
Yes, but there's an easy fix. You could do the bresenham algorithms with a higher resolution (say, 16- or 256-fold) and use the lower bits (the "post decimal point digits") as phase information to reduce jitter.
The code I posted as demo for my step/dir generator already contains support for circular moves with constant velocity. Because it's a demo I was lazy and haven't coded it in a very clever way. Instead, I simply used sine, cosine and arctan functions of the "Float32Full" object which wastes two cogs, unfortunatelly.
CON resolution = 200 ' steps/mm Frapid = 6000 ' 6m/min or 100mm/s accel = 1000 ' mm/s² ramp = Frapid * 1000 / 60 / accel ' ms feedfactor = 800.0 * 60.0 ' (ticks/s) * (s/min) Pi2 = 2.0 * Pi Pi05 = 0.5 * Pi OBJ stpX: "StepDirGen" stpY: "StepDirGen" stpZ: "StepDirGen" fm : "Float32Full" VAR long lastX, lastY, lastZ PRI Helix (cx, cy, toZ, feedrate) | dz, da, r, x, y, z, a, dx, dy, time, count, dist dz:= toZ - lastZ dx:= cx - lastX dy:= cy - lastY a:= fm.FSub (CartToPolar (dx, dy), Pi) r:= fm.Fsqr (fm.FFloat (dx*dx + dy*dy)) dist:= fm.FMul (r, Pi2) r:= fm.FMul (r, fm.FFloat (resolution)) cx:= fm.FFloat (cx * resolution) cy:= fm.FFloat (cy * resolution) dist:= fm.Fsqr (fm.FAdd (fm.FMul (dist, dist), fm.FFloat (dz*dz))) count:= fm.FRound (fm.FMul (fm.FDiv (dist, fm.FFloat(feedrate)), feedfactor)) time:= fm.FFloat (count) dz:= fm.FDiv (fm.FFloat (dz * resolution), time) da:= fm.FDiv (Pi2, time) z:= fm.FFloat (lastZ * resolution) repeat count a:= fm.FAdd (a, da) x:= fm.FAdd (cx, fm.FMul (fm.Cos (a), r)) y:= fm.FAdd (cy, fm.FMul (fm.Sin (a), r)) z:= fm.FAdd (z, dz) stpX.SetPosition (fm.FRound(x)) stpY.SetPosition (fm.FRound(y)) stpZ.SetPosition (fm.FRound(z)) stpX.WaitTick lastZ:= toZ PRI CartToPolar (x, y): angle | o o:= ||x > ||y x:= fm.FFloat (x) y:= fm.FFloat (y) if o angle:= fm.Atan (fm.FDiv (y, x)) else angle:= fm.FSub (Pi05, fm.Atan (fm.FDiv (x, y))) if y<0 if x<0 o:= Pi else o:= Pi2 angle:= fm.FAdd (o, angle)The handling of floating point math is a bit complicated in spin (e.g. fm.FDiv (x, y) instead of x/y...) but the basic algorithm should be clear. "a" is the current angle and "da" is the angle step that is added each iteration. CartToPolar is used to calculate the starting angle with the arctan funtion. I you'd replace the Float32Full Sin, Cos and Atan funtions with lookup table versions it could also be done in assembler and in a single cog.