# Cura Nearest Neighbor Question(s)

## Recommended Posts

Posted (edited) · Cura Nearest Neighbor Question(s)

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 by kreeser1
Clarifying my question
##### Share on other sites

Posted · Cura Nearest Neighbor Question(s)

Anyone able to help with this topic?

##### Share on other sites

Posted (edited) · Cura Nearest Neighbor Question(s)
On 1/18/2019 at 12:24 AM, kreeser1 said:

1.)  Is this still how the Cura software determines the ord﻿er 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 c﻿hecked 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.

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 by ghostkeeper
Clarified starting position X,Y settings
• 1
• 1

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account

• ### Our picks

• Cura 5.7 is here and it brings a handy new workflow improvement when using Thingiverse and Cura together, as well as additional capabilities for Method series printers, and a powerful way of sharing print settings using new printer-agnostic project files! Read on to find out about all of these improvements and more.

• 18 replies
• S-Line Firmware 8.3.0 was released Nov. 20th on the "Latest" firmware branch.
(Sorry, was out of office when this released)

This update is for...
All UltiMaker S series
New features

Temperature status. During print preparation, the temperatures of the print cores and build plate will be shown on the display. This gives a better indication of the progress and remaining wait time. Save log files in paused state. It is now possible to save the printer's log files to USB if the currently active print job is paused. Previously, the Dump logs to USB option was only enabled if the printer was in idle state. Confirm print removal via Digital Factory. If the printer is connected to the Digital Factory, it is now possible to confirm the removal of a previous print job via the Digital Factory interface. This is useful in situations where the build plate is clear, but the operator forgot to select Confirm removal on the printer’s display. Visit this page for more information about this feature.
• 0 replies
×

• #### Activity

• UltiMaker.com
×
• Create New...