Algorithm or software for slicing a mesh
What is the right approach for slicing a 3D mesh? The mesh are all closed surfaces and the slices need to be binary images of what's inside the mesh. So for example, a mesh representing a sphere and slice images are those of filled circles.
I am looking for a software library or algorithm that I can integrate into my current C++ project.
Answer
My open source game library contains an implementation of mesh slicing. It works with the Irrlicht api, but could be rewritten to use a different API with a modest effort. You can use the code under the terms of the BSD license, or learn from it an implement your own.
See MeshTools::splitMeshZ in this file for an implementation of mesh slicing.
If you just want to know the algorithm, here's a high-level description of what I did:
I initially thought of using an axis-aligned bounding box to specify where to cut the mesh. This was problematic because it introduced many special-cases. For instance, an edge that crosses the corner of the box may be split into three pieces rather than just two.
Using a plane to cut the mesh into just a left mesh and a right mesh reduces the number of special cases, because an edge is either on one side of the plane or the other, or it crosses the plane and so is chopped into exactly two pieces.
Any desired configuration of cuts can be made simply by cutting once, taking one of the resulting meshes and cutting it again in another location, and so forth. Specifically in the case you describe in the section, a circle could be cut from a sphere by cutting one half the sphere off, moving the plane a small amount and cutting off the other half leaving only a thin band. (You can't cut a mesh down to literally no depth with the code I wrote, but you could cut a mesh up to whatever you have set your floating point equality threshold to be. I think I arbitrarily chose 0.001 in my code.)
Using similar logic, any desired angle of the cutting plane can be achieved using a fixed plane; you just need to transform the mesh to rotate it relative to the fixed cutting plane, and then transform the result back. (For my game I only needed cuts perpendicular to the XY plane, so for simplicity I only allow the Z value of the cut to be set, and assume the cut is at that Z location.)
OK, now that we've simplified the problem, the algorithm is not so bad:
Starting condition: You have a cutting plane. You have a set of source triangles. You have two destination sets of polygons (not triangles; quads may be generated by cutting the triangle). The two destination sets are called Left and Right.
Process: Iterate over three points of a triangle. Count the number of points that are less than the cutting plane. I will call those less than the cutting plane Left and those greater than the cutting plane Right. There are only a handful of cases:
- All triangle points are on the Left: put the triangle in the Left set
- All points are on the Right: put the triangle in the Right set
- One point is Left, others are Right: if you cut a triangle across two edges, and you were holding one of the points, you end up holding a smaller triangle. Put a triangle in the Left set made up of the Left point, and the two points where the edges crosses the plane. Put a quad in the Right set (see next case).
Two points are Left, one point is Right. If you are holding an edge of a triangle and cut it across the other two edges, you are left holding a trapezoid. Put a quad in the Left set made up of the two points in your hand, plus the two points which cross the cut. Put a triangle in the right set (mirror image of case above).
When finished, turn the quads into triangles by adding a link across the shortest part.
That's it. That's the basic algorithm. The actual code handles a few more cases such as what if an edge is exactly equal to the cut, what if a triangle is exactly on the edge, don't add degenerate polygons (e.g. a point with no body), etc.
Misc. issues (all covered in the linked code):
Don't overcomplicate the math for LERP'ing the spot where the edge crosses the cutting plane. It doesn't need a full linear interpolation, it is actually just Highschool Algebra II: rise over run, times a ratio
It is advantageous to cache the generated (LERP'ed) points so that triangles which shared vertices in the uncut mesh will share the corresponding new vertices in the cut mesh.
If you are going to preserve vertex sharing, and you are using triangle index buffers, you unfortunately don't know the index yet when you first generate the shapes to put in the Left and Right sets. I use a class called "PossibleVertex" to represent a future triangle index number.
If you are going to display the mesh, winding order matters. Careful thought about how you code it up can ensure the resulting polygons use the same winding order as the triangles they came from. This gets especially tricky when triangulating the quads. I can't remember the details but it's all handled in the linked code.
For my game, I wanted to make a flat ribbon connecting two cut meshes. That's why splitMeshZ results in 3 meshes, rather than just two. You can use the middle mesh, or just ignore it.