8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "The only difference is that half edge uses directional edge and winged edge uses undirectional edge." From my understanding, more like: Half-edge is doubly linked (and each direction may contain additional information), while winged edge is, most commonly, counter-clockwise only. $\endgroup$ – David Kuri Feb 15 '16 at 11:28
  • $\begingroup$ So, you mean the way they use doubly linked simply to add more info explicitly? Because I think by using Half Edge there might be some performance gained for specific query from the mesh. But till now, I still cannot figure which query.. $\endgroup$ – Bla... Feb 16 '16 at 7:28
  • $\begingroup$ While we're on edge-representations, this is a great paper, generalising a lot of them: graphics.cs.ucdavis.edu/~joy/ecs178/Unit-9/resources/… $\endgroup$ – Mikkel Gjoel Feb 16 '16 at 19:56
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.