How to handle disconnected faces with same vertex for a half edge structure?

Question

I am trying to implement a half edge structure. It looks like this:

vertex:

• edge

• position

edge:

• vertex

• face

• previouse edge

• next edge

• twin edge

face:

• edge

now i noticed a problem when the mesh has two disconnected faces that share one vertex. For example in the case that all edge twins are null. I this case i can't find all edges from a vertex anymore.

image of a problem case.

In the image the vertex in the middle has only a reference to an edge of the white face. The black face is not reachable. How can i make this possible with the half edge structure?

Answer 1

Half-edge data structure allows only to represent manifold surfaces, thus this configuration is not allowed....

... but, if you add an unbounded face, the surface becomes manifold and you can describe this configuration. This is usually the solution used in the main library that implement HDS data structures.

With this unbounded face, each edge has two half-edges (there is no more null twin), and you need a way to differentiate half-edges that belong to the unbounded face and other half-edges (sometimes the unbounded half-edges have a null face).

Last remark, if you have several connected component, you will have several unbounded faces.