Building an arc in discrete steps

Question

Good afternoon,

Background
My question is related to the construction of an arbitrary arc in space using discrete steps. However, it is unique in that I do not paint on canvas in the typical sense. The firmware that I am developing is intended for the gcode interpreter for a CNC machine, which will translate commands into stepper motors. Now I have already found a similar question on this site itself, but the proposed methodology (Breshenem algorithm) seems incompatible for moving an object in space, since it relies only on calculating one octane of a circle, which is then mirrored about the other axes of symmetry. In addition, the prescribed method for calculating the arc between two arbitrary angles depends on trigonometry (I implement it on a microcontroller and would like to avoid expensive trigger functions, if possible) and simply do not take steps that are out of range. Finally, the algorithm is designed only to work in one direction of rotation (for example, counterclockwise).

Question
So, to the question: does anyone know of a universal algorithm that can be used to "draw" an arbitrary arc in discrete steps, while maintaining the angular relation (CW / CCW)? The final implementation will be done in C, but the language is not relevant for the purpose of the question.

Thanks in advance.

References
SO post when drawing a simple circle using the Breshenem algorithm:
"Drawing" an arc in discrete steps xy

Wiki page describing the Breshenem algorithm for the 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 solve this problem accurately and quickly for an arbitrary rational curve, translating it into a rational Bezier curve, and then applying the Castellau algorithm. This is easy to do for conics such as 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 redo the curve into discrete steps, you should use the Castellau algorithm. This algorithm uses dynamic programming and is very fast and numerically reliable. If you have not heard about this before, I would recommend learning about it, since this is a pretty smart algorithm:

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

There are several ways you can use the Castellau algorithm to obtain a discrete sample of your curve. Firstly, you can simply naively apply it to evaluate a curve along your parameter space with uniform increments. If the increments should be evenly distributed, you need to change the interpolation coordinates to units of arc length:

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

The refinement of this method is to instead transform into a parameterization of the chord length, which approaches the parameterization of the length of the arc 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 simply apply the de Castellau algorithm as an angular cutting procedure to improve the vector of the starting control point in a limited polygon, which arbitrarily approximately matches your desired curve to a user-defined tolerance:

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

These notes were taken from Professor K.K. Schöne course knowledge, which is an excellent resource for exploring splines and partition surfaces:

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

Answer 2

This is a dumb idea, but it can just work to calculate the circles of any possible radius on a computer and store this information in the memory of the microcoller.
let's say you have circles from 1 to 1000 pixels in radius. that 1000 * (1000 + 1) / 2 * 2 * pi = 3 million points on all circles
for each point you really only need an offset from the previous point, there are 8 cases, they can be encoded in 3 bits
depending on how many bits you have a microcontroller, say 8/16 bit, have 2 pixels / byte or 5 pixels / word
you will need 1.5 MB of memory on an 8-bit micro, 1.2 MB on a 16-bit chip.
you can store circles in increments of pixels of radius k and use only 1.5 MB / k memory.
Another optimization will be to simulate a circle as a polygon with many sides, you do not hold the offset to the previous point, but to a point two steps or more and somehow interpolate the pixels between them.
if you hold the offset for pixels in two steps, you have 16 cases encoded in 4 bits => 3/2 million dots => 750 KB
if you hold pixels at every step, you have s * 8 possibilities that can be encoded in bits 3 + log2 (s).
LE:
pixels every 32 steps / 8mils => 10-inch radius circle 10 * 4000 * 2 * pi / 32steps * 1byte = 7.85KB, pixels every 128 steps / 32mils => 10inch radius circle 10 * 4000 * 2 * pi / 128 * 10bits = 19634Kbits = 2.4KB
LLE: you really don't have s * 8 features, there are fewer of them because the circle enlarged in a straight line comes down to how well you can pack data or use external memory
another optimization: store only quadrants or octants and figure out the rest from LLLE symmetry : each