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.