Is it feasible to use half-edge mesh, in games, instead of vertex-face structure? What comes to my mind is that it could be useful in mesh simplification (dynamic level of detail). However, I'm worried it could take too much memory, or even have a negative impact on a games rendering performance.

  • 1
    \$\begingroup\$ If you need to edit the mesh in a complicated way considering local topology, then half edge and winged edge DSs are good, theoretical candidates. Mind that they rely on heap allocated data, which can lead to poor performance. Do you need multiresolution mesh editing? Are you measuring internal distances on polyhedral surfaces? \$\endgroup\$
    – teodron
    Feb 7, 2013 at 12:51

1 Answer 1


I just read about the half-edge mesh structure; this page was helpful. Thanks for showing it to me!

If your main game mechanic involves lots of dynamic level of detail calculations on meshes, then it would be a great choice. Also if you were developing a mesh editor, you might consider using it if the user would often perform operations which the structure is better at. Otherwise, it doesn't seem like an advantage for game purposes. Personally, I would rather precalculate level of detail meshes and then use the conventional mesh format.

Furthermore, the restriction that it can only represent manifold surfaces sounds like a deal-breaker to me. I imagine very few game models are actually capable of being represented this way.

I think with any alternate data structure, you should consider the cons along with the pros. This data structure looks neat, it certainly has its pros, but it doesn't seem a better fit for games than the current widely used format of vertices and faces (whatever its name may be).

  • 1
    \$\begingroup\$ I just read that page too -- thanks! It seems like you could handle holes in manifolds by filling them in with "dummy" faces that don't get rendered (and which probably don't even need to be flat). Then you could decompose your models into a bunch of partial manifolds, which probably comes pretty naturally in many cases anyway. \$\endgroup\$ Nov 15, 2011 at 14:20
  • \$\begingroup\$ I am thinking of taking the two paths.. for example I would use half-edge data structure for meshes that heavily uses DLOD or if used in the game editor otherwise I would just convert it to vertex-face representation. \$\endgroup\$
    – concept3d
    Nov 15, 2011 at 14:30
  • \$\begingroup\$ I don't know that heavy DLOD is a good idea no matter the format. Clearly the half-edge format is better at it, but it still seems like it would be a pretty heavyweight calculation. And normally you would precalculate anything so intensive - which, of course, basically defeats the point of using the special format, unless your precalculation stage is extremely time-sensitive. \$\endgroup\$
    – Ricket
    Nov 15, 2011 at 14:39
  • \$\begingroup\$ It's easy to support non-manifold meshes with a halfedge structure. I've done it myself. You need a few more checks in various places that would normally assume every halfedge has a pair but it works fine. \$\endgroup\$
    – Andy Baker
    Dec 31, 2020 at 16:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .