<p><strong>1. Method: Vertex Clustering</strong></p>

<p>This is more or less a low-quality method, but depending on your mesh it could work well.<br>
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.<br>
Then calculate the connectivity based on the connectivity of the original vertices.</p>

<p><img src="https://i.sstatic.net/ijNC6.png" alt="2D Vertex Clustering"></p>

<p>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.<br>
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.</p>

<p>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.</p>

<p><strong>2. Method: Incremental Mesh Decimation with with Half-edge Collapse</strong></p>

<p><a href="https://www.researchgate.net/figure/221129055_fig1_Fig-1-Half-edge-collapse-decimation-operation" rel="nofollow noreferrer"><img src="https://i.sstatic.net/vPLlx.png" alt="Figure 2"></a></p>

<p>One vertex gets collapsed into its neighbour. Thereby you get again a subsampling.<br>
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.</p>

<p><strong>Method 3: Progressive Mesh Decimation with Vertex Decimation.</strong></p>

<p>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.</p>

CC BY-SA 3.0
2016-07-06T14:36:15.557Z
2018-04-18T22:33:49.680Z
2018-04-18T22:33:49.680Z
Dragonseel
<p>I have a human body 'surface' mesh data.: triangular mesh (vertices, face)</p>

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

<p>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..</p>

<p>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.</p>

CC BY-SA 3.0
2016-07-05T09:32:38.003Z
Just to confirm, you want the output vertices to be a subset of the input vertices? It isn't sufficient for the output vertices to be on the surface defined by the input mesh?
trichoplax is on Codidact now
<algorithm><mesh>
exact down sampling and re-triangulation of mesh data(non-convex)
taeyoon
# exact down sampling and re-triangulation of mesh data(non-convex)

(Asked by: username_0 on 2016-07-05)

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.

**Tags:** algorithm, mesh

> **Comments:**
> **username_1**: Just to confirm, you want the output vertices to be a subset of the input vertices? It isn't sufficient for the output vertices to be on the surface defined by the input mesh?  

---

## 1 answers

### Answer by username_2 on 2016-07-06. Score: 4

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

![2D Vertex Clustering](https://i.sstatic.net/ijNC6.png)

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**

[![Figure 2](https://i.sstatic.net/vPLlx.png)](https://www.researchgate.net/figure/221129055_fig1_Fig-1-Half-edge-collapse-decimation-operation)

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.


---

