Bug: Auto-arrange moves object off of build plate even when valid

[coreyward]

Version

2.3.0-rc2+

Operating system type + version

macOS 10.14.6

3D printer brand / version + firmware version (if known)

Prusa MK3

Behavior

Auto-arrange seems to have a bug. In some scenarios it will move geometry off of the build plate despite being possible to fit, even considering spacing and rotation settings. Increasing the auto-arrange spacing results in the correct behavior, as does reducing it to zero. Here's an example of the problematic behavior:

https://user-images.githubusercontent.com/81224/103426769-6d353500-4b81-11eb-9d40-7f76c1076692.mov

Project File (.3MF) where problem occurs

Auto-arrange bug demo.3mf.zip

Spacing values > ~8 work fine, but values in the range 0.01–7 result in erroneous behavior.

[timur-tabi]

Did you try reducing the minimum spacing between objects? You had the option pop up when you right-clicked on the Arrange button.

[coreyward]

@timur-tabi As I mentioned and show in the video, the objects fit with more spacing than is specified in the slider. Reducing the spacing to 0.01 produces the same issue, but reducing it to zero places the objects on the build plate (albeit with lots of space around the outside). I.e. this is a bug.

[coreyward]

Fiddled around with it some more and found that increasing the spacing results in the objects being arranged on the build plate as expected. Updated the original post to reflect this finding.

[tamasmeszaros]

This is an edge case where the arrange algorithm is uncertain about the placement order of these items. They occupy just about the same 2D area. With zero distance (no inflation applied) the square items are a tiny bit bigger than the rectangular item and are placed on the bed earlier. With some offset applied, the rectangle becomes bigger than the square items, and is placed first, then the next is the square, which is placed under that in the center, leaving no place for the last square... game over for the last square. I would not consider this a bug, as the algorithm performs as expected.

To produce better results in this case, a deeper search would be needed (was discussed here on Github), that might become a feature one day.

[coreyward]

@tamasmeszaros Why does it work with larger spacing? Does that result in less ambiguous ordering?

A naive rectilinear-boundary based grid-fill algorithm would result in improved behavior and would be cheap. Perhaps an improvement would be to add it as a fallback routine if the current algorithm has too many edge cases or isn't amenable to refinement.

In any case I'd label this a bug—the algorithm might perform as expected from a development point of view, but from a user standpoint the contract is broken.

[tamasmeszaros]

@coreyward It could work with larger spacing because that is realized with 2D inflation provided by the clipper library (they call it offsetting). That enlarges the given shapes appropriately but can alter the geometry of the original shapes ever so slightly and given that the two shapes on that scene are very close in 2D area, any offset can change the ordering, depending on the outcome of the inflation procedure.

I understand that this is a deficiency that renders the feature unhelpful in this case. We will address it (and many others) in some way or another. What I'm saying is that it requires additional logic and heuristics to be designed and implemented.