mathematics - Can someone explain dual contouring?

I've been trying to understand voxel rendering and have been looking at dual contouring (DC).

So far I understand this much:

1. Run a density function for a set of grid points (i.e noise function)


2. Find which edges in the gird contain changes between end-points


3. From these edges create intersection points (i.e vectors)

Now this is where I'm stuck, next would be to generate normals, but how? When looking at this topic this image normally crops up.

                                                   

Doing research indicates that the normals would be generated from an isosurface. Is it correct to think that I go from noise to isosurface to normals? If so how would I accomplish each step?

To my understanding, the next step would be the following from the DC paper;

For each edge that exhibits a sign change, generate a quad connecting the minimizing vertices of the four cubes containing the edge.

Is this quote represented by the above image?

Finally the next step would be to run the QEF with the intersecting points and normals and this would generate my vertex data. Is this correct?

Answer

The normals would be generated based on the gradient of the density function at the same time that you get the intersection points between the edges and the surface. If it's something simple and closed-form like a sphere then you can calculate the normals analytically, but with noise you'll need to take samples.

You have the next steps in the wrong order. First, you generate a vertex for each cell that exhibits a sign change. The QEF you are minimizing is simply the total distance to each of the planes that are defined by the intersection point/normal pairs for that cell. Then you walk through the edges that exhibit sign changes and create a quad using the four adjacent vertices (which are guaranteed to have been generated in the last step).

Now, my biggest hurdle in implementing this was solving the QEF. I actually came up with a simple iterative solution that will run well on (for example) a GPU in parallel. Basically, you start the vertex in the centre of the cell. Then you average all the vectors taken from the vertex to each plane and move the vertex along that resultant, and repeat this step a fixed number of times. I found moving it ~70% along the resultant would stabilize in the least amount of iterations.