Jump to content

Tool path planning in Cura


Recommended Posts

Posted (edited) · Tool path planning in Cura

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

    Posted · Tool path planning in Cura

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

  • Link to post
    Share on other sites

    Posted (edited) · Tool path planning in Cura

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

    Posted · Tool path planning in Cura

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


  • Link to post
    Share on other sites

    Posted · Tool path planning in Cura

    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.


    • Like 1
    Link to post
    Share on other sites

    Posted · Tool path planning in Cura

    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.


  • 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

      • 🎄✨ Thingiverse Tree Ornament Challenge! ✨🎄
        We've been running a Tree Ornament Challenge with a chance to win an UltiMaker S3 or colorFabb filament.
        Design a 3D printable tree ornament and join our festive challenge on Thingiverse. 🎁✨

        📆 Submission Deadline: December 22
        🏷️Tag your designs with Holidays2023

        Click here to join and check out the over 300 other amazing designs

        How to Enter
        Design an Ornament
        Create a 3D printable tree ornament that captures the magic of the winter season. Think snowflakes, sleighs, reindeer, cozy mittens, or anything that embodies the joy of the holidays. Upload to Thingiverse
        Share your masterpiece on Thingiverse and add the tag Holidays2023. Don't forget to include a captivating description and images that showcase your design from different angles. Submit by December 22
        All entries must be submitted by December 22nd to be eligible for consideration.
          Entering a new design
        Entering an existing design
        Winning designs should:
        Be original Creations
        Your designs should be original works, avoiding the use of others' intellectual property without permission. Include STL Files
        Each submission must include at least one STL file for 3D printing. Showcase a Completed Print
        Provide at least one photograph featuring a completed print of your design. Include Documentation
        Share the creative journey! Include documentation of your design process, giving us a peek behind the scenes. For example, show a screenshot of the model in your design program. Use the Tag Holidays2023.
        Use this tag to ensure your entry is counted in the Tree Ornament Challenge. Be submitted after October 1st, 2023
        Ensure your design was uploaded to Thingiverse after October 1st, 2023. Adhere to Submission Guidelines and Terms of Service
        Make sure your submission aligns with our guidelines and Thingiverse's Terms of Service.  
        Good luck 🎉
        • 0 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
      • Ultimaker Cura 5.6 stable released
        Cura now supports Method series printers!
        A year after the merger of Ultimaker and MakerBotQQ, we have unlocked the ability for users of our Method series printers to slice files using UltiMaker Cura. As of this release, users can find profiles for our Method and Method XL printers, as well as material profiles for ABS-R, ABS-CF, and RapidRinse. Meaning it’s now possible to use either Cura or the existing cloud-slicing software CloudPrint when printing with these printers or materials
        • 11 replies
    • Create New...