The algorithm was initially implemented in fall of 2023 as part of my "png2rml" commandline PCB-milling toolpath generator for the Roland MDX-50, for situations involving excessively large boards or excessively low patience, e.g. the PCB for a custom mechanical keyboard.
Occassionly I would advertise the algorithm to students who ask for my help milling, and recently I was told that it has caught the attention of Prof. Neil Gershenfeld, who requested that I document the algorithm. I gladly obliged and sepearated the relavant parts from "png2rml" and put it onto this page which you are currently viewing, where each step is (hopefully) explained clearly.
Both the general idea and the steps involved are very simple. Everything below is implemented in plain old JavaScript with no dependencies. When you update the test image in the demo section near the top of this page, the illustrations below will also update accordingly.
We start with a binary image, where traces and pads (things to be kept intact) are white, and things to be milled away are black. This is the standard format for mods, and can easily procured using ECAD softwares.
First step would be to sepearate each trace from one another. For this, I scan every pixel, and once I encounter a white pixel, I pick a new color, and flood-fill starting from that pixel. In the end, I get an image where each trace is colored a different color. Of course, the actual colors doesn't matter; in the code, I just have different ID's for each trace.
The code below uses a basic stack-based flood-fill, surely it could be improved for efficiency...
Consider how closely related distance transform is to Voronoi diagrams. When thinking of Voronoi diagrams, one would usually imagine a bunch of dots inside a bunch of cells, squished together in some organic fashion resembling roe or passion fruit. But the dots (called "sites") doesn't necessarily need to be dots, they can be more complicated shapes as well. So instead of finding which dot each pixel is closest to, find which shape each pixel is closest to. Now this sounds suspiciously like distance transform, which basically computes the distance from each pixel to the closest shape.
The only catch is that your run-of-the-mill distance transform algorithm only gives you, well, the distance, and not actually which nearby shape caused this distance reading. The Jump Flood Algorithm (JFA) does give you that information. In fact, I've previously implemented it with WebGL shaders here. However, it is mainly suitable for GPU, so for this simple PCB-milling stuff I don't want to involve in the headache of encoding floating-point textures etc.
After carefully inspecting the inner workings of my favorite CPU distance transform algorithm in linear-time (Meijster's Distance), I realized that it could easily be modified such that the ID of the initial shape can be carried over in the computation. In other words I "poison" the inital distance reading (0) with the shape ID. And when the distance is propogated that info is propogated along, so in the end, I know where each reading came from.
The final step is to trace the raster image to obtain the toolpath. I've been tracing binary images for a long time using my implementation of the same paper which OpenCV's "findCountours" function implements. But what about colorful images? Here's where I get a bit lazy. I just sepearate each color into a different binary image. Then I trace every binary image one by one and combine the results. So it takes longer the more traces you have... Luckily the "findCountours" algorithm itself is linear. You can read my JS implementation here.
I believe with an improved algorithm, one can trace multiple colors simultaneously in one pass with some modifications not unlike the modifications I did in the previous section to distance trasnform...
Now that we have a bunch of contours, the original version of this feature in "png2rml" stops here, and goes on directly to toolpath generation. However, there can be one additional optimization. Every single edge is actually drawn twice, because they're shared by adjacent Voronoi cells (except the ones on the border of course). So it would take about twice as long as is really necessary to mill (though it is already so fast that twice as slow isn't that slow anyways).
For this special web-demo edition, I added this final optimization. It is very simple: I check the orientation of every single edge, and drop it if it is on the wrong half of the clock face. This works because for two adjacent cells, the shared edge will have opposite orientation. Of course, I keep a "run" array so that the contours are not shattered into tiny pieces and instead stick together for as long as posible.