Jump to content
  • Advertisement
Sign in to follow this  
Dirk Gregorius

Mesh simplification

This topic is 1069 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement

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!

Edited by Randy Gaul

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!