## Offsets of triangulated surfaces

Wednesday, September 26th, 2007 at 7:27 pm

There’s an annoying obsession with speed which is something to do with getting sales — it’s the one and only property of CAM software which users bother to perceive when shopping around.

I always thought that as long as the software generated toolpaths faster than the machine could run them, we’d be ahead. Remember, I began programming this stuff on 486s when it was the other way round, so that always seemed to be the benchmark.

Except it isn’t these days. Don’t people realize that unnecessarily speeding up the software decreases reliability by making the code far more complex, as well as taking time away from improving features? It’s no good telling programmers to make it as fast as they can, because that’s asking for a lifetime of work. No one is sure what the upper limit on speed is, and you could work for a month and make the software only 1% faster.

Sometimes you find that after a lot of work you’ve made it 10% slower because you made a guess that turned out wrong. Suppose the job is to steer an object through a maze. You can put more and more effort into the path planning so that it goes the shortest route, but at some stage it starts to take longer to get the perfect path than the time “lost” on a sub-optimal solution.

The fundamental function in CAM systems is the Dropcutter routine. Given the shape of the cutter, the set of triangles, and the XY coordinates of its axis, lower the cutter in Z until it makes contact with the first triangle.

For most strategies, most of the time is consumed in this function.

The trivial implementation is to loop through all the triangles, calculate the contact height between the tool and each triangle (if there is one), and pick the highest. This doesn’t work if the function is used a million times on a part that has a million triangles because then the inner loop is executed a trillion times.

An optimized implementation is to bucket the triangles: arrange a grid across the region of interest. Each cell in the grid contains the list of triangles which cross over it. Then if you search only through the cells which are in the shadow of the cutter at its XY position, you can narrow down the number of triangles you compare against considerably.

There are many optimizations to add to this. One thing to note is that there is a trade-off. If the gridcells are too wide then the triangle search are not narrowed very well (in the extreme case you have one gridcell and the situation is back as it was before). If you make the cells too small then you lose a lot of time scanning through thousands of cells, which soon becomes just as bad as scanning through the thousands of triangles in the first place.

The optimum width for the cell has to be found by experiment. I’ve tried to set projects for new programmers to run scripts to search for the optimum in a variety of situations, but it’s never caught on. The gridcell width has always been set at 20% of the cutter radius since I first set it in 1995, and has never been changed. The concept of rigorously working it out by running the algorithm thousands of times on different computers continuously and analyzing the results seems too hard to get across as something which is important.

A more optimized and memory intensive option is to offset the triangles by the cutter shape before posting them into the cells. This means that instead of scanning through all the cells in the shadow of the cutter (a circle around the XY position the radius of the shaft), you scan only in the cell that contains its centre point. Now there is no compromise with the efficiency. The smaller you make the cells, the more focussed is the scanning since the number of triangles that overlaps each cell is reduced towards the theoretical minimum. All you do is set the amount of memory you want to consume, and go for the limit.

Unfortunately, the geometry involved in considering the offsets of the triangulated surface is rather complex, which is why up till now I have only ever attempted it for the triangles. Now for the first time I am attempting to extend it to the edges and points of the triangulation.

An offset triangle is just a triangle. An offset edge (for a ballnosed cutter only) is a piece of a cylinder which, when you project it into the XY plane, is composed of two parallel lines and two halves of an ellipse. The blue and green parts on the shape above is what I am referring to. That surface overlaps exactly 11 cells of the red grid.

Luckily you can use the connectivity of the triangles to the edge to narrow it down significantly. For example, if two triangles connect to an edge downwards like butterfly wings it’s impossible for the ball to make contact with it and it can be disregarded. If the triangles are nearly coplanar, there’s a thin rectangle where cutter can touch it. Only when the two adjacent triangles bend downwards like a pitched roof can a wide area of contact be made. In this case it would be across 6 cells in the blue region.

A crude implementation in a mere 600 lines of code (there are many special cases with this shape if you want to do it fast) takes 20% away from the execution time. I’m beginning to work on the vertex problem next. I’m leaving aside toroidal cutters for the moment. Tapered cutters are, for sure, are going to have to lump it. Life is too short.

### 1 Comment

• 1. Freesteel&hellip replies at 8th October 2008, 3:58 pm :

[…] Projection and Drop Cutter functions, because the Drop Cutter, being as fundamental as it is, is unbelievably optimized. In its case there is a rotational symmetry about the Z-axis that can be heavily exploited. Once […]