I decided to work on automatically converting the more conventional PCB designs that my PCB software produces into ones suitable for a CNC router.

What I want to do is not produce any unconnected copper on the board, which happens with the conventional approach of simply outlining all of the traces.

I decided to do the work with the PCB as an image file rather than vector data. The reason for that is because I couldn't really think of a way to do it as vector data that wouldn't have so many edge cases that I'd never figure it out. While doing it as an image creates less than perfect results, It's much easier, and I note that there's only so perfectly that the board is going to be carved anyway. The carving bit is going to take out a 20 mill wide chunk anywhere I put it down. So if I process the image at a 1 mill resolution, the inaccuracy of the process should be drowned out by the inaccuracy of the carving itself.

So, step one was to convert the PCB to an image. For this I simply used ghostscript to convert the postscript output that my PCB editor is already capable of to an image.

I then load that image, and flood-fill a different color into each black area, ending up with this:

I then use a modified flood fill algorithm, which pays attention to how far the color has flowed from its source, to simultaneously flood all of the colors into the white area, until no more white area remains. Since I had to create a bunch of image output to see how this was working, I made a video to show it happening.

When it's done, we have this:

I then go over the image and change every pixel that is of one color but adjacent to a pixel of another color to black. This creates a thin line which represents where the carving needs to occur.

To turn this line into gcode, I simply find a black pixel, and starting there, I turn all of the black pixels within 10 pixels to white, and take note of which of them was the furthest away. I then move to that furthest away point, and repeat. To make the path chosen more sensible, it gives bonus points to shorter paths when finding a new place to start, and paths which continue along a color which it was already carving beside.

So here's the final image:

To test the generated gcode, I used the laser to burn it to a piece of cardboard:

So I guess this problem is solved. The laser movement was a bit jerky due to the slightly jerky path this process creates, but the machine has to carve it much slower anyway so I doubt I'll even notice.