Before anything can be milled, the mill needs to know how to mill it. This is done through a format know as G-Code, which describes everything the mill does, such as moving around, tuning the spindle on and off, and so on. A typical snippet might look something like this:

(Op: bldc-Edge_Cuts.gbr)
(Tool: 60° V Precision)
G0 Z0.5
M06 T1 (60° V Precision)
G0 Z0.5
G0 X-1.7744 Y14.0416
G1 Z-0.05 F100
G1 F400
G1 X-1.7844 Y14.0356
G1 X-1.7882 Y14.0333
G1 X-1.7931 Y14.0299
G1 X-1.8049 Y14.0211
G1 X-1.8084 Y14.0183
G1 X-1.8123 Y14.0149
G1 X-1.8232 Y14.005
G1 X-1.8265 Y14.0019
G1 X-1.8283 Y14
G1 X-1.9279 Y14
G0 Z0.5

I won't go into full detail here, but the G1 and G0 commands are specifying coordinates to move to. While it is possible to do some math and write these out by hand, it quickly becomes very tedious.

This is where a Computer Aided Manufacturing (CAM) program comes in: It will take some model file as input, and generate the G-Code to mill it. For milling circuit boards, the model file would be your gerbers. There are a few PCB CAM tools out there, but none of them really did what I wanted. Many are either difficult to use, are limited in what they do, and none seem to be able to properly clear off all the copper.

It is common when when milling PCBs to isolate each trace by doing a perimeter around each trace. This gets each trace separated from the rest of the copper, but it also leaves a bunch of copper where there are no traces. This extra copper becomes easy to bridge solder to, so I tend to peel it off anyway in tight spaces. It would be much easier if the mill could just mill it all way.

So, I set out to write my own. How hard could it be?

Trying things out

My first goal was to play around and see how things would turn out. For this, I turned to Python, and after a bit of searching, the Shapely geometry library. This would make it easy to try things out, without having to deal with memory management or higher-level architecture.

The first setep was to figure out the copper that needs to be removed. This is a simple difference betweent the board outline and the traces. To remove this area, the cutting bit will need to travel over it all at lead once. I decided to do this recursively: The algorithm would try to remove one pass of material, figure out what was left, then call itself again. This started by offsetting the area to remove inwards by the tool's radius each recursion, eventually making its way to the center.

This does a pretty decent job of getting rid of the bulk of the copper, but there are still bits remaining that the endmill could still get. For example, there is often a sliver of material left at the center, thinner than the width of the bit. This results in the inward offset giving no results: it would have offset to past the center of the sliver.

In order to catch these, and a few other cases, there needs to be a failover for in case the offset operation gives no results. For areas not near any traces, an easy way is it trace the outline of the uncut area. Since there was not enough space for the inward offset, it is guaranteed to be thin enough to be taken off in one pass. However, this approach ends up cutting outside the uncut area, so it may cut nearby traces. That's not good. The approach to fix this was to try and offset the traces outwards where the uncut area is, to cut along the trace. This was a bit tricky to get right. What I ended up with was to first offset the entire trace outwards by the radius of the tool, then intersect the resulting boundary with the uncut area. This generates a path that will cut the uncut area, but may still intersect with some traces. To resolve this, a rather brute force approach was taken: Take the offset traces, and chop of anything that overlaps the generated paths.

I'm pretty sure that this gets all, or at least the vast majority of, the copper to cut. The resulting Python is shown below:

