Add Monotonic infill pattern, like in Prusaslicer alpha (2.3.0)

[Ntrino]

Is your feature request related to a problem? Please describe. Yes, when a hole is going through the top layer, the infill pattern creates a visible line stemming from the hole, not following the path of the rest Monotonic infill pattern, like in Prusaslicer alpha (2.3.0) seems to solve this problem

Left - Cura | Right - Monotonic infill pattern (Prusaslicer)

Describe the solution you'd like Adding the same Monotonic infill pattern feature that Prusaslicer alpha (2.3.0) has

Describe alternatives you've considered No other settings in Cura seem to address this issue

Affected users and/or printers I would assume everyone

Additional context Please add it : )

[Liger0]

That would be an awesome addition applied on the optional "Top surface skin layer". I'm not sure if it increases the printing time, in which case leaving the basic top layers printing with the old pattern is more convenient. Maybe it would also be useful for the very bottom layer.

[rburema]

We've made a ticket on the backlog (now known to us internally as CURA-7928), but have not prioritised it yet.

[smartavionics]

I have added a monotonic skin lines setting to my latest release https://github.com/smartavionics/Cura/releases/tag/20210214. It's not a sophisticated implementation and doesn't attempt to minimise the travel moves required but it does appear to work. If you try it out and have any feedback, please open an issue at https://github.com/smartavionics/Cura rather than commenting here.

[Minner1337]

I would also love to see this in an official release. +1

[gohigher14]

This is such a super option to have on cura. Prusaslicer slicer has this already , so please add this also to cura. That's would be a great improvement.

[kylane]

@rburema - Has it progressed in the priority list as yet? Really need this.

[smartavionics]

Still available at https://github.com/smartavionics/Cura/releases :)

[rburema]

@kylane We discussed it in refinement with the team today. It seems we do really want this. Don't count on it for the next version though.

[TheAdamWoods]

Another bump for this. Would be awesome.

[nallath]

No worries! I expect that we will start on this in a few sprints.

[KodeMunkie]

@smartavionics Cheers dude, I'm trying this build today. Hope @nallath is talking about merging your fork rather than re-inventing the wheel :)

[smartavionics]

Sorry @KodeMunkie , it will be up to UM to implement as I no longer contribute new features to UM Cura.

[ahernsean]

@smartavionics That's a big loss. You contributed some significant and useful features to Cura. Your efforts will be missed.

[smartavionics]

Thanks @ahernsean, I'm glad to have been useful.

[stmcculloch]

@smartavionics Your fork has solved my issue, thanks so much! I need to use Cura to print production-quality parts. I don't know why the Cura team is waiting to implement monotonic top surfaces. It makes a huge difference.

[TheAdamWoods]

Thanks @ahernsean, I'm glad to have been useful.

Another grateful supporter. Your build is awesome.

[nallath]

This ticket is in our Current sprint, so we are currently working on the implementation.

[nallath]

Sneak peak!

[nallath]

Both of the PR's have been merged, so it's my great honor to close this FR!

The 4.11 BETA will be around soon and will contain the changes.

[smartavionics]

Well done for getting this implemented, your users will be happy.

I just merged your master to compare with my implementation and find in a quick test that the output appears monotonic but it's doing more travel than perhaps it should. FYI, I attach a sample model file and the gcode produced using mb and um monotonic skin implementations. All other settings are identical. Hope this helps.

monotonic_feedback.zip

[smartavionics]

I should add that my monotonic ordering algorithm only tries to minimise the travel distance to the next sequence of monotonically printed lines, it doesn't make any effort to come up with the optimal order in which to print the sequences. As such, I consider it a naive implementation.

[KodeMunkie]

Out of interest Is this just a special case of the travelling salesman problem? If so, has any particular algorithm been implemented (in both implementations)?

[smartavionics]

