Over 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.
I 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 pick-and-place machine that I got off the company that made me redundant 2 years ago (they allowed me to buy all their gear at knock-down prices). The camera didn't work terribly well with the pick-and-place 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 Z-axis 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 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.
Being in camera mode allows you to control the CNC machine to be controlled, and gives a cross-hairs 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
The 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.
The 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 hole-punch 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.
With 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 problem
This is quite long, I'm afraid!
One of the most well-known 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.466x10219 possible solutions. Even if it took 1µs (1 millionth of a second) to find the answer, it'll take 6.466x10213 seconds - or 7.484x10208 days. Or 2.0499x10206 years. In case you don't know what that is, here it is in full:
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 well-known 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 algorithm has five different algorithms within it to try to come up with a good enough solution.
The 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!
This 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 points
This 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 path
This 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 paths
This 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 together
The 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 variations
When 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.
I'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 cross-overs 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; re-running 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 re-run 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.
If you want an animated GIF of these steps, then you can download them here:
|© Copyright 1997-2019|
Tribbeck.com / Jason Tribbeck
All trademarks are the property of their respective owners.