5

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:

enter image description here

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.

miketucker
  • 1,074
  • 1
  • 15
  • 27
  • 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? – JSQuareD Jul 27 '13 at 10:21
  • How is the data you're trying to translate represented? – JSQuareD Jul 27 '13 at 10:25
  • Why does it have to be the "minimum" triangles? Can't you just carve out the interior squares? – Nicol Bolas Jul 27 '13 at 10:50
  • @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. – miketucker Jul 27 '13 at 15:19
  • @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. – miketucker Jul 27 '13 at 15:21

4 Answers4

10

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:

enter image description here

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

After some steps your mesh will look like that: enter image description here

Harry Berry
  • 318
  • 1
  • 10
4

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

user2599140
  • 476
  • 2
  • 9
  • 1
    OP can also look into Triangle.Net for unity (available in github) for triangulation. Works beautifully well for 2D points on a contour. – Vignesh Jun 22 '17 at 12:20
0

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.

Quonux
  • 2,975
  • 1
  • 24
  • 32
0

EDIT: Use Ear Clipping on resulting contours:

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

abenci
  • 8,422
  • 19
  • 69
  • 134