Fighting with computers

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 peri

Once a triangular mesh is cut by an intersecting plane, the resulting halves are no longer a water-tight mesh, because some holes are created by the cutting action of the plane. In the image here, the volume of a [solid] hat was cut by a vertical plane, splitting it in two. In order for this half to be back a 2-manifold triangular mesh, all the triangles with black edges have been added to create a flat surface that covers what the cut plane would otherwise reveal (the inside of the hat). The problem is how given a certain polygon, like the red polygonal line here, a collection of triangles can be created to cover entirely all the area delimited by such a perimeter (aka polygon triangulation). The problem gets even more interesting once we consider that some meshes can present holes inside these perimeters obtained after cutting the mesh with a plane. Fortunately, there are different algorithms to solve that problem, and I will settle with the so-called Ear clipping . Fortuna

When we use a plane to cut a triangular mesh, several cases can be considered. If there is a non-null intersection between the plane and a given triangle, there are mostly five different cases: The plane contains one vertex of the triangle: not very useful for cutting purposes if the rest of the triangle lays above the cutting plane and we want to keep all that is below. The plane contains two vertices of the triangle, then the intersection is a line segment but we will only keep that triangle if the other vertex is below the cutting plane. The plane contains three vertices of the triangle: that is a keeper. The plane does not contain any vertices of the triangle, but there is an intersection with two of the edges: this is what we will talk about today here. A fifth case can be considered when the plane contains one vertex but the two other are on opposite sides of the plane, and it can easily be incorporated to the previous case. The following picture shows us a couple of t