# Mesh Simplification

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

## Recommended Posts

Hello, I'm working on a mesh simplification algorithm. (I know Dx9 has one but seems to ignore my VertexWeights so its not much use to me). I have been pointed by various internet site to the Quadric Error Metrics algorithm SIGGRAPH 97 Garland & Heckbert. Having played around with this for a while and getting myself in a bit of a mess, I suddenly realised I think I've missed something. As far as I can see this algorithm only works for a 2D mesh that forms a Convex Hull. Am I correct in this ? Eventually my implementation of the algorithm (which operates only in 2D for the sake of simplicity) ends up generating a Concave Hull when the hull is the other Vertexes used by the triangles sharing the two vertexes to be eliminated. In the instance of A and B vertexes the hull is expressed as the vertexes of all the triangles sharing A and B. Essentially one can visualise this as a rough square with a 'panhandle' extending from it. This shape expresses a Concave Hull, and all things being equal the 'triangle flipping' will take place eventually. Two questions : (a) am I correct, and (b) is the easy way around it simply to check for this condition and prevent simplification around two vertexes whose component triangles express a Concave Hull ? Thanks (Please - I'm not a mathematician, if you can give me any advice simplicity would be appreciated).

##### Share on other sites
Quote:
 Original post by Phillip HamlynTwo questions : (a) am I correct, and (b) is the easy way around it simply to check for this condition and prevent simplification around two vertexes whose component triangles express a Concave Hull ?

The Garland-Heckbert approach works for orientable meshes in general (2D or 3D, manifold or nonmanifold). All that matters is that you have an adjacency graph for the vertices, edges, and triangles. My experience is that it is tedious and challenging to get a correctly working simplification algorithm of this type.

The topological problem you mention can occur, what I call the mesh "folding over" itself. Just having a triangle mesh whose boundary curve is a nonconvex polygon is not enough to guarantee the folding over will occur. It is possible that an edge collapse converts a nonconvex triangulated polygon of 5 sides to a convex triangulated quadrilateral. Yes, you should test for the folding over and disallow the edge collapse if it should lead to this condition. The same problem occurs even for nonplanar meshes in 3D. My implementation of the algorithm detects this and responds in the appropriate manner. Code can be found at my magic-software.com site, Source Code page, then Graphics tab, Component = Level of Detail, and file WmlCreateClodMesh.cpp. The function CollapseCausesFolding is relevant to the topic at hand.

##### Share on other sites
One other thing that you should be careful of with the Quadric error metric method is that if you have edges that you do NOT wish to potentially go away, be sure that you include quadrics for extra penalty planes so those edges will occur at the bottom of the priority queue. For example, if you have a 2D mesh that has a rectangular boundary, e.g., a terrain page that you wish to simplify without changing the boundary, make sure that you add a penalty plane each boundary vertex, for each triangle edge that the vertex participates in. In the terrain case, corner vertices will be affected by 2 penalty planes (1 vertical and 1 horizontal), and vertices on the interior of a boundary edge will be affected by 1 penalty plane (1 vertical *or* 1 horizontal depending on whether the vertex lies on the north, east, south, or west boundary.

##### Share on other sites
Thanks for the advice, its greatly appreciated.

Out of interest its the edge vertex weighting you describe that is leading me to go down implementing this myself - I'm pretty convinved the Dx9 SimplificationMesh and Mesh.Simplify use this algorithm but it ignores my VertexWeighting properties leading to ripping when I retessellate my meshes. I couldn't get it working at all .... :-(.

I'll persevere with the Quadric Error Metrics approach and test for a Convex Hull and see how far this gets me.

##### Share on other sites
Actually, I've just implemented a quadric error metric mesh simplifier myself. Once you get it right, it works really well. You really want to look at Appendix A of Garland's Ph.D thesis, which describes in succinct but sufficient detail his data structures and the entire algorithm as implemented in QSlim 2. I basically followed the appendix step-by-step and it just works. There may be one missing detail, which isn't too hard to figure out. The appendix may not explicitly show where to do the mesh folding test, but the thesis proper does describe a good way to do this test.

Quadric-Based Polygonal Surface Simplification, Ph.D Thesis

##### Share on other sites
Thanks to all that replied.

I've followed up the posted suggestions that I check for a Concave Hull before merging two vertexes; it took me a while but I got there in the end. It now simplifies my meshes wonderfully. Its a little faster than the Dx9 implementation as well although it is optimised for the specific case I'm working with (tessellated terrain meshes) so I'm not claiming its better in the general case ...

Its written in C# and being a professional .net developer it never ceases to suprise me what a nicely crafted language and library set it is; thats the tubthumping over.

Thanks all.

Phillip Hamlyn.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 22
• 16
• 13
• 14