Tree support uses more material than necessary

[lukehutch]

Application version
4.7.1

Platform
Linux Fedora 32

Printer
AnyCubic i3 Mega

Reproduction steps
Enabled tree support
Sliced (0.1mm)

Screenshot(s)
(Image showing the problem, perhaps before/after images.)

Actual results
Slicing this model with tree supports leads to extremely wide supports, which requires a lot of material and time to print. A lot of the support material ends up being printed as vertical walls, with several nested interior shells also printed as vertical walls. This is not much better than the regular support system.

Expected results
Since an overhang threshold angle of 45-60 degrees is supported on most printers, the supports could be much thinner in diameter, and therefore use less material.

Project file
https://gofile.io/d/1jNXd8

Log file
Let me know if you need this.

[Ghostkeeper]

We won't need the log file for this. The project file reproduces the issue in this case.

This is a global optimisation problem. The algorithm currently generates from top to bottom and only looks locally for how it can reduce the amount of support needed while still creating somewhat stable support. Optimising this globally would be very expensive to compute. In the case of this print, it would require looking ahead at the lower layers, seeing how big those layers become (due to the new branches near the ankles of Nike) and trying things to already move ahead towards those positions on the higher layers. This is an exponential problem of possibilities so it could explode the slicing time from 2 minutes to anywhere between 5 minutes and several years, depending on the model and the heuristics chosen.

The current algorithm basically works as follows. First it's going to create the minimum spanning tree for all of the branches in the layer. The minimum spanning tree connects branches together in such a way that the total length of the connections is minimised. You can sort of see the shape of the minimum spanning tree when the branches start getting closer together:

Each branch is then moved to the average position of all of its neighbours. This reduces the size of the minimum spanning tree and therefore also the amount of material printed. If this causes branches to come very close together, the branches are merged together forming one single branch.

In your print there are branches merging in from the back, due to the tip of the wing. These branches are collapsing together very closely from both sides, and thus the average position of each branch's neighbours moves very slowly. It's only when the big branch coming in from the base of the wing is merged that the cluster at the tip starts to move towards the rest of the print. And that's a long way to go.

I think collapsing neighbouring branches earlier would help to speed things up, since the neighbouring branches wouldn't stay in position, spaced out evenly just too far to merge. But merging them could cause a jump in the outline of the support as a branch suddenly falls away. There are some opportunities for improvement I think, but it won't be trivial.

(For the purpose of the screenshots, I reduced the infill density to 0% so you can see better what the actual outline of the support is.)