   Mesh simplification algorithms
  I am looking for a mesh simplification algorithm, preferably with some sample code. The reason I am looking for one such algorithm is for having different LODs for meshes, and also to deduce a collision mesh from my models.I have a description of the edge-collapse algorithm, but I'm curious if there are better/faster/easier algorithms out there.   
  I use an algorithm from the paper 'Surface Simplification Using Quadric Error Metrics' by M Garland and P Heckbert myself. Its one example of an edge collapse algorithm, which most mesh simplification algorithms are. In my experience its extremely good, though if your using it for games you will need to run it in advance. Its quite easy to implement if you have the code for a good mesh data structure, matrix inversion and a priority queue available.Anyway, you can get the various version of the paper from http://graphics.cs.uiuc.edu/~garland/research/quadrics.html and a piece of software with sourcecode available for download from http://graphics.cs.uiuc.edu/~garland/software/qslim.html. Not sure what license is on that programs code though, and you would have to separate it from the gui etc.One quick note though, you can not use mesh simplification algorithms to generate collision meshes as there will be parts in the original mesh that exit the bounds of the simplified mesh, which is usually not the desired affect. There are presumably algorithms designed with this in mind, but I have no idea of any specific one.   ;  You might find these useful:http://www.cs.virginia.edu/~luebke/publications/pdf/cg+a.2001.pdfhttp://www.stanford.edu/~jtalton/papers/Talton04SSMSA.pdf   ;  Thanks for the links, they seem very useful. Esuvs first link also mentions the Quadric Error Metrics algorithm and calls it having "perhaps the best balance yet between speed, fidelity, and robustness". So far it seems the best candidate.Quote:Original post by LetheOne quick note though, you can not use mesh simplification algorithms to generate collision meshes as there will be parts in the original mesh that exit the bounds of the simplified mesh, which is usually not the desired affect. There are presumably algorithms designed with this in mind, but I have no idea of any specific one.I am not sure what you mean by this. Especially the part "exit the bounds of the original mesh". Finding an algorithm for generating a collision mesh is at this point very important to me (more than LOD at this point).I can not imagine an algorithm that reduces geometry AND can preserve the exact shape of the object. Unless the triangles that are removed are coplanar, the reduced mesh will always be smaller than the original and you will see the meshes intersect eachother. In my opinion this is acceptable up to some level.If you mean the algorithm removing spiky features from the mesh, I thought I read QEM accounts for this in the paper in Esuvs second link.I know no more about this subject than what I just read in those papers, so please correct me if I'm wrong.   ;  John Ratcliff did some great work on this topic.  Check it out at:linkyI used some of this stuff during some R & D work at my previous employer.  The tools he has created are extremely helpful.  You might also look through his website a bit to see if he has an updated version / discussion of these tools.   ;  Here is a very very easy algorithm that works fairly well :http://www.graphicon.ru/2004/Proceedings/Technical/2%5B4%5D.pdfAnd here is a very interesting comparison of VIPM methods :http://home.comcast.net/~tom_forsyth/papers/gem_vipm_webversion.htmlRegardig the collision meshes, the problem is that edge collapse techniques result in a mesh that intersects the original mesh, whereas what you usually want is a collision mesh that includes (i.e. bigger than) the original mesh.Vincent   