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.
There are two main conditions for an edge collapse:
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:
The triangle between the orange and cyan edge is not manifold anymore.
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:
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With