From CGAFaq

Contents 1 What is a good way to implement the half-edge structure? 1.1 Introduction 1.2 Goals 1.3 Marking the boundary of the mesh 1.4 Conventions 1.5 Making two half-edges adjacent 1.6 Adding a vertex 1.7 Adding an edge 1.8 Adding a polygon into the mesh 1.9 Removing a polygon 1.10 Removing an edge 1.11 Removing a vertex

What is a good way to implement the half-edge structure?

Introduction

There are many ways to implement the half-edge structure. They differ both in capability of representing different kinds of meshes, in the ease of use and in the ease of implementation. This article represents an implementation strategy that does well in all of these areas.

This article relies on the conventions given in the introductory article.

Goals

• Algorithms must make it possible to represent the widest possible set of different polygon meshes that the half-edge structure can represent.
• Algorithms must be easy to understand.

Marking the boundary of the mesh

Isolated vertices are represented by their half-edge pointer being null.

Boundary half-edges are marked with a null 'left' polygon.

In particular, a null half-edge pointer in the half-edge 'pair' field should not be used to mark the boundary. If this is done then the data structure cannot be used to traverse around the vertices correctly. This is the reason why the existence of pairs is guaranteed by the invariants.

Conventions

For a half-edge h and vertex v, we define:

• h.rotateNext() := h.pair().next()
• h.isFree() := h.left().empty()
• v.isolated() := v.half().empty()

Making two half-edges adjacent

Given is a half edge A arriving at vertex V, and a half edge B leaving from V. We would like to order, if possible, the neighbourhood of V such that A is a predecessor of B (B.previous = A) and B is a successor of A (A.next == B).

Of course, for this to make sense, A and B must both be free (A.left = B.left = null). Reordering the neighbourhood is required when adding a polygon. Because we want to connect A and B together, the link chain around V must be cut at A.next and B.previous. These two half-edges denote a region around V. This region was between A and B, but now it has to be moved between two other successive, free half-edges, say G and H (H = g.next). If there is no such half-edge G, the reordering is not possible.

bool HalfMesh::makeAdjacent(Half in, Half out)
{
    if (in.next() == out)
    {
        // Adjacency is already correct.

        return true;
    }

    Half b(in.next());
    Half d(out.previous());

    // Find a free incident half edge
    // after 'out' and before 'in'.
    Half g(findFreeIncident(out.pair(), in));
    if (g.empty())
    {
        // There is no such half-edge.
        return false;
    }
    Half h(g.next());

    in.half_->next_ = out.half_;
    out.half_->previous_ = in.half_;

    g.half_->next_ = b.half_;
    b.half_->previous_ = g.half_;

    d.half_->next_ = h.half_;
    h.half_->previous_ = d.half_;

    return true;
}

The findFreeIncident is defined as follows:

Half HalfMesh::findFreeIncident(
    Half startingFrom, Half andBefore) const
{
    if (andBefore == startingFrom)
    {
        return Half();
    }
    Half current(startingFrom);
    do
    {
        if (current.left().empty())
        {
            return current;
        }
        current = current.next().pair();
    }
    while (current != andBefore);
    return Half();
}

Adding a vertex

• Allocate the vertex.
• Set the vertex's 'half' field to null.

Adding an edge

• Allocate an edge.
• Allocate two half-edges.
• Initialize the half-edges to be paired and linked to each other.
• Associate the half-edges with the edge and vice versa.
• Link one side of the edge to the mesh.
• Link the other side of the edge to the mesh.

Edge HalfMesh::addEdge(Vertex fromVertex, 
                       Vertex toVertex)
{
   // Decide what to do with loop edges.
   bool loopEdges = true;
   if (!loopEdges)
   {
      if (fromVertex == toVertex)
      {
         return Edge();
      }
   }

   // Decide what to do with parallel edges.
   bool parallelEdges = true;
   if (!parallelEdges)
   {
      Half existingHalf(findSomeHalf(fromVertex,
         toVertex));

      if (!existingHalf.empty())
      {
         return existingHalf.edge();
      }
   }

   // Allocate data

   Edge edge(allocateEdge());
   Half fromToHalf(allocateHalf());
   Half toFromHalf(allocateHalf());

   // Initialize data

   {
      EdgeData* edgeData = edge.edge_;
      edgeData->half_ = fromToHalf.half_;
   }

   {
      HalfData* halfData = fromToHalf.half_;

      halfData->next_ = toFromHalf.half_;
      halfData->previous_ = toFromHalf.half_;
      halfData->pair_ = toFromHalf.half_;
      halfData->origin_ = fromVertex.vertex_;
      halfData->edge_ = edge.edge_;
      halfData->left_ = 0;
   }

   {
      HalfData* halfData = toFromHalf.half_;

      halfData->next_ = fromToHalf.half_;
      halfData->previous_ = fromToHalf.half_;
      halfData->pair_ = fromToHalf.half_;
      halfData->origin_ = toVertex.vertex_;
      halfData->edge_ = edge.edge_;
      halfData->left_ = 0;
   }

   // Link the from-side of the edge.

   if (fromVertex.isolated())
   {
      VertexData* vertexData = fromVertex.vertex_;
      vertexData->half_ = fromToHalf.half_;
   }
   else
   {
      Half fromIn(findFreeIncident(fromVertex));
      Half fromOut(fromIn.next());

      fromIn.half_->next_ = fromToHalf.half_;
      fromToHalf.half_->previous_ = fromIn.half_;

      toFromHalf.half_->next_ = fromOut.half_;
      fromOut.half_->previous_ = toFromHalf.half_;
   }

   // Link the to-side of the edge.

   if (toVertex.isolated())
   {
      VertexData* vertexData = toVertex.vertex_;
      vertexData->half_ = toFromHalf.half_;
   }
   else
   {
      Half toIn(findFreeIncident(toVertex));
      Half toOut(toIn.next());

      toIn.half_->next_ = toFromHalf.half_;
      toFromHalf.half_->previous_ = toIn.half_;

      fromToHalf.half_->next_ = toOut.half_;
      toOut.half_->previous_ = fromToHalf.half_;
   }

   return edge;
}

Adding a polygon into the mesh

• Check that the data is valid and that the given half-edge loop can be turned into a polygon as given by the required conditions.
• Reorder the links such that the given half-edge loop becomes sequential, ie. that the 'next'-field of one half-edge points to the next half-edge in the loop (similarly for 'previous'-fields).
• Create the polygon.
• Associate polygon with one of the half-edges of the given half-edge loop.
• Associate all of the half-edges of the loop with the polygon.

Polygon HalfMesh::addPolygon(const std::vector<Half>& halfLoop)
{
   if (halfLoop.empty())
   {
      return Polygon();
   }

   integer halfCount = halfLoop.size();

   // Check that the half-edges are free
   // and form a chain.

   for (integer i = 0;i < halfCount;++i)
   {
      integer nextIndex = i + 1;
      if (nextIndex == halfCount)
      {
         nextIndex = 0;
      }

      Half current(halfLoop[i]);
      Half next(halfLoop[nextIndex]);

      if (current.destination() != next.origin())
      {
         // The half-edges do not form a chain.
         return Polygon();
      }
      if (!current.isFree())
      {
         // The half-edge would introduce a
         // non-manifold condition.
         return Polygon();
      }
   }

   // Try to reorder the links to get
   // a proper orientation.

   for (integer i = 0;i < halfCount;++i)
   {
      integer nextIndex = i + 1;
      if (nextIndex == halfCount)
      {
         nextIndex = 0;
      }

      if (!makeAdjacent(halfLoop[i], halfLoop[nextIndex]))
      {
         // The polygon would introduce a non-manifold
         // condition.
         return Polygon();
      }
   }

   // Create the polygon

   Polygon newPolygon(allocatePolygon());

   // Link the polygon to a half-edge

   PolygonData* polygonData = newPolygon.polygon_;
   polygonData->half_ = halfLoop[0].half_;

   // Link half-edges to the polygon.

   for (integer i = 0;i < halfCount;++i)
   {
      Half current(halfLoop[i]);

      HalfData* halfData = current.half_;
      halfData->left_ = newPolygon.polygon_;
   }

   return newPolygon;
}

Removing a polygon

• Associate all of the half-edges of the polygon to the null polygon.
• Deallocate the polygon.

void HalfMesh::removePolygon(Polygon polygon)
{
   Half begin(polygon.half());
   Half current(begin);

   do
   {
      HalfData* halfData = current.half_;
      halfData->left_ = 0;
      current = current.next();
   } 
   while(current != begin);

   deAllocatePolygon(polygon);
}

Removing an edge

• Remove all of the associated polygons of the edge.
• Link the half-edges of the edge off from the mesh. This requires modifying the relationships between neighbouring half-edges and possibly modifying the 'half'-field of the endvertices.
• Deallocate the edge and its half-edges.

bool HalfMesh::removeEdge(Edge edge)
{
   Half fromToHalf(edge.half());
   Half toFromHalf(fromToHalf.reverse());

   // Remove the neighbouring polygons.

   if (!fromToHalf.left().empty())
   {
      removePolygon(fromToHalf.left());
   }

   if (!toFromHalf.left().empty())
   {
      removePolygon(toFromHalf.left());
   }

   // Link the from-side of the edge
   // off the model.

   Vertex fromVertex(fromToHalf.origin());

   Half fromIn(fromToHalf.previous());
   Half fromOut(fromToHalf.rotateNext());

   if (fromVertex.half() == fromToHalf)
   {
      if (fromOut == fromToHalf)
      {
         fromVertex.vertex_->half_ = 0;
      }
      else
      {
         fromVertex.vertex_->half_ = fromOut.half_;
      }
   }

   fromIn.half_->next_ = fromOut.half_;
   fromOut.half_->previous_ = fromIn.half_;

   // Link the to-side of the edge
   // off the model.

   Vertex toVertex(toFromHalf.origin());

   Half toIn(toFromHalf.previous());
   Half toOut(toFromHalf.rotateNext());

   if (toVertex.half() == toFromHalf)
   {
      if (toOut == toFromHalf)
      {
         toVertex.vertex_->half_ = 0;
      }
      else
      {
         toVertex.vertex_->half_ = toOut.half_;
      }
   }

   toIn.half_->next_ = toOut.half_;
   toOut.half_->previous_ = toIn.half_;

   // 3) Deallocate data

   deAllocateHalf(fromToHalf);
   deAllocateHalf(toFromHalf);
   deAllocateEdge(edge);
}

Removing a vertex

• Remove all of the edges associated to the vertex.
• Deallocate the vertex.

void HalfMesh::removeVertex(Vertex vertex)
{
   if (!vertex.isolated())
   {
      // Remove every edge that is connected
      // to this vertex

      Half current;
      Half next(vertex.half());

      do
      {
         current = next;
         next = next.rotateNext();
         // Avoid removing the same edge
         // twice in case of an edge loop.
         if (next.edge() == current.edge())
         {
            next = next.rotateNext();
         }
         removeEdge(current.edge());
      }
      while(current != next);
   }

   deAllocateVertex(vertex);
}