
PCB DrillOver two years ago, I bought and assembled a cheap CNC milling machine  the idea was to use it to make a new version of my "STL Cutter" machine  albeit a bit smaller. However, I was in the process of selling my house, and when I moved, I was renting a house for a while, and didn't really want to ruin the carpet (although it was already in a pretty sorry state!) I eventually decided to use it for drilling PCBs that I make  however, the problem is all about alignment. The hardwareI covered the wires with some plastic wire covers I bought for my first kit car (now that would be 20+ years ago!), and fitted a camera to it:
The camera is a USB camera that came with a manual pickandplace machine that I got off the company that made me redundant 2 years ago (they allowed me to buy all their gear at knockdown prices). The camera didn't work terribly well with the pickandplace machine, so it had been languishing in a box for a while. It has a 19mm body, and I just knocked up some mounts for the camera that are held into the Zaxis of the CNC machine body. It doesn't move up and down with the drill  just side to side and front and back. I also made some clamps for the PCB, since the CNC machine didn't come with any (slightly annoying). The softwareThe software starts with a blank screen  you need to import the Gerber drill files. I've only got the files from Altium, so there hasn't been a lot of for other packages as yet...
Once you have loaded some drill patterns (you can load multiple  since Altium will export PTH and NPTH files separately, and I don't have PTH capability...), it'll show all the drill positions:
The icons along the top are:
The points that are highlighted in red are the currently selected size (0.6mm in this case). Once you have got the board roughly how it'll be on the milling machine, go into camera mode. Camera modeBeing in camera mode allows you to control the CNC machine to be controlled, and gives a crosshairs for where the camera is looking  this is NOT where it'll be drilling.
The icons to the right (a few are currently greyed out) are as follows:
The arrows can have key modifiers assigned to them:
The key combinations are cumulative, which means that pressing Shift+Control on the double arrows will move the board 25.4mm Board alignmentThe first thing to do is to get the board aligned. Rather than painstakingly adjusting the board's position, the camera allows the software to work out the board alignment. Clicking on the target icon, the board view will show you what point you need to select  it will be the one closest to the centre of the board. When the camera is centred over this hole, then click on the target icon again. Note that when I make PCBs, I use a technique I first learnt in Eagle PCB, which is something called "Drill Aid", where every drill point is replaced by a small hole (0.25mm). This makes camera alignment very easy. The machine will move to the next point for alignment purposes  on the assumption that the board is square. It almost certainly isn't, so you'll need to move the board (via the CNC machine) around until it is. The second point is the one nearest the top left. When it is aligned, click on the target icon again. It will then use these two points to have a better guess as to where the third point is  which will be the one closest to the top centre. Again, move it around (if ncessary), and click on the target to select the next point (which will be the top right). This continues for a total of 9 alignment points, and then return back to the centre point. At this point, you can click on any point in the board view, and it'll move the camera to that location. Hopefully it's nicely aligned because I haven't written any code to correct this! With the 9 points, it'll be able to cope with any stretching of the layout caused when printing onto the sheet, or slight variations in scale. Drill alignmentThe software does have a default drill offset (from the camera to the drill) in it, but this can be verified if necessary. Once all the alignment points have been selected, the camera can be pointed to a bit of the board that doesn't matter if it has an extra hole in it. Pressing the holepunch button will move the drill to (hopefully) where the camera was pointing, and then drill downwards. Note that the drill bit must be a millimeter or so above the board  otherwise it'll drill into air! You also need to make sure the drill bit doesn't hit any obstacles on the way (I forgot this twice, and broke a couple of drill bits on the clamp during early development). When drilled, the camera moves back. If it's indicating the correct point, then it'll be in the centre. Otherwise, move the board (via the CNC machine) until it's aligned, and click on the target icon to set the new position. This step is optional if you are happy with the general alignment. DrillingWith everything aligned, click on the "Play" button. This will move the drill up, and ask you to select the smallest diameter drill bit for this project. When it's in the drill, acknowledge the message box and move the drill bit to just above the board (1mm is fine). Then click on the Play icon again. It will then drill the holes using this drill bit. At the end, it'll move the drill upwards and ask you to select the next drill size up. This process is repeated until all the holes have been drilled at all sizes.
The board is now ready! Note that it's not 100% perfect, but a heck of a lot closer that I was able to do by eye on my old pillar drill. Travelling salesman problemThis is quite long, I'm afraid! One of the most wellknown problems in computing (or mathematics) is known as the travelling salesman problem. This is basically all about a salesman who has to travel to a certain number of cities and they need to know the quickest way to achieve this. Working out the most efficient way to drill the holes on the board is basically this problem. And the problem is quite difficult to solve  if you had 5 different locations, then there are 5x4x3x2(x1) possible answers (also known as 5 factorial, or 5! for short). If it took 1 second to calculate a solution, then it'll take you 120 seconds to find all the answers. If you add a new location, then it's now 6!  or 720 seconds. A seventh point increases this to 5040 seconds, or 1 hour 24 minutes. The board above has 130 points on it, which means that there are 6.466x10^{219} possible solutions. Even if it took 1µs (1 millionth of a second) to find the answer, it'll take 6.466x10^{213} seconds  or 7.484x10^{208} days. Or 2.0499x10^{206} years. In case you don't know what that is, here it is in full:
20,492,228,462,305,400,000,000,000,000, I think that's right! Since I can't wait that long  and nor can most people  you don't normally try every possible combination to see what is the best. Since it is a wellknown problem, there are plenty of people who have written up on this. But copying someone else is not any kind of challenge to me! My algorithmMy algorithm has five different algorithms within it to try to come up with a good enough solution.
Grouping locationsThe idea behind this sequence (which is only used once) is to come up with a very rough pattern which will be used as a basis. This algorithm tries to make groups of points that have between 1 and 10 points in them by extending a radius around each point and seeing if they touch. The simplest way to describe it is in pictures. Here, it has taken the 130 points, and created groups of them based on a radius around each point:
Using this particular radius, it has created 9 groups of points  some of which only have 1 point in them. It then looks at any grouping which has more than 10 points in it, and reduces the radius down until it has between 5 and 10 new groups. This is the magenta group in the bottom middle of the board:
It has created 7 groups from this  and it will divide down further. This is the dark yellow at the bottom:
This is good enough; it does not need to subdivide further. However, the green section in the second picture needs more division:
It will now move back to the cyan block to the left of the first picture. This is subdivded:
The red bit needs subdividing:
And finally, the pink section on the subdivision of the original cyan bit:
That's the subdivision done. It will use these groups and points within the groups based on a "nearest first" approach. It starts off with the first subdivision, and visit each group based on which one is nearest. Inside that group, it does the same thing until all points in that group have been added. And this occurs for all groups. The route that is chosen isn't particularly optimal  although (as I commented to a friend of mine) it would still be quicker for the CNC machine to drill them than I would by hand. But I like optimising things! Swapping neighboursThis is a fairly simple algorithm that swaps one point with the one next to it. If the new path is shorter, then use it; otherwise keep the old one. This is repeated until no more optimisations can be done. Find far pointsThis algorithm I call "Outliers", and it basically looks for any points that are quite a distance from their "neighbours" (being the ones it is connected to). If it finds any, it'll try to find the points that are actually closer to it than the ones they're connected to and insert it in between those two points. If the new route is shorter, then it'll keep it  otherwise look for the next point. This algorithm looks at the worst offenders first of all, and recalculates each time up to a maximum of 30 points (otherwise it could get bogged down when there'll be very little gain). At the end of this stage, the Swapping neighbours algorithm is performed repeatedly to tidy things up. Points along a pathThis has a fairly simple premise in that if you're travelling from A to B, and C is pretty close to being on the way, you may as well go via C anyway. This looks at all points, and sees if there are any lines that happen to be near it. If there are, it will rearrange the route to go via the point and if it's shorter, it'll use the new route. Otherwise, it'll use the old one. As the previous outlier algorithm, the swap neighbours is called to tidy it up. Removing crossed pathsThis was based on an observation I had with the 130 points that some paths were crossed. To me, it looked like if they weren't crossed, then it would be quicker. So I wrote the algorithm that looks at all the line segments and if there were any crossed points, it would swap the order around so they wouldn't end up being crossed. This did actually show the new route was quicker. As before, the swap neighbours is called after this Putting it togetherThe first algorithm is performed once (although there are two variants of it which produce different results). After then, the four algorithms are repeated until no more optimisations can be made. The grouping variationsWhen I initially wrote the grouping algorithm, I hadn't realised that the "ordering by nearest" was always from the same point (either the current drill position, or from the centre of the group). I had actually meant the current drill position to follow the group or point it had selected. However, when I recoded it to be correct, the new algorithm was worse for the 130 points, but was actually better for a subset of them. So it tries one, and then the other  and keeps the best one. Running itI've just realised that there's 134 points (+1 for the start position), not 130. However, I'm not going to do the maths again  you just need to multiply the previous time by 308,178,024... The "correct" grouping algorithm produces this route (the drill starts at the centre of the board):
Currently, it's at 785.408mm. The left hand side is particularly bad. If you look closely, you can see numbers next to each point. This is its position in the route, and occasionally I'll mention them. The algorithim will perform the "swap neighbours", "outliers" and "swap neighbours" first of all:
That's a bit better  now at 692.045mm. However, if you look just above the middle of the board, there's a long line that points 4 to 8 are nearby. This is where the "find points along a path" algorithm kicks in  which it'll also do for the left hand side (although that is difficult to see because the lines overlap). After this:
Now it's 654.102mm  but still some optimisations to do, such as a couple of loops between points 20 and 49. The "Remove crossed paths" algorithm will try to fix that...
With that, pretty much all the crossovers have been removed, and our length is 628.307mm. There's still some on the bottom left hand side, but that's because the points are actually on the lines (line is betwen points 45 and 46, and the points are 52 and 54). The crossed paths algorithm doesn't consider points on a line as crossing  and the earlier "find points near a route" didn't spot it because it was such a mess beforehand. It'll now look at the outliers again:
Here, it only moves one point  what was point 110 is now point 102, and the route is 618.454mm. It then runs "find points near a line" again:
And we now see that the two points on the bottom left hand side that I'd mentioned earlier that were on the line are now put in the same line. Our length is 618.380mm  we only saved 0.074mm! But we have some crossed points...
The second execution of the remove crossed paths algorithm has now eliminated them, and the length is 613.374mm This is the best it can come up with; rerunning the algorithms has no benefit, so it stops there. So it starts again, this time with the "incorrect" grouping algorithm:
Oh dear  its initial length is 926.089mm, which is a considerable way from the "correct" algorithm. Never mind, let's do the first step (outliers):
That's actually quite good  675.855mm. The path is looking quite well defined, so let's move the points near lines:
Now at 614.507mm  which is shorted than the "correct" algorithm!. We have some crossed paths which can be worked on:
This has brought it down to 596.108mm  and the path looks quite good! But let's rerun the outlier algorithm again...
And it's 591.981mm  the biggest difference is point 63 (was 81), which on the "correct" algorithm was the one it had troubles with until the end. And another attempt to move points to a line:
It's now 587.708mm  the only difference is points 74 onwards where it's done a slight rejigging of the order. The repeat of the remove cross paths didn't yield any differences, so no image was captured  but another outlier attempt has swapped some points in the same area as before:
We've now got to 578.102mm  with some crossed paths, which we'll sort out:
And that's the final answer  575.009mm. It can't optimise any more than it already has. How long does it take?As I said, to exhaustively search for every answer at 1µs per search would take a long time  running these two algorithms took a total of 0.144683 seconds. This means you barely notice it when it starts to drill the pattern for your selected drill bit. AnimationsIf you want an animated GIF of these steps, then you can download them here: "Correct" algorithm  "Incorrect" algorithm
Updated: 20190916 20:46:06  Comments: 0
 Show comments
 Add comment

© Copyright 19972019 Tribbeck.com / Jason Tribbeck All trademarks are the property of their respective owners. 