def clear_polygons(
        # The copper area to remove
        polygons: MultiPolygon,
        
        # Areas that should be not be cut, such as traces
        avoid: MultiPolygon,
        
        # The cutting tool being used
        tool: Dict,
):
    paths = []

    tool_radius = tool['diameter'] / 2

    # Used for determining if a cut would cut the avoid area. 
    # Make it slightly smaller than it should be so cuts exactly
    # the tool radius away don't get removed.
    expanded_avoid = avoid.buffer(tool_radius * 0.99)

    if not isinstance(polygons, MultiPolygon):
        polygons = MultiPolygon([polygons])

    for outline in polygons:
        # Offset inwards the area to cut
        path = outline.buffer(-tool_radius)

        # The offset worked
        if not path.is_empty:
            if isinstance(path, (Polygon, MultiPolygon)):
                path = path.boundary

            # Determine what still needs to be cut ...
            cut = path.buffer(tool_radius)
            remaining = outline.difference(cut)

            if isinstance(remaining, Polygon):
                remaining = MultiPolygon([remaining])

            # ... and recurse again to cut it
            next_paths = clear_polygons(remaining, avoid, tool)

            paths.append(path)
            paths += next_paths

        # The offset failed; the area is narrower than the tool's diameter
        elif not outline.is_empty:
        
            # Figure out if cutting the boundary of the remaining area would cut too much
            local_path = unary_union([outline.exterior] + list(outline.interiors))
            cut = local_path.buffer(tool_radius)
            if not cut.overlaps(avoid):
                cut = local_path.buffer(tool_radius)
                useful_cut = cut.intersection(outline)
                paths.append(local_path)
                    
            # Otherwise, we need to run the tool along the avoid area in the cut area
            else:
                intersections = cut.intersection(avoid.boundary)
                if isinstance(intersections, LineString):
                    local_path = intersections.parallel_offset(tool_radius, 'left')
                elif isinstance(intersections, MultiLineString):
                    local_path = []
                    for intersection in intersections:
                        local_path.append(intersection.parallel_offset(tool_radius, 'left'))
                    local_path = unary_union(local_path)

                if isinstance(local_path, LineString):
                    local_path = MultiLineString([local_path])

                local_path = local_path.difference(expanded_avoid)

                expanded_outline = outline.buffer(tool_radius)
                local_path = local_path.intersection(expanded_outline)

                cut = local_path.buffer(tool_radius)
                useful_cut = cut.intersection(outline)

                if useful_cut.area > tool['min_cut_area']:
                    if isinstance(local_path, GeometryCollection):
                        for g in local_path:
                            paths.append(g)
                    else:
                        paths.append(local_path)

    return paths

Just under 100 lines. Not bad!

Now that this works for one tool, what's left is to make it work for multiple tools. Doing this was relatively simple: We can cut what we can with the largest, figure out what's left, cut that with the 2nd largest tool, and repeat.

A GUI

Now that the basic algorithm works, there needs to be an easy way to use it, manage tools, and so on. Since I had something going in Python, I first tried to get something going with PyQT, since it seemed to most cross platform and eays to use.

However, QT is very object-oriented, and I quickly found myself swimming in a pool of objects, all calling and accessing each other's fields with no regard. What really set it off though, was the Qt data handler for lists. In order to have a Qt list reflect a custom storage backing, you need to extend one of Qt's classes to provide you're own methods for accessing elements of the list, getting the size, etc. However, these all have to match each other, and if they don't, you get subtle bugs that are very difficult to track down. Since I have tended to work in Rust recently, where these kinds of issues are typically just not there, I found this rather annoying and untenable.

Since I liked Rust, and wanted to try out some of the new GUI libraries, I decided to give it a go. After doing a bit of research and poking around at the options, I eventually settled on Druid. It seemed to be the most mature, and had the features I needed: a canvas to draw what's being cut, cross platform, and a good number of widgets.

However, there are no good Rust geometry libraries like Shapely. Since I didn't want to write my own just yet, I decided to keep the python code, and bridge the gap with PyO3. PyO3 lets you call into python code form Rust relatively easily, and it worked great for my use. I set up a separate worker thread that handles the Python runtime and calling into the Python functions, and communicates with the GUI through a druid AppDelegate and some channels.

This worked well. I quickly got a basic GUI going to manage a list of tools, their properties, and load and cut PCBs.

