Looking for Winged-Edge data structure implementation?

bit old but still cuts the mushroom: https://stackoverflow.com/questions/6694724/how-does-the-winged-edge-structure-for-meshes-work​

this course will show u some algos but u've gotta cut the mushroom yourself, not hard, give a go: http://www.cs.cornell.edu/courses/cs4620/2013fa/lectures/07trimesh.pdf​

That's it … all the best ?

Well ….. I just learned something new. I've been using something like this for years and never knew it had an actual name. Mine is tied to my reference counting heap however and only supports tris and quads at the moment, as that is really all I need. But It does support subdivision and chunking for LOD. At least I can show you it working. There is a video in my blog entry here: https://www.gamedev.net/blogs/entry/2267347-here-comes-the-sun/​

It's pretty fast for LOD because you don't have to go up and down the quad-tree to spit and merge polygons and in fact whole chunks. But I don't need non manifold geometry. I think it would be easy to support it If I did. You would basically need to have edges that support N number (or perhaps some max number) of back pointers. You could also use weak pointers instead of back pointers but you might end up with a lot of temporarily uncollected faces if you did that, depending on exactly how you use it.

You should also determine how you want to traverse your data. For instance I never start at a vertex for a traversal so my vertexes don't have any pointers. I can start at any face or edge and go from face to edge to face, or I can go around the edges of any poly and find all it's edges and vertexes.

In any case I would figure out how exactly you are going to use the data before settling on an implementation, because the devil is in the details. You can always go for something super general, but there are probably some performance trade offs. However, if it's going to be used in an offline tool and not a game you may not care.

SRaD said:
Winged edge data structures seem to be used quite often

AFAIK, winged edge has the same manifold ‘limitation’ than half edge, though i never used it so not sure. (I think Winged edge uses only one struct per edge, while half edge uses two for each side. But winged also assumes an edge can only be adjacent to two faces, so it's restricted to manifold as well.)

You really should tell us more about your requirements and application, otherwise it's hard to help.
What are the non manifold cases you need to support? Maybe, after some talk it would turn out you can do what you want while still using OpenMesh. (I'm pretty sure that's the case.)

Here are some examples, and how to resolve them:

• Extruding a face from a closed edge. Imagine you have mesh of a sphere, and you take one edge and want to extrude a quad out of it, eventually so you can add hair or foliage details using alpha tested texture.
  To do this using manifold mesh, you can either: Duplicate the edge including the vertices and create the face from that (face so is disconnected from the sphere mesh and no non-manifold situation comes up.)
  Or: Open the edge and actually add 2 quads (front and back face). Then the new quads are connected to the sphere surface and it's correctly manifold. And you can use usual backface culling to draw only the quad that is facing the camera at runtime.
• Making two objects touch at a single vertex. Imagine two cubes, and they should share one of their corner vertices each. This is not possible using half edge, but you can just duplicate the vertex.

In fact the only cases that require non manifold mesh data structure are impossible objects like Moebius Strip or Klein Bottle. But nobody would need stuff like that for games. Collision detection would not work either, etc.

Gnollrunner said:
You should also determine how you want to traverse your data. For instance I never start at a vertex for a traversal so my vertexes don't have any pointers. I can start at any face or edge and go from face to edge to face, or I can go around the edges of any poly and find all it's edges and vertexes.

That's really a strong feature of Half Edge: You can traverse edges of a face or edges at a vertex (all in clock wise order), using the same data structure.

Before i've switched to Half Edge, i was using my own data structure of each vertex and face storing clock wise sorted lists of adjacency. After the change it turned out half edge takes less memory and implementing mesh editing became much easier.

For a newbie, usually the first obstacle with Half Edge is the construction of a mesh from imported index mesh data, like used in most mesh file formats. But i would assume OpenMesh makes this easy.

That said, i can recommend Half Edge for geometry processing tasks, just usually such tasks rarely come up for games production because 3D editing software does it for us.

That's really a strong feature of Half Edge: You can traverse edges of a face or edges at a vertex (all in clock wise order), using the same data structure.

If I ever need to do that I can add one pointer from a vertex to one of it's owning, edges but at this point I simply don't need it. The rest of the stuff I can do with a single edge instead of half edges. The down side is I store pointers to each edge with the face which takes more memory. The up side is I don't have to circle the face though edges and vertexes to get to the edge I need, so moving from face to face has less of a chance of generating cache misses. For me that's important because I intend to do pathing with it. I guess like everything else it depends what exactly you are going to use it for