Tool path planning in Cura

[Ricky 5]

Tool path planning (a.k.a how to instruct nozzle movement in G code by slicer) always intrigues me. I like watching time lapse in real or also view it in Cura 3.x layer view mode. But from time to time, there are some crazy dance in 3.x which doesn't make any sense to me. So I decided to read their code and see how they do path planning.

 

Here are my findings. Please correct me if I'm wrong.

 

Common issue

In both 15.04 and 3.x:

1. Parts (a.k.a island/cell in 2D layer or union of overlapped polygons) order optimize without exact information of entry point and exit point of the part. This is due to the fact that the G code generation is done in the following order: layers -> parts -> any sub type (like infill, wall and etc) in part.

This inaccurate information almost undermined the optimization work in part path planning even with exact/approximated TSP. But why not separate parts path planning from G code generation? In other word, do part path order optimization after sub type path order optimization and entry and exit of the part are known.

3.x issue

In 3.x:

1. Within each part, the path of each sub type (like infill, wall and etc) is optimized independently. It might be local optimum in each sub type. But it is definitely not a global optimum within a part.
2. There are ad-hoc tweaking of staring point for z-seam alignment purpose like random, shortest and sharpest corner. I'd believe this tweak alone caused some bizarre nozzle movement compared to 15.04. More often than not, it caused more bugled wall than usual.

 

In any case, there seems to be a great room for path planning improvement in Cura. IMHO, I'd like to figure out how to fix the common issue first (the part order). I think part order optimization can convert into an asymmetry TSP. This is due to the fact that the parts in our problem has an entry and an exit. I did a test on symmetry TSP of complete graph with commercial software. The performance is quite impressive for solving 100 cities within 0.5 seconds. But that's the performance of commercial software. I don't know how good I can write a hobbyist level integer programming solver.

Edited May 13, 2018 by Ricky

[nallath 1,120]

I don't know the Cura Engine code that well, so I can't give you that much feedback. We "solve" the TSP by just attempting a best effort. We by no means even attempt to "truely" solve the problem. A lot of the improvements are due to various heuristics that we know work in our case (or work in most cases).

[Ricky 5]

Solving minimal distance can potentially save the print time and improve print quality.

 

10 seconds wasted due to sub par path planning in one layer will lead to 16 minutes longer (given100 layers). In addition, the longer nozzle travel in FDM, the higher probability the nozzle drips the filament no matter how good you calibrate retraction.

 

We always has one path. That works. But my point is that there may be some better way to do it. I'm going to do some work with my spare time and see how things will get improved.

 

Here is my plan:

1. Output parts coordinates in the file. There was a routine to output in SVG. But it is scaled. My purpose is to let other operation research folks (if they are interested) looks into the problem easily. Because those guys always ask for data.
2. Move parts order optimization after all infill, wall and etc in the part is processed.
3. Add information about an entry and an exit point of each part.
4. Experiment exact/approximate TSP.

My work is here. I don't know who else will be interested in my proposal. 

Edited May 14, 2018 by Ricky

[nallath 1,120]

If I were you, i'd check out the latest version of the engine. You're working on a version that is 5000(!!) commits behind master. Any changes you make to that version are very, very unlikely to be merged into master.

I'm well aware of why solving the problem is important, but in all attempts i've seen so far, it took 5-10+ times as much slicing as time that was actually saved in printing. This might be interesting if you're optimising for production, but i think most people tend to print low volumes (and thus, this costs more time than it actually saves).

 

[Ricky 5]

The proposed fix I'm going to make is relativly easy to migrate from 15.04 legacy branch into master branch. Basically, nobody has improved path optimization since then except tweaking starting point. As I'm aware, there are way too many moving variables in master branch as I pointed it out in 3.x issue that might undermine my effort, eg sub part selection in the starting point of shell, infill and etc within a part/island.

 

At the cost of slicing performance, reducing the air time travel in FDM may also reduce the chance of retraction. This alone should make print better than any hack/tweak we have added. The improvement doesn't require human intervention. 

 

I have done plan #1 already -- output the polygons in external file and wrote a small script in matplotlib to plot the part as well. This should attract enough interest from operation research people to chime in (if any). They always screamed for data.

 

Regarding to the performance of slicing, in my hobbyist level 3D printing I seldom see the number of my parts are more than 100. That small problem size should be good enough to solve in exact TSP in a reasonable time frame given we have a good mixed integer linear programming solver and a beefy machine (not raspberry pi).

 

On the other hand, if layers has more than 100 parts/islands, that is another good motivation to minimize the air time travel as much as possible. But perhaps it is done in approximated TSP approach, instead of exact approach. In such case, I should checked if the probabilities of getting better optimized result from approximated TSP is higher than the one of the nearest neighbor.

 

Again, I'm not a OR expert. That requires me my further research in my spare time. I have tons of smart people in my community. They may help.

 

[Ricky 5]

Here is a small visualize progress I made so far. I output the closed polygon of the parts from Cura Engine into a file. Then, I used matplotlib to draw the parts. You can change the layer index to explore the parts in different layer.

 

The file format is defined in here: https://gist.github.com/rickyzhang82/33831c6d5a3eaaa3de3ffb5122f15b69

My work is in my repo dev-15.04.6 https://github.com/rickyzhang82/CuraEngine/tree/dev-15.04.6

 

To get the parts data, just compile cura engine and replace stocked 15.04 CuraEngine in Linux/Mac (no Windows). Slice a model and it will generate file in /tmp/parts_by_layers.txt

 

Then run:

cd CuraEngine/utils

PYTHONPATH=$PWD python ui/main_app.py

 

My next step is to output the entry point and the exit point of each part into another text file. I believe the problem is an asymmetry TSP.