What is the best data structure for mesh simplification using some error metric and edge collapse? I like the half-edge data structure, but it doesn't support non-manifold meshes which I cannot ignore. It seems the more adjacency information you create the more complicated the book-keeping becomes. I wonder what is the best balance and I want an edge type since I deal with very large meshes (V > 1M) and I want to put the edges on a heap.

I had a little experience with this at one of my internships. From what I remember winged-edge was used and a fairly high level of abstraction was desired. The code that originally dealt with mesh simplification was very low-level and operated directly on the mesh indices, and after time experience showed that some helpers/abstraction were needed to maintain the code without going insane. Helpers for "allocating", collapsing, checking for adjacent or non-existent data, etc.

Eventually the heap itself became a performance bottleneck due to the single-threaded nature of the heap minimization, even though this code was for a bake-time preprocess. After I left my internship I heard work was put into modifying the algorithm to allow for multiple threads to do simultaneous work, since baking was just plain taking too long.

Hope this helps!

Winged-edge is the opposite of simple and a total overkill for this problem in my opinion. I am also surprised that the heap became a performance issue. Heap updates are 1-2 us for ~1M elements if implemented correctly. Hard to believe that this becomes a bottleneck.