However, taking a step back, it seems kind of backwards to implement the GUI in a compiled systems language list Rust, and do all the heavy math in an interpreted language like Python. Granted, all of Shapely's operations are written in C, so the speed is not too bad, it seemed like a good step to try and get more of it in Rust. As mentioned before, there are no good geometry libraries in Rust, but I did come accross the Clipper C++ library. I briefly toyed with the idea of rewriting it in Rust (how hard can it be?), but I eventually settled on calling into the C++ code directly with bindgen. However, Clipper uses C++'s std::vector in its interface quite a bit, and bindgen doesn't know what to do with it. I tried using cxx instead of bindgen, since it claims to support translating between Rust and C++ vectors. I quickly found out, though, that it doesn't support the nested vectors that Clipper needs. So, I went back to bindgen and did it the manually: by writing a C interface for bindgen. This includes the least common deminator for a vector, just a pointer and a length, with C functions for allocating and deallocating these vectors, and for calling into Clipper while translating to C++ vectors and back. The Rust side includes ways to copy to/from the C "vectors", and provides a safe API. This is now found in clipper-rs.

Now that I have a good geometry library in Rust, I went ahead and ported the Python cutting algorithms to Rust. This went pretty smoothly, and even does away with a lot of the manual type checks (isinstance) from the Python version:

fn clear_polygons(
    polygons: &MultiPolygon,
    avoid: &MultiPolygon,
    tool: &ToolSettings,
    i: usize,
) -> MultiLineString {
    let mut paths = MultiLineString {
        linestrings: vector![],
    };

    let tool_radius = tool.diameter / 2.0;

    let expanded_avoid = avoid.clone().offset(tool_radius * 0.90);

    for outline in polygons.polygons.iter() {
        if outline.area() > tool.min_cut_area {
            let path = outline.clone().offset(-tool_radius);

            if !path.is_empty() {
                let path = if i > 0 {
                    path.offset(tool_radius * tool_radius)
                } else {
                    path
                };

                let path = path.into_boundary();

                let cut = path.clone().offset(tool_radius);

                let remaining =
                    difference(vec![outline as &dyn Geometry], vec![&cut as &dyn Geometry]);

                let next_paths = clear_polygons(&remaining, avoid, tool, i + 1);

                paths.append(path);
                paths.append(next_paths);
            } else {
                let local_path = outline.clone().into_boundary();

                let cut = local_path.clone().offset(tool_radius);

                let avoid_boundary = avoid.clone().into_boundary();

                let (cut_avoid, _): (MultiLineString, MultiPolygon) = intersection(
                    vec![&avoid_boundary as &dyn Geometry],
                    vec![&cut as &dyn Geometry],
                );

                if cut_avoid.is_empty() {
                    let useful_cut: MultiPolygon =
                        intersection(vec![&cut as &dyn Geometry], vec![outline as &dyn Geometry]);

                    if useful_cut.area() > tool.min_cut_area {
                        paths.append(local_path);
                    }
                } else {
                    let local_path = cut_avoid.offset(tool_radius).into_boundary();

                    let (local_path, _): (MultiLineString, MultiPolygon) = difference(
                        vec![&local_path as &dyn Geometry],
                        vec![&expanded_avoid as &dyn Geometry],
                    );

                    let expanded_outline = outline.clone().offset(tool_radius);

                    let (local_path, _): (MultiLineString, MultiPolygon) = intersection(
                        vec![&local_path as &dyn Geometry],
                        vec![&expanded_outline as &dyn Geometry],
                    );

                    let cut = local_path.clone().offset(tool_radius);

                    let useful_cut: MultiPolygon =
                        intersection(vec![&cut as &dyn Geometry], vec![outline as &dyn Geometry]);

                    if useful_cut.area() > tool.min_cut_area {
                        paths.append(local_path);
                    }
                }
            }
        }
    }

    paths
}

A few features got added along the way, but I'd say that is a pretty clean translation.

Now, the whole thing works pretty well. The gerber loading is still python, but it's on the to-do list to convert to Rust. I'm still adding features here and there that makes it more generally useful, such as SVG support.