# Inserting a new face in a Half Edge data structure (open-mesh and not)

I'm trying to figure how to implement face insertion in a halfedge data structure to represent 3D meshes, I think it's safe to assume I'll only deal with meshes that have disc topology.

Although I've asked here to help me out with the understanding of the algorithm (taken from the open-mesh library). However I just read through the documentation and openmesh can also handle non manifold meshes, therefore maybe understanding that algorithm doesn't have any benefit on the case of manifold surfaces.

If you have any understanding of open-mesh can you please share, if you know, how the insert face works?

Otherwise, for the case of disc topology meshes, can you tell me how the new face insertion should work?

The bit I get confused is how to guarantee the disc topology is preserved when one of bounding vertices is already incident to some faces.

Even a reference would be great.

More detail:

In a mesh library like CGAL or OpenMesh the first step in creating a mesh is to specify vertices. I.e. suppose you have vertices $$v_1,\ldots, v_n$$ this would be added to a mesh with function calls like vh[i] = m.add_vertex(v[i]) here vh[i] is the vertex handle (usually returned) by inserting v[i]. Once this is done we can specify connectivity of such vertices.

As mentioned in openmesh to PolyConnectivity class as a method add_face whose input is a list of vertex handles, if you read through the code you can see how the connectivity is updated. As I mentioned I've tried to read through the code, but is quite hard for me to understand why some halfedges are updated in a certain way.

• What do you mean by insert a new face? Are you subdividing an existing face, extending a face outwards from the boundary using an existing edge (or path of boundary edges), or creating a brand new face on its own disconnected from the existing data? – John Apr 29 at 12:32
• I'll update my post. – user8469759 Apr 29 at 13:03
• I've updated my post and to answer your question is creating new faces on its own. Extending a face using boundary edge is also a use case. – user8469759 Apr 29 at 13:09