When the top of a cut is not that simple

In the previous entry, I discussed how the silhouette of a cut, which would be a closed polygonal line, could be turned into a triangulated surface so these triangles could form a closed lid for the sliced triangular mesh.

But there are many cases when that surface is not that simple as a closed polygonal line. So the general case is a little bit more challenging. Let us see some sample cases in the image below:

So the simple case I talked about would be the circle label with the number 1. But the rest of the cases 2,3, and 4 are a bit trickier.

• Case 2: We have a hole inside the exterior cut. That would be the result of cutting a tube-like shape. Here we do not want to cover the whole circle as in case number 1, but we want to keep the hole uncovered. Luckily, the Earcut library handles the cases where the external polygonal line encloses an area with one or more holes. But we still need to tell the library which points delimit the external perimeter and which ones are the perimeter of each hole. So having just a few lists of points is not enough, we will need to make sense of the role for each one of such lists.
• Case 3: Not only we have a hole in our part, but there is an additional piece inside of the hole, and to make it more complete, that piece inside the hole has another hole inside. As you can guess, I could have been able to go on and on. And in fact, I did that in one of my tests as you can see below.

• Case 4: It is a simpler case than number 3, in the sense that there are a few holes inside the same perimeter. 

It can be argued that a multiplicity of any of the cases above could be yet another case, as we need a solution that works for any possible scenario.

I can remember that Netfabb software use to get it wrong for cases different than 1, but that was some years ago. But now I see how that could have happened ;-)

On to the algorithm

I am sure this has to be described somewhere on the Internet. However, I have not had the time to look it up. So I will explain what I thought it could work that, so far, it is working nicely.

I start with one or more coordinate arrays. Each array details one perimeter, that is, the sequence of points that form a perimeter around one of the edges of the cut of a triangular mesh. In my drawing above would each one of the closed lines that appear in magenta color. 

Case 1 would have one array (one perimeter), case 2 would have two, case 3 would have four perimeters and case 4 would have four perimeters too (one for the outer square plus three for each one of the circular holes).

The plane cutting algorithm I use does not guarantee any specific order for these perimeter arrays, which means I cannot make the assumption the exterior perimeter will always be first. In fact, for some cuts, you may have more than one exterior perimeter too.

So to get some idea of the topology I run the cross product of each perimeter to create an inclusion matrix, where each M(i,j) cell indicates whether or not perimeter i is included inside perimeter j. Of course where are not interested on M(i,i,) values, but let us assume we set them to false.

How do I get to know whether one perimeter in inside another one. Well, I do not do this but a shortcut: For M(i,j) I will choose any point at random from perimeter i and I will check if that point is contained inside perimeter j. As we do not have cases of crossing perimeters that check should be equivalent to checking perimeter i is inside perimeter j.

For example, if the arrays are numbered like in the picture above, the matrix values would be:

M=[(false, true, true, true),

   (false,false, true, true),

   (false,false,false, true),

   (false,false,false,false)]

Based on that matrix I just calculated, I create a Hashtable that will list all the perimeters that are contained inside a given (more exterior) perimeter.  For the example case it will look like this:

H={ (3,[0,1,2]),

    (2,[0,1]),

    (1,[0]),

    (0,[]) }

My next step here is to focus on entries that have just one perimeter, in the example that would be (1,[0]) and remove both elements from any other list of holes. In the table above that would transform it into the new version:

H={ (3,[2]),

    (2,[]),

    (1,[0]),

    (0,[]) }

And the logic will tell us to just cover the space between perimeter 3 and hole 2 and between perimeter 0 and hole 1. But what to do with entries with just the key value and an empty list? At this step we discard them, but we will see that is not the end of it.

Now I want to bring your attention to Case 1 again. What would be the output of the slicing process: just a single perimeter! (with no holes). So the above representation for that case would be.

H={ (0,[]) }

And for that case we clearly want to cover that perimeter with a triangulated surface, but, if we did as above and went ahead and removed all the entries with an empty list of holes the algorithm would not work. What we need is an additional step that will reintroduce only the perimeters that are needed, and that are those perimeters from the cut that are not yet in the Hashtable (or were removed before) and that is no part of any of the list of holes of any other perimeter on the hashtable.

Once this is done, what is left is to loop through the hashtable and triangulate the external perimeter of the key with all the holes detailed in the list found in the value associated with each key. For example, (0,[1,2,3]) will set the triangulation algorithm to use the array 0 for the exterior perimeter of the area with arrays 1,2, and 3 as the arrays representing three different holes in that area (that could match case 4 in the image above).