Initializing Half-edge data structure from vertices

Question

I'm working on implementing various subdivision algorithms (such as catmull-clark); to do this efficiently requires a good way to store information about a grid of tesselated polygons. I implemented the half-edge data structure as outlined by flipcode, but now I'm not sure how to populate the data structure from vertices!

My initial attempt was to

• create vertices
• group vertices into faces
• sort vertices within faces (using their angle relative to the centroid)
• for each face, grab the first vertex and then walk through the sorted vertex list to create a half-edge list.

However, this creates a list of faces (with half-edges) that don't have any information about adjacent faces! This also feels a bit wrong, because it seems as if the faces are really the first-class object and the edges provide auxiliary information; I really feel like I should be creating edges from the vertices and then sorting out the faces from there. But again, I'm not really sure how to go about it that way -- I can't think of a way to create a list of half-edges without creating the faces first.

Any suggestions for what the best way to go turning data about vertices (and faces) into half-edges?

Answer 1

First, I'd like to point you to an excellent C++ implementation of the half-edge data structure: OpenMesh. If you want to use it, make sure you work you way through the tutorial. If (and only if) you do that, working with OpenMesh is quite straightforward. It also contains some nice methods on top of which you can implement subdivision or reduction algorithms.

Now to your question:

However, this creates a list of faces (with half-edges) that don't have any information about adjacent faces! This also feels a bit wrong, because it seems as if the faces are really the first-class object and the edges provide auxiliary information

I think this somewhat misses the point of the half-edge data structure. In a half-edge structure, it is the half-edges that carry the most information!

Quoting shamelessly from the OpenMesh documentation (see also the figure there):

• Each vertex references one outgoing halfedge, i.e. a halfedge that starts at this vertex.
• Each face references one of the halfedges bounding it.
• Each halfedge provides a handle to
  • the vertex it points to ,
  • the face it belongs to
  • the next halfedge inside the face (ordered counter-clockwise) ,
  • the opposite halfedge ,
  • (optionally: the previous halfedge in the face ).

As you see, most information is stored in the half-edges - these are the primary objects. Iterating over meshes in this data-structure is all about cleverly following pointers.

However, this creates a list of faces (with half-edges) that don't have any information about adjacent faces!

This is perfectly ok! As you see above, a face references only one bounding half edge. Assuming a triangle mesh, the chain of pointers you follow to get the 3 adjacent triangles to a given face F is the following:

F -> halfEdge -> oppositeHalfEdge -> face

F -> halfEdge -> nextHalfEdge -> oppositeHalfEdge -> face

F -> halfEdge -> previousHalfEdge -> oppositeHalfEdge -> face

Optionally, you can use nextHalfEdge -> nextHalfEdge if you don't use the 'previous' pointers. This, of course, generalizes easily to quads or higher order polygons.

If you set the pointers listed above correctly when building your mesh, then you can iterate over all kinds of adjacencies in your mesh like this. If you use OpenMesh, you can use a bunch of special iterators that to the pointer chasing for you.

Setting the "opposite half edge" pointers is of course the tricky part when building a half-edge structure from a "triangle soup". I suggest to use a map data-structure of some kind to keep track of half-edges already created.

To be more specific, here is some very conceptual pseudo-code for creating a half-edge mesh from faces. I omitted the vertex part, which is simpler, and can be implemented in the same spirit. I assume that iteration over a face edges is ordered (e.g. clock-wise).

I assume half edges are implemented as structs of type HalfEdge, which contain the pointers listed above as members.

   struct HalfEdge
   {
      HalfEdge * oppositeHalfEdge;
      HalfEdge * nextHalfEdge;
      Vertex * vertex;
      Face * face;
   }

Let Edges be a map from pairs of vertex identifiers to pointers to the actual half-edge instances, e.g.

map< pair<unsigned int, unsigned int>, HalfEdge* > Edges;

in C++. Here is the construction pseudo-code (without the vertex and face part):

map< pair<unsigned int, unsigned int>, HalfEdge* > Edges;

for each face F
{
   for each edge (u,v) of F
   {
      Edges[ pair(u,v) ] = new HalfEdge();
      Edges[ pair(u,v) ]->face = F;
   }
   for each edge (u,v) of F
   {
      set Edges[ pair(u,v) ]->nextHalfEdge to next half-edge in F
      if ( Edges.find( pair(v,u) ) != Edges.end() )
      {
         Edges[ pair(u,v) ]->oppositeHalfEdge = Edges[ pair(v,u) ];
         Edges[ pair(v,u) ]->oppositeHalfEdge = Edges[ pair(u,v) ];
       }
    }
 }

EDIT: Made the code a bit less pseudo, to be more clear about the Edges map and the pointers.