Suboptimal path inside of the object

[m-Th]

Version

Slic3r Prusa Edition
Version: 1.36.2-prusa3d-stable-win64
Build: Slic3r-1.36.2-prusa3d-stable-win64-full-201707281104
Operating System: MSWin32
System Architecture: MSWin32-x64-multi-thread
Windows Version: Microsoft Windows [Version 6.1.7601]

Behavior

• When we try to print the attached STL file (generated GCode included) it gives us an suboptimal path. Use this tool
  https://www.thingiverse.com/thing:44286/#files
  on the attached file. Pay attention, for example, at the first layer.

Is this a new feature request?
No.

STL/Config (.ZIP) where problem occurs

TUSH-holder files.zip

[bubnikv]

Are you objecting the infill path planning? Currently Slic3r PE applies a relatively simple greedy path planning algorithm, which tries to maximize the lengths of continous paths first, then it tries to minimize the travel distances. Anything more involved requires computation intensive optimizations.

…

On Sat, Aug 12, 2017 at 6:33 PM, m-Th ***@***.***> wrote: Version Slic3r Prusa Edition Version: 1.36.2-prusa3d-stable-win64 Build: Slic3r-1.36.2-prusa3d-stable-win64-full-201707281104 Operating System: MSWin32 System Architecture: MSWin32-x64-multi-thread Windows Version: Microsoft Windows [Version 6.1.7601] Behavior - When we try to print the attached STL file (generated GCode included) it gives us an suboptimal path. Use this tool https://www.thingiverse.com/thing:44286/#files on the attached file. Pay attention, for example, at the first layer. *Is this a new feature request?* No. STL/Config (.ZIP) where problem occurs TUSH-holder files.zip <https://github.com/prusa3d/Slic3r/files/1219904/TUSH-holder.files.zip> — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#471>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AFj5I2B5eUnRPjqUgzE3ggsMWaGLvVsqks5sXdPGgaJpZM4O1dTn> .

[m-Th]

Then the algo isn't quite good. Here is what I mean:

The first layer of the above file rendered with the above program.

I would expect to have the entire thing filled from left to right, for example, and not in steps and patches because this provokes unnecessary distances for travel.

[bubnikv]

I have annotated the starts and ends of each of the draws, the ends are with apostrophes.

You see for example, that 2 is closest to 1'. There is another path close to 1', but it starts at the bottom of the unfilled region.

I am not saying that the current algorithm is perfect, only that it is more complex than it seems. The cost of trying to get a continuous line is seemingly a longer travel.

I can look into it once, but it is a non-trivial optimization problem.

[m-Th]

....also leave the program to show you at least the first 3 layers: you will see that for each layer there are separate paths (!). If you leave the simulation 10-15 minutes you will see very interesting things...

Why?

(The shape isn't complicated at all).

[m-Th]

Btw, isn't better to continue with 1' till end on the trunk of the object? ...perhaps you could try to optimize for minimizing the travel distances FIRST and after this for path lengths?

Anyway, the paths on which the machine is extruding must be done insn't it? (I know that we deal with variable speeds)

[bubnikv]

Btw, isn't better to continue with 1' till end on the trunk of the object?

Yes, this seems to be a weakness of the current implementation. I will have to think about that, this is a good example.

[m-Th]

Hmmm....

I am speaking now ONLY for the INSIDE of the object (the topic at hand) - outside is different (hence another Issue here: #409 )

We have the paths which are fixed. This is it. We only need to (re)order them in order to have the least amount of time spent with travel.

Hence you can use TSP (traveling salesman problem) algorithms to solve it, just to take care to adapt them to our problem. (we don't have points as towns, we have paths)

Some TSP implementations in C++ :

1. https://github.com/beckysag/traveling-salesman (this is better; an analysis for it is here: https://core.ac.uk/download/pdf/61220613.pdf - the authors did an implementation for Cura (!) )

2. https://github.com/samlbest/traveling-salesman

Some Tweaks (from top of my head)

• take care to put each path twice because the "salesman" can "travel" either to a node (start) either to the other (end). Take care to mark both copies of the same path as "visited"
• ban a "travel" on the same path
• in a classical TSP algo the start node for the next step/iteration is equal with the stop node of the current step/iteration. Here we need the start node for the next step to be the 'other node' of the path which is started with the end node of the current step/iteration. DO NOT forget to add the 'cost' (IOW time needed to print the path = distance / speed ).
• always calc the time (= distance / speed). I know that there are accelerations & other stuff but IMHO it is better than just calculating the traveling distance.

[DrLex0]

I agree with this issue, watching infill being printed with the newer versions, often makes me cringe. It doesn't look optimal in any way, because all the travel moves that need to be done after the initial maximized paths, tend to increase total print time and make top surfaces look ugly as well.
I don't care about the particular print order for internal layers as long as it is close to optimal, but for top surfaces I would like to see absolute priority go to printing the infill from one side to the other, with each patch printed in the same direction. Changing direction of the infill causes a visible difference especially with shiny or glossy filaments. This seems to have gotten much worse since one of the recent releases.

This is related to main Slic3r issue 3492 where I noticed that the infill in perfectly convex areas like ellipses is often printed in a similar incomprehensibly cumbersome way, with a big unnecessary travel move marring the freshly printed surface, to print a few remaining lines of infill that should have been printed at the start. I can still reproduce this in 1.37.2.

[bubnikv]

A similar issue / proposal: #519

[DrLex0]

I think your above description of the algorithm explains what I observed in issue 3492 (and still observe all the time in both flavors of Slic3r). When filling such elliptical shapes, the infill has considerably shorter lines at the edges, such that they are not considered part of the continuous zig-zag that fills most of the ellipse. The algorithm tries to make a long continuous path first, therefore it starts with the zig-zag, ignoring the short disconnected lines. Then at the end it fills in the missing bits, and this causes the awkward huge travel move all across the freshly printed surface, because as aptly described in the comments of 3492, “it has painted itself into a corner”.
This travel move costs time and mars top surfaces unnecessarily, and it bugs me every time I see it, especially on large objects. If the algorithm would be made a little smarter such that at least this scenario won't happen anymore, I would be glad to wait slightly longer on a slicing operation.

[joeynuggetz]

Bump

[m-Th]

...I think that after finishing the „Gizmo period” we should concentrate on making the printer (much) faster by having a true path optimizer.

[DrLex0]

I think this has much improved in the current master. At least the horrible travel move to fill in the systematically few forgotten lines at the other end of elliptical areas is now gone, and the infill sequence of the TUSH example looks a lot more sane.
I would still like to see an option to print all top infill in the same direction though, which would greatly improve the appearance on objects where it matters…

[bubnikv]

Monotonic infill is the default since PrusaSlicer 2.3.0-alpha1 for top/bottom skins.