Freesteel Blog » The slot drill that fell through a triangle

The slot drill that fell through a triangle

Thursday, April 19th, 2012 at 11:47 pm Written by:

No one thought there could be a bug in something as fundamental as the drop cutter onto triangles function, which has been in use at the heart of most every machining algorithm since I had started writing these functions 20 years ago. But the farm found one.

The farm is a set of scripts that constantly generate random triangulated models against which all the machining algorithms are tested with random parameters night and day looking for failures — software crashes and gouges. It exposes all the known weaknesses in some of my algorithms, which is evidence that it is pretty effective.

The worst results are always with flat bottomed cutters, because their sharp circular bottom corner creates discontinuities in the solution.

It was just one of these discontinuities which cause the cutter to fall through a triangulated surface in the rare situation when its profile was exactly tangent with the highest edge.

The cutter shape is lowered and tested against the components of the triangulated surface independently — the triangle surface, the edges, and the points.

On the left, with a ball nosed cutter, you can see that the red contact point with the yellow triangle is well inside the area. There is no doubt that it will be recorded. Independently (if you ignore the triangle) it will also make contact with the blue edge — just barely as its circular profile (as seen from above) is tangentially overlapping with it. Depending on the slope of the triangle, there is a wide overlap between when the tool is held up by the interior of the triangle, and when it is held up by the blue edge. It will never fall through between the two.

On the right is a flat bottomed cutter in roughly the same position. Note how, when its circular profile (as seen from above) is tangential to the blue edge, the contact point is in the same place — because the contact point must be on the rim of the cutter if the triangle is sloping.

Now it is possible for the two regions not to overlap. As the flat bottomed tool gradually moves to the left, the red contact point will leave the yellow triangle’s surface at exactly the same time as it first encounters the blue edge. Any slight miscalculation (of the order of 1e-14, say) and there could be a gap where neither the triangle’s interior surface nor the blue edge is holding up the tool, and then the tool will fall through and gouge the model.

That was the bug. I wouldn’t be surprised if it is in most machining software as the circumstance is very rare.

The fix is to consider the flat bottomed cutter against a triangle case specially, choose the closest point on the triangle’s perimeter when the contact point with the plane containing the triangle is only just out of its region, and force the cutter to be lifted up by it. This requires the use of an epsilon value (to quantify the meaning of “just out of the region”), and I don’t like epsilon values because they assume the scale for the calculations (what happens when I get a 1micron cutter?). However, I don’t think this one is too bad as it just tests against a point in the triangle anyway as a lower protection, and if the algorithm worked, then the tool will be lifted up from it. That is if I was to through in a random point from the interior of every triangle into the drop cutter calculation, it shouldn’t make any difference.

As with all of these types of fixes, it is very difficult to know how frequently the exceptional calculation gets applied. You don’t want it to happen too often as it would change everything and slow things down. So what can you do? It’s possible to count the uses of this exception, and then what do I do with this number? There’s nowhere to report it to, or compare against expectations, or do anything useful with it. And anyway I am likely to entirely forget what it was tomorrow when I move on to the next interesting issue. Long term performance monitoring of calculation algorithms should be done, but there is little infrastructure to do it. So we just put it in place and hope for the best — having tried to keep the change as simple as possible, and having walked through all the different cases, leaving some assertions in place.

Oh, and we keep running it on the farm night and day looking for other miscalculations before anyone finds them in real life.

1 Comment

  • 1. Freesteel&hellip replies at 28th May 2012, 7:38 pm :

    […] interesting calculation bug, to go with the previous one, that has been in my code for decades, occurred as a result of not properly factoring down a […]

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <blockquote cite=""> <code> <em> <strong>