Stone Devlog: Dual Contending

Well, this is embarrassing. Shortly after my last post lauding the clean edges I was getting with Cubical Marching Squares, I realized all my Dual Contouring implementation needed was a fix that I had already applied to my CMS implementation. One copy and paste job later, and suddenly my Dual Contouring implementation was up to scratch:

Clean edges even at a low sample resolution

As I've complained about previously, there was a distinct lack of CMS implementations floating around the Internet for me to borrow. When I finally tried to implement it myself, I was careful and took a bottom up approach. I started with sampling a single point from a signed distance function, and detecting if the surface crossed between two points. Then I moved to finding the crossing point between the two points. With that, I could handle an edge, so handling a face was just a matter of handling four edges. Similarly, handling the entire cube was just handling six faces. While time consuming, this was a great exercise to really dig in an understand each step of the algorithm and how it all fit together.

I spent a lot of time dealing with only a single cell and seeing how it handled anything I could throw at it. One issue that cropped up was a nasty, but all too common scenario. When finding the crossing point on an edge, we sample the SDF at each endpoint of the edge. If the surface crosses the edge, the values sampled by the function will be positive at one end and negative at the other. We can use these values to approximate the crossing point by interpolating between the two end points. However, since the value sampled from the function is the shortest distance to the surface, there's no guarantee that the value represents the distance to the surface along the edge. Take a look at this handy visual aid:

This is exactly the sort of scenario I was running into. The surface crosses two edges on the square, with one point inside the volume and two outside. The red and blue lines represent the positive and negative distances we'd need to properly interpolate the crossing point. However, only the top left corner will yield that distance when we sample it. For the other two points, there is a shorter distance, shown in magenta, to the surface than the distance along the edge we're evaluating. The lower left corner even gets us a distance in the complete opposite direction as the left edge. Any interpolation using these values will dramatically misplace the crossing point.

Funnily enough, inspiration for the solution to this problem came from a different Dual Contouring implementation. The fact I didn't put two and two together sooner only adds to my shame. Anyways, in that implementation, to approximate the surface crossing point on an edge, they take X evenly spaced samples along the edge and go with the point with the closest value to zero. That works, but personally I am not a fan of that sort of "close enough" approach. Instead, I opted for an approach reminiscent of a binary search. First, I interpolate the crossing point as I was already doing. However, rather than using the calculated crossing point, I sample the function at that point. If the value is outside of a set threshold, I determine whether the surface crosses between the calculated point and first or second point of the edge. I treat this like a new edge and recursively do it all again. For the most part, the first interpolation is sufficient, but when this scenario is encountered, it can typically find an acceptable crossing point in two to four iterations.

By this point, I'm well over a year out from when I initially implemented Dual Contouring. I knew at a high level that DC positioned a vertex in the cell using a QEF solver, but it completely slipped my mind that it calculates the edge crossing points to use as inputs. A quick look through the code revealed that my DC implementation was relying on the naïve crossing point calculation. All I had to do was plop in the interpolation function from my Cubical Marching Squares implementation and the janky edges were no more.

Turns out trying to implement Cubical Marching Squares really was a blessing for this project. Between identifying common error scenarios and just getting a decent QEF solver working, my Dual Contouring implementation is now pretty solid. Conversely, my CMS implementation still suffers from the issues we looked at my last post, which have proven to be non-trivial to address. However, my DC code could certainly use a touch up. As I recall, it was more or less just a port of the code from a tutorial, with some nonsense I added to accommodate my specific requirements. Now that I've established that there are merits to doing it myself beyond feeding my ego, I think my next step will be revisiting DC with the same bottom up approach I took for implementing CMS. At the very least, I'd like my DC implementation to support an adaptive resolution grid using an octree. I had intended that for my CMS implementation, but with some of the complexities of the algorithm, that is a daunting prospect. Perhaps taking a stab at using an octree with a 'simpler' algorithm could bear some fruit for both implementations. I guess we'll see. Stay tuned.