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

    Posted · Path Planning Algorithm Used in Cura

    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?

    image.thumb.png.c8f49a66a75497b9716f2ef376f8fe09.png

  • Link to post
    Share on other sites

    Posted · Path Planning Algorithm Used in Cura

    Use an infill pattern instead of modeling the grid.

  • Link to post
    Share on other sites

    Posted · Path Planning Algorithm Used in Cura

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

     

  • Link to post
    Share on other sites

    Posted · Path Planning Algorithm Used in Cura

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

  • Link to post
    Share on other sites

    Posted · Path Planning Algorithm Used in Cura

    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.

  • Link to post
    Share on other sites

    Posted (edited) · Path Planning Algorithm Used in Cura
    On 4/26/2024 at 7:03 AM, gr5 said:

    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.

    This is another view of the file, its an Autodesk Inventor part converted to STL. The grids unfortunately need to be in specific locations, otherwise I may try modifying the print in some other way. I purposefully made the grid size the width of a single line, with the hole being 1mm wide, but for some reason it just doesn't behave as expected. Here is another image as well. It looks like it is more random than just going to the 'nearest island' since it also seems to be inconsistent what it chooses as an island, indicated by all the white sections at the grid intersections presumably because the program didn't complete those paths.

     image.thumb.png.e9ea4d519b802f7b29f80d1453fb7acc.pngimage.thumb.png.6e4955a9009844cefe3040305cc3358d.png

    Edited by PrIsMaTiSm
  • Link to post
    Share on other sites

    Posted · Path Planning Algorithm Used in Cura

    I wouldn't really have a problem with this pathing, since the efficiency loss isn't a big deal, but the problem comes when printing it. The resulting prints resemble more of a blob than a grid.

  • Link to post
    Share on other sites

    Posted (edited) · Path Planning Algorithm Used in Cura

    "..The resulting prints resemble more of a blob than a grid." 

    I can see that happening.

    Think of the grid as a bunch of long horizontal walls running right to left.  Now consider all the vertical walls not as complete long walls, but rather as partitions between each horizontal wall.  Cura doesn't really want to run over the "cross" at the wall intersections.  That means each of those little partitions needs to be a separate extrusion with a 0.4mm travel across the horizontal wall, then another 1mm extrusion follower by another short travel.  That would be highly inefficient so it appears that Cura has decided to print 2 walls of each square so the extrusion can simply continue.  I uess that's why many of the toolpath segments look like zigzags.

     

    This is a model I made up with 1mm square holes and 0.4 walls between them.  I've used "Remove all holes" and set a grid infill with no top or bottom skins.

    This is Cura printing the grid infill.  Each stripe goes from left to right to left, and then the vertical stripes go in.

    image.thumb.png.26b447421ca3962687015a09a2f7c9dd.png

     

    The down side is that at the crossings, the extrusions don't stop extruding so there is a double bit of material at each crossing.

    You can use a support blocker as a mesh modifier and make the infill for your different areas different

    Here one model is as above, and the second is a copy but has 1.9 line spacing and the grid has been rotated and offset.

    image.thumb.png.c81810322eeb8f77c81c70f5c2a529ad.png

     

    Edited by GregValiant
    • Like 1
    Link to post
    Share on other sites

    Posted (edited) · Path Planning Algorithm Used in Cura
    1 hour ago, GregValiant said:

    This is Cura printing the grid infill. 

    Very great visual and proof of concept!

     

    This is what I was thinking to do, since I know the grid infill option Cura has works well, and although it doesnt stop extruding over the intersections, it should be more than sufficient. I am however, not an expert at the program, so I may need some guidance as how to remove only the necessary holes, then add support structure in place whilst maintaining the precision of the part. I can easily modify the part in Inventor, but again, I need to maintain the position of the grids.

    Edited by PrIsMaTiSm
  • Link to post
    Share on other sites

    Posted · Path Planning Algorithm Used in Cura

    Post the STL (if you can share it) and maybe something can be done.

     

    One thing for sure is that the grid areas must be printed sllowwly with a lot of fan.  The initial lines must be cool or they will deform when the crossing lines are laid down because the nozzle runs into them.

  • 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 the UltiMaker Factor 4
        We are happy to announce the next evolution in the UltiMaker 3D printer lineup: the UltiMaker Factor 4 industrial-grade 3D printer, designed to take manufacturing to new levels of efficiency and reliability. Factor 4 is an end-to-end 3D printing solution for light industrial applications
          • Thanks
          • Like
        • 3 replies
      • UltiMaker Cura 5.7 stable released
        Cura 5.7 is here and it brings a handy new workflow improvement when using Thingiverse and Cura together, as well as additional capabilities for Method series printers, and a powerful way of sharing print settings using new printer-agnostic project files! Read on to find out about all of these improvements and more. 
         
          • Like
        • 26 replies
    ×
    ×
    • Create New...