Stone Devlog: Let's Get Cubical

I'm going to bury the lede on this one and start off by saying that I'm working on implementing Cubical Marching Squares (again) and actually making some good headway. However, for this post, I want to stroke my ego a bit and riff on an improvement to the algorithm that I've been toying around with. Considering I still don't have a firm grasp on all the intricacies of the algorithm yet, this can only go well.

It's been a while since we've talked about contouring algorithms, and I don't believe I've ever went into depth on what the deal is with Cubical Marching Squares. It's much like the other surface extraction algorithms we've discussed in that it operates on cubical cells by sampling the volume density at each corner of the cell. The short of it is that Cubical Marching Squares essentially derives the Marching Cubes case for the cell by evaluating each of the 6 faces of the cell as Marching Squares. That's what makes it Cubical Marching Squares. After each face has been evaluated, a sharp feature vertex is potentially placed inside the cell in a similar way to Dual Contouring. If a sharp feature is detected, sharp features are also placed on each of the faces that the surface intersects, and then the vertex inside the cell is connected to each line segment on the faces to form a triangle fan. The ideas behind the algorithm are pretty neat, but it's the sharp feature placement on the cell faces that I believe can be improved.

As we learned previously, algorithms like Dual Contouring use the surface normals at the points where the surface intersects cell edges in order to approximate the placement of sharp features within the cell. Cubical Marching Squares uses a very similar idea as Dual Contouring to place a vertex (or two) within the cell, but it also uses these normals to place vertices on the cell faces when evaluating them à la Marching Squares. On the plus side, the sharp feature placement in 2D is a lot more straightforward than in 3D.

Let's say we have a square, with its corner lying somewhere inside a given cell we're evaluating:

Cell (white) intersected by a square (gray).
The edge intersections and joining segment are marked in blue on the right.

The Marching Squares case for this configuration is a straight line connecting the two points where the surface intersects the cell, lopping off the corner of the square. That is less than ideal, so if we want to preserve the corner, we need to put in a bit more effort. First, we take the normal of the surface at the intersection points. The normals can be found by a derivative of the density function, cached in their own grid, or simply approximated by sampling several close points and calculating the rate of change. Once we have the normals, we take the perpendicular vectors of each normal, and find where those perpendicular vectors intersect. The intersection of the perpendicular vectors is our sharp feature. Since we're dealing with 2D space, and (hopefully) only two vectors, unless the vectors are parallel, they will intersect at a single point.

If we look at this in practice on the square, it looks like the perfect solution:

Perpendicular vectors are projected from the surface intersection points to find where they meet

However, let's take a look at the same scenario with a circle instead of a square:

The Marching Squares case is exactly the same. That is to be expected considering that, like with the square, the surface intersects the cell at two points. Marching Squares does not discriminate. However, if we try to detect a sharp feature, the surface is round, so we shouldn't be able to, right? 

That can't be right. It ends up finding the same sharp feature as the square. Unfortunately, though, this is correct. The normal of the square is orthogonal to the edge, whereas the normal to a circle is a straight line out from the center point. Since this circle is centered on the cell corner, the normals end up being colinear with the edge, the same as the square, which results in the same sharp feature being found. Granted this situation largely comes down to the sample resolution. Increasing the sample resolution immediately alleviates the issue.

After subdividing the cell, there is enough normal data to properly approximate the shape.

Even still, it rubs me the wrong way that we end up settling for either a Marching Squares case that falls short or a "sharp" feature that overshoots the surface. Why can't we have a happy middle ground? Maybe we can! This is where my completely unqualified 'improvement' comes in. Normally in Cubical Marching Squares, we decide whether or not there should be a sharp feature and if there should be one, we use it. However, this also means that in cases where there are no sharp features, after we rewrap the faces of the cube, we just put all this extra effort in to produce the same geometry as Marching Cubes.

My proposal is simple. Instead of sometimes using a sharp feature, I say we use it most of the time. Then, rather than using it as a vertex, we sample the density at the position of the sharp feature. If the point lies too far outside the surface, we can take a sample at the midpoint of the segment formed by the Marching Squares case and then interpolate between those two points to accurately place a vertex on the surface.

The circle case with my proposed interpolation.

I only recently came up with this solution, so only time will tell if it works out. Naturally, this will be slower, as it requires more computation per face, compounded by the number of cells. And it remains to be seen whether this idea will hold water against some more complicated scenarios, such as the dreaded ambiguous cases of Marching Squares. Still, I was proud to have figured out some form of a solution to this problem I encountered, even if it may not end up being optimal. Next time maybe we'll get to discuss how I was a big dumb-dumb for thinking this was a good idea. Stay tuned for that.

On a completely unrelated note, did you know it was "bury the lede" and not "bury the lead" because I sure as heck didn't.