Calculate n-dimensional arc path

Question

I'm implementing a driver for a CNC mill, and I'm having trouble implementing the G-code arc commands.

I have found several implementations of the midpoint circle algorithm, but it is not really usable as-is.

The problem with the midpoint circle algo as I found it, is that it is 2D and draws all the octants at the same time, while I need sequential steps through a 3D path, given by the start, end and center points.

I found a nice multidimensional equivalent of Bresenham’s line drawing algo using floating point operations. Maybe a similar thing exists for drawing an arc?

I might be able to bend this algo to my will using a lot of thinking and experimenting, but since drawing an arc is not an unsolved problem, and CNC machines have been made before, I wonder if an elegant solution already exists?

Answer 1

Well on CNC there is usually more than just 2D as there are also speeds, tool angles more than one actuator per axis kinematics etc... For this purpose I usually use parametric cubics with parameter t=<0.0,1.0>. So I convert the path into set of cubic curves which are easily evaluable in any dimensionality. After this step you got 3 usual ways of rasterization:

1. constant dt step

   parametric cubics are usually nonlinear so in order to move to another pixel (or whatever) you need to increase parameter t with smaller step than your resolution is something like:

   dt < 1.0 / curve_length  
   

   the less dt is the better chances are you will not miss a pixel but of coarse will have many more duplicate positions.

2. search next dt step

   using binary search you can find what is the next t so the distance to current position is single pixel. This is much more precise but also slower up to a point...

3. convert to lines

   you can sample your cubic curve into set of lines (how many depends on size of the curve) and rasterize lines as usuall using DDA or Bresenham. This is simplest but the result will not be exactly a curve.

Cubics are like this:

P(t) = a0 + a1*t + a2*t^2 + a3*t^3
t = <0.0,1.0>

where P(t) is position and a0,a1,a2,a3 are coefficients in for m of vectors where each axis has own scalar coefficient.

See How can i produce multi point linear interpolation? and the sublinks on how to use/compute them.

Anyway if you insist on arc interpolation assuming circular arc:

P(t) = ( Rotation_matrix(t) * (P0 - Pcenter) ) + Pcenter
t = <0.0,2*PI>

Where Rotation_matrix rotates your point around (0,0,0,...,0) by t [rad] in the curve direction and P0 is start point and Pcenter is center of the arc.

In case of non axis aligned rotation you can use Rodrigues_rotation_formula instead.

However using homogenous transform matrices is your best option in ND you just scale up the matrix size:

• How to use 4d rotors

Answer 2

My dxftools python package used for processing DXF files for a not very smart 2D cutter has a function to split an arc into line segments in 2D. You could use this code and then use 3D coordinate tranformations to arbitrarily place this in 3D space. Examples of coordinate transforms can be found in my py-stl package.

Answer 3

In LinuxCNC, position generation is separated from step generation. In the position generating loop, the system tracks the distance it has already moved along the current primitive (line or helix) and uses a simple formula to get the location that is distance D along that primitive. (Typically, this is done once per millisecond). This position can be used in different ways depending on whether you have servos, hardware step generation, or software step generation.

In a software step generation system, the difference between the old commanded position and the new commanded position is determined along each axis, and this is used to update the rates of a digital waveform generator using the direct digital synthesis method (DDS). Then, at a higher rate (typically every 20-50µs), the DDS determines for each axis whether a step should be generated at that time.

This is a different design than you are describing, but it is a more flexible one. For instance, by separating position generation from step generation, you can revise the blending algorithm in your position generation code without revising step generation; and you can replace software step generation with hardware step generation or servo control with algorithms like PID.

In your design, you can approximate the method I describe above by simply dicing your helical arc into line segments as described by Roland, and using those as inputs into your step generation code which understands only lines. In a sense, this is not too different from what LinuxCNC does, except that the curve primitive becomes sampled according to distance instead of according to time.