• Advertisement

3D Mesh Simplification & Decimation

Recommended Posts

Hello i recently started to tackle the various mesh decimation & simplification algorithms, mostly from Hoppe & Melax. The algorithms in question are the Quadric error metrics mesh simplification & the Progressive mesh simplification. I found a few good github starting points (VTK, hoppe's & melax's githubs etc.) to try and test the various implementations but i run into some problems:

1. I tried to simplify a few of mine and a few of the provided (inside the code base) meshes and i noticed that not all meshes survive the same simplification. For example a 400 vertices robot mesh can be simplified down do 10-20 (or about 3-7% of the src vertices) vertices without any problem no missing faces or huge topology distortion, yet an Eagle mesh with 3000 vertices can be just simplified to 1900-2000 (or about ~60-70% of the src vertices) vertices before i start noticing that the mesh starts to lose faces (which leads to a mesh with quite noticeable number of holes). And that is something i noticed with quite a few models (be it mine or the provided). I would like to know what is the actual cause which stops / prohibits some meshes from being simplified as much as others. I am probably asking a quite stupid or obvious question 

2. Even if the simplification was perfect i still have difficulty figuring out how would i preserve the vertex appearance (uv coord, tangents, normals etc.) I read a few papers - one in particular from Hoppe - New Quadric Metric for Simplifying Meshes with Appearance Attributes. But did not find any real world examples or at least snippets of code to give me a better grasp of the technique


Furthermore what has been bugging me lately is more about techniques to dynamically render different LOD levels when walking over a large terrain mesh (non regular grid - NOT generated from a height map, noise, 2D data, etc. so clipmapping techniques and alike go to the bin). I will give you a CS:GO analogy or Take League of Legends as it seems a more appropriate example here, i am not sure if they are doing that exact thing, but presume that their maps are mostly hand crafted, all trees, boxes, walls buildings which are not interactive, destructible or static are probably embedded and modeled along with the rest of the map & terrain. This can potentially allow for fewer draw calls, and much richer environment. But then again how would one optimize such a huge rendering step, where the entire model of the map / terrain may consist of at least 400-500k triangles at best
Or is it just a flat plane, with everything else rendered as a separate entity on top (instancing where possible, although given that most objects are quite unique and not very many instancing will be limited) ?

Edited by ????????? ?????

Share this post

Link to post
Share on other sites

No answers, but some input...


Interesting remeshing project, mainly due its performance and simplicity.

Remeshing and LODs is closely related. You should also try Simplygon which offers both options. There remeshing can fuse multiple objects and materials. Think of fusing terrain and individual rock models: In combination with megatexturing you can turn geometry into texture texels at the distance. Another interesting usecase for remeshing is geometry images and displacement mapping. (although i'm not impressd by current hardware displacement mapping, but the idea presists.)

There is also the idea to morph between fixed precalculated LOD levels. So instead of traversing something like a tree of collapsing edges, each LOD level has a morphing version with the vertex count of the higher detail level, but also knowing the positions of the lower detail to allow seamless transition (much more hardware friendly).

For high frequency/detailed geometry (e.g. vegetation) none of the above can do wonders, but things like volume rendering, splatting or automatic generation of billboards makes sense.


Personally i think the main issue is that we lack robust algorithms that can 'understand' geometry. Just collapsing edges is pretty naive if you think about it. Most interesting current approaches are there in the fields of quad remeshing (e.g. 'QuadCover' or 'Mixed Integer Quadrangulation') or automatic generation of Polycubes. Unlike the simple project linked above those methods try to find a global (likely minimal) set of singularities on the surface, and from that you could calculate things like minimal possible LOD or seamless UV parametrization (the latter is my current interest).


There is also related research on texture mapping: http://www.cemyuksel.com/courses/conferences/siggraph2017-rethinking_texture_mapping/rethinking_texture_mapping_course_notes.pdf

E.g. you can use volume encoded UV maps to decouple mesh LODs from texture coords.

Edited by JoeJ

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By too_many_stars
      Hello Everyone,
      I have been going over a number of books and examples that deal with GLSL. It's common after viewing the source code to have something like this...
      class Model{ public: Model(); void render(); private: GLSL glsl_program; }; ////// .cpp Model::Model(){ glsl_program.compileAndLinkShaders() } void Model::render(){ glsl_program.use() //render something glsl_program.unUse(); } Is this how a shader program should be used in real time applications? For example, if I have a particle class, for every particle that's created, do I want to compiling and linking a vertex, frag shader? It seems to a noob such as myself this might not be the best approach to real time applications.
      If I am correct, what is the best work around?
      Thanks so much for all the help,
    • By katastrophic88

      Hello Everyone!
      I’m now working with Zugalu -- developer of an upcoming SHMUP named Technolites – as Community Manager.
      In Technolites, you’ll take command of a fully customizable ship and dash across the universe to defeat an ancient alien threat. Deploy more than 500 weapons and utility upgrades – fighting by yourself or with a friend. The fate of humanity rests in your hands. We’re currently live on Kickstarter, and we’d love it if you could check out our page! Any feedback is greatly appreciated
      Looking forward to seeing all of the great game projects being developed and launching this year!
    • By getoutofmycar
      I'm having some difficulty understanding how data would flow or get inserted into a multi-threaded opengl renderer where there is a thread pool and a render thread and an update thread (possibly main). My understanding is that the threadpool will continually execute jobs, assemble these and when done send them off to be rendered where I can further sort these and achieve some cheap form of statelessness. I don't want anything overly complicated or too fine grained,  fibers,  job stealing etc. My end goal is to simply have my renderer isolated in its own thread and only concerned with drawing and swapping buffers. 
      My questions are:
      1. At what point in this pipeline are resources created?
      Say I have a
      class CCommandList { void SetVertexBuffer(...); void SetIndexBuffer(...); void SetVertexShader(...); void SetPixelShader(...); } borrowed from an existing post here. I would need to generate a VAO at some point and call glGenBuffers etc especially if I start with an empty scene. If my context lives on another thread, how do I call these commands if the command list is only supposed to be a collection of state and what command to use. I don't think that the render thread should do this and somehow add a task to the queue or am I wrong?
      Or could I do some variation where I do the loading in a thread with shared context and from there generate a command that has the handle to the resources needed.
      2. How do I know all my jobs are done.
      I'm working with C++, is this as simple as knowing how many objects there are in the scene, for every task that gets added increment a counter and when it matches aforementioned count I signal the renderer that the command list is ready? I was thinking a condition_variable or something would suffice to alert the renderthread that work is ready.
      3. Does all work come from a singular queue that the thread pool constantly cycles over?
      With the notion of jobs, we are basically sending the same work repeatedly right? Do all jobs need to be added to a single persistent queue to be submitted over and over again?
      4. Are resources destroyed with commands?
      Likewise with initializing and assuming #3 is correct, removing an item from the scene would mean removing it from the job queue, no? Would I need to send a onetime command to the renderer to cleanup?
    • By Nimmagadda Subba Rao
         I am a CAM developer working with C++ and C# for the past 5 years. I started working on DirectX from past 6 months. I developed a touch screen control viewer using Direct2D. I am working on 3D viewer currently. I am very slow with working on Direct3D. I want to be a gaming developer. As i am new to this i want to know what are the possibilities to explore in this area. How to start developing gaming engines? Is it through tutorials? I heard suggestions from my friends that going for an MS helps. I am not sure on which path to choose. Is it better to go for higher studies and start exploring? I am currently working in India. I want to go to Canada and settle there. Are there any good universities there to learn about graphics programming? Sorry if I am asking too many questions but i want to know the options to choose to get ahead. 
  • Advertisement