How to remove an edge from a half edge structure?

Question

I am trying to implement an algorithm to remove an edge and a vertex from a half edge structure. See the attached image for an illustration:

I know there's libraries like Openmesh and CGAL etc that can help me achieve this but I plan to implement it myself.

My original idea is as follows:

1. Find out the half edges associated with that edge
2. Find out all the faces associated with each half edge
3. Find out all the edges and vertices corresponds to each face
4. Not sure how to merge them together ie how to merge edge 1 edge 2, vertex 4 and 2 and edge 5 and 4 in the attached graph.
5. Delete all the faces.
6. Delete all the half edges

Can someone please give some suggestion if I am on the right track?

I also did some research online and found an article online that seems to be helpful.

Here's the link: http://kaba.hilvi.org/homepage/blog/halfedge/halfedge.htm

Under the Removing an edge section it lists the following steps:

1.Remove all of the polygons connected to the edge.
2.Link the half-edges of the edge off from the mesh.
3.Deallocate the edge and its half-edges.

The first and last ones make sense to me. However, I am not sure what the author mean by link the half-edges of the edge off from the mesh? Can someone please explain this to me? Thanks!

Ceric

The operation you're showing isn't edge deletion. That would leave a 4-sided face. What you're asking about is "edge collapse". It's a very common operation. If you do some searching, you ought to find both discussions of the algorithm and implementations. Here's the first one I found in a quick search: utdallas.edu/~praba/6v81/3dModeling.pdf – Cuckoo

@Cuckoo Thanks for the heads up. I am going to go through that slides. Can you also suggest some readings for removing vertex. The tricky part is that no open boundary should be produced as shown in the second image. Thanks a lot! – Ceric

Your second picture is even more confusing than the first. You remove four edges and a vertex and create a new edge. – Transistorize

@YvesDaoust The second one is for remove vertex function. I removed the vertex at the center thus the fours edges have to be removed. I am talking about triangle mesh so that's the reason why I need to create a new edge. Otherwise the structure is not valid. – Ceric

@CCC: you shouldn't let us guess. – Transistorize

The link he provided suggests that this is about CG where triangles are the common structure. But, yeah, he shouldn't let us guess. – Fibroma

What do you expect to happen when you want to remove a vertex in the center of a pentagon? Or a hexagon... – Nopar

aka edge contraction – Kelleykelli

Answer 1

I will take this question to mean "How to implement edge collapse".

The algorithm itself is not that complicated once you have a working half edge DS.

• Grab the 2 vertices connected by the edge
• Set their out half edge pointers to be the next of the selected half edge and the pair (to avoid creating invalid pointers)
• Obtain the next of the half edge and the prev set them as a new half edge pair.
• Do the same for the pair of the selected half edge
• Select either of the vertices opposite to the the half edge. Set it to be the connecting vertex between the 2 newly generated half edges.
• Delete both faces, the unused vertex and the selected half edges.

Coolie

Can you recommend working implementations of such a DS? – Kelleykelli

You could try using OpenMesh. You could also try CGAL, those are the ones I know of the top of my head but I work with an implementation I made in my open source pet project so I have not used them personally. – Coolie