Feature Request: Optimize Fill Operations to Reduce Travel and Stringing

[LuckyResistor]

Problem

With the PrusaXL and larger prints, I've noticed a flaw in the algorithm that orders the operations for internal fill, solid infill, and bridge infill. The current algorithm tries to connect as many operations into a single continuous line as possible, often leading to suboptimal results. It frequently omits many tiny islands that need to be finished afterward, requiring long travel movements across the part and leading to stringing.

In the example below, the algorithm starts the fill near the seam, continues from bottom left to top right, leaving a large island behind after the first printed infill line. While it continues joining all infill lines, it leaves small gaps marked with numbers. After reaching the far end of that line, it has to backtrack to the small patches, using long travel moves and dragging fine strings of filament over the part. While stringing can be reduced with perfectly dry filament, some materials like PETG still tend to leave short strings behind.

As this issue repeats layer after layer, the fine strings accumulate, melt with movements on upper layers, and sometimes leave blobs and imperfections that are time-consuming to remove from the final print.

Another example illustrates unnecessary long travels across the part because of gaps left in the infill:

Proposed Solution

We can avoid these small islands by changing the ordering or joining algorithm in the slicer software, at the cost of very little additional print time. This problem can be addressed using graph theory, specifically related to the Hamiltonian cycle.

1. After generating all lines for a layer, a graph algorithm shall optimize their order.
2. Group the lines into continuous patches that form a node in the graph.
3. Nodes with closely located lines (e.g., < 2mm apart) are directly connected in the graph.
4. If all lines in a node are printed, it cannot be traveled again, blocking access to any neighbors.
5. If the graph includes a case like this (e.g., a leaf node), the neighbor node (continuous line) must be split into two nodes at a suitable spot, allowing the isolated leaf node to be inserted into the path, preventing an island.
6. By iteratively resolving issues with isolated nodes and streamlining the graph into a linear path, the print process is optimized to minimize stringing.

Proposed Integration in PrusaSlicer

This optimization should be an optional step, similar to "Avoid Crossing Perimeters," as it may slightly slow down the print.

Impact

Optimizations like this are expected to have minimal impact on fast printers like the PrusaXL or PrusaMK4 but will increase print quality, reduce issues, and decrease post-processing time. The slightly increased energy costs for the 1-2% longer printing time are negligible compared to the increased labor cost for fixing small issues on the print.

[robustini]

100% agree, there is unfortunately much more focus on speed than final quality, and this is a very good proposal.

[Flyingvette]

You are absolutely on the mark and I suspect that many do not realize how bad of an issue this is. I currently have a complex print that has failed multiple times due to this travel, and it causes a significant amount of extra print time and then post process work dealing with excessive stringing and blobbing solely due to the extruder passing over the entire print multiple times for no good reason. I don't know if your solution is the correct one or not, but any attempt to fix this would be extremely welcome. It seems to be the worst when dealing with islands of multi extruder driven work that border different sides of the objects primary mass / bulk. Might be worth putting up a forum post to get more attention on it if you haven't already.