How Do Tool Path Algorithms Decide Which Direction to Print a Closed-Loop Polygon

Question

I understand how slicer programs create sets of closed-loop polygons to print on a layer-by-layer basis. For a given closed loop polygon which needs to be printed, the tool path generator will know the coordinates and how those coordinates are connected to each other, such that traversing a set of segments in that order will bring the extruder head back to the first coordinate to complete the closed loop.

My question is: By what mechanism does the tool path generator decide which direction to traverse the closed loop? As it is a loop, that loop could be printed "clockwise" or "counter-clockwise", as it were. Any details, and links to further explanations of how some of the big-name slicer programs determine this is much appreciated.

Answer 1

While this answer makes a valid attempt at answering the question, it is based on personal experience.

I went to the literature and directly to the source code in Cura to find the answer. In the academic article "Identifying the Directions of a Set of 2D Contours for Additive Manufacturing Process Planning", Volpato et al. describe several methods for identifying the arbitrary directions of each contour in each layer, and additionally identifying which contours were "internal" and which were "external". I quote from the paper:

The information regarding contour direction, which is either clockwise (CW — internal) or counterclockwise (CCW — external), is needed for path planning for material processing.

They go on to explain the importance of identifying which contours are external, and which are internal, such that the path planning algorithm can later determine where infill should be placed. Infill is placed internal to any external contours, and external to any internal contours.

When the normal vectors in STL models are assumed to be correct, a simple way to identify whether a 2D contour is CW or CCW is to analyze the vector (cross) product between a normal vector and a vector obtained from two vertices of the facet.

This assumes the slicer has already determined intersection points between slicing planes and the STL file, and has sorted those intersection points into closed-contours. This initial intersection point gathering and contour construction leads to an arbitrary directionality:

As any line segment of a contour can be the first in the sequence when the segments are connected, its orientation will dictate the direction of the contour. Hence, the 2D contours formed are classified randomly, and an external contour, for example, might be assigned a CW or CCW direction. Therefore, this step is unable to correctly identify the directions of the contours generated.

The ray-tracing method, which is actually based on the point-in-polygon test, determines which contours are contained by others, and the orientation of each contour is then alternated between CCW and CW, the outermost contours being oriented CCW.

So, the default directionality of a closed contour generated by a slicing program for FDM additive manufacturing turns out to be CCW based on cross products described above (and based on additional methods outlined in the paper). Of course the standard directionality of a PRINTED contour does not HAVE to be this way, it appears to be a standard adopted by the AM community. However, when a model produces contours inside of contours, the arbitrary directionality of those contours is determined, and then alternated from outside to inside, starting with CCW.

As confirmation, according to a simple comment in the CURA source code:

/*!
 * Outer polygons should be counter-clockwise,
 * inner hole polygons should be clockwise.
 * (When negative X is to the left and negative Y is downward.)
 */

Answer 2

Math

In math, there is a way how a path is to be followed, and that is usually counterclockwise:

Assuming a perimeter path of a circle with $r=1$ around $(2,2)$, then the path can be defined as $f(p)={{\cos(p)+2}\choose{\sin(p)+2}}$ - where $p$ is the path parameter, in this case an angle of 0 to 360°, and just increasing the angle rotates right hand around. If we had the same path but a different starting point, a shift by $\theta$, then the path would read $f(p)={{\cos(p+\theta)+2}\choose{\sin(p+\theta)+2}}$. So math is usually counterclockwise.

Slicers

Every slicer is applying math. As far as I can tell, any Slicer generates a perimeter path, which is always performed in the same way if sliced with the same settings. For one case look at this: Counterclockwise starting from a 7 o clock position in this case. However, other slicers or other objects on the printbed might use other engines, thus doing it not that way. They might go clockwise since solving a path with $p=0°\to360°$ and solving it $p=360°\to0°$ results in producing the exact same print, just opposed print direction of the perimeter.

As long as the perimeter of an object is solved as being done as one closed loop, the perimeter will need to have just one, prescribed direction. This direction will be clockwise or counterclockwise depending on how the slicer exactly solves its calculations. Since both directions are equally valid, it is a programmer's decision. A programmer might even prescribe clockwise or counterclockwise solution based on any factor they wanted. They might use layer number (for alternating directions) or a user setting or even an RNG, if they wanted to.

On the other hand, how the memory is operated and written can also result in the path and the math looking differently. Two examples:

• Solving the path correctly counterclockwise and putting the slicing into a FILO memory, resulting in a clockwise operation starting from the last solved point.
• Solving counterclockwise and saving into FIFO, running counterclockwise.

Conclusion

Slicers for 3D printing have a hard-coded way to choose the direction that is followed when producing G-code. Any and all perimeters will be printed, starting from some arbitrary point, into that direction. In the end, it is a choice of the programmer of the slicing engine that determines if the path is to be run down "forward" or "backward" in mathematical sense.

Addendum

Slicers are derived from CAM programming. CAM - computer assisted machining - takes into account one more thing when solving the tool path that is not relevant to a 3D printer: The direction of the fluting of the tool. In fact, this one will determine into which direction the path will give a better cut and changing the fluting should swap the path direction to ensure best results.