Jump to content
  • Advertisement
LifeIsGood

A novel approach to (non-manifold) Dual Contouring

Recommended Posts

Posted (edited)

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)

Looking at the problem in 2D significantly simplifies the problem, so let's do that first.
dcnorms.png.1feb72ddfac6a5b2a0863f84d28c1e97.pngdc.png.572cd8b30732a140ad084379680b4078.png
Here's the information we have:
  • 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
So, how do we find the best vertex for that cell ?
The normal is obviously orthogonal to our surface, so, what does our surface at that point look like ? Of course, it's simply an edge orthogonal to the normal!
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)

newDC.png.5b72dfa878f17e4257d1391f21784165.png
 
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.
newDC2.png.d6bb9648e274d68e7c11a15d9f4cde94.png
 
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.
newDC3.png.f819f8e8ae358b022a8c3b22a796b792.png
 
And that's it! That's what our actual surface looks like.

So, here's all we need to do summarized:
  • 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)

In 3D, there is an infinite amount of orthogonal vectors to our normal, so how do we pick the one representing the edge of our surface ?
In 2D, we can represent the course of a surface in a specific point with the tangent line.
In 3D, the same principal exists. This time, it is a tangent plane.
tangent-planes-1.png.8e0414e7d1c2a2ab0c1a7e01a5f5fa41.png
So, instead of 2 vectors as in 2D (the 2 orthogonal vectors to our normal) we have 4 this time. The vector u & v describing the tangent plane, as well as their inverses.
We can apply the same principal as in 2D to find the one vector we are looking for, to represent our surface edge at this point.
Now, all we got to do is to again find the intersection of 2 lines (or more specifically, line segments).

Results in 2D

Circle, from left to right: The complete surface, hermite data (sign changes & normals), resulting vertices (points of intersection)
result01.png.56ec771954b0d3d27ee2606a9c885d9f.pngresult01HM.png.65fbeefc347fbd3da50547e7ac6c324a.pngresult01Vertices.png.1e8eace858ec39f0fb3cf6cf80a6db60.png
 
Square, from left to right: The complete surface, hermite data (sign changes & normals), resulting vertices (points of intersection)
result02.png.842a8308e4499138318e7dee357a858c.pngresult02HM.thumb.png.8176e0dc6a7fc282829bec18bec2e4d3.pngresult02Vertices.png.4365a01b0e634c16a8972aae6927d5f3.png
 

Results in 3D

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

Edited by LifeIsGood

Share this post


Link to post
Share on other sites
Advertisement
Posted (edited)

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

 

Edited by LifeIsGood

Share this post


Link to post
Share on other sites

Do you have code handy for the 3D case? I'm having trouble visualising what you are doing differently to the original dual contouring implementation.

Share this post


Link to post
Share on other sites
Posted (edited)

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 :D

Edited by LifeIsGood

Share this post


Link to post
Share on other sites

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

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

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).

Share this post


Link to post
Share on other sites
Posted (edited)
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.

Edited by Gnollrunner

Share this post


Link to post
Share on other sites
Posted (edited)
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.

Edited by LifeIsGood

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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.

Dual.jpg

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!