Freesteel Blog » Detecting shallow areas on bad triangulations

Detecting shallow areas on bad triangulations

Monday, November 23rd, 2009 at 12:21 am Written by:

Horrors! This happened in our shiny CAM system when demoed in front of a customer. Everything was performing swimmingly slick and faster than anyone had seen, until this buggered-up boundary appeared, and the customer decided he liked his old CAM system better because it gave smoother, more consistent results.


The desired area is the subset of the surface of cutter locations where the cutter is in contact with the model with a contact normal of less than 45 degrees to the vertical.

As we are using triangulated surfaces for our machining algorithms — as do all CAM systems that actually work (although don’t try to explain it to the academics) — we expect some roughness along shallow area boundaries as the computer traces around the flat facets above and below the slope threshhold.

To compensate for this, we rely on a smoothing operation — offsetting the area out and then in by the same amount (using the scallop constant stepover algorithm) — designed to close the holes and soften the jaggies.

To see what’s going wrong underneath all this processing, you have to use the development version and turn off all the smoothing.


(I have left in the weave structure of the area model visible to make it obvious how the nodes are bound by it.)

As you can see, there are quite a few little fragments and saw-tooth motions that are too severe to be smoothed away.

The geometry of this nastiness becomes apparent when you look along the contour in a foreshortened view.


Do you see that? It’s the outline of two long thin triangles.

This gives a clue to the source of the problem. But why is the result so bad?

Unlike the scallop constant stepover algorithm, which has received a considerable amount of work and can handle 8-way cells (and more recently the 12-way cell), the area detection function is not so well developed.

The underlying algorithm is the same, but the within-cell modelling is simpler and was coded only to handle one or two contours passing through the same cell.

But these two thin triangles are responsible for an extremely close zig-zag motion which inevitably cuts many of the cells 3 times (making 6-way cells). 6-way cells were ignored, which accounts for the gaps.

Now they’re handled properly. It took about half a day to port the code over from the scallop algorithm, once I identified the problem.

Here you can see the result.


Now when we offset this shape outwards (prior to offsetting inwards), the narrow sliver merges with the rest of the area, and you only get bumps in where it is disconnected on the right. These failures are inevitable, because as the triangle tapers to a point, it will thwart any tolerance setting you choose while in the process making everything else much much slower (as a result of setting an unnecessarily tight global sampling rate).

The problem was proven by taking the triangulation from our system, importing it into the customer’s system, and verifying that their algorithm performed just as badly.


Well, actually, it’s worse now because I have improved ours to handle horrible triangulations which theirs doesn’t need to, because they have their own triangulation of the surface model.

What’s wrong with the triangulation?

Let’s look at this picture again:


Can you see the stripes running along the surface from top to bottom? We’re supposed to be looking straight down at a U-shaped surface with the light above us, and instead of going bright to dark smoothly, it goes bright again, and then goes dark a bit more, and then bright again, and so on.

Here’s my theory for what’s going on with that triangulation. They’re doing it with triangle fans. In the picture, triangles a, b and c get progressively steeper as we move away from the axis. But then d is shallower again. It has the same slope as a relative to the left-right direction, but it is tilted up slightly — though not very much if the surface is very long. Then e, f and g get progressively steeper, and then h has the same slope as g. In this case d would have about the same brightness and slope as a

A triangulation has to be pretty poor to show this effect. It doesn’t even look good visually, which is going to be the usual excuse if you complain to the CAD system that it’s not good enough — it’s only for graphics; you’re not supposed to machine against it, they’ll say.

Anyways, the time is coming when I’m going to have to implement my 1993 triangulator which I first did in Machining Strategist. And I never had an excuse to come back to it, even though it was pretty trivial — divide all the surfaces into small rectangles like a piece of graph paper, and then divide each rectangle into two triangles. Not the best way to do it, but a whole lot better than this.

Why isn’t something as fundamental as triangulation software perfected and easily available to the world as a public good, like the ZLIB and PNG libraries? Then all the obvious mistakes like this would be known and discussed by the club of developers who maintain it, and sorted out, and no one would need to put up with this ever again. It’s annoying.

I would guess that the each triangulator in the majority of CADCAM systems was written by one guy in a few weeks, with no discussion, and they never came back and reviewed it. This is something that could be verified by looking at the version control systems.

