Jump to content

Path Planning Algorithm Used in Cura


fast_planner

Recommended Posts

Posted (edited) · Path Planning Algorithm Used in Cura

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 by Guest
  • Link to post
    Share on other sites

    Posted · Path Planning Algorithm Used in Cura

    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.

  • Link to post
    Share on other sites

    • 4 weeks later...
    Posted · Path Planning Algorithm Used in Cura

    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.

  • Link to post
    Share on other sites

    • 10 months later...
    Posted · Path Planning Algorithm Used in Cura

    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.

  • Link to post
    Share on other sites

    Posted · Path Planning Algorithm Used in Cura

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

    5a33262ddf3d7_Screenshotfrom2017-01-13150811.png.3ebb3a390cf9b4a0281fec8b7c93d608.png

    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.

    5a33262ddf3d7_Screenshotfrom2017-01-13150811.png.3ebb3a390cf9b4a0281fec8b7c93d608.png

  • Link to post
    Share on other sites

    Posted · Path Planning Algorithm Used in Cura

    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..

  • Link to post
    Share on other sites

    Posted · Path Planning Algorithm Used in Cura

    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).

  • Link to post
    Share on other sites

    Posted · Path Planning Algorithm Used in Cura

    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

  • Link to post
    Share on other sites

    Posted · Path Planning Algorithm Used in Cura

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

  • Link to post
    Share on other sites

    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now
    • Our picks

      • Introducing Universal Cura Projects in the UltiMaker Cura 5.7 beta
        Strap in for the first Cura release of 2024! This 5.7 beta release brings new material profiles as well as cloud printing for Method series printers, and introduces a powerful new way of sharing print settings using printer-agnostic project files! Also, if you want to download the cute dinosaur card holder featured below, it was specially designed for this release and can be found on Thingiverse! 
          • Like
        • 10 replies
      • S-Line Firmware 8.3.0 was released Nov. 20th on the "Latest" firmware branch.
        (Sorry, was out of office when this released)

        This update is for...
        All UltiMaker S series  
        New features
         
        Temperature status. During print preparation, the temperatures of the print cores and build plate will be shown on the display. This gives a better indication of the progress and remaining wait time. Save log files in paused state. It is now possible to save the printer's log files to USB if the currently active print job is paused. Previously, the Dump logs to USB option was only enabled if the printer was in idle state. Confirm print removal via Digital Factory. If the printer is connected to the Digital Factory, it is now possible to confirm the removal of a previous print job via the Digital Factory interface. This is useful in situations where the build plate is clear, but the operator forgot to select Confirm removal on the printer’s display. Visit this page for more information about this feature.
          • Like
        • 0 replies
    ×
    ×
    • Create New...