Plotting an Arc in Discrete Steps

Good afternoon,

Background

My question relates to the plotting of an arbitrary arc in space using discrete steps. It is unique, however, in that I am not drawing to a canvas in the typical sense. The firmware I am designing is for a gcode interpreter for a CNC mill that will translate commands into stepper motor movements. Now, I have already found a similar question on this very site, but the methodology suggested (Bresenham's Algorithm) appears to be incompatable for moving an object in space, as it only relies on the calculation of one octant of a circle which is then mirrored about the remaining axes of symmetry. Furthermore, the prescribed method of calculation an arc between two arbitrary angles relies on trigonometry (I am implementing on a microcontroller and would like to avoid costly trig functions, if possible) and simply not taking the steps that are out of the range. Finally, the algorithm only is designed to work in one rotational direction (e.g. counterclockwise).

Question

So, on to the actual question: Does anyone know of a general-purpose algorithm that can be used to "draw" an arbitrary arc in discrete steps while still giving respect to angular direction (CW / CCW)? The final implementation will be done in C, but the language for the purp开发者_StackOverflow中文版ose of the question is irrelevant.

Thank you in advance.

References

S.O post on drawing a simple circle using Bresenham's Algorithm:

"Drawing" an arc in discrete x-y steps

Wiki page describing Bresenham's Algorithm for a circle

http://en.wikipedia.org/wiki/Midpoint_circle_algorithm

Gcode instructions to be implemented (see. G2 and G3)

http://linuxcnc.org/docs/html/gcode.html

You can resolve this problem accurately and quickly for an arbitrary rational curve by converting it to a rational Bezier curve, then applying de Casteljau's algorithm. This can easily be done for conics like circles and hyperbolas:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/NURBS/RB-conics.html

Once you have a rational Bezier curve, to resample the curve into discrete steps, you should use de Casteljau's algorithm . This algorithm uses dynamic programming, and is very fast and numerically robust. If you have not heard of it before, I would really recommend learning about it since it is a fairly clever little algorithm:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/de-casteljau.html

There are several ways that you can then use de Casteljau's algorithm to get a discrete sampling of your curve. First, you can just naively apply it to evaluate the curve along its parameter space at uniform increments. If the increments need to be evenly spaced, you have to change your interpolation coordinates into units of arc length:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/curves/continuity.html#Arc-Length-Parameterization

A refinement of this technique is to instead convert into a chord length parameterization which approaches the arc length parameterization over time:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/INT-APP/PARA-chord-length.html

Finally, if you need a lot of points on the curve, you can just apply de Casteljau's algorithm as a corner cutting procedure to refine the initial control point vector into a limit polygon that arbitrarily approximates your desired curve up to some user specified tolerance:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/bezier-sub.html

These notes were taken from Prof. C.K. Shene's course notes, which is a great resource for learning about splines and subdivision surfaces:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/

this is a silly idea but it might just work
compute circles of every possible radius on computer and hold this information in the microcotroller memory.
let's say you have circles 1 to 1000 pixels in radius. that's 1000*(1000+1)/2*2*pi=3 million points on all circles
for each point you actually need only the offset from the previous point, there are 8 cases, these can be encoded in 3 bits
depending on how many bits you microcontroller has, say 8/16 bits, have 2pixels/byte or 5pixels/word
you'll need 1.5MB of memory on a 8bit micro, 1.2MB on a 16bit micro.
you could store circles with the radius k pixel increments, and use only 1.5MB/k memory.
another optimization would be to model the circle as a polygon with many sides, you don't hold the offset to the previous point, but to a point two steps away or more, and interpolate somehow the pixels in between.
if you hold offset for pixels two steps away you have 16 cases, encoded on 4 bits => 3/2million points => 750KBytes
if you hold pixels every s steps you have s*8 possibilities which can be encoded in 3+log2(s) bits.
LE:
pixels every 32steps/8mils => 10inch radius circle 10*4000*2*pi/32steps*1byte=7.85KB, pixels every 128steps/32mils => 10inch radius circle 10*4000*2*pi/128*10bits=19634Kbits=2.4KB
LLE: you actually don't have s*8 possibilities, there are fewer than that because the circle zoomed in is a straight line
it all comes down to how well you can pack the data, or use external memory
another optimization: store only quadrants or octants and figure the rest from symmetry LLLE: every