Dual Contours: Step One

The last few months I’ve been working on a voxel based game, and we’ve been using Marching Cubes to actually get the terrain surfaces we’ve been using so far. Marching Cubes is quite good at what it does, very straightforward and there’s a bunch of literature about it around the internet. It generates buttery smooth isosurfaces, but this comes at a cost, lots of triangles. It also has a downside that it’s really only good for smooth surfaces, it doesn’t handle sharp edges that are part of structures like buildings, they end up being very rounded. Due to this I’ve been taking looking into various other methods of isosurface extraction.

Dual contouring is a method of isosurface extraction very similar to Marching Cubes. The key difference between these two methods is that while Marching Cubes generates up to 5 vertices on the edges of the cube that is being scanned, Dual Contouring places a single vertex within the cube’s bounds. Basically it averages the edge intersections to generate a single vertex from all of the edge intersection points of the cube from the isosurface. In a few ways this is much simpler and in others much more complicated. It does have a net effect of reducing the vertex count considerably which results in fewer triangles. As a bonus it handles sharp edges deftly and can be used for generating terrain as well as structures.

So far I’ve only done a very simple implementation of this but I thought I’d share a few tips. When working with Dual Contours there are a few steps, which mimic Marching Cubes. To do this over a square grid I used two arrays and two lists, an array containing voxel data, an array containing a vertex index along with an integer for which edges were intersected (this is an array of tuples), a vertex list and an index list.

  • Generate voxel data on a square grid (*)
  • March the grid’s cubes, for each cube you march
    • Find the intersection points for all of the cube’s edges
    • If there are no intersections points skip this cube
    • Average the intersection points to get a centroid point
    • Generate a vertex for the centroid, using trilinear interpolation to determine the normal at the vertex
    • Store the vertex index along with an integer storing which edges were intersected in the tuple array
    • Place the vertex in the vertex list
  • Iterate over the tuple array to build the index list, for every cube you visit
    • If there is no tuple for this cube (no vertex or edge intersections) skip it
    • Build a quad for every edge intersection (there are 4 cubes belonging to each edge, which gives a quad)
    • Add the quad’s indices to the index list

* I used a cubed grid, however octrees are a better option here.

For finding the intersection points I simply used my Marching Cubes algorithm for determining edge intersections. After the centroid point is generated there is an extra step which I’m still working on, pushing the vertex closer to isosurface. This can be solved in a few ways, one is to use quadratic error functions (complicated), the others involve using a force vector to push the vertex towards the surface interface. I will post about these various options later when I’ve had more time to mess with them.

On the second iteration of the cubes, the triangle generation pass, there are a few things to keep in mind. One is that only three edges ever need to be examined as by iterating the cubes the front of triangle generation is advancing, meaning all previous triangles have already been generated. So it is only the edges attached to the upper right corner that we build triangles from.  The other is that you only generate triangles between cubes that share an edge. I’ve made a simple 2D diagram to show this.

A simple 2D diagram of dual contouring.

A simple 2D diagram of dual contouring.

The 3D case is a simple extension of this. Whereas in 2D an edge is only shared by 2 squares, in 3D an edge is shared by 4 cubes. The process moves from the lower left to the upper right, creating a line (or quad in 3D) between cells’ centroid points sharing a common edge with an intersection.

And with that you should be able to do a simple dual contour, but it’s not perfect. This is however just step one, hopefully I’ll have time to mess with moving the centroid vertices closer to the actual isosurface over the next few weeks.

 

Wireframe mesh generated by Dual Contouring of a Perlin noise isosurface.

Wireframe mesh generated by Dual Contouring of a Perlin noise isosurface.

2 comments to Dual Contours: Step One

  • Wolf  says:

    If you have implemented this algorithm, can you continue the description please?
    I ‘m trying to understand how it works on the Official documents, but I have very bad at math.

    • panbake  says:

      I have implemented far enough to get the mesh generated, but it remains untextured, my implementation was heavily influenced by some freely available source at github (I couldn’t find the exact one I used but just searching for Dual Contour gave a few decent results).

Leave a reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>