Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Mesh Simplification: Edge Collapse Conditions

I am trying to implement a mesh simplification algorithm by doing a series of edge collapses. Currently, I am going through each triangle and then collapsing the shortest edge and the algorithm is stable(doesn't go out of bounds). But beyond a point, it starts to create broken(holes) artifacts. What is the correct way to determine whether an edge is collapsible or not so that it doesn't lead to non-manifold artifacts(or mesh)?

NOTE: I use a half-edge data structure. Also, I do not want to use any external libraries like OpenMesh or CGAL. I have my reasons for not using them.

like image 944
jaykumarark Avatar asked Nov 20 '14 20:11

jaykumarark


1 Answers

There are two main conditions for an edge collapse:

Connectivity

On each side of the collapsed edge, only one pair of edges must be merged. This can be checked by counting the joint neighbour vertices of the two merging vertices (there must be exactly two). Consider the following example where the red edge is being collapsed:

Invalid Edge collapse

The triangle between the orange and cyan edge is not manifold anymore.

Geometry

Triangles must not flip during the edge collapse. This can be checked by calculating the angle between the triangle normal before the flip and after the flip for triangles that are kept.

Here is an example where the normal of the green triangle is flipped during the collapse:

Normal Flip

like image 142
Nico Schertler Avatar answered Nov 19 '22 16:11

Nico Schertler