Previously I wrote about useless triangles that are created when a mesh is split in two. By useless I mean they are adjacent to each other and on the same plane (plus have the same normal vectors). So why not join them? In the following I present two simple rules that can be used to determine if three triangles (created by splitting a mesh by plane) can be presented with two triangles.
From polygon to triangles
We need to reduce the number of triangles in a mesh. A quad (polygon with four vertices) can be represented with two triangles. So if we find quads that consist of more than two triangles we optimize!
When looking for optimization candidates we only have to check the triangles that have one or two vertices on the splitting plane. We don’t want to accidentally ”optimize” other parts of the model that should be unaffected by the splitting 🙂 Also, if a triangle has one or all vertices on the splitting plane it is not interesting as it is not split.
A quad with three triangles, gross!!
If we take a triangle that has one or two vertices on a plane we have one of the following ”neighborhood situations”:
Below the triangles is the number of vertices in a polygon created by the intersecting triangle (light green) and its neighbors. If n = 4 we have a quad and we can represent that with two triangles. If n = 3 the situation is even better – we can represent all three triangles with a single triangle. Cool! If n > 4 we cannot join the triangles since impossibru!
Thats it! In one of the next articles I will show what kind of impact these two simple optimizations can actually have when implemented (in Unity).
Splitting an already split mesh just by splitting all of the triangles that intersect the splitting plane and outputting a new set of triangles creates an bunch of new triangles that are adjacent to each other and are on the same plane.
These triangles are essentially useless since in most cases they can be joined to their neighboring triangles. This optimization is not mandatory but the more your split your meshes the more messier it gets. The picture below illustrates one clear candidate for optimization.
In the next articles I will explain a simple optimization technique which will hopefully reduce the number of triangles in you scene significantly.
After the split we have a bunch of triangles that are on one side of the plane and a bunch of triangles that are on the other side of the plane. One could use these triangles to output two meshes but they would be missing a face (the intersection area).
Filling ”the gap”
So both of the meshes (or ”bunch of triangles”) created have an intersection area that has to be filled. This can be done by calculating a polygon from the intersection area and triangulating that into a face.
Triangles that are ”touching” the intersection plane have vertices that are on the intersection plane. From these vertices, I calculated the longest ”streak” of vertices that are connected to each other (with an edge) trying to ”get around” the intersection area. Hopefully this forms an edge loop (first and last vertices are connected) and we have the polygon that we can fill.
Splitting a mesh and triangulating the intersection area were my first steps in this coding adventure. The first implementation was not very robust and needed many optimizations to reduce excess triangle creation. I will try to write about them in the following articles.