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.

Calvert

So you've run the isoline algorithm described on the wiki page you linked, it has supplied you with a grid, and you want to translate this into a minimum triangular representation? – Phenylalanine

How is the data you're trying to translate represented? – Phenylalanine

Why does it have to be the "minimum" triangles? Can't you just carve out the interior squares? – Scepter

@JSQuareD, correct I have a two dimensional array of IsoCells which result in many redundant polygons (like in the supplied image). So the objective is to reduce the number of polygons as much as possible to optimize the mesh. – Calvert

@NicolBolas It doesn't have to be perfectly the minimum, but ideally very simplified. I'm using the resulting triangulation for a rigidbody collision mesh, which is very slow to instantiate with complex meshes. – Calvert

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:

Mckinzie

Great answer as far as I can tell. I wonder why no one got any votes – Margarettamargarette

Answer 2

Simplifying a mesh generated by marching squares (like suggested in the answers above) is highly inefficient. To get a polygon out of a scalar field (e.g. a bitmap) you should first run a modified version of marching squares that only generates the polygon contour (i.e. in the 16 cases of marching squares you don't generate geometry, you just add points to a polygon), and after that you run a triangulation algorithm (e.g. Delaunay or Ear Clipping).

Fireback

OP can also look into Triangle.Net for unity (available in github) for triangulation. Works beautifully well for 2D points on a contour. – Ebonize

Answer 3

Do it with an immediate step, go from your volume representation to the grid representation.

After that you can then group the areas with case 3,6,9,12 into bigger/longer versions.

You can aslo try to group squares into bigger squares, but its a NP problem so an ideal optimization could take a long time.

Then you can convert it into the polygon version.

After converting it to polygons you can fuse the edges.

Vesicatory

Answer 4

EDIT: Use Ear Clipping on resulting contours:

http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

Contravene

Ear Clipping is a triangulation algorithm. It's not meant to generate contours from scalar fields. – Fireback

Ear Clipping can fill a polygon with the minimum number of triangles. – Contravene

Sure, but that by itself doesn't answer the OP's question. He needs an efficient way to generate a contour and triangulate, not just triangulate. – Fireback