CAM

I'm (slowly) working on some CAM-algorithms. I did some early tests in matlab. Then in C# where the code was called monocam. Currently the projects are in C++ with python bindings. The code is on github.com/aewallin and there are debian packages for ubuntu in a PPA at ppa:anders-e-e-wallin/cam.

Since good(?) CAM programs (like MasterCAM, SurfCAM, or OneCNC) cost tens of thousands of euros/dollars, I'm interested in an open source alternative. I'm trying to provide a set of machining algorithms under the GPL and then I hope that there are enough people interested in this so that they develop a useful GUI and post-processors etc. FreeCAD looks promising (but there are GPL-problems with OpenCascade). See also the Open Source CAM wiki page (or similar stuff at the EMC wiki here and here).

See also notes on CAM systems and Intelligent machining algorithms by Julian Todd. Dragomatz and Mann reviewed toolpath algorithms in 1997. There's also a 2010 review paper by Lasemi et al.

OpenVoronoi for 2D toolpaths

OpenVoronoi is my 2D Voronoi diagram algorithm. It's a C++ library (about 6k lines) with python bindings. I'm using the incremental topology-oriented approach. The diagram is stored as a boost-graph-library graph, and there are functions for incrementally inserting point or line-segment sites into the diagram.

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. Checking for global interference among N offsets requires N^2 time. There's a 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. Since voronoi cells/faces subdivide the plane into areas where the offset is trivial, the global interference problem is avoided.

Once the offset curve is obtained, it should be fairly straightforward to create the typical roughing/clearing paths. There are a number of clearing strategies: zig / zigzag (examplefrom Martin Held), contour offset (example from Martin Held). morph or blend toolpaths could be created as described by Bieterman. Spiral.
Another use for the VD is the medial axis. V-carving toolpaths position the cutter along the medial axis at a Z-depth corresponding to the clerance-disk radius.

OpenVoronoi now handles points and line-segments as input. An improvement would be to support circular arcs also. There are many issues with numerical stability.

There is a gallery of sample output from OpenVoronoi on picasa https://picasaweb.google.com/106188605401091280402/OpenVoronoiExamples

OpenCAMLib for 3D toolpaths

OpenCAMLib is my 3D CAM-library. It is a C++ library with python bindings. The main functionality it provides is axial and radial cutter-projection algorithms against polyhedral (triangulated) surfaces.

If you believe the freesteel guys (and you probably should, they are pros on CAM algorithms. AFAIK they make the HSM-plugin for Mastercam, sold by Cimco), 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 also 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.

Opencamlib currently has two algorithms for cutter location: drop-cutter (axial cutter projection) and push-cutter (radial cutter projection). 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 calculates the height the tool would be at when touching each of these 7 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. Push-cutter is similar, but holds the cutter at a constant Z-coordinate, and pushes it into contact with the model along either the X or Y axis. An interval corresponding to the legal cutter locations along the X (or Y) axis is returned. These intervals (or fibers(?)) are used to create an area-model (weave?) from which  a waterline toolpath can be extracted.

Roughing: Roughing toolpaths could be created by creating a waterline (constant-z) contour of the model, and clearing the appropriate area with a pocketing toolpath. The current Waterline implementation in opencamlib is problematic and requires a rewrite!

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.

Shallow/steep strategy: This is not implemented yet. The idea is to use a 'zigzag' style finishing operation on shallow areas of the model, and a waterline or constant-step-over operation on steep areas of the model. Detecting the areas could be done via a triangulated cutter-location surface, where one detects and 'condenses' together areas where the triangle-normal is in either a shallow or steep range. There should probably be some overlap (hysteresis in the condensation/fusing step) so that the border between shallow and steep is visited.

Constant step-over: This is not implemented yet. One could create an adaptively refined triangulated cutter-location surface, and then calculate geodesics on this surface.

Pencil milling: This is not implemented yet. This is based on detecting abrupt changes in the contact-normal at the cutter-contact point. Once these areas are identified a reasonably smooth pencil-path must somehow be laid down.

Adaptive toolpaths. Not implemented yet. 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 ("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.

Freesteel takes 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. Possibly a quad-tree or a triangulation in 2D, or an adaptive z-map or an octree in 3D. 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.

Cutsim for cutting simulation

I have explored various options for cutting simulation. My code stores a scalar field in an octree, and uses a contouring algorithm (such as Marching Cubes) to produce the stock surface.

Joseph Coffland has independently made great progress with this, so check his OpenSCAM project at http://openscam.com/

CAD

There are a number of interesting open-source CAD-developments.

• LibreCAD, 2D, for Windows/Mac/Linux, a fork of QCad CE. Uses Qt.
• freecad for Windows/Mac/Linux. C++ with python bindings. Uses OpenCascade, Coin3D, and Qt. License is a mix of GPL and LGPL.
• heekscad for Windows/Linux (mac?). C++. Uses OpenCascade and WxWidgets. New BSD License.
• narocad, in C#/.NET for Windows. Uses OpenCascade. GPL.
• See also the LinuxCNC wiki page on CAM: http://wiki.linuxcnc.org/cgi-bin/wiki.pl?Cam