How to simplify a marching squares mesh?

Question

I'm running a marching squares (relative of the marching cubes) algorithm over an iso plane, then translating the data into a triangular mesh.

This works, but creates very complex mesh data. I would like to simplify this to the minimum triangles required, as seen illustrated below:

I have tried looping around contours (point -> segment -> point -> ...), but the contour can become inverted if a point has more than 2 attaching segments.

Ideally the solution should be fairly fast so that it can be done at runtime. The language I'm using is C#, but could probably port it from most other C-like languages.

Answer 1

This is a very common problem in 3D computer graphics. Algorithms solving this problem are called mesh simplification algorithms. The problem is however much simpler to solve in the 2D case, as no surface normals need to be considered.

The first important thing is to have a reliable mesh data structure, that provides operations to modify the mesh. A set of operations, that can produce and modify any mesh is for instance the set of "Euler Operators".

To simplify a 2D mesh provide a dense version of the 2D mesh. You can simply convert your quad mesh to a triangle mesh by splitting each quad at its diagonal.

Dense triangle mesh:

Then iteratively collapse the shortest edges, which are not at the boundary. "Edge collapse" is a typical mesh operation, depicted here:

After some steps your mesh will look like that: