I have the greatest respect for the Visolate program, currently available at GitHub. It produces Voronoi Isolations of PCB traces enabling PCBs to be produced on a CNC mill. The milled paths are centralised in the available space thereby maximising current carrying capacity and allowing a single milling pass to separate two traces. However Visolate was initially a research project and unsupported for a while. As that time, I started to develop an alternative, based on a Cellular Automata approach, which also met my needs by performing some optimisation of the cutting paths (in order to reduce milling time) and producing a (likewise optimised) list of drill points as a G-code file. As this program is based on a Cellular Automaton, rather than a Voronoi approach, I have always called it Cisolate (although actually it may just be a different way of producing Voronoi diagrams). Cisolate is also available on GitHub. Here is an example of some of Cisolate’s output for the test PCB used by Visolate:
On the left is the board with the isolation paths identified in green. In the middle is the automatically identified set of drill positions and an approximation to the optimum order in which to drill them. On the right is again the isolation paths, but in red are the unnecessary transits (where the mill lifts off the board and moves to a new location). The quality of the optimisation is indicated by the limited number of red paths.
On this particular example, all processing was complete in 10 seconds on a not especially recent machine, although note that the code operates in parallel using multiple threads (configurable) and can therefore use all available processors. Significantly more complex boards are still analysed in minutes, with the majority of the work being in the optimisations.
While having no wish to criticise Visolate, I think Cisolate offers the following advantages
1. Cisolate uses native Java libraries, so there is no need to install anything beyond the JRE (This was a design intent)
2. Cisolate operates purely from an image, so can be used in various situations where a Gerber file is not available, including potentially repair after scanning a PCB image. This is paired with the weakness that it cannot directly use Gerber files as input, but other programs will convert Gerber files to images.
3. Cisolate undertakes optimisation of the G-code so that it produces far fewer transits (for reduced manufacture time and less wear-and-tear) and shorter code.
4. Cisolate automatically produces a G-Code Drill file (as well as a G-Code mill file and/or an etch image). Likewise there is a disadvantage that a PCB image must include the drill points : not having drill points does not just mean there is no drill file, it means traces are not anchored and are seen as dead ends that the process removes.
There are two other interesting outputs from Cisolate as shown below:
On the left is the automatic determination, based on the Cellular Automata output, of which points are three-way intersections (blue) or four-way intersections (magenta) in the milling path. This enables the extraction of individual line segments that can then be combined in an optimum order. I was especially impressed with the CA, which produces highly robust results. The lack of any need to process special cases was notable making the coding much easier. On the right is a ‘heat map’ which indicates the generation of the CA by which a given point had been determined. The benefit of this heat map is that it allows the later path optimiser to have an idea of the freedom it has to smooth or move a path. Black indicates original copper and may not be encroached upon. The more white the area, the greater freedom there is to change (with white itself being the original ‘watershed’). White dots are drill points and cannot move as they are surrounded by copper.
The overall process is for a Cellular Automata to thin the areas between the copper tracks to their median positions. The advantage of the CA is that its output is kingwise-connected pixels such that the nodes of the diagram are clearly identifiable via certain pixel patterns. One-way intersections are points – ipso facto drill locations. Three- and four-way intersections are also robustly determined (diagram above). Given the identification of the nodes, this makes it easy and unambiguous to extract the individual lines between nodes as individual paths to mill. There are now three optimisations. The order in which the drill points should be drilled is a classic travelling salesman optimisation. The mill traces are similar – but note they are lines not points, and only the transits between the start and end of the lines are optimised at this point. There may also be a need to reverse the order in which a line is traversed. Finally the milling lines themselves are optimised (smoothed) by attempting to fit circular arcs to them subject to the heat map information. This minimises the number of individual G-code lines, within certain constraints. It leads to huge reductions in file size and probably allows much better look ahead optimisation by the ultimate cutter, at the expense of slightly worse fit to the exact solution
The core engine implements a cellular automata method, derived from that due to Guo and Hall (Parallel Thinning with Two Sub-iteration Algorithms, Communications of the ACM 32(1989) 359-373,759) also described in Knuth TAoCP 4A (7.1.3) for thinning an image. I had to add some further cells (shown below) to remove dead-ends (you do not want to waste time milling an electrical isolation path that doesn’t reach another path as it won’t isolate anyway). Note however that this is the reason that drill points must be marked on the image (see above). The lack of a drill point makes a pad look like a needless salient that can be removed, whereas the drill points anchor it.
The optimisation currently uses simulated annealing and seems to work well, although SA always has more tuneable parameters than I really like.
In the absence of a standard pattern, Cisolate uses the following design pattern for the Travelling Salesman optimisations, which separates the Optimiser (currently Simulated Annealing) from the Seeker (that records the current result and provides alternative perturbations to try) and provides an Optimee function as a metric to optimise against. The whole is a Runnable, as optimisation is a slow process so the ability to pass it to parallel threads is desirable.
This pattern is not used for the G-code smoothing optimisation as that just conducts an exhaustive search based on the fact that G-code only allows straight lines or circular arcs. Hence these are the key primitives. Arbitrarily, allowable arcs are constrained to a fixed set to ease computation. Again, arbitrarily, the radii of this set follow a geometric progression. The largest radius is set s.t. w.l.g. it may be considered a straight line. Hence, during the computation, only ‘circular’ arcs are considered, some of which are later assigned as straight lines when the G-Code is written.
There is a ‘de minimus’ concept in the optimisation to decide whether it is worth worrying about differences, which allows a reduction in the number of different sequences on this basis.
The process is to first determine fixed control points and then, subject to avoiding copper traces, conduct a greedy optimisation to find the best (closest fit to original curve) arc through each pair of consecutive control points. Then again greedily, join adjacent control points that have identical radii between them. The process continues by merge further adjacent curves if a compromise radius does not violate a de minimus setting and then jitters control points to facilitate further merger.
This screenshot of the program shows the effect of optimisation on the G-code after the curves have been straightened (note especially the situation near the top right). The individual tabs (Board, Isolations, Drill, Drill Path …) show different views of the situation (as used for illustrations throughout this blog) and they are all linked together, so that pan and zoom affects them all at once and the views can be tabbed between.
Finally, for a more complex board, this is this board from an individual’s projects on the web to prove that Cisolate can just work with an image directly. After a small amount of tidying (there is no point in ‘isolating’ text or keeping orphan pieces of copper). After processing for fewer than 5 minutes, these are the results (you may need to zoom in):
Having tested on about twenty boards, I am confident that the technical processing is correct and that a GUI and command line version are working so that I can use them. At the moment however the system is not user friendly – for instance only 24-bit bitmaps are accepted and some parameters (etch width, drill plunge depth) are hardcoded.