## 3-axis tool holder checking

Friday, August 12th, 2011 at 2:34 pm

Trying to do some machining work here. I’ve got the task of making the 5-axis holder collision check work a bit faster. But first check the review of the 3-axis holder case.

Consider the following diagram. The background yellowish volume is the model, the blue is the toolholder that can collide with the model when it is lowered along its z axis, and the barchart thing represents the box-set containing the model. The box-set is the structure that puts all the triangles, points and edges of the model into rectangular boxes so as to reduce the number of elements that need to be scanned.

For example, if the model contains a million triangles spread across a metre squared, then it’s going to take a long time to scan all of them for each tool holder location to test for collisions. However, if the triangles are listed in boxes, then (according to this diagram) we need only to scan the triangles that appear in the 12 boxes between A and B, which is a fraction of the total.

Also, each box has the triangles listed in order of max z (within the box). Since we know the minimum z of the toolholder where it overhangs each box, we need only scan down the triangles in each box until we reach the first triangle whose maximum z is below this minimum.

Even so, with a big toolholder shape covering a broad area, there can be numerous boxes to scan, many of whose top triangle is well below the min z of the holder over that box.

So there is scope for optimization.

For any toolholder xy axis position, there is a height difference between the maximum z of the triangles in each box, and the minimum z of the tool holder over that box.

We can sort references to these boxes by this order.

In this example (if the tool holder were a fraction lower), we can see it would look at the top few triangles in box 1, then maybe a lesser few in box 2, and finally since box 3 and all subsequent boxes are lower than their corresponding holder min z, we can stop there, having scanned 2 boxes instead of 12, and quite possibly discovering a collision (if there is one) on the first box.

Obviously, producing this list of priorities for each box takes a bit of time as well as memory. As with any precalculation, care has to be taken that you are actually reducing the end-to-end calculation load.

The size of the boxes in which these lists are made can be much bigger than the boxes containing the triangles of the model.

At the extreme case, you can use a single holder box, and just list the triangle boxes in order of max-z. Then the algorithm simplifies to merely going through them in order until the box that is below the lowest point of the toolholder is encountered.

• 1. Collision checking algori&hellip replies at 14th August 2011, 2:46 pm :

• 2. Patrick replies at 22nd September 2011, 8:29 am :

Some fragmented ideas which might help:
1. If you put the boxes of interest in a priority queue you could save time sorting boxes you turn out to never need to examine.
2. Since the toolholder profile is monotone with distance from the axis you should also prefer to visit boxes close to the axis first – but do not compute an exact distance every time and sort by it, just use a precomputed pattern based on the boxset cells (using the order in which a Bresenham circle fill algorithm would colour in the grid starting from the centre).
3. When you find a hit on a real triangle it’s a local maximum which narrows the range within which you need to look elsewhere – convenient for a parallel branch-and-bound algorithm, because all threads can benefit from this information (superlinear speedup!).
4. You’re going to be doing this for bazillions of x,y axis-centre positions, corresponding to all the sample points on your desired toolpath. Exploit spatial coherence – if only by dragging the box in which the maximum was found for a neighbouring sample point to the front of the queue, or by processing the sample points in batches whose granularity roughly matches that of the boxset.