HalfEdge mesh representation

govert wrote at 2012-02-03 13:57:

HalfEdge-based representations of unstructured polygonal meshes are common in contemporary mesh processing libraries like OpenMesh, VCG and CGAL. A previous discussion here mentioned the HalfEdge representations briefly, and I wanted to add some links I've run into recently and start a discussion on the topic, as some integration of such representations and related algorithms into the Helix Toolkit would be great (though not an urgent priority for me).

The typical HalfEdge implementations are template heavy C++ code, using traits to embed additional data into the structures. This makes the conversion of such data types to .NET quite tricky, though keeping some compatibility with the C++ data structures can be useful to ease porting of the processing algorithms to .NET.

Having a look around a bit, I found this article by Alexander Kolliopoupos which discusses the implementation issues and suggests an elegant implementation in C#: http://www.dgp.toronto.edu/~alexk/halfedge.pdf. He also has an open source (liberal zlib/libpng license) library that implements these data structures here: http://www.dgp.toronto.edu/~alexk/lydos.html. It doesn't look like it is actively maintained, but might be a good start for integrating such a mesh representation into the Helix Toolkit.

If other users have some experience working with HalfEdge or related mesh representations in .NET, I'd be interested in any pointers. I'm particularly interested in pragmatic algorithms for model repair, smoothing and simplification. I also wonder what people think about implementing these in C# vs. wrapping one of the C++- based libraries in a .NET wrapper. (The GPL licensing of the existing libraries is a bit of a problem for me.)

Any thoughts appreciated...

objo wrote at 2012-02-03 14:09:

This looks very interesting! Will have a look at Kolliopoulos' article and code.

objo wrote at 2012-02-21 21:29:

I tried to make a naive halfedge class using LINQ, but don't have time to finish it right now. I checked it into the examples anyway. See HalfEdgeMeshDemo. I hope to continue this class later, it's an interesting algorithm to explore :)

At this point I did not include any generic traits (as the referenced libraries do) and did not focus on performance, I just wanted to see if I could get the data structure right. I also added a Visual3D class that lets you point and click to see adjacent vertices/edges/faces.