## More machining questions

Thursday, April 13th, 2006 at 9:58 pm

I’ve had some lovely questions from the author of MeshCAM yesterday. I am pretty fully aware of how these machining algorithms work in all the CAM systems I have seen. The underlying concepts are simple. If there’s the will I think we could all work together to find out what headings to put these into wikipedia and maybe with a few diagrams. Someone ought to start the pages.

1) In a blog post you discuss a function which determines the tool height given a triangle and an xy point. This type of function implies to me that you layout the toolpath in a signle plae and then step over it to set the z height. Am I correct and is this the way that commercial programs do it? If so then I assume the step size is adjusted dynamically to pickup the curret triangle edge positions? If so, is there a lower limit of the step size to keep from trying to step over nearly vertical triangles?

Yes. This accounts for all the toolpath strategies that seem to be made by tracing out a path shape in 2D above the model, and projecting it down into the toolspace by setting the appropriate Z values for a series of XY points along the path according to my previous post. The sample rate is set according to the toolsize and the machining tolerance. Larger tools get sampled less because the cusps between two close sample points would be smaller for them.

After the first pass of samples is done, we consider every pair of points (cutter locations) and test whether a new sample needs adding at the half-way point. This is done according to the following criteria. If the two samples are closer in XY than 0.001mm (the tolerance of the machine tool) there is no further subdivision. Otherwise there is subdivision if the Z-value changes by more than, say, 2mm. And there is subdivision if the contact normals of the two cutter locations differ by more than, say, 20 degrees. (The contact normal is calculated as a byproduct of the calculation that gives the Z-value.)

2) In another post you mention having to remove “spikes” and “glitches.” I’ve run into these type of problems and can usually remove them by setting some minimum length or equivalent metric coupled with a few heuristincs about what should be correct. This never felt very scientific and I always wondered what the big guys did to remove this stuff. How do you decide good/no good on a section of a toolpath?

The spikes and glitches come in the implementation of the constant stepover/constant scallop algorithm. What we are discussing above is the simple 2D toolpath projection finishing algorithm, and spikes and glitches are very rare in general unless there is a dodgy calculation in the implementation. In theory I had expected there to be lots of spikes in the above algorithm, but in practice the numerical results are good enough such that they don’t happen.

3) What is the preferred curve/polyline offset algorithm in use? Voronoi algorithms seem to be very hard to implement correctly and PWID and Hansen/Arbab (and it’s derivatives) can be slow and be subject to numerical accuracy problems. What do the big guys do and how do they make them robust?

I’ve written an implementation of a voronoi twice, and won’t do one again and keep it private. It takes about six months and is very hard work. Martin Held is the expert and has come up with a third version of the algorithm which he sells, although he should be releasing it under the GPL as well. One day I might do a final implementation and make it GPL, if there’s anyone who can use it in that form.

You’ll have to tell me what PWID and Hansen are, I’ve not heard of them. Most companies work by brute force, and solve robustness problems like this by employing a programmer to work on debugging it day after day every day for eighteen months.

I managed to get my Voronoi module for NC Graphics pretty robust, but for final reliability I would detect any failures, shift the points a few microns in random directions, and rerun it. Usually this changed their alignments so that the miscalculations happened differently, and the result would get through.

The best way to approach something like this is to recognize that it’s a very hard problem in the first place. This is good for separating the men from the boys; the boys think it’s going to be easy and get stuck in right away. The men who have more sense do everything they can to redesign the system to avoid having to solve it in the first place.

• 1. Jeff replies at 14th April 2006, 5:17 am :

I enjoy reading your blog, especially about machining and algorithm, some of them will be an important part of NC toolpath wikipedia.

In your last time blog about Basic Cutter Location Studies, you wrote,
>But a good way to imagine it is you turn the model on its side >and do one straight toolpath from the top to the bottom, and >then turn it back upright again. You’ve now got a piece of Z->slice.

Do you use the same function( which determines the tool height given a triangle and an xy point) to get straight toolpath? How many different directions are needed to get one complete Z-slice?

• 2. Robert replies at 14th April 2006, 5:53 am :

Two followup questions:

1) How do you determine the initial stepping distance along a path?
2) When you calculate the tool height from a triangle do you generally take into account the neighboring triangles to correct or optimize for things like convex corners or do you just treat each triangle on its own?

By the way, I agree with Jeff- great blog.

• 3. Julian replies at 14th April 2006, 8:50 am :

I need some diagrams. I’ll have to find out how to draw them at some point. It’ll make the statements a little more obvious.

The Z-slicing relies on modelling the cutter at a particular Z-height and projecting it along a horizontal vector until it makes contact with a triangle. (This is not strictly the calculation, but it is the best way to imagine it). The finishing type location starts at an XY position above the triangles, and lowers it down until it makes contact with the triangle(s).

You can consider each triangle entirely separately and return the maximum value of all your answers. There is a lot of obvious optimization that can happen, which isn’t important for understanding the process. For example, as you calculate higher and higher maximum Z-s, there’s a larger number of triangles you can discard from consideration because no part of them gets high enough to make a difference.

• 4. Julian replies at 14th April 2006, 10:20 am :

I’ve answered (1) in the next post.

I can’t use the same function locate the cutter from above as from the side. The silhouette of the cutter are different shapes. From above it’s much simpler since the silhouette is a circle and you only need to consider the tip surface. The side is a more complex shape involving the shaft as well.

• 5. Les Newell replies at 14th April 2006, 12:51 pm :

It makes me feel much better when you say it takes a long time to debug brute force offsetting. I have been at it for 2 years now and still people occasionally manage to make it choke 🙂

Oh, the joys of floating point numbers…