Path Planning Algorithm Used in Cura

[dampmaskin 0]

I wonder if a configurable bucket grid size would help my prints. I am currently mass producing a part, 15 parts per print. Solid infill. My part is roughly U shaped when viewed from above.

On every layer, Cura starts the infill in the middle of one of the "arms" of the U shape. It proceeds to jump a lot back and forth between different parts of the layer.

With "optimal" optimization, I think it would be possible to start at one end of the U, and fill in a layer (for a single part) with only one or two travels as it crosses the curve, but Cura 15.04.4 does at least 5 travel (combing) movements for each part, maybe more. Some of the travel movements seem very inefficient and doesn't make sense to me.

If I could double or quadruple the bucket grid size (or maybe even increase it to the size of my part), perhaps the optimization would work better?

My PC has 32 GB RAM and a nice CPU, and I wouldn't mind waiting for half an hour or more for Cura to optimize my print. After all, each print takes over 3 hours to complete, and I'm doing lots of them, so even if optimizing the path took the whole day, it would still be worth it to me.

Edited February 14, 2016 by Guest

[neotko 1,417]

It could be nice indeed to have the option to control the path algorithm. Sometimesfor an object to be able to select the priority (speed, top layer always on the same direction, etc?). I also won't mind to take time, indeed the print time will always be longer than the calculation time.

[pratiksha 0]

The LineOrderOptimizer::cluster() function is grouping up lines where both endpoints are right next to each other, using a nearest-neighbour search. This happens often in Cura, especially with skin lines which are all just parallel. It's not working very well with infill lines if the infill is too sparse. I'm thinking of making the grid size depend on the infill density.

It takes a line. Then it finds the nearest line where both endpoints are less than 5mm away from the first line's endpoints. Then it finds the nearest line where both endpoints are less than 5mm away from the second line's endpoints. And so on. When it finds no more lines where both endpoints are less than 5mm away from the previous, it puts all those lines in a cluster and starts with the next cluster, using a line that wasn't picked yet.

The LineOrderOptimizer::optimize() function gathers up those clusters, and calls the TSP solver to determine in what order the clusters should be traversed, and in what direction. The TSP solver uses the random insertion method.

Random insertion is an approximation of a solution to the Travelling Salesman problem where the goal is to find a short path along all elements. First it will take a random element (= cluster of lines, in this case) and save that as a path: That path is currently the short path along all elements it has inserted. Then the main idea: Keep taking a random element from your to-do list and insert it at the "best" position in the path. What the "best" position is in this case is up for debate, but basically it should minimize the travel time between clusters. The basic idea behind it is that after the first few elements are inserted in the path, the path should more or less span the entire space. For all the rest of the elements, there is a large chance that there is a segment of the path that runs right past the currently inserted element, so that it can insert it without much additional cost.

Only for CuraEngine, normal randomness is not allowed, since we'd like to keep the result predictable across slices. So it uses a seeded pseudorandom number generator, so that the outcome is still deterministic but the effect is the same. The algorithm is still subject to change, too.

 

Where is code for TSP solver or the random insertion algorithm.Can you please provide the link to it?

I am unable to locate it.

Thanks.

[ynilsiam 0]

I try to print a cylinder with a hole in the middle. Why the beginning of the path starts in the middle of the layerpath, not the edge?

Is there anyway to change that? So the print goes only one direction in each layer, not jumping back and forth.

Thank you very much.

[ynilsiam 0]

I just want to be clear about the question. Please see the image below.

The path starts with the red path then the 2 green paths and then jump out to black and print for a couple line, then jump inside, and so on.

I want to print a 100% solid object with concentric pattern.

Is there a way to start the beginning path from the edge?

Thank you very much.

[peggyb 170]

in Cura 2 you can set your bottom/top routine to concentric. If the model needs to be solid, set the bottom/top thickness to 99 or so, and set your wall count to 1.

Setting the infill to concentric, 100%, does the same..

[gr5 2,173]

Cura prints in 3 sections: outermost shell, inner shells, infill. These can print in different possible orders - typically the outermost shell is printed after the inner shell to try to improve quality but I have lost track of which versions print in which order. There is a checkbox in cura 15.X that lets you change this order. There is probably also a similar feature hidden somewhere deep in cura 2.X (there is a search feature for the features as there are so many now! try searching maybe for "order" or "first" or "last").

Making shell thickness 100mm will combine the "infill" and "shell" into one thing which will help a little bit.

Why do you want it solid? Solid objects aren't much stronger (maybe .1%?) than objects with 20% infill and a shell that is about 10% of the thickness of the part. Is it just the weight you want? Do you need the object to be heavier? There are other tricks to make a part heavier (brassfill, add metal weights into the hollows of the part).

[Ricky 5]

When solving path planning, it was better that we solve it in exact algorithm if the number of closed polygons is small or the distance among polygons are large enough.

 

Can anyone explain the latest Cura 3.31 path planning in https://github.com/Ultimaker/CuraEngine/blob/master/src/pathOrderOptimizer.cpp? For sure, I can read. But it takes time to digest and understand.

 

I'd wonder why it deliver subpar route for simple case like the ticket I posted here

[bagel-orb 61]

Your problem is not specific to the path planning algorithms. See comments in the ticket.

[PrIsMaTiSm 0]

I have an issue when making fine grids, this program seems to very randomly drag across instead of doing a logical maneuver. Is there a way to fix this?

[ahoeben 1,948]

Use an infill pattern instead of modeling the grid.

[GregValiant 1,251]

I don't like to guess, but this is a guess.

Cura doesn't see a bunch of walls, it sees a bunch of square holes and each hole has "outer-wall" around it.  The fact that the distance between holes is about 1 line width means that each square hole shares a wall with the adjacent hole.  That might be what is giving the funky toolpath.  You can try playing with "Group Outer Walls" and "Optimize Wall Printing Order".  You may end up with a different toolpath, but not necessarily a "better" toolpath.

 

As AHoeben suggests, if you make that area solid, and use a properly spaced "Grid" infill (you might have to use a Mesh Modifier and adjust the line distance rather than the infill density) then Cura will print the grid as lines from one side to the other,  You can rotate the grid so it is perpendicular to the structure by adjusting the line directions to something like "[0]" as the default (empty brackets "[ ]") is 45°. 

 

[gr5 2,173]

I believe someone on the Cura team once told me that when it finishes an "island" (aka a loop) it then looks for the nearest loop.  So I imagine it goes through the list of all loops and when it finds a point closer it updates the index to that and the distance.  So if it finds several of equal distance you get the first on in the list.

 

Unfortunately the list is unordered because the triangles in the STL are unordered.

 

So a hack-fix might be to modify the distance between each island by say .00001mm through .00500mm in the order in which you want to print them.  If you are creating these with openscad, this is pretty trivial.  Almost any other CAD, it's not so easy.

 

By the way, this is the famous "traveling salesman problem" which tries to find the shortest path to visit many locations and is exceptionally complicated and there are probably thousands of papers and algorithms on the subject.  When you get above 20 or so locations, there are more possible paths than atoms in the universe.  So you have to do an algorithm that's usually "reasonable".  The current algorithm is not very sophisticated at all obviously (just go to the nearest next island).

[gr5 2,173]

By the way, this looks like one big island. Which seems like a bad idea to me. But I can't tell as I can't zoom in much.