This is another project for the unborn science of software archaeology. After someone has looked at all the quartic solvers.

A commenter asked why not calculate average normals first.

Apart from the fact that is a geometric fudge which can cause problems where the angle between the triangles is high (I’m using contact points on the tool, not points from the triangles), this doesn’t address the problem of the fragmentation of the area defined by where the contact slope is less than 45degrees.

Almost no amount of smoothing can get rid of it. See the facetted cross section of the valley showing the way the surface wobbles. The segments are red where their slope is less than 45degrees, and there is a detached fragment on the left.

Any reasonable smoothing applied to this model will leave these wobbles in place meaning that this shallow area set can still be fragmented.

This is a large scale feature. As a rule of thumb, if you want to get rid of a feature, you need to apply a smoothing filter with a diameter at least 3 times the diameter of the feature. That way 2 good bits on either side can outweigh the 1 bad bit in the middle. In this example, the filter would have to be so wide that large sections of the model would become so rounded that it’s likely the area would no longer be near the original surface that is machined.


  • 1. Live replies at 23rd November 2009, 7:17 pm :

    Hello Julian
    Why do you just not calculate an average normal per vertex?
    E.g. when you calculate a toolpath in MasterCAM and use an STL file for the model of the part, the first stage of the toolpath computation process sounds like “Calculating average normals”.

  • 2. Julian replies at 8th December 2009, 5:09 pm :

    Hi there,

    An update to this point with a new diagram has been added to the bottom of the post.

  • 3. Live replies at 8th December 2009, 6:59 pm :

    Hello Julian,
    Why do you not use exact surface normals?
    A well developed surface tessellation algorithm provides this extra info.
    E.g., the SolidWorks API offers the Face2.GetTessNorms method for that.

  • 4. Julian replies at 8th December 2009, 7:47 pm :

    I don’t have control over that. All I get is an STL file, and the triangulation they are using (as seen above) is not well-developed. It’s also too slow on really serious parts with >40k surfaces.

    We’ve got away with it for a few years, but this situation proves that we need an improvement.

    We’re looking into the possibility of exporting NURBS surfaces and their trimming curves in a simple format (ie not embedded in something unnecessarily complex like STEP or IGES) and develop our own triangulator — something which we shouldn’t need to do in this day and age.

    After all, we’ve got free zip libraries, and free graphics libraries, free math libraries, so why don’t we have free surface triangulation libraries?

  • 5. Live replies at 9th December 2009, 6:24 am :

    For Nurbs there is absolutely free but not open source glu.dll which comes with every OS with OpenGL support and provides as well a planar triangulation algorithm.

  • 6. Julian Todd replies at 9th December 2009, 8:36 am :

    I think there is a GPL version of glu within mesa3d.

    There is an public domain open source version of the nurbs routine in OpenNURBS, which is sourced from RhinoCAD.

    Then there is the issue of packaging and incorporating a new library into the system, when we don’t know its capabilities and its limitations and it adds a new compilation stage that we will be stuck with forevermore.

    It would be great if these external libraries could be embedded into the system at no cost, but they aren’t. There is a risk that they are missing something, and that it takes a week to get it set up right. If you have had experience with them and have encountered all the problems, then I would love to hear about it.

    Alternatively, if the implementation without the libraries are just 2 C++ files using calculations we can copy out of a book, then the effort required is predictable and it has long term benefits — a programmer in 10 years time won’t get stuck for two weeks because she has problems compiling the external library. Been there, done that. Know what I mean?

    It is not enough for the software to be there, it has to be integrable at a predictable cost.

  • 7. Live replies at 9th December 2009, 12:21 pm :

    I know what you mean.
    Sometimes several pictures of the “weave cells” on the give much more than hundnred of useless papers on machining algorithms. 🙂

  • 8. Live replies at 19th December 2009, 11:12 am :

    I have tried it out.
    A slope area achieved using drop cutter on a triangular mesh with exact surface normals still requires smoothing.
    The only way to avoid smoothing is to drop the cutter on an exact surface model. The disatvantage is the surface drop cutter is much slower than a triangular one for the 3d case if the triangulation tolerance is low.

Leave a comment

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