Thanks for your reply.
I wonder whether I can use my path planning knowledge to improve the linking of line segments in an STL into loops. May I know what is the current algorithm used for linking these line segments in the STL?
One more thing: while 3D printing, does a printing nozzle follows all lines in the STL and all links between those lines?
As far as I'm aware we're not using any scientific papers as a basis for our algorithms.
@bagel-orb or @ghostkeeper are the people working on the engine these days, so they will be able to give you a summary if you like.
Edited by GuestYes, it would be really appreciated if they can provide me more information regarding this. Thank you.
Interested in that too. I believe it's an interesting research topic for academics 
One more thing: while 3D printing, does a printing nozzle follows all lines in the STL and all links between those lines?
Short answer; No.
Longer answer; There is a lot of heuristics going on in the slicer. If a model is non-manifold, things need to be fixed before they can be printed. If a model has too much small detail (sub micron level) they are 'squashed' in order to prevent duplicates and speed up the process. Depending on the thickness of the part, some lines might not be followed at all (or multiple lines are only followed by one pass, etc).
some lines might not be followed at all.
So, those parts won't be printed?
The fixing algorithm can fail sometimes, which can result in some lines not being printed.
This is all easier to explain with pencil and paper but here goes...
After slicing and you have all these line segments cura tries to hook them up into loops so it looks for any 2 line segments that appear to have a vertex at the same point. But what is "same"? you have floating point errors because these vertexes were created by an intersection of a line and 2 different triangle faces and so you might not get the exact same point *anywhere*. So you have to pick "close enough". I don't know what the limit is but lets assume .01mm. So it starts linking line segments up but once it finds a match I'm pretty sure it doesn't try to link in a 3rd line - that would be insanity.
Yet this insanity exists - a lot. Expecially in sketchup models where you have 3 planes all coming together - where the hell is the inside? Where is the outside? Cura basically picks at random if you have all the fix horrible options turned off which pre-process the 3d model.
What if you connect up all those line segments and you get an *almost* loop that doesn't come back together? It is ignored and that part of the model (for this slice anyway) is ignored and not printed. This happens a lot with non-manifold objects also. That's why you never want a hole in your walls of your model and you never want walls *inside* your part.
You need to make it very clear what's solid and what's *not* solid in your model. Sketchup is not so good at that.
Thanks a lot for your explanation. Things are clearer now.
This is also why 'solid modelling' is much more suited for 3D printing, as in that case you are very explicit in what is inside and what is outside. Voxel based modeling is a good example of this, as voxels are essentialy 3D pixels.
Regarding the path planning itself, everything is really just based on nearest neighbour. There are currently two major spots where it is required (as far as I know; I still haven't seen everything after a month of CuraEngine programming): Optimising the order of polygons and optimising the order of skin/infill. The rest, such as filling small gaps, I don't know of where the code is but I'm told is also nearest-neighbour-based. These main two algorithms are in pathOrderOptimizer.cpp.
The first is the order in which to draw polygons, which includes infill and walls and such. For these it first finds the point on each polygon that is closest to the starting position of the path. Then it treats the polygons as points so it can execute a simple nearest neighbour algorithm: Just keep going to whichever polygon is nearest to your current position that you haven't visited yet.
The second application is the order in which to draw lines of skin or infill. This has a bucket grid heuristic. First all endpoints of the lines are put in an array of buckets, each bucket representing a 5x5mm area of the build plate. Then it starts the nearest neighbour search, but with a heuristic. It keeps going to whatever line is nearest to the current position (initially the starting position, thereafter the endpoint of each line). But instead of going through all lines and looking for which is closest, it will first go though all lines with an endpoint in the bucket that the current position would fall in. Only if there aren't any lines in the current bucket, it will go through the rest of the lines.
The nearest neighbour algorithm is fast to compute and simple to implement, but it has a performance ratio of O(log N), meaning that the ratio of the optimal path to the worst case path from nearest neighbour scales with the logarithm of the number of nodes. The average results of nearest neighbour aren't good either, on average 24% longer than the optimal on city maps. I've been working on a new implementation based on randomised insertion that provides much better bounds (worst-case performance ratio of 2), much better average results (on average 11% longer than the shortest path on city maps) and should take a similar amount of time to compute.
Edit: Source on average performance ratio.
Edited by Guest
2
Just to clarify some mistakes made in this thread:
- there are no floating point errors because cura engine works with integers at most places
- the bucket grid looks at patches of 3x3 buckets, so that consecutive lines falling just on two sides of the border between two buckets won't be treated as distant to each other.
- filling small gaps is done as normal line infill
Edited by Guest
1
Thanks all for useful information. I'll study the source code (pathOrderOptimizer.cpp) and get back here if I need any further clarifications.
The pathOrderOptimizer is currently being revised. You should take a look at the feature branch https://github.com/Ultimaker/CuraEngine/tree/PathOptimizer_RandomInsertion
I cannot find "PathOptimizer_RandomInsertion" :(
That's a branch.
See https://github.com/Ultimaker/CuraEngine/tree/PathOptimizer_RandomInsertion
Google "git branch" if you want to learn more.
I had a look at the new branch. I noticed that LineOrderOptimizer::optimize() function has been significantly modified and LineOrderOptimizer::cluster() function has been introduced to PathOrderOptimizer.cpp. Do you mind giving some explanation on these changes? Especially how this random insertion method differs from the nearest neighbor method that is explained by ghostkeeper?
Edited by Guest
The LineOrderOptimizer::cluster() function is grouping up lines where both endpoints are right next to each other, using a nearest-neighbour search. This happens often in Cura, especially with skin lines which are all just parallel. It's not working very well with infill lines if the infill is too sparse. I'm thinking of making the grid size depend on the infill density.
It takes a line. Then it finds the nearest line where both endpoints are less than 5mm away from the first line's endpoints. Then it finds the nearest line where both endpoints are less than 5mm away from the second line's endpoints. And so on. When it finds no more lines where both endpoints are less than 5mm away from the previous, it puts all those lines in a cluster and starts with the next cluster, using a line that wasn't picked yet.
The LineOrderOptimizer::optimize() function gathers up those clusters, and calls the TSP solver to determine in what order the clusters should be traversed, and in what direction. The TSP solver uses the random insertion method.
Random insertion is an approximation of a solution to the Travelling Salesman problem where the goal is to find a short path along all elements. First it will take a random element (= cluster of lines, in this case) and save that as a path: That path is currently the short path along all elements it has inserted. Then the main idea: Keep taking a random element from your to-do list and insert it at the "best" position in the path. What the "best" position is in this case is up for debate, but basically it should minimize the travel time between clusters. The basic idea behind it is that after the first few elements are inserted in the path, the path should more or less span the entire space. For all the rest of the elements, there is a large chance that there is a segment of the path that runs right past the currently inserted element, so that it can insert it without much additional cost.
Only for CuraEngine, normal randomness is not allowed, since we'd like to keep the result predictable across slices. So it uses a seeded pseudorandom number generator, so that the outcome is still deterministic but the effect is the same. The algorithm is still subject to change, too.
1
Thanks for the explanation, ghostkeeper. Much appreciated. 
does the LineOrderOptimizer algorithm take into account combing? A guy in another thread is printing a maze and so obviously only the walls are printed. Because combing is turned on it is jumping all over the place following very long paths to get to the next spot to do infill on. The next spot might be 1cm away but it might travel 20cm to get there through the walls of the maze.
But it skips right past many other areas that need infill while it goes over there.
Edited by Guest
No, it doesn't, neither the old nor the new. It just determines the order and direction of each part, and combing is then applied to the travel moves afterwards.
That is a difficult one! It is prohibitively time-consuming to go combing for every distance calculation. If someone has a bright idea on how to tackle this, it'd be welcome (but don't expect it to be implemented anytime soon, can't make any promises).
If combing is on and you have to comb to get from one line to another then make sure you aren't passing over infill lines that haven't been filled in yet on the way. That should help.
The guy with the maze turned off combing and his print was much faster. He's happy.
It's too much computation to check every infill line separately. Instead we just check the whole infill area - disregarding which part of it has already been laid down.
It's too much computation to make sure you aren't passing over infill lines that haven't been filled in yet on the way.
ArunC posted a topic in UltiMaker Cura,
.thumb.jpeg.0b7a05eafc09add17b8338efde5852e9.jpeg)
Dustin posted a topic in Firmware,
Recommended Posts
gr5 2,167
I can explain some of the details. There are 3 different rewrites of the engine by the way. There are many steps - an STL has all the triangles in random order so when you intersect that with a plane you get a bunch of unrelated random line segments and you Cura then goes and links them into loops but sometimes has trouble.
That's one of the key steps that it has trouble with.
What were you curious about in particular? infill algorithms? shell? Support algorithms? Slicing? "fix horrible" features? Calculating line width? There's tons of details but usually people only care about one tiny aspect.
Link to post
Share on other sites