Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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). But I'm worried it could take too much memory or even have a negative impact on game's rendering performance.

share|improve this question
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? – teodron Feb 7 '13 at 12:51

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).

share|improve this answer
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. – Ilmari Karonen Nov 15 '11 at 14:20
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. – concept3d Nov 15 '11 at 14:30
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. – Ricket Nov 15 '11 at 14:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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