Joining adjacent triangles

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!

BLOGO
A quad can be presented with two triangles, a polygon with five vertices needs more.

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”:

optimointi - viereisten kolmioiden yhdistäminen
The light green triangle has one or two vertices on the splitting plane (yellow line). All the triangles are on the same plane.

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).

Problem: coplanar neighbor triangles

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.

problem
On the left: the original cube. Center: cube split in two – this is still ok. On the right: splitting the bottom part of the cube again creates triangles that could be joined to their neighbors.

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.

5
Meshes containing very thin triangles caused by non-optimized splitting algorithm.

In the next articles I will explain a simple optimization technique which will hopefully reduce the number of triangles in you scene significantly.

Triangle splitting and polygon triangulation

Triangle splitting

The first problem I needed to solve was how to split a mesh (at least a convex one) in two with a plane. This will hopefully be a helpful tool for severing arms, legs and heads 🙂

1
A simple cube and a split plane

I started by splitting all the mesh triangles that intersect the splitting plane. The splitting algorithm I wrote is based on two very helpful articles written by Randy Gaul:

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”

Intersection polygon

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.

Triangulation

Filling a polygon means (in this context) triangulating the polygon. I used an simple polygon ear clipping method described in Ear-clipping Based Algorithms of Generating High-quality Polygon Triangulation.

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.

2
Cube split in two (meshes)
4
Triangulated intersection area in a cylinder showing very ”thin” triangles caused by the ear clipping method