Plotting an Arc in Discrete Steps

Question

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 purpose 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

Answer 1

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/