Sunday, April 3, 2011

Dual Contouring

Dual Contouring is a method for meshing implicit surfaces, or surfaces which are defined as the level-set of scalar function. Conceptually it is similar to Marching Cubes, except that meshing is performed on a dual mesh, and requires that the scalar function be able to provide gradients or surface normals in addition to the function value.

The primary advantage of dual contouring is that it is able to reproduce sharp features, which is something that most other implicit surface meshing algorithms are unable to do. I also consider Dual Contouring to be simpler to implement from scratch than Marching Cubes, since you don't need to form large tables of stencils.

The overall algorithm is very simple. First the region to be meshed is divided into convex non-overlapping cells (like uniform cubes or tetrahedra). The scalar function $f(x,y,z)$ that is being meshed is then evaluated at the vertices of those cells, and each vertex is labeled as being either inside or outside of the surface to be meshed.

Those cells that have a mix of inside and outside vertices must then contain a portion of the surface. It is this point where Dual Contouring begins to differ from Marching Cubes: instead of applying a stencil based on which vertices are inside or outside, Dual Contouring generates a single 'dual' vertex per cell straddling the surface. It then connects every dual vertex with it's neighboring dual vertices to form the final mesh. The only difficultly arises in choosing the location of the dual vertices to best represent the underlying surface being meshed.

To choose where to place vertices, dual contouring uses not only the intersection of the surface with the edges of the mesh, but also the surface normals at those locations. It then solves for the dual vertex location $\mathbf{d}$ which minimizes the error in satisfying planes that pass through the edge intersections with the same normals as at the intersections. This corresponds to minimizing the following error:

$E(\mathbf{d}) = \sum_{i=1}^{n}((\mathbf{d}-\mathbf{p_i})\cdot \mathbf{N_i})^2$

where $\mathbf{d}$ is the dual vertex position, $\mathbf{p_i}$ is the location of the i'th (of n) edge intersection and $\mathbf{N_i}$ is the corresponding normal for the i'th intersection. This is just a least squares system

$\left[\begin{array}{ccc}N_{1_x} & N_{1_y} & N_{1_z} \\N_{2_x} & N_{2_y} & N_{2_z} \\ & \vdots & \\N_{n_x} & N_{n_y} & N_{n_z}\end{array}\right] \mathbf{d} = \left[ \begin{array}{c}N_1 \cdot p_1 \\N_2 \cdot p_2 \\ \vdots \\N_n \cdot p_n \end{array} \right]$

which can be solved using a QR decomposition, or by forming the normal equations. One tricky aspect of this is that although there are always at least as many intersected edges as unknowns, it may not be the case that the row contributed by each edge is linearly independent from the other rows. In flat regions of the surface the normals will be nearly if not exactly the same, and the set of equations will be (nearly) singular.

One way to handle this is to add special-case code to check that the system is not singular, and if it is, solve a different system in 1D for the offset of the dual vertex in the normal direction that minimizes the fitting error. It is also possible to add a regularization term with low weight that prevents the system from being singular, but does not affect the results too badly in the event the system is well conditioned. I have done this by adding a (small) multiple of identity to the normal equations coefficient matrix, and the same small multiple of the original dual vertex position (i.e. the cell centroid) to the right hand side.

The image above shows an example of this in action. I generated an isosurface representation of the fandisk model, then ran it through dual contouring to produce the result you see above. Note that the method faithfully reproduces the sharp edges of this CAD model. I appear to have some minor bugs in the implementation however, as there are some artifacts on concave sharp edges.
The regularization approach seems to work well and eliminates the need for special case code. It also provides a knob to trade off mesh quality for approximation error: if the regularization term is small, then the method will try to reproduce the underlying surface faithfully. On the other hand, if the regularization term is large, dual vertices will be placed close to the centroid of the cells that generate them, producing a high quality mesh, but with staircasing artifacts where approximation error has been introduced.

Nigliazzo said...

Hi, i'm trying to create a fully destructible environment and i noticed that, soon or late, i'll have to demolish structures with sharp edges like walls. Now... i've already implemented dual marching cubes and it works fine, but i just can't understand the error function thing. Any help, please?

Anonymous said...

Hey James, appreciate the write up. I'm following the logic but falling down on the QEF, and you lost me completely on your regularization term approach. :)

I'm tackling getting my head around the math because that's obviously what's throwing me. Least Squares is a regression technique I recall from statistics I believe but I can't pair the two.

If you do any follow up or have any links or concepts to share it would be appreciated.

Arjuna said...

I'm going to join this comments train :) What on earth is QR Decomposition and how do I do it? I've search many sites and haven't understood how it applies to Dual contouring and how to "calculate" anything using it.

Unknown said...

Thank you for putting an effort to published this article. You've done a great job! Good bless!

Yong
www.gofastek.com

Unknown said...

We are all like flowers that blooms or withered in the garden depending on how we take good care of our self. So do not let negativity pass through. Enjoy and be confident. Have a good day and visit my site for more information.

n8fan.net

www.n8fan.net

Unknown said...

There are definitely a lot of particulars like that to take into consideration. That may be a great point to convey up. I provide the ideas above as normal inspiration but clearly there are questions like the one you convey up where an important factor might be working in honest good faith. I don?t know if finest practices have emerged around issues like that, but I am positive that your job is clearly identified as a fair game. Both boys and girls feel the influence of just a second’s pleasure, for the remainder of their lives. gsn casino games

Charles Knott said...
dale said...