My take on this is that you need the ordering to be cheap (timewise) because there can be a lot of lines to order when the skin contains many holes or has a complex outline. So my approach was simply to minimise the travel distance between the last printed sequence of monotonic lines and the next sequence to be printed. I guess that you could have a setting that enabled optimal ordering of the sequences for those people who don't mind it taking longer to slice. I'm not going to be doing that but maybe UM could in the future.

[KodeMunkie]

For future optimization, as this does appear to be the travelling salesperson problem, the accepted best effort solution to minimise processing (Vs brute force) and distance is a branch and bound algorithm - the wikipedia article has a nice plain English implementation https://en.m.wikipedia.org/wiki/Branch_and_bound

EDIT: This is probably useless given the travel between points needs to be directional not optimal.

[smartavionics]

Here's some screen shots that show the travel moves on the first layer...

mb-master

UM

[rburema]

Some notes from our perspective on this:

• One other thing (unrelated to the travel between sections) that should perhaps be mentioned is that in version 4.11 monotonic behaviour will by default be off initially. (So you'll have to enable it manually if you want it.) For versions after that, we're looking at making it the default for at least some profiles. We did it this way to give our materials team more time to test this, but not delay this feature any further.

• Travel optimization (between sections) was out of scope for this time. We might take a look at it after Arachne has been merged into mainline CuraEngine, since the way some data-structures work has changed there, which especially impacts the path-optimization, of which monotonic is one type ... in fact, we purposefully built the current monotonic optimization to be future-compatible with that merge.

[m-sundman]

Travel optimization (between sections) was out of scope for this time.

Is there an issue created for the monotonic line travel optimization feature, and if so, what's the issue number?

[rburema]

Hi @m-sundman thanks for mentioning it! As a result, we've now made an internal ticket for this (other devs see internal ticket: CURA-8474). We don't expect it that soon though, as the current code is set up in such a way to be relatively easy to merge with the eventual introduction of Arachne. Getting rid of the mutual exclusivity of the two ordering methods without merging Arachne would cause the branches (main and Arachne) to diverge, and we'd like to prevent that if possible. (Also there are a lot of other things that the team needs to work on of course.)

[Ghostkeeper]

Out of interest Is this just a special case of the travelling salesman problem? If so, has any particular algorithm been implemented (in both implementations)?

@KodeMunkie The monotonic constraint is not a travelling salesman problem in itself. Optimising the travel moves between sequences of monotonic lines while maintaining the monotonic ordering is indeed a special case of travelling salesman though. It is a special case because the entry point of each sequence of monotonic lines is fixed, and the order of the monotonic lines is fixed too. The fixed parts cannot be optimised, so they must be deducted from the total cost of the path (cost 0). So effectively when the salesman starts with one such sequences it is like it enters a wormhole to the end of the path. This makes it a non-metric TSP. The same goes for optimising the order of individual lines though, which CuraEngine already does. We simply approximate this with Nearest Neighbour.

We have previously implemented better approximations of the travelling salesman solution in this context. That wasn't a branch-and-bound, but a random-insertion algorithm. It provided 0-2% reduced travel times, and consequently 0-0.2% reduced total printing times. We found that the added complexity of maintenance and slicing time didn't weigh up to the extremely marginal gain in printing time and quality. So it was not merged. Nearest neighbour is considered to be perfectly fine in most cases, keeping in mind that this is already in an O(N⁴) hot loop.

The monotonic ordering is not optimised for travel moves at all. It orders the starting points of the sequences in a monotonic order, which happens to guarantee that the segments that overlap are all printed in monotonic order too. To ensure that the ordering has (approximatedly) minimal travel moves, we would have to track which segment overlaps which other segment and optimise from the starting points of the resulting DAG.

[KodeMunkie]

Thanks for that @Ghostkeeper . Have you also previously considered a genetic algorithm to determine a best effort solution i.e. the fitness function is both the shortest travel moves and that which results in zero or as close to, overlaps? Monotonic traversal would not be part of the fitness function as it would part of the behaviour that paths are directional. (This makes an assumption as to how the path code is stored, i.e. a monotonic path is actually a directional vector). Anyway it feels like I'm back seat driving (and not actually contributing!) so thanks for implementing this don't feel the need to consider this as an additional feature request - it's me just toying around with how I'd like to do greenfield dev experimentation.

[Ghostkeeper]

We haven't considered any genetic algorithm - or other machine learning algorithms - to this end because that would imply that the optimal solution could be a combination of some monotonic lines and some un-monotonic overlaps. Generally when users select "monotonic" they expect that it will always be monotonic. We try to steer away from such combined solutions since they take away control from the user; it's hard for the user to predict in which cases it would choose to print monotonically and in which cases it would choose to print with the shortest travel moves.

I'd rather implement some static number that determines the extra length of travel it would consider to print monotonically, as a setting, and optimise that number experimentally.

But again, that would significantly increase the complexity of maintenance as well. It needs a dash of KISS. Also such a setting would be very hard to understand so almost nobody would really use it or optimise it for their printers.

[KodeMunkie]

O/T because I find this fascinating - I personally would rather have ML or genetic algorithms churn out the thousands of combinations needed for a tuned/optimal print, as opposed to the expense of try it and see - especially due to cost. If this was marketing/online advertising I see this akin to doing manual A/B testing (slow, imprecise, limited data set) when you could be doing ML multi-arm bandit style algorithms (real time reactive, more precise, large data set) which is optimal and ultimately more profitable.

I've also heard the very hard to understand argument before in workplaces, but 40 years ago building your own computer was hard, 20 years ago neural nets were hard, these days you can just call an API to train it or use it...

As a proponent of ML at work I find people are scared to use these abilities because project owners don't understand, or the technology is beyond staff understanding because they don't want to learn it - in reality it's no longer rooted in complex maths, but the fear is there and the lack of will to learn something significantly different (NOT reflective of Cura staff - I'm just telling a story!) which ultimately is why new young starters, who have ML experience, generally are in higher demand.

I guess the point I'm making is that at some future time clever ML techniques will be normal (as it is becoming in other industries) and at that point Cura will potentially fall behind in general result quality, and I'd rather not see that happen. I'd offer to do a spike, but honestly I don't have enough time in the day with a family and my current out of work commitments.

Again please don't see this as criticism of a superb product, I'm hinting at a longer term future policy position for Cura to prevent it losing innovation ground.

Final edit note - if you're looking to commercial profitability ML processing can be offered as paid additional functionality (i.e. SaaS general subscription/pay per print if using ML cloud computing), if that's something that floats your boat.

[Ghostkeeper]

I majored my bachelor's in artificial intelligence, specifically on examining the topology of the hypothesis space to learn more effectively. Machine learning in general is not something we are afraid of within Ultimaker. (Though the status of machine learning use within Ultimaker is not something I am allowed to tell you about.)

But we do think about it pragmatically, and favour control in low-level optimisations as well as maintainability in the long term and by other people. I think in the case of optimising the order of lines, machine learning is inappropriate.

[KodeMunkie]

A neural net/pre trained machine learning model in this case would have been inappropriate but I actually had in mind the general case, i.e. training models based on triangle point layout (similar shapes making up the larger print must be common, so for example speed, acceleration or other print feature could be better controlled when a pattern is seen), or optimal Cura settings for a print based on other factors, e.g cube without detail could be performed at 0.28 layer height (admittedly that could also just be simple if/else rule based).

In the case of monotonic behaviour I feel a genetic algorithm could have been a good match, running simulations during the calc phase, and why I mentioned it specifically, but I understand your perspective and as you majored in it you probably have more recent and detailed experience - my comment was in no way intended to challenge that if that's how it came across :)

Further O/T - I've a BSc in Comp Sci + Software Engineering Post Grad, and have been using lesser AI techniques in code (NLP rules based systems, text classification, A/B testing, image recognition) for about 10 years having been a developer for 20+ years).

I'll keep quiet now but please feel free to contact me via GitHub if you'd like to talk further :)