Cura Nearest Neighbor Question(s)

[kreeser1 0]

I have a couple questions related to this thread from 2015, where there is a discussion of the nearest neighbor algorithm used to determine the order in which polygons are printed.  Ghostkeeper comments:

 

"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 neighbor algorithm: Just keep going to whichever polygon is nearest to your current position that you haven't visited yet."

 

1.)  Is this still how the Cura software determines the order in which to print polygons on a layer-by-layer basis?

 

2.)  I am confused by Ghostkeeper's statement and would like clarification.  After the slicing step, Cura knows all of the intersection points (or nodes) that the slicing plane made with the model, and it also knows which points are grouped together into polygons.  It also knows the order in which the points in each polygon need to be printed, but the actual printing of the loop doesn't matter because the loop starts and ends at the same point.  Does Ghostkeeper truly mean that, (a) for each layer, given some starting point, all loops are represented by the point on the loop that is closest to the initial starting point, proceeding with a simple nearest neighbor solution?  Or does it mean that, (b) for a given starting point, all nodes on all untraversed polygons are checked for the smallest distance from the starting point, then representing that second polygon as a single point at the node, and so on and so forth until there are no polygons left?  

 

If (a), it seems like this solution would be highly dependent on starting node, so how is the starting node picked?  Does the algorithm cycle through all potential starting nodes?

 

If (b), I think this would make more sense and yield a better answer, but be potentially costly in testing each "current point's" distance from every node in every other untraveled polygon.  

 

3.) Finally, if the bit of code isn't too large, or there is a comment directly in the code that explains it further, could someone provide that in the comments, along with what file it's located in?  I am writing an academic paper for that has a small section in which I would like to cite how one or more popular tool path generation programs solve this problem for the 3D printing use-case.  

 

 

 

Edited January 17, 2019 by kreeser1
Clarifying my question

[kreeser1 0]

Anyone able to help with this topic?

[ghostkeeper 105]

On 1/18/2019 at 12:24 AM, kreeser1 said:

1.)  Is this still how the Cura software determines the order in which to print polygons on a layer-by-layer basis?

Yup, it hasn't changed. My statement wasn't quite complete though. There are multiple orderings going on, from significant to insignificant:

• It needs to print all mesh groups in order (in case of one-at-a-time mode) so that they can be printed without colliding with the print head.
• It needs to print all layers from bottom to top.
• It needs to print all extruders in such a way to introduce the fewest extruder switches.
• It needs to print all meshes for an extruder in such a way to reduce travel distances, by nearest neighbour (as described above).
• Within a mesh, if a mesh consists of multiple simple polygons at a certain layer, it needs to print all parts in such a way to reduce travel distances, by nearest neighbour (as described above).

On 1/18/2019 at 12:24 AM, kreeser1 said:

but the actual printing of the loop doesn't matter because the loop starts and ends at the same point. 

It prints all of the part together. Usually it doesn't print just a loop for the outer wall, but also inner walls, infill and skin. It's not common to end at the same point.

 

On 1/18/2019 at 12:24 AM, kreeser1 said:

Does Ghostkeeper truly mean that, (a) for each layer, given some starting point, all loops are represented by the point on the loop that is closest to the initial starting point, proceeding with a simple nearest neighbor solution?  Or does it mean that, (b) for a given starting point, all nodes on all untraversed polygons are checked for the smallest distance from the starting point, then representing that second polygon as a single point at the node, and so on and so forth until there are no polygons left?

Neither, to be precise. It finds the closest point on each polygon from the starting point (so you get a bunch of coordinates on the borders of polygons), then from those points chooses the closest one to go to. Then it prints that polygon completely and ends up on a new position. It again finds the closest point on each remaining polygon from the new starting point and chooses the closest one again, and so forth until there are no polygons left.

 

On 1/18/2019 at 12:24 AM, kreeser1 said:

If (a), it seems like this solution would be highly dependent on starting node, so how is the starting node picked?  Does the algorithm cycle through all potential starting nodes?

Indeed it is. The starting position is two settings: Layer Start X and Layer Start Y. It's not (necessarily) on an existing polygon and it doesn't actually travel to this starting position first. Previously we had the option to make the starting position the position where the nozzle ended in the previous layer, but that didn't work any more once we introduced multi-threaded slicing.

 

On 1/18/2019 at 12:24 AM, kreeser1 said:

If (b), I think this would make more sense and yield a better answer, but be potentially costly in testing each "current point's" distance from every node in every other untraveled polygon.

It uses Pythagoras, but omits the square root, so we're comparing squared distances. It's not so taxing then, just two multiplications, one addition and a comparison per polygon. It scales quadratically but you'll rarely have more than 1000 polygons anyway. In fact, we're doing the same algorithm to determine the order in which to print skin lines and infill lines.

 

On 1/18/2019 at 12:24 AM, kreeser1 said:

3.) Finally, if the bit of code isn't too large, or there is a comment directly in the code that explains it further, could someone provide that in the comments, along with what file it's located in?  I am writing an academic paper for that has a small section in which I would like to cite how one or more popular tool path generation programs solve this problem for the 3D printing use-case. 

https://github.com/Ultimaker/CuraEngine/blob/a03d9291c6d9a37e8b4f23df60d76c249c045172/src/pathOrderOptimizer.cpp#L16

There's some stuff in there for finding the proper location to put the Z-seam as well that you can ignore (unless you do want to write about that because it's specific to 3D printing). There is also an optimisation that I hadn't mentioned yet with a bin map, which finds points that are very close together faster (the grid is stored in the loc_to_line variable).

Edited January 22, 2019 by ghostkeeper
Clarified starting position X,Y settings