Computer Graphics Stack Exchange is a question and answer site for computer graphics researchers and programmers. It only takes a minute to sign up.
Sign up to join this community
For mesh representation, what is the benefit of using Half Edge over Winged Edge data structure?
I understand both mesh representations, the only difference is that half edge uses directional edge and winged edge uses undirectional edge. So far, I cannot think of what is the usefulness of using directional edge, yet it only gives more memory consumption.
As far as I can tell, the main advantage of half-edge is that traversal can be a bit simpler due to a guarantee of edges having a consistent orientation within each face.
Consider the problem of iterating over all the vertices or edges of a given face, in counterclockwise order. In the half-edge structure, this can be done by starting with an arbitrary half-edge of that face and simply following the "next" pointers until you get back where you started.
In contrast, doing this in a winged-edge structure is a bit annoying, because the edges are oriented arbitrarily; any given edge that you encounter might point either clockwise or counterclockwise relative to the face you're trying to iterate around, so you have to do an extra conditional check at each step to see if you should traverse the current edge forward or backward.
Other kinds of connectivity queries behave similarly: the half-edge version lets you follow links in a consistent sequence while the winged-edge version requires orientation checks at each step.
Whether the conditionals are actually a performance problem for winged-edge will probably depend on other factors. For a "naive" implementation with pointers every which way and data scattered across memory, I'd expect cache miss overhead to swamp any effect of the conditionals. On the other hand, if you have a tightly packed data structure with everything hot in the cache, you might see some effects from the conditionals due to incorrect branch predictions, etc. It's hard to say.
Leaving performance alone, I'd prefer half-edge just because it seems easier to reason about and write correct code for, even if it results in a slight memory overhead.
By the way, there are a couple of other design choices with mesh data structures that often seem to get confused with this one. A commenter mentioned single vs double linking, but naturally you can do either single or double linking with either half-edge or winged-edge. (Although I don't see how single linking with winged-edge would even work, since as mentioned above, you might have to traverse edges either backward or forward in the course of a query.)
Also, there's the question of whether the vertex and face structures store a list of all their edges, or just one (and require you to traverse the edges to find the rest). Having a variable-length list of edges per vertex/face considerably complicates the logic if you want to do it efficiently (i.e. not having a separate heap allocation per vertex/face), but again this is independent of whether the edges are half-edge or winged-edge.
