CAM

I’m (slowly) working on some CAM-algorithms. The code is called monocam.

List of Updates/News:

To-Do

  • triangle-slicing by XZ-planes (creates segments in the clearance-plane)
  • segment-joining function (seg1 contains seg2, seg1 extends seg2)
  • segment-linking function (zigzag or zig)
    • simple (in the same order as segments created)
    • greedy (always choose nearest starting point next)
    • modified TSP
    • other graph-traversal algorithms?

Since good CAM programs (like MasterCAM, SurfCAM, or OneCNC) cost tens of thousands of dollars, I’m interested in an open source alternative. As far as I know there is no serious open source development going on - everyone seems to be waiting for someone else to make the first (big) move. I’m not very good at GUI or graphics programming, but I’m interested in the machining algorithms. An idea would be to provide a set of machining algorithms under the GPL and then hope that there are enough people interested in this so that they develop a useful GUI and graphics view of the whole thing. See also the Open Source CAM wiki page (or similar stuff at the EMC wiki here and here).

We now have a 3-axis cnc mill, so at least at first I am mostly interested in 3-axis milling toolpaths. But we might get a lathe in the future…

As a start I will be calculating and plotting things in Matlab, since doing it in OpenGL would require too much effort. I like high-level languages like C#/Python, so after initial tests in matlab I will probably implement the algorithms in C#.

See also notes on CAM systems by Julian Todd.

Input geometry

There’s a lot of academic literature on how to calculate offsets or toolpaths directly from parametric curves or surfaces. It gets mathematically advanced pretty easily, and I understand that in practice most commercial CAM systems don’t use these fancy algorithms anyway. They use much simpler curve and surface representations.

So the input geometry to a CAM algorithm should be based on a set of simple geometry primitives. I think there needs to be three types of input geometry objects:

  1. Points, defined by their (x, y, z) coordinates and used for 1D toolpaths such as drilling, countersinking, tapping, and other ‘drill-press’ like operations.
  2. Curve segments, either lines or arcs. These are used to define a 2D or 3D curve in space. Lines are simply linear segments between two points in space. Arcs need one or two more parameters to define the radius of curvature and the direction of the arc. Complex curves , like Bezier or NURBS curves need to be ‘tesselated’ into lines or arcs (or both) at some given precision before entering the toolpath algorithm.
  3. Surfaces are represented by triangles. All surfaces need to be triangulated at some finite but small precision into a set of triangles. This makes calculating 3D toolpaths fairly straightforward since essentially the algorithm deals with the tool agains one triangle (three vertices, three edges, one face) at a time.

1D Toolpaths

1D toolpaths are based on points. Typically you would specify a point e.g. where you want to drill a hole. This algorithm is very simple: (1) in the clearance plane, rapid to the (x,y) point, (2) rapid down to the feed plane, (3) feed down to the point and do the machining operation (drill, tap, peck-drill etc).

A first stupid version of the algorithm could just machine the points in the order they were given to the algorithm. A smarter version would use one of the many TSP algorithms for improving the order of the points. Solving the TSP should probably be done with a different algorithm depending on the problem size.

For small sets (<10 or so) you can calculate all routes by brute-force. For medium-sized problems a number of heuristic approaches exist (nearest neighbour, spanning trees, etc.) For really large sets some general purpose optimization algorithm is probably more suitable. David MacNab’s pygene module that implements a genetic algorithm might be a good starting point. Simulated annealing is another option. Here’s a nice C# implementation of a genetic algorithm for the traveling salesman problem.

These general purpose optimization algorithms could also be used for sorting more advanced operations, along the lines discussed here.

2D Toolpaths

2D toolpahts are based on planar two-dimensional curves. Some CAM programs treat all curves as polylines (smooth curves are approximated by many small line segments), but since all cnc machines use G2/3 moves for circular arcs, I think it makes sense to have two 2D-curve primitives: line-segment and arc-segment.

A toolpath for exactly following a given input geometry (e.g. for laser cutting) is trivial. The challenge is in creating robust offsets (an offset curve is shifted, along the curve normal, from the part by half of the cutter diameter, so that the cutter edge cuts exactly the part).

Generating ‘local’ offsets to arc or line segments is quite easy, and joining them up end-to-end is also not that hard. The problem is ‘global’ intersections or interference. All the simple papers describe how the local problem is solved, but very often just skip the problem with global intersections.

There’s a recent paper by Liu et al. on 2D offsetting of arcs and lines which uses this approach of first generating the trivial offset segments, then joining up them locally pair-wise, and then looking for the globally problematic areas.

The Voronoi diagram approach is described in Martin Held’s rather theoretical book. It seems to be a robust way of dealing with the local/global intersections. Held’s code is not open-source if I understood correctly, but there must be open-source implementations for generating Voronoi diagrams.

On a mill, the tool shape in the (x,y) plane is always a circle, so a constant offset can be applied for all planar curves, but something more advanced might be needed for lathe toolpahts when the cutter might not be symmetric (or are we always cutting with the circular tip of the tool?).

