The slicing algorithm is done on the STL model and it is ensured that the result is a series of simple polygons that do not intersect each other. In other words all of those polygons generate closed loops. I need to identify which of those loops are outer and inner loops. There have been some references suggesting tree depth can be used to identify external and internal loops, without any outline of the algorithm.

It would be great if anyone can point to more detailed references where the tree depth can be utilized to filter out inner and outer contour lines.

The following images will provide more information:

Partition areas Depth Tree Structure

According to the article that I am following - a, b, e, f, and j are outer loops, while the rest are inner loops.

In the current situation, I am identifying the inner and outer loops while doing the scanline over each layer after the slicing operation. But I want to identify the inner and outer loops ahead of the scanline operation, so that I can create inner/outer offset for the identified loops and then run the scanline to generate the fill pattern.

The article that I am following is titled - "Equidistant path generation for improving scanning efficiency in layered manufacturing". I googled up and I am afraid that it is not public. I downloaded the article through the university database.

  • $\begingroup$ Hi @sajis997, it's hard to understand what you're talking about from words alone. Could you add a screenshot or diagram to show what you mean by inner and outer loops and tree depth? $\endgroup$ May 11, 2016 at 16:43
  • $\begingroup$ Hi @NathanReed, The initial question is edited with some image snapshot. I hope it wil be clear now. $\endgroup$
    – sajis997
    May 11, 2016 at 19:24
  • $\begingroup$ Do you have access to the tree shown in the image? If so my answer would be "the outer loops are at even depths, the inner loops are at odd depths". Is your requirement to produce this tree, or to interpret its results? $\endgroup$ May 13, 2016 at 1:01
  • $\begingroup$ After the slicing operation, I have closed loops . I want separate into separate layer parts when each layer part contain an outer loop, one/several loops and infill pattern. I want to use Tree data structure for this purpose as mentioned in the paper. $\endgroup$
    – sajis997
    May 13, 2016 at 7:38

1 Answer 1


Take a random vertex on your loop, shoot a ray trough all the other loops. For loops you crossed a odd number of times your inside for loops you crossed a even number of times your outside.

The loops that are outside of all others is in the root of your tree. Then find loops that are inside that, but not inside some other. Then find next level and next level and so on.

enter image description here

Image 1: Animation of arranging in tree by shooting rays

You can optimize this by using bounding boxes/ bsp trees for the test areas. But for a small number of areas that might be overkill. just sorting them left to right top to bottom should suffice. You can use the same algorithms as your scan line operators.


Image 2: And now you can offset the shape. But you need to recheck that there is no intersection left after this.

Now the topology is somewhat stable across levels of slices so you can use that to your benefit. Just follow the 3D surface.

Or you could do the offset in 3D on the polygons so you do not need this info. Also if you just need the winding for knowing which way to offset rule you can derive it from the 3d model itself, each vertex has a normal so project the normal for one triangle in each loop with your slicing algorithm per loop. That then gives you the direction of loops outside which is inside for nearly free. You wouldn't get the tree but then again you might not need it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.