Inefficient grid generation in TreeSupport::generateContactPoints

[bjude]

The grid generation in TreeSupport::generateContactPoints() claims to be creating a grid pattern at an angle of 22 degrees but what the code actually does is different.

The code as it stands:

• take the model bounding box and rotate it 22 degrees
• take the AABB of that rotated box and rotate it back 22 degrees
• create a grid of point across the AABB of the re-rotated box
• rotate those points 22 degrees and translate them to the model coordiantes

This is wildly inefficient and means that the box that the points are generated over is 1.7 times bigger in each dimension (for a square initial AABB). This is easy to fix and i can generate a PR if desired.

However, i have another idea for point sampling that will be more efficient still. The comments state that the 22 degree rotated grid is employed so better support diagonal lines, which presumably are likely to fall between the lines of an aligned grid. But this just shifts the problem to poorly supporting lines that are 22 degrees rotated (which may well be uncommon but we're not really addressing the real problem this way).

The sampling problem could be addressed by using a low-discrepancy sequence like the Halton Sequence to generate 2d points This could either be done by simply generating a sequence of Halton points across the entire AABB until the density is sufficient (eg mean distance between points is support_tree_branch_distance) or by splitting the AABB into a grid and generating a smaller sequence of Halton points in each grid cell. Both approaches should fix the issue of having "channels" of empty space through the grid.

[rburema]

Hi @bjude, Thank you for your report.

As you've noticed, TreeSupport is a relatively new area of the code, with many possible future optimisations. The option as a whole is still in the 'experimental' part of the settings, and there might be relatively large changes to that part of the code base still to come.

Moreover, as you've already mentioned as well, the grid generation will only run for 'generateContactPoints', which only runs once for each branch of the tree. Right now, if we where about to fix inefficiencies in TreeSupport we'd look into the parts of the code which run for each layer.

That said: If you, or anyone else in the community wants to create a PR, please go ahead. However, our attention is required elsewhere at the moment.

cheers, Remco.

[bjude]

Thanks for the reply Remco.

While it does only run once per branch, it causes 190% more point-polygon intersection checks so by fixing this we could go for much higher precision at the same computational effort.

I figured being an experimental feature might mean its in flux internally at Ultimaker so didnt want to step on anyones toes by submitting PRs without raising an issue first. I really like tree supports compared to traditional grid supports for small models and I've got a few ideas for improving the code and am happy to submit PRs for them in the next few weeks once work calms down a bit.

[rburema]

Hi @bjude, While we might indeed change it before it moves out of experimental, I don't foresee we're going to work on tree-support in the next few weeks, so go ahead. I'll tag @Ghostkeeper just in case there are any issues I'm not aware of. cheers, Remco.

[Ghostkeeper]

The sampling problem could be addressed by using a low-discrepancy sequence like the Halton Sequence to generate 2d points

Honestly this is the sort of idea that I am really thankful for to have a smart community that can come up with ideas like that.

[Ghostkeeper]

This is fixed by the issue reporter himself: https://github.com/Ultimaker/CuraEngine/pull/869

So thanks!