Once the offset curve is obtained, it should be fairly straightforward to create the typical simple roughing/clearing paths:

  • zig / zigzag (example from Martin Held)
    • this typically uses a ‘machining-graph’ that is generated from the outline curve of the pocket by a sweep-line algorithm. The toolpath generator then traverses this graph making sure that all edges are travelled along at least once. Some other heuristics might also be included to make the path better from a machining point of view.
  • spiral (use a ‘winding-angle sweep line’)
  • contour offset (example from Martin Held)
  • morph or blend toolpaths could be created as described by Bieterman.

Some post-processing of a 2D toolpath may include line-simplification with the Douglas-Peucker algorithm (here and here), and an arc-filter to find G2/G3 moves among many short linear segments (haven’t found a reference for that yet).

Dragomatz and Mann reviewed toolpath algorithms in 1997.

3D Toolpaths

If you believe the freesteel guys (and you probably should, they are pros on CAM algorithms), 3D toolpaths should be based strictly on triangulated surfaces only. CAD programs like to represent surfaces in parametric form, but they should be tessellated into triangles for the CAM algorithm.

This requires a 3D cutter definition. A simple notation is C(d,r) where d is the shaft diameter of the cutter, and r is the corner radius. Thus C(10,0) is a d=10 cylindical endmill, C(10,5) is a spherical or ballnose endmill, and C(10,2) is a filleted (or bullnose/toroidal) cutter (see diagram). A development of this is to include tapered cutters, but I’m not sure how common/useful those are in the cnc industry.

Roughing: Simple roughing toolpaths could be created by slicing the model with a z-plane to obtain a 2D contour at that z-value. Then use one of the 2D algorithms to clear this contour. This is possibly valid only for cylindrical cutters, so may be of less use with toroidal or ballnose cutters.

need to find a reference on how to calculate z-slice from a set of triangles! slicing a triangle with a z-plane is trivial, but you end up with a whole lot of line segments or points probably in an un-ordered list. How would one then order these points and lines so that they can be used as input for a 2D algorithm?

Finishing: A simple approach is to create a 2D pattern in the clearance plane using one of the 2D algorithms (like zigzag), then sample points along this toolpath at some (high) sample rate, and for each (x,y) point use a ‘drop-cutter’ algorithm to drop down the cutter so it touches the model. See some notes on determining the machining sample rate. Besides the freesteel blog, some papers where this approach is discussed are: Chuang2004 and Chuang2002.

Drop-cutter takes an initial X, Y position for the tool and drops down the tool along the z-axis until it hits the model. As the model is triangulated there are three kinds of objects the tool could hit: a vertex (one of three corner points of a triangle), an edge (one of the three edges of the triangle), or the facet (the area in-between the edges). The algorithm simply mathematically calculates the height the tool would be at when touching each of these 13 objects (three vertices, three edges, one facet), and then chooses the highest z-value as the position of the tool. Some notes on the vertex test, edge test, and facet test.

Adaptive toolpaths

An open source CAM program with the classic toolpath types described above would already be a great start. A recent development is adaptive toolpaths where the CAM program models the remaining stock as the toolpath is created.

A 2D stock model could simply be a pixelated version of the part geometry where a ‘1′ pixel means there is material left, and ‘0′ means the pixel has been cut. The toolpath algorithm could then be a sort of ‘agent’ program (think about an automatic vacuum cleaner robot) that has an overall mission (clear all pixels in a given area), some means to move (take an 1mm step in one of 360 different directions), but it’s path is subject to constraints (don’t bump in to the part, don’t remove too much material per step). I think a first version of this idea should strive for creating circular spiral-type toolpaths that emerge from some simple agent rules.

The Freesteel dudes take this idea one step further and model the whole 3D stock as a z-map. That allows them not only to create adaptive 2D paths, but also choose an optimal depth of cut for each roughing level.

In any case, to save memory and cpu-time, the stock model probably needs to be adaptive, so that cleared or untouched areas of the model are represented at low resolution, and the parts that are being cut are represented at high resolution.

This can later also be used for rest-milling, i.e. after a roughing operation with some large diameter tool the algorithm ‘knows’ where there is still material left, and can choose a smaller tool and calculate the toolpaths to remove this material.

Gui, OpenGL, etc.

In addition to the toolpath algorithms, a lot of stuff is required to make up a complete CAM system:

  • A 3D OpenGL view of the part geometry and toolpaths
    • should allow creating, deleting, and editing geometry
    • selecting geometry for input to CAM algorithm
  • A tool library (with associated machining parameters for each tool)
  • geometry import (DXF, IGES, etc)
  • A machining operations manager (e.g. rough, finish, drill, tap, etc.)
  • post processors that turn the native toolpath format into something the machine controller understands (usually G-code).
  • A machining simulator to verify the created toolpath. The most common models seem to be z-buffer or ‘match-stick’ models, see for example here.
    • this should include an ability to monitor the material removal rate while running the toolpath. this will be nice for developing adaptive toolpaths that aim to keep the material removal rate constant.