exact down sampling and re-triangulation of mesh data(non-convex) I have a human body 'surface' mesh data.: triangular mesh (vertices, face)

What I want to get from this is 'exact-down-sampled' version of the current mesh.

Which means.. the processed output mesh should have the vertices that all belong to the input mesh and the mesh data should be in the triangular mesh form..

I know there are some surface mesh simplification algorithms, such as poisson surface reconstruction algorithm. But as far as I know, they don't preserve the positions of the input mesh.
 What I simply want is to down-sample the points and triangulate them.
1. Method: Vertex Clustering

This is more or less a low-quality method, but depending on your mesh it could work well.
The basic idea is to partition the space into a regular grid, and then choose one representative for each cell that holds at least one vertex.
Then calculate the connectivity based on the connectivity of the original vertices.



In the image you see a basic 2D clustering. The unreduced mesh on the left, and the reduced on the right with the chosen representatives.
As you can see, just choosing an existing vertex as representative (by closest to mean, or closest to center, or any other idea you can think of) you get a subset of vertices.

But you also see the problem, thin parts will degenerate and parts that are close to forming a loop will probably get connected. But as already said, it depends on your mesh if this works.

2. Method: Incremental Mesh Decimation with with Half-edge Collapse



One vertex gets collapsed into its neighbour. Thereby you get again a subsampling.
This is a progressive method. You evaluate which collapse will decrease the quality (for example total distance to the original surface, but many more possible) and collapse it. Then you check if your quality has dropped too much for another collapse, and if so you stop. Otherwise you do it again. Until either the quality drops too much or the target size is reached.

Method 3: Progressive Mesh Decimation with Vertex Decimation.

The same progressive idea as in method 2, but this time instead of a collapse you just delete a vertex and calculate a new triangulation for the hole that this created.