Hi!

First of all, this is still very basic. I just managed to get my first results running, but I figured I would share my thought process & what I have done so far.
I'm not that well versed when it comes to Math, so I'm definitely looking forward to hear your guys opinions.
This thread is quite long, so feel free to just jump to the heading that interests you.

Recently, @Boris The Brave has released a really nice tutorial on Marching Cubes & Dual Contouring. A few years ago, I was already messing around with those algorithms but was lagging the required knowledge about programming back then. When Boris' tutorial came up, it again arouse my interest in this type of field.
Also, let me appologize for my poor paint skills in advance

Classic Dual Contouring

The heart of the dual contouring algorithm is to solve the problem of finding the best fitting vertex for a surface inside of a cell. In the original paper, this problem has been solved with a quite complex solution (at least to us non-mathematicians): Solving & minimizing the Quadratic Error Funtion (QEF)
Most projects simply reuse the original paper's implementation to solve the QEF and/or (slightly) adjust it to their needs. Usually, this works perfectly fine & yields pretty good results.
However, I was curious if I could find a way to simplify the problem.

My approach (2D)

• We know the exact position of a sign change on one or more edges.
• We know the normal of the surface at that exact position

That means, there are only 2 possibilities in 2D! (which are essentially kind of the same as they are only the inverse of one another)

One of the easiest ways to decide which of those 2 directional vectors we need is to simply move our point a bit in each of the directions. The point that's closer to the next sign change is the direction we are looking for.

Now, all we need to do to find the best fitting vertex, is to find the intersection of those 2 directional vectors! (That is, we want to make lines out of those 2 vectors.)
Since we know, that we have 2 or more sign changes in this cell, we know that there is either going to be an intersection of those 2 lines inside of the cell, or none at all.

• For each sign change, calculate the 2 orthogonals to the normal
• For each other sign change, do the same
• Look for an intersection between those 2 resulting lines (Essentially, we are looping over all sign changes twice.)

In the end, we simply take the median of all found intersection points (required if there are more then just 2 sign changes)

My approach (3D)

Results in 2D

Results in 3D

Left: My approach, right: The result from Boris The Brave's implementation.
https://youtu.be/LtZCa359exU

I have fixed a few errors in my implementation.
You can see the new results here:

Sure. It's a bit messy right now though. Here's my Solve function (I have not included the intersection function etc. since this is just basic geometry):

 

    private Vector3 Solve(Vector3[] signChanges, Vector3[] normals)
    {
        var intersections = new List<Vector3>();
        float avrX = 0, avrY = 0, avrZ = 0;

        for (int i = 0; i < normals.Length; i++)
        {
            var n = -normals[i];
            Vector3 u, v;
            GetTangentPlane(n, out u, out v);

            for (int j = 0; j < normals.Length; j++)
            {
                // Do not try to find an intersection point with yourself.
                if (j == i)
                    continue;

                var n2 = -normals[j];

                Vector3 u2, v2;
                GetTangentPlane(n2, out u2, out v2);
              	// When you calculate the tangent plane, you have effectively 4 directional vectors representing your surface
                // (u, v & their inverses)
		// Since we want to "expand" in a specific direction, this method simply figures out which of those 4 vectors to choose.
                var surfDir1 = GetSurfaceDirection(signChanges[i], signChanges[j], u, v);
                var surfDir2 = GetSurfaceDirection(signChanges[j], signChanges[i], u2, v2);

              	// Calculate the intersection point of those 2 line segments 
                // (basically the surface edges from the involved sign changed positions)
                var intersec = GetIntersectionPoint(signChanges[i], surfDir1, signChanges[j], surfDir2);

              	// No intersection.
                if (float.IsNaN(intersec.x) || intersections.Contains(intersec))
                {
                    continue;
                }

                intersections.Add(intersec);
                avrX += intersec.x;
                avrY += intersec.y;
                avrZ += intersec.z;
            }
        }

        if (intersections.Count < 1)
        {
          // This should not happen, since we already know we have at least 2 sign changes here.
	  // So, if we end up in here, something is wrong...
        }
		
      	// Average the position, if there's multiple intersection points.
        // This point now is the vertex we were looking for.
        var vertex = new Vector3(avrX / intersections.Count, avrY / intersections.Count, avrZ / intersections.Count);
        return vertex;
    }

Also, maybe the video I've posted in the comment before helps you to visualize.

Edit:
Idk why I called it solve.... it doesn't solve an equation like the original implementation. Just sticked with it for some reason

4 hours ago, swiftcoder said:

What happens if you run this on a mesh with sharp edges that are not grid-aligned (for example, a cube rotated by 45 degrees)? That's the scenario where dual contouring really shines at producing sharp corners,

Actually this is something I keep wondering about.  Every time I look at examples they always show the required point being inside the voxel. However  it seems to me that the required point could easily be far outside the voxel which would destroy your sharp corner anyway if you forced it to be inside.  I've been shying away from dual contouring for this reason.  To me seems like it CAN give you sharp corners but can also easily fail depending on the angle of the corners and the alignment with the grid. Is there something I'm missing here?  Perhaps I should take another look at it.

Quote

Ok, it looks to me like you are averaging the intersection points of each pair of tangents. Is that correct?

Pretty much, yeah. Since we're handling the 3D case there's no tangent, but rather a tangent plane. However, we're only interested in one of the 2 vectors (one of those will resample exactly the surface edge we are interested in), that make up the tangent plane.

Quote

Are the U & V vectors returned by GetTangentPlane() always aligned with the grid in 2 dimensions?

No. The tangent plane can have any orientation, as you can see here:
https://www.khanacademy.org/math/multivariable-calculus/applications-of-multivariable-derivatives/tangent-planes-and-local-linearization/a/tangent-planes

Quote

What happens if you run this on a mesh with sharp edges that are not grid-aligned (for example, a cube rotated by 45 degrees)? That's the scenario where dual contouring really shines at producing sharp corners, and I have a feeling that this is going to smooth them out (more along the lines of Surface Nets).

I think it should work. I'll reply back with some results once I've tested that.

There is indeed a problem with sharp features when averaging the intersection points, as you can see in this video.
However, it is not as prevalent as it is with Marching Cubes.

Notice the intersection points (in light blue / cyan) and the generated vertex (in dark blue)
The averaging smoothes out the corners. I'm currently looking for a better solution then simply averaging the intersection points.
Ideally, the generated vertex would lie right above the lower intersection point, creating a normal corner.

https://youtu.be/PXKI1PWlmt0

Quote

However  it seems to me that the required point could easily be far outside the voxel which would destroy your sharp corner anyway if you forced it to be inside

This is a misconception about how the algorithm actually works.
2 or more sign changes per grid cell mean, the function changes here from non solid to solid (or vice versa), so no matter what kind of surface we have in this space, the vertex we're looking for is guaranteed to lie inside this cell.

So, when the QEF returns a point outside the cell, it's actually just an "error" of the applied solution.

45 minutes ago, LifeIsGood said:

This is a misconception about how the algorithm actually works.
2 or more sign changes per grid cell mean, the function changes here from non solid to solid (or vice versa), so no matter what kind of surface we have in this space, the vertex we're looking for is guaranteed to lie inside this cell.

OK here's an example. We have a couple edges coming into a voxel (two sign changes). The arrows are the normals from the Hermite data. Where would we put the intersection to retain a sharp corner? I don't see how it's possible but perhaps I'm missing something.

Ah, I see what you mean. There's no need to create a vertex here, since there's going to be no intersection inside of this cell (keep in mind that we are working with line segments) the vertex will be generated in the cell above this one.

If the corner is outside of the grid's bounds, well, then you simply don't have enough space to generate the whole mesh.

I am not too sure how standard DC would handle this, but here's my guess:
- You would simply snap the vertex into the cells bounds and you would still get a sharp feature, since we're going to create another vertex in the cell above.