Freesteel Blog » Embarrassing toolpath ordering

Embarrassing toolpath ordering

Monday, January 15th, 2007 at 5:25 pm Written by:

Here’s the before and after, after a couple of days of hacking. It’s a difficult issue — the problem of planning the directions for the Adaptive Clearing toolpath — since any plan would depend on the remaining stock, whose shape changes completely throughout the process.

The best plan is no plan at all, because there’s nothing to go wrong, and things run a bit quicker. At all stages during the calculation, the algorithm maintains a list of potential starting points. The simplest plan is always to select the most recently left potential starting point, and try to cut forward from it. If that fails (eg there’s no material there anymore), then discard it and try the second most recent potential starting point. (There’s a class in the system called PotentialStartPath.)

Simple though it is, it’s still way complicated, because there are over seven different types of starting points (on contour, from helix, from corner, towards contour, away from contour, double cut breakthrough, towards vanishing point on last level, and so on), all with radically different geometric requirements. This entire nightmare of confused logic is coded in Python using its high level structures and easier hackability. There are maps, dynamic lists, and placeholder variables galore. It takes a good few hours to get into it, and then you don’t want to mess it about too much.

I was told of a small complaint about the ordering. It turns out that though this strategy is quite adequate for most of the machining operation, it looks awful at the start when the tool is hopping around at random sniffing the shape out. With a simple a part, like the one pictured where the sides are coincident with the stock and do not require any machining, the first thing it would do is go once round and visit every corner before settling down to nibble one of them away. Then it would jump back counter-clockwise one corner, instead of going ahead to the closer one, and work on that.

It doesn’t give a good first impression.

It took two tweaks to fix. The first was to always go for the closest starting point to where it last broke off. (Best would be to do a linking path to each possible starting point and pick the shortest one; sometimes it’s quicker to carry on forwards to some material in front than to do a big loop to get to a point immediately behind.)

The second tweak was a more tricky. When starting with a rectangular piece of stock, it tends to aim for the corner which is the best starting point for spiralling in from. Unfortunately, in this example, aiming for the corner is worst possible place because that lands in the middle of a disconnected fragment of stock. It’s better to aim for the middle of one side of the model, and follow it along till meeting the stock.

The algorithm is now a bit slower on account of scanning along all the contours looking for these starting points. There’s no reason it has to check all of them. It could try ten places at random and stand a good chance of hitting one of these large unnecessary-to-cut areas with a high probability. But that’ll be much more complicated to program, so I’ll leave it at that until speed becomes an issue again. One of the worst things you can do is optimize you code too early before it is its final form.


  • 1. Anders replies at 15th January 2007, 6:20 pm :

    Hi Julian,

    I’ve thought about cnc simulation, i.e. simulating the amount of stock left when the cutter moves around programmed by G-code. From EMC it should be easy to get a stream of G0-3 commands based on a G-code file.

    The hardest part seems to be choosing a good representation for the 3D stock material. What do you use and why? Heightmap? Octree? CSG? Triangulated surface (==STL?)


  • 2. Julian replies at 15th January 2007, 7:17 pm :

    Best way (the way I use) is commonly called the “matchstick” model. It starts as a grid of points with a z-value on each one of them. Each segment from the cutter path trims of those matchsticks it interferes with. If you do it well, you can add extra matchsticks in areas where required (at the cusps between two cutter paths). You then form a triangulated surface from the points given by the tops of the matchsticks.

    Octree is a waste of memory. In believe Lightworks/Machineworks uses a triangulated surface, which is a method that obviously can’t possibly work due to the inevidable complexity of the surfaces. So they must be very good programmers to have actually got a result from it, but very foolish too, in my opinion.

  • 3. Anders replies at 16th January 2007, 9:56 am :

    Thanks for the rapid reply,

    Is your “matchstick” model similar to what is called a heightmap ?

    Using this model does mean that cutting with an angled cutter (5D machining), with a slot-mill, or from the side or the bottom of the model is impossible ?

    When you have time, I’d be interested if you could elaborate on how the adaptive insertion of more “matchsticks” is done.



  • 4. Darius replies at 17th January 2007, 12:45 pm :

    interesting article.

    —————— – all about privacy

Leave a comment

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