Winged-edge vs half-edge

Question

I try to understand boundary representation (B-rep) and I cannot find what's the advantages of the half-edge data structure versus the winged-edge one. I've found in this book that winged-edge cannot represent the state where a vertex but no edges exists in space. But there is no sample.

Another book says that there is an ambiguity in the edge direction.

And finally, on a this web page, performance reasons are invoked.

score 5 · Answer 1 · answered Jan 03 '16 at 08:17

I've found the solution in this paper.

With winged-edge, you've got this data structure:

The code in C# is as follow:

public class WingedEdge
{
    public Curve3d Curve { get; set; }

    /// <summary>
    /// Edge of the left loop starting on the end vertex of this edge.
    /// </summary>
    public Edge EndLeftEdge { get; set; }

    /// <summary>
    /// Edge of the right loop starting on the end vertex of this edge.
    /// </summary>
    public Edge EndRightEdge { get; set; }

    /// <summary>
    /// Vertex on the end point of the edge.
    /// </summary>
    public Vertex EndVertex { get; set; }

    /// <summary>
    /// Face on the left side of the edge.
    /// </summary>
    public Face LeftFace { get; set; }

    /// <summary>
    /// Face on the right side of the edge.
    /// </summary>
    public Face RightFace { get; set; }

    /// <summary>
    /// Edge of the left loop ending on the start vertex of this edge.
    /// </summary>
    public Edge StartLeftEdge { get; set; }

    /// <summary>
    /// Edge of the right loop ending on the start vertex of this edge.
    /// </summary>
    public Edge StartRightEdge { get; set; }

    /// <summary>
    /// Vertex on the start point of the edge.
    /// </summary>
    public Vertex StartVertex { get; set; }
}

On the face, you only need to store one of the bounding edge, as the structure forms a double linked list, you can retrieve the other edges:

public class Face
{
    /// <summary>
    /// One of the edges bounding this face.
    /// </summary>
    public WingedEdge FirstEdge { get; set; }
}

But if you need to iterate over the edges of a face, you will use this code:

WingedEdge edge = face.FirstEdge;
do {
  // Do something with the edge
  WingedEdge edge = edge.LeftFace == face ? edge.LeftNextEdge : edge.RightNextEdge;
} while (edge != face.FirstEdge)

We have to use a conditional expression (? :) in the loop to find the next edge. On modern processors, this lead to a performance hit, as described in this post.

The half-edge data structure has not this problem (but takes more memory).

Winged-edge vs half-edge

1 Answers1