Regression: "Arrange" function got worse

[RichiH]

Description of the bug

While Arrange was never perfect, it used to be better at autoplacing than the current version. See the automatic arrangement:

versus manually arranging:

or even:

While I understand that binpacking is an NP-hard problem, there's a trivial approach if the objects are all the same: Try quadratic arrangement as per photo or ideally offset as per second screenshot. The same could be tried for other similarly sized objects, first.

Project file & How to reproduce

Import a bunch of STLs and click arrange

Checklist of files included above

• Project file
• Screenshot

Version of PrusaSlicer

PrusaSlicer-2.7.2+linux-x64-GTK3-202402291307.AppImage

Operating system

Debian unstable

Printer model

Prusa XL

[RichiH]

CC @pstrobl96 because you asked for this

[pstrobl96]

I have tried multiple older versions of PrusaSlicer. Obviously algorithm is non-deterministic and it's struggling when multiple smaller prints are on the bed.

[RichiH]

As an update, the "I didn't have this problem before" stuck in my head... After more debugging, it does not seem to happen with the Mk4 or Mini, only the XL. So maybe the total size is part of the issue?

[u89djt]

Don't forget to reduce the spacing parameter to the best you can achieve by right clicking on the layout icon. I seem to be ok with 0.44, which is the best I can hit with my mouse. That value also applies when you take a single instance, right click and choose "fill bed with instances".

I guess with the popularity of maker coins, it might be worth hard-coding the coordinates of good packings available for circles in a square for the XL plate.

This site provides coordinates for packing up to 10000 circles into a square in a handy format "All coordinates of all packings":
http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html
I guess we don't need more than 6 significant figures realistically?

It also provides near optimal paths spanning the instances, "All optimal TSP tours", but they're distributed across pdfs in the single assembly of all of them, but they're available individually in plain text, e.g.
http://hydra.nat.uni-magdeburg.de/packing/csq/tsp/csq83.tsp
If there's any interest in doing this, I can assemble all of these, dig around a bit more, or email the author and ask if they have an archive already. Since the extrusion layers of all the instances - if not rotated, as they don't need to be - start and stop at the same place, that will provide a good printing order. Obviously the path could be followed forward for one layer, then reverse, then forward again and so forth. 83 appears to be a closed loop, though - I haven't looked at whether this is the rule for all of them.

It looks like with 0.44mm gap between objects but not at the border, 83 40mm discs could be fit on the XL plate. Let me know if I flubbed the arithmetic.
http://hydra.nat.uni-magdeburg.de/packing/csq/csq83.html

The magenta discs /look/ like they're free to move, but I speculate that their position is or could be chosen to minimise the tour length. Looks like they're referred to as "rattlers" https://groups.google.com/g/sci.math/c/702XyjRLaG0

[u89djt]

@RichiH @pstrobl96 I kept going and published a couple of bed layouts: https://www.printables.com/model/815386-xl-bed-disccoin-packings-83x40mmclearance-and-35x6
I didn't include your specific object in that post, so here it is:
83-grafana-coins-on-XL-bed.zip