Stone Devlog: Lookin' Sharp

Going for a quickie this time. While working on my Cubical Marching Square implementation, I came to the realization that the Quadratic Error Function solver I was using simply was not working correctly. As we've discussed in the past, the QEF solver is responsible for positioning a vertex within a cell in some isosurface extraction algorithms (like Dual Contouring) in order to preserve sharp features. The whole appeal of something like Dual Contouring over Marching Cubes is the sharp feature preservation, so getting it right is crucial.

I had tried several C# ports of a popular QEF solver and most were able to accurately place the corner of a cube without issue as long as the cube was rotated only on a single axis. However, when cube was rotated on a second axis, the vertex placement collapsed inward, creating a concavity rather than a point. I have no idea why, and was not overly enthused by the prospect of debugging someone else's code that is chocked full of math I do not understand. After much frustration, I decided to bite the bullet, go straight to the source, and port the code to C# myself. Lo and behold, my port actually worked:

A single cell contoured by my CMS implementation, with the sharp feature accurately approximated inside the cell.

Incidentally, I also got the rest of my Cubical Marching Squares implementation (mostly) working as well. The algorithm itself is actually fairly simple when broken up into its individual components, but the QEF solver ended up being a major stopping block. Once I had had that final piece, everything fell together. Take a look at the whole cube being contoured:

Rotated cube generated by CMS.

Obviously there are still some kinks to work out, but this is incredibly promising. The resolution of the sampling grid isn't even particularly high, yet the edges are crisp. Funnily enough, the corners are where my edge cases lie. Conversely, the edges have been the bane of my Dual Contouring implementation. Check out the same cube generated by DC at a much higher resolution:

Rotated cube generated by DC.

The new QEF solver also definitely contributes to the DC topology being more acceptable. It may be worthwhile to give my DC implementation a scrub through to see if I can improve those edges. I'm not sure how well it will compare to CMS for more complex geometry, but the only way I'll know for sure is if both algorithms are working correctly. Maybe soon we will see a "final" algorithm and can get back to the knapping system. Stay tuned for that.