UltiMaker Community of 3D Printing Experts

# 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

Register a new account

• ### Our picks

• In this stable release, Cura 5.3 achieves yet another huge leap forward in 3D printing thanks to material interlocking! As well as introducing an expanded recommended print settings menu and lots of print quality improvements. Not to mention, a whole bunch of new printer profiles for non-UltiMaker printers!
• 28 replies
• The UltiMaker S7 is built on the success of the UltiMaker S5 and its design decisions were heavily based on feedback from customers.

So what’s new?
The obvious change is the S7’s height. It now includes an integrated Air Manager. This filters the exhaust air of every print and also improves build temperature stability. To further enclose the build chamber the S7 only has one magnetically latched door.

The build stack has also been completely redesigned. A PEI-coated flexible steel build plate makes a big difference to productivity. Not only do you not need tools to pop a printed part off. But we also don’t recommend using or adhesion structures for UltiMaker materials (except PC, because...it’s PC). Along with that, 4 pins and 25 magnets make it easy to replace the flex plate perfectly – even with one hand.

The re-engineered print head has an inductive sensor which reduces noise when probing the build plate. This effectively makes it much harder to not achieve a perfect first layer, improving overall print success. We also reversed the front fan direction (fewer plastic hairs, less maintenance), made the print core door magnets stronger, and add a sensor that helps avoid flooding.

The UltiMaker S7 also includes quality of life improvements:
Reliable bed tilt compensation (no more thumbscrews) 2.4 and 5 GHz Wi-Fi A 1080p camera (mounted higher for a better view) Compatibility with 280+ Marketplace materials Compatibility with S5 project files (no reslicing needed) And a whole lot more
Curious to see the S7 in action?
We’re hosting a free tech demo on February 7.
It will be live and you can ask any questions to our CTO, Miguel Calvo.
Register here for the Webinar
• 18 replies
• Are you a fan of tree support, but dislike the removal process and the amount of filament it uses? Then we would like to invite you to try this special release of UltiMaker Cura. Brought to you by our special community contributor @thomasrahm

We generated a special version of Cura 5.2 called 5.3.0 Alpha + Xmas. The only changes we introduced compared to UltiMaker Cura 5.2.1 are those which are needed for the new supports. So keep in mind, this is not a sneak peek for Cura 5.3 (there are some really cool new features coming up) but a spotlight release highlighting this new version of tree supports.
• 22 replies
×

• #### Activity

• UltiMaker.com
×
• Create New...