Mesh Simplification Algorithm: Improved

After a bit of tweaking, I managed to obtain much better results from the mesh simplification algorithm. I made two essential changes. First, I make the algorithm keep track of how far a vertex has moved from it's original position (displacement). Vertices that have already been collapsed to locations far from their original position will be less likely to be collapsed. This makes the edge collapsing look much more uniform, and simultaneously fixes the problem I mentioned earlier with normal distortion. Normals now look great!

The second major changed I made was doing multiple passes over the vertex list, slowly raising the maximum collapse cost until it matches the value given to the simplification function. This ensures that low-cost collapses will be performed before high-cost collapses.

I couldn't be happier with these results!! Finally, after two weeks, I'm done with the mesh simplification algorithm.

Mesh Simplification Algorithm

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.

Ellipsoid Modeling - Starship

Using an isosurface extraction algorithm, it is possible to model in far more intuitive ways than with extrusions, welds, and the other tedious tasks of typical 3D modeling software. One such method is via the use of ellipsoids that influence the density function from which an isosurface is extracted. Modeling using ellipsoids is fast, intuitive, and requires only a fraction of the space that a regular mesh would take to store.

The following simple starship mesh was created in about ten minutes using only 14 ellipsoids.

Note that ALL of the assets used in this demo, including my core engine, the precompiled drawing shaders, as well as the ship meta-mesh and extraction algorithm, fit into a single 33kb executable (after UPX compression). And no D3DX dependency, either! I'm quite proud of how space-efficient my project is turning out to be.

All hail the marching cubes!

Marching Cubes Algorithm Implemented

After a great deal of problems and long nights of debugging, I finally have the marching cubes polygonization algorithm up and working in my engine! I was hesitant to implement the algorithm in the first place, since it requires a lot of constant global memory (several KB for the lookup tables), and I'm trying to keep my executable size as low as possible. In the end, however, it was worth the few extra kilobytes. The results are incredible! Isosurface extraction may be the answer to all of A New Reality's problems!

Using isosurface extraction, it will be loads easier to create procedural models. My fear, however, is performance. The algorithm is sluggish at best, even on powerful CPUs. No wonder, considering it has to sample tens, possibly hundreds, of thousands of grid points in the density function. For high-quality procedural modeling to be feasible using isosurface extraction, I'm going to have to hope that CPU power increases a lot in the near future. Until then, I will continue attempting to optimize the algorithm as well as explore multithreaded options to prevent lockups during mesh creation.

I hope to post some results of the algorithm soon!