Mesh Simplification Algorithm

September 24, 2010 General News 0 Comments

I must admit, this is the hardest problem I've ever encountered in all my years of programming. I'm not sure why it took me so long, but I had to retry this problem four times before I finally got the algorithm right. I approached it using STL, then I approached it using custom containers, hacky tricks, and finally came back around to STL and got it right this time. It took two weeks of painful debugging and it completely halted all other progress - but it's done.

Mesh simplification is really a very necessary tool to have in conjunction with marching cubes, since the polygonization algorithm has no concept of efficients and will allocate as many triangles to a planar surface as it will a curved one. Obviously, such waste is not acceptable on a large scale.

Below are a few shots that demonstrate the results of the algorithm, which I ran on the ellipsoid-starship discussed in the previous post. I'm happy with the results. The algorithm can slash the polygons in half without much loss in visual quality, even though the starship isn't a very wasteful surface to begin with (it has a lot of curvature). I'm aware that the wireframes look rather messy and odd, but that's just how edge collapse works.

My only complain is with shading. While the mesh doesn't lose an appreciable amount of quality at MQ, the shading does. Normals get ugly fast, and I'm not sure what I can do to fix that.