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.
Where is code for TSP solver or the random insertion algorithm.Can you please provide the link to it?
I am unable to locate it.
Thanks.
Recommended Posts
neotko 1,417
It could be nice indeed to have the option to control the path algorithm. Sometimesfor an object to be able to select the priority (speed, top layer always on the same direction, etc?). I also won't mind to take time, indeed the print time will always be longer than the calculation time.
Link to post
Share on other sites