I've created a map editor for a game I've been developing. The maps (planets) are made using a form of meta ball editing. Basically, in the end the Marching Cubes algorithm is used to get my final model.

Here's an example: enter image description here

In the game however, when planets are or a largish size, as you would expect, I start having quite a lot of lag. So what I was wondering, is are there any good libraries out there that could be used to remove clusters or triangles that are basically flat and turn them into a single triangle?

I'm not after simply reducing the count, I want the same amount of detail, but to merge triangles where their normal is practically the same.

Also curious, as to how you would go about having more/less detail as you approach/leave areas of a planet. Obviously chunks isn't the easiest method when the world's a sphere.

The project is in C#.


What you are looking for is called a mesh simplification/decimation algorithm. There are several of them out there, you'd just have to implement the one you choose in C# if no C# implementation exists.

Here are a few that Google turned up:

From a quick search, the only C# implementation that I found was part of Managed DirectX (predecessor to XNA), it had a SimplificationMesh class.


You can follow Robert's suggestions.

If you're looking for a sharp implementation, you could try to wrap some of the modules of the CGAL library (that's C++ based) using C++/CLI (the C++ managed dialect). I suggest CGAL since it's quite one of the best libs for this kind of jobs.

For a more in-depth understanding and/or a from-scratch implementation (shouldn't take you more than a week), you can consult the seminal papers of Hoppe (Microsoft Research) and that of Greg Turk on mesh decimation via edge collapses (heuristic based approaches for progressive mesh simplification/multiresolution applications/LOD):

Additionally, a fairly interesting and more mathematical approach was built using lifting schemes and second generation wavelet analysis and synthesis. In essence, that means that if you have a subdivision scheme on your hands (say the Butterfly scheme), you can find a converse decimation operator (from many to fewer points). If you already have a "nice" surface in terms of how the triangle faces are distributed and of the density of regular points (those with valence 6), then you can apply the decimation operator to do the job.

If you want to achieve multiresolution representation, the steps are crudely summarized as follows:

  1. decimate the mesh M_{i+1} to a mesh M_{i}
  2. subdivide M_{i} and record the differences between S*M_{i} and M_{i+1} as the so called wavelet coefficients
  3. a well chosen subdivision scheme is expected to predict the positions of the removed points (via edge collapse/decimation,etc.) quite well - hence one can threshold the differences/wavelet coefficients and discard small values

In the end, you get a coarse resolution M_{0} and a hierarchy of detail vectors which you usually store. Considering that most of those coefficients were discarded, you get a storage space optimization. You can, of course, apply some floating point numerical compression (quantization, Huffman and/or entropy encoding, what not) - but that's not the point of your question. The advantage is that the coarsest level mesh, M_{0} only requires the storage of a few hundred points, whereas the initial mesh could've been millions of vertices large. You get the intermediate levels through subdivision and correction via your non-zero wavelet coefficients. Again, considering that many of the differences are expected to be small, you automatically gain the edge since you store less information than within the original mesh and get the intermediate LODs at the expense of your CPU (which is much better than pushing that info over a socket, for example).

Some wavelet multiresolution bibliography:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.