Path planning may degenerate to merely sorting according to Y coordinates

[DrLex0]

Version

1.35.5

Operating system type + version

Mac OS X 10.11.6

Behavior

• In some cases, path planning will simply sort and print structures according to their overall Y position, instead of globally optimizing travel moves. The result is that the nozzle zig-zags horizontally across the print, using unnecessarily large travel moves.
• Steps needed to reproduce the problem
  • Slice the attached ‘HarioSkerton-standTry1.stl’ model with the attached settings.
  • Look at the result in a G-code viewer and check the ordering in which the Japanese letters are printed.
• Expected Results
  • The letters are always printed more or less according to the circular shape they are placed in, such that travel moves are as small as possible.
• Actual Results
  • The letters are printed in a top-to-bottom ordering and there are many undesirable large travel moves. When printing with a filament that has a tendency to ooze, this has a visible impact on the print, and of course it increases print time.

STL/Config (.ZIP) where problem occurs

Slic3rPathPlanningBug.zip
Here is where it gets really annoying and where I expect the first reply to be: “it works on my machine”. The first time I sliced this model, the problem was not there, see HarioSkerton-stand-good.gcode. Then, when slicing a slightly modified model with a few minor config changes, it suddenly started showing up, see HarioSkerton-stand-fail.gcode. One would expect that if I now re-slice the original model with the original settings, it will again look right, but no, it consistently produces the same bad result, even after rebooting the whole computer. During one of my attempts to find any sense in it, the sliced file had good planning for the first layer of the letters, and bad planning on the two following layers.

The good file was sliced with 1.35.2, and the bad one with 1.35.5, but this doesn't matter: 1.35.2 also consistently messes up the paths at this moment. It is a pity that 1.35.2 seems to omit some of the settings in the .gcode file, but my start G-code lists most of the missing ones anyway.

I don't know why I initially got a correct result and now a consistently bad result that I cannot get rid of. I have seen this bug before once, while printing this dualstrusion model, the smaller parts were also printed with the same suboptimal path planning.

The ZIP also contains a somewhat similar model that does not exhibit the problem, well at least not at this very moment…

Good:

Bad:

[DrLex0]

I have a better reproduction scenario, it always happens with the inlays in this dual extrusion model. Perimeters are printed with this kind of degenerate planning, the infill is OK (maybe not truly optimal, but at least it tries).
PokerChip-config-models.zip

[bubnikv]

I would say it is much better with the current master. The path planning aka "Traveling Salesman Problem" was improved to not to take the next closest point, but to
https://en.wikipedia.org/wiki/Multi-fragment_algorithm

Closing.

[bubnikv]

The change will be part of PrusaSlicer 2.2