Half-Edge Collapse

Question

I'm currently trying to implement a half-edge collapse in order to perform incremental remeshing. I'm dealing with a manifold mesh. Consider the following simple mesh:

The goal is to collapse a into b.

In this case however, this results in a non-manifold mesh

which I want to prevent. My question is:

How can I do this in advance, i.e. perform a check before the collapse whether the collapse operation is safe?

I've tried the criteria (link condition) from Hoppe, but both are fulfilled as it seems. Also, the only intersection of the one-rings of a and b is c, thus only one point as it is a boundary edge.

Also generally speaking, what other checks do I need to perform to avoid an illegal collapse?

Right now, I have the following criteria:

• if a and b are boundary vertices, the edge ab must be a boundary edge
• a, b and the third vertex of triangles adjacent to edge ab must be a valid triangle (link condition)
• if triangles adjacent to edge ab are boundary triangles, do not collapse if a is on the boundary edge
• if the intersection of the a-1-ring and b-1-ring is not equal to two (or one for boundary edges), do not collapse

Answer 1

You may want to look at this paper:

Tamal Dey, Herbert Edelsbrunner, Sumanta Guha, and Dmitry Nekhayev. Topology preserving edge contraction.

I'm not sure which Hoppe's paper you are referring to (progressive mesh?) but Tamal Dey's link condition is different from the one you stated. Intuitively, an edge ab is collapsible if

one-ring(a) intersected with one-ring(b) == one-ring(ab).

For an edge ab, one-ring is the set of the other vertices of the faces sharing ab. Also in Tamal Dey's link condition, you need to take the dimension of the embedding space into consideration. (i.e. the link condition is different for an edge in 2d and in 3d). Many other work use this link condition to collapse edges without incurring topological errors.

What's confusing is from your example I couldn't really tell whether it's a mesh-with-boundary in 3d or 2d, or how "planar" it is. These factors determine whether the resulting mesh has a "folding" or not, e.g. triangle bcd is considered folded in 2d but could be fine in 3d if the mesh is not planar.