[WIP] New Tree Support Implementation

[ThomasRahm]

I reimplemented the tree support, as the current implementation does not meet my expectations. It is currently work in progress and should not be merged yet.

How the new tree support looks:

How to use:

Settings can be changed in the GUI using this modified fdmprinter.def.json.

Settings:

Tree Support Preferred Branch Angle vs Tree Support Maximum Branch Angle

Tree Support Branch angle is ONLY used when Tree Support Branch angle slow is not enough to avoid the model. This causes branches to only move with "Tree Support Preferred Branch Angle" to merge with other branches.

Idea behind this is that Tree Support Preferred Branch Angle is a very stable angle, but if some parts could not be supported with the smaller angle the larger angle can be used to reach these parts.

This setting is named Tree Support Branch Angle Slow and Tree Support Branch Angle respectively in the screen-shots, but has since then been renamed to improve clarity.

Tree Support Diameter Increase To Model

Branches that can reach the buildplate and branches that cannot are able to merge. This setting limits how much the diameter of the branch connecting with the model can be increased by such merges.

This setting is intended to specify how important it is that connections with the model are avoided (the lower this setting, the less contact area with the model).

Small Diameter Increase To Model:

Large Diameter Increase To Model:

Tree Support Minimum Height To Model

If only a few layers space are left between the position where the branch begins and where it ends, removing the support is impossible. This setting removes all branches that have a height lower than "Tree Support Minimum Height To Model" to prevent this. Only branches that rest on the model are removed.

Small Minimum Height To Model:

Large Minimum Height To Model:

Tree Support Initial Layer Diameter

Branches try to ensure to reach this diameter at layer 0.

Large Initial Layer Diameter:

Small Initial Layer Diameter:

Tree Support Branch Density

A percentage of space that has to be filled by the top most layer of a branch aka the layer that supports the overhang. When a roof is supported the overhang is the line of the roof. When no support roof is used it behaves similarly to the supporting(top most) layer when using regular support. High values (Is depending on your other settings) of >35% can cause the resulting support areas to overlap. This causes cura to merge them to a single area, as cura assumes every support area is supported by support areas below. If a low support infill is used this assumption is wrong. There is nothing reasonable i can do to prevent this, so in this case adjust your support infill accordingly.

Simulate regular support pattern:

Tree Support Branch Diameter and Tree Support Branch Diameter Angle behave like in the current tree support implementation, but Tree Support Branch Diameter Angle is ignored when a diameter increase would invalidate a branch, as a small branch has a higher chance of supporting the model than no branch at all.

What does it do better:

Uses significant less filament.

Also makes my implementation much easier to remove from the model.

Current tree support:

My tree support:

Disclaimer: This is only the material used for support structures, not the whole model. The measuring unit is mm of 1.75mm diameter filament, as displayed in cura.

Can handle large branch angles.

Current tree support:

My tree support:

Supports Roofs more consistently.

Current tree support:

My tree support:

Branches avoid support blocker.

Setting applicable now on a per-mesh basis.

All tree support related settings are now settable per mesh and support related settings are correctly used by the tree support. This may increase slicing time drastically for settings that are not only relevant on the top most support layers. So to avoid slicing times being longer by factor 10 try not to slice 10 different models with different branch radii (Slicing 2 models with different should not take much longer than slicing 2 times). Trees with settings that are incompatible with each other can not merge and will avoid each other.

Few settings differences allow merges:

More variables of the regular support are now supported by the tree support

The newly supported settings are: Support Distance Priority, Support Horizontal Expansion, Support Interface Horizontal Expansion, Minimum Support Roof Area and Minimum Support Floor Area (was enabled in the UI, but did not do anything if i am correct), Minimum Support Area (though i would recommend leaving this setting at 0)

Slices faster on multicore cpus.

Measured was the time it takes to generate the tree support for the test model (hobgoblin).

Settings used for benchmarking: Profile for current treesupport Profile for my treesupport implementation

Further attributes this implementation has:

If a model is sliced twice, the same trees will result. If this is somehow not the case something went very wrong. Every point that can be supported with the given Branch Angle, will be supported when the support can only rest on the build plate. This means some settings may be paused to ensure such behavior. For example: Tree Support Branch Diameter Angle will be paused if a radius increase would cause a branch to become invalid.

How it works

This explains the idea behind the algorithm. As such it is simplified a fair bit to avoid explaining fixes for some edge cases.

0. The model

1. Calculate avoidance

An avoidance is an area that has to be avoided to achieve certain given results. For example an area in which a branch would be unable to reach the buildplate has to be avoided, if the support is not allowed to rest on the model. This idea is identical to the current tree support. My implementation just uses a lot more avoidances(slow, fast, slow to model, fast to model, fast without holes, fast without holes to model), and precalculates them in parallel. Avoidances are calculated from the bottom up.

2. Generate influence areas

An influence area is an area,in which every point of the represented current branch, can reach all support points it has to support. Is is similar to an avoidance, but other that the avoidance, it represents possible center point areas, rather than excluding impossible ones. If two influence areas intersect, only the intersection will be used going forward. This causes branches to merge. Influence areas are calculated from the top downwards, as they grow from the overhang downwards.

3. Generate tree path

Using the influence areas, the center points of the circles that build the branches are set. This happens from the bottom up.

4. Draw Tree

The circles, which center-point was calculated in 3. are drawn. Here also happens a fair bit of post processing to avoid edge-cases by the fact that the drawn radius in the tip of a branch is always increased (for stability reasons), even if a normal circle would not fit.

Things to do:

Formatting for long lines and a bit more documentation. Public beta-testing.

Possible future improvements:

Automatically increase branch height when the angle is large.

Further Information

I did not make the mini hobgoblin i used to test. I used it because it cloak makes it very hard to slice in a way that the cloak is supported while not having a connection of the branch to the model. All screen-shots of the current tree support were made using version 4.7.1. Thank you to a friend of mine, for providing the images explaining the algorithm and creating the graphs out of the performance data.

[Ghostkeeper]

A couple of comments while you're working on this, to address the questions you've posed and some concerns:

• Code style and naming conventions for C++ is a combination of the Generic Code Conventions of Ultimaker and the exceptions/expansions of that geared towards C++.
• New settings have to be added to fdmprinter.def.json in the front-end. Here are the changes that originally introduced tree support, as an example. If you're on Windows you can edit that file in your Program Files to test. For Linux and MacOS that file will be packed inside the application file, which is a little harder to modify sometimes. It's also pretty easy for us to fix if you need some help.
• This is a big pull request. We're talking several thousand lines of code here, a few new features as to customisation on how the branches are generated, and refactoring. This goes against some of the etiquette on how pull requests are presented. It's not necessarily a problem, but you have to understand that this is seriously hard to plan into a schedule. It also imposes serious risk for us: There are likely going to be new bugs in this code (unavoidable) and once we need to debug this, we are going to be less familiar with this code. This makes it harder to approve of a pull request.
• The collision volumes were originally implemented with the same technique as what you're doing now: Multi-threaded generation of the volumes at different radii. It's still supposed to be multi-threaded, but it now lazily generates them in order to reduce the total amount of work, rather than pre-generating them. We did performance tests when this was implemented to compare performance, using different sorts of computers (few cores vs. many cores, old memory and new memory sticks) and different sorts of models (tall/small, organic/artificial) and found improvements for the most common cases.
• We've learned to avoid creating settings for every little thing that could be adjusted. If nobody is going to adjust a setting, you might as well not have the setting. This makes a feature less overwhelming for someone who is not so involved in Cura or in your feature. From your description for instance I wouldn't know why people would want to adjust the support_tree_angle_slow setting or why they'd need that much control over the resolution at which the collision volumes are calculated.
• Normally we prefer to have only one implementation of a feature. This is something that our users sometimes don't like (e.g. when we replaced the Prime Tower implementation), but it's important for the developers to be able to maintain an application with as many features as Cura. We're 6 programmers working with 2.5 million lines of code here, so we try to prevent having to maintain 5 different implementations of Tree Support that we added over time, so to say. For that we must be sure that the new implementation is capable of filling all the use cases of the old implementation. If some use cases are still possible but less than ideal (e.g. increased printing time) that may be acceptable.
• For Cura 4.7, Tree Support is getting particular attention to try to get it out of the Experimental section. You might see some merge collisions and it might even alleviate your concerns as to why you decided to rewrite it.
• That problem you found with the bridge settings adjusting the line directions is known and currently accepted. It's hard to ensure that the line directions of support are always perpendicular because that involves breaking up the support into zones with different line directions which is not beneficial to the strength of the supports or the quality of the overhangs either. I'd say that your fix is not proper then (as you describe it) because it would cause it to go wrong in different cases then.

We didn't review your code yet though. This is only a reaction to the description you posted on the pull request.

[ThomasRahm]

Thank you for your feedback.

Regarding the bullet points:

1. Thank you very much, i will change my code over time as soon as i have time for it.

2. Thanks, i did not know it was this easy :) I added a preliminary settings file to my description above.

3. I understand. One of my main reasons to open the draft was that a friend wanted to be able to share the resulting binary with a friend, and i did not feel comfortable sharing it without publishing the source.

4. I suspect the difference is that i only calculate the collision volumes up to the highest required layer, so collision volumes with a high radius may only be calculated for a few layer, instead of for the whole model. I am sure though that currently the lazy generation does not happen multi-threaded as i believe the comment:\warning This class is NOT currently thread-safe and should not be accessed in OpenMP blocks in TreeSupport.h.

5. I agree and have reduced the amount of available settings.

6. I did include the old implementation only because i believe every change breaks someones work-flow, and i did try to avoid that. My implementation aims to behave superior in every way and be a complete replacement. As such i now removed the old tree support.

7. I am happy to hear that tree support gets extra attention in 4.7, and will try to ensure my implementation remains superior ;) I do not expect to be done with the documentation before its release as my exams are at the end of the month.

8. I feared as much. This means i will have to check whether a skin area is a bridge, and what the line orientation will be. I will have to investigate how to get to this information.

[Ghostkeeper]

I did include the old implementation only because i believe every change breaks someones work-flow, and i did try to avoid that.

True. It's a concession we've needed to make. Our position on it has so far been that those people can stick with the old Cura version if they liked the workflow that one provided, rather than trying to pack all dozens of Cura versions in one release.

[Ghostkeeper]

On point 8, honestly it's probably easier on yourself and on the code base if you drop that feature! It's not in the expected behaviour now, and while the result will be better in the short term, if that makes the code harder to maintain in the long term it's also going to hurt. So you're welcome to try fixing it, but keep in mind that code complexity is something we'll look at too.

[ThomasRahm]

Hi, i would like to release a version with my tree support implementation for others to be able to beta test it. For this i would just upload a zip with a complete compiled cura with the treesupport replaced to the release section of my github fork. I already modified the version from 4.9 to 4.9_TS2 to avoid issues with cached definitions. Is there some issue with me doing it this way?

[Ghostkeeper]

No, I expect that would work fine. Maybe choose carefully which operating system(s) you'll release on.

I wonder how you'll know that your Cura version is being used, though? If you get no bug reports, is that a sign that it's bug free, or that nobody found your version?

[Ghostkeeper]

I should also say that reviewing and testing 5000 lines of C++ code is no small task. Might take quite a while to get that in, especially considering there is not going to be any push from our managers to merge this, I expect. It kind of hinges on us being able to explain well why this change is necessary.

[ThomasRahm]

Thanks for the response :) I currently plan to post a link to my treesupport version on reddit. I hope that the post will get enough attention, so that i can get feedback and bug reports to evaluate the situation in addition to enabling my treesupport to show its worth. I plan on releasing for windows only, as im going to assume that linux users are more likely able to compile it themselves. I dont know yet when i will have enough time available to be able to all this, as i want to be able to fix potential bugs fast when they come up, though i hope to find time within a month.

[chrisvanderpennen]

Hey, I've been using the fork for a few months and I'm very happy with the results, particularly for printing miniatures - to the point where I'm keeping it installed alongside the main Cura release specifically for minis.

I find the current tree algorithm tends to produce thick walls of merged support branches, that are difficult to separate and remove without damaging the model. This new algorithm instead converges quickly to single thick branches, which can very easily be clipped and separated.

[ThomasRahm]

Sorry for the late response, git-hub did not send me an email notification, for some reason i still have to figure out. To my knowledge i did no changes in the Polygons class.
I currently only changed TreeSupport.h andTreeSupport.cpp (and after the 5.0 update algorithms.h as i need a #pragma omp for nowait replacement and a few lines in support.cpp to keep emulated support lines from splitting into two). Any other changes should come from me merging the different release branches.
Any commit changing some file, other than these was accidental and i will try to get rid of them when updating to 5.0!

[ThomasRahm]

Hi, When should i change this pull request from draft to regular? I think in the current state my implementation is better than the current tree support, but there are still some further improvements possible regarding pointy overhangs, which fail more often than i would like, and branches getting too thin when moving very fast (>65°).

[casperlamboo]

Hi @ThomasRahm,

Thank you for you contribution. We are very much interested in including your improved tree support in our 5.3 release. As soon as the merge conflicts are resolved the [WIP] can be removed and we'll start reviewing.

[ThomasRahm]

Ok, i resolved the merge conflict.

While reviewing please consider that all todo LayerIndex are that the cura::parallel_for should be used with the template type LayerIndex, but that does not work as this function uses distance, which is not defined on LayerIndex and i did not want to change cura::parallel_for. So as a workaround i used coord_t as type instead.

[casperlamboo]

Thanks for resolving the merge conflicts! I'm planning on starting the code review this week. In the mean time, can the [WIP] status be removed from the PR?

[ThomasRahm]

Please note that this PR also contains #1671.

[rburema]

@ThomasRahm Since we think this is a very valuable improvement on the one hand, and a big change on the other, that, after discussion with the team we've decided that it would be best to release this as a 'spotlight' beta based on 5.2.x to both promote this and have some extra beta-testers during the holidays even before the normal 5.3-beta period starts (probably sometime next year).

(I've taken over the review from @casperlamboo for the moment.)

Our question to you is, would you be OK/comfortable if we put this contribution in the spotlight like that to the community?

[ThomasRahm]

Sure. I already have a version on my github page where people using windows are able to try it out, but i wasn't able to compile for Linux and know of at least one person using Linux that would like to try it out, so having a spotlight version that everyone can use for testing sounds great.

[ThomasRahm]

I just fixed a bug that can prevent some support from generating for overhangs (with a smallish overhang angle e.g. 60°), that is noticeable when the support distance priority is z_overrides_xy (otherwise the support could be further down for overhangs smaller than 90°)

The change in TreeSupport.cpp to the extra_outset is to prevent differences in supported areas between a tip diameter of one line width compared to two line width tip diameter.

Ps: In the branch where you do the formatting i think found an error in the file TreeSupport.cpp line 299 (getEvaluatePointForNextLayerFunction). (The link does not automatically go to the selected line)

The function will be returned, as such capturing current_layer and xy_overrides by reference will cause issues, as when the function is executed, the references will no longer be valid.

[rburema]

Thanks!

Good timing, I was just about to point you to that branch so you know what's going on when I saw this come in (... or, well, 6 hours ago).

I'll switch it back to by-copy (instead of by-reference) for the bug I introduced.

I'll try to cherry-pick the bugfix for the other bug as well to that branch (We're basing the alpha on 5.2.x, so people don't see all the half-finished 5.3 stuff we're still debugging.)

[ThomasRahm]

I wanted to ask what why the support_tree_bp_diameter was disabled in the UI. The other two that were disabled were settings that my tree support does not use (support_tree_branch_distance and support_tree_collision_resolution)

I personally use support_tree_bp_diameter a lot to improve adhesion with the buildplate (with enabled support brim) as especially for small models, having a small branch radius, but still having a large connection area with the buildplate can be beneficial.

[nallath]

I just talked to our print process engineers, and they indicate it was disabled because they didn't notice any change when increasing/decreasing the setting. So I assume that something in the refactor might have broken it.

We're going to investigate a bit more how it broke!

[ThomasRahm]

Hm, you are correct, something broke though this was not caused by your re-factor... Here is a comparison of what it should do: Small Initial Layer Diameter Large Initial Layer Diameter

Thanks for the bug report, i will get back to you on this.

[rburema]

Though I do see it change something (even) from the current source -- I'm not sure now on what build PP&M based their conclusions :-/

• I ~propose we~ have re-enable(d) it in any case. In the worst case we have a setting in the xmas-alpha that does nothing after all.

[ThomasRahm]

Update: The setting works when support type is Touching buildplate or the rest preference is Buildplate, as when the rest preference is On any flat surface the branches do not know if the will rest on the buildplate or on the model and because of that the radius of the branch will not be increased (to not needlessly increase the contact area with the model).

[jellespijker]

@rijkvanmanen and @pkuiper-ultimaker FYI

[ThomasRahm]

The issue is that On any flat surface is implemented by never using the regular avoidance, just the avoidance to model (as logically a branch can further down choose to rest on the model instead), and the initial layer diameter is no increased when a branch is not known to rest on the buildplate .

Possible solutions are:

1. Changing avoidance to model to not include the buildplate and then calculate avoidances by unioning the to model avoidance without the radius increase with the to buildplate avoidance with the larger radius. Downside is that these hybrid avoidances cant be pre-calculated, so there would definitely be a performance impact and this would take quite a bit of work.
2. Just increase the Collision Radius if possible, and when it turned out that it rests on the buildplate set a flag to also increase the radius. Easy to implement, but has the downside being that branches may go to buildplate as they can no longer rest on the model because of the increased collision radius.

I implemented the second option. When the initial layer diameter is reasonable the downside may not be obvious, but there can be an argument made to document this behavior somewhere (E.g. in the description of rest preference: A large initial layer diameter can cause branches to rest on the buildplate (instead of the model))

P.S. I noticed that there could be cases where the fix could cause issues when a branch that can go to the buildplate, which radius was already increased, merges with a branch that rests on the model, as the resulting branch will rest on the model causing a possible jump in radius. I will solve this at some point, but it may be better to not include the the above mentioned fix in the spotlight beta as it will probably be after Christmas by then.

[rburema]

@ThomasRahm The spotlight will be an alpha even, so there's still time to fix some bugs! [The 5.3.x release itinerary is now: 5.3._-xmas-tree-alpha (-> merge that into an actual 5.3 branch) -> 5.3-beta -> 5.3.0 final]

Something slightly different: @rijkvanmanen & I had an investigation into an unrelated (support) issue, and (as a side effect) it turns out the default mitre parameter for the clipperlib 'offset'-operation, jtMitre gives terrible results (can be asymmetrical for a symmetric model even). That could be the cause of at least some of the 'rounding errors' you're seeing. We where originally OK with that for CuraEngine, since it results in cheaper operations, but it seems its wrong (or at the very least gives counter-intuitive results) in many instances. In our (unrelated to tree) experiment yesterday, we had good results with jtRound (though no clue yet how much slower that will make the code overall -- or if we could also use jtSquare instead).

[ThomasRahm]

I already use jtRound in most places. jtRound is a bit slower, but not by too much. Most performance impact comes from the fact that the resulting Polygon has much more vertices, so calling simplify from time to time is essential. In increaseAreas there is even a line that effectively uses a jtRound offset twice, as a single round offset still had issues for very small influence areas (with few vertices). There may be an argument made to change the ones that don't use jtRound to jtSquare or jtRound. All offsets directly related to influence areas or avoidances should in my opinion stay jtRound, as non-accurate offsets can cause disappearing branches (in other words, cause an influence area to disappear).

One reason why the jtMiter may not work as expected for you is that the default miter limit of 1.2 is actually a miter limit of 2.0, as clipper has an internal minimum for it.

I think the reason for me encountering so many rounding errors is that sometimes influence areas can become very small (i definitely encountered areas smaller than 50 square-microns consisting of only a hand-full of vertices in the past, but hope i mellowed down the tendencies for that small influence areas) causing me to run into some rounding errors that are part of clipper and some that are unavoidable as sometimes the difference between an influence area that works fine and one that causes errors can be few microns in width.

Furthermore, in the known issues you listed "Support Interface are not always working corretly". Can i get an example for this ?

Also i have seen the commit https://github.com/Ultimaker/CuraEngine/commit/3c4180381b8ecf503c299cf65b442a2ccd58726 and i think i see the reason. When the rest preference is on any flat surface the regular avoidance is not precalculated, as it will not be needed. So if it is then requested before the loop, it then will be calculated on the fly, which may take a while if it works correctly (The calculating of avoidances when needed is not very well tested, as it is just a fallback for when an error occurs). If you have a case where it actually deadlocks (and not just takes minutes instead of seconds), i also would like an example, as this should not be happening.

[rburema]

Thanks!

I should have remembered you already mostly using jtRound. Rijk also pointed out the 1.2 thing as well. I'm not sure that's the problem though. I suspect they put it that low because the higher parameter was already causing the sort of problems we're still seeing.

---

About the known issues:

Furthermore, in the known issues you listed "Support Interface are not always working corretly". Can i get an example for this ?

This is what QA came back with when testing:

When Interface priority is set to preferred, there is missing interface for some branches.

The interface should follow the model, not the support.

---

About the last minute bug fix:

Also i have seen the commit https://github.com/Ultimaker/CuraEngine/commit/3c4180381b8ecf503c299cf65b442a2ccd58726 and i think i see the reason. [...] If you have a case where it actually deadlocks (and not just takes minutes instead of seconds), i also would like an example, as this should not be happening.

Ah, yes, that makes sense. The model that took long enough to convince me to write it down as 'deadlock' (even though I didn't do a thorough investigation yet, so it isn't confirmed -- we where trying to get the alpha out yesterday when this came up as a last-minute bug), is this: possible_deadlock.zip

[rburema]

P.S. Coming to think of it, it probably isn't a deadlock, at least not in all threads, as it was still spamming the logs full of warnings.