I've been looking around for a better implementation of surface extraction as I really need the ability to extract a surface from a volume but keep the hard/soft edges where necessary. I don't want an all smooth or all hard terrain and as I understand it the marching cubes surface extractor with Polyvox currently does not do this.
So, I recently found THISimplementation with source and it looks really nice. I've been playing around in the source a bit and might give it a go with PolyVox. However I thought I'd first come in here and pass it around in case anyone more skilled than I wanted to tackle it - It would probably take me the better part of a month to work it all out and integrate it.

This is correct. The marching cubes surface extractor does not allow you to have a smooth surface in some places and sharp corners in others.



Unfortunatly I don't know much about how Dual Contouring works. Does it operate on just a density field (like Marching Cubes) or is extra per-voxel data required to control the sharpness? It's interesting, but I have no plans to work on it myself.

Also, I found this page which might be useful to you: http://swiftcoder.wordpress.com/planets/isosurface-extraction/ There are several papers about Dual Marching Cubes.

After looking at the code it does look like it uses a density field. I'm not sure how it all works yet however.

Sorry about raising this topic.

I also think that DC is a nice approach that could possibly complement Polyvox. It is crack free out of box and preserves sharp features.

I asked to Tao Ju about possible perf hits and he said that DC should be on par with MC.
He also added that using an octree should even help to extract the isosurface substantially faster.

There are some slight gotchas though. For example, Ju's intersection free DC implementation does not take into account the face orientation when turned to triangles.
No real issue if rendered 2-sided but annoying if not.

The principle is brilliantly simple. You basically create a quad out of the minimizer(minimizing QEF) points provided by the four Hermite data voxels sharing the same edge.

Ju's DC code takes in a Hermite volume (with signs at the grid points and point/normal data along grid edges whose ends have different signs).

The density field used for MC has to be turned into such Hermite format.

Another catch is in deciding the splitting direction for the quad that can sometimes lead to small imperfections on the sharp features.

This fellow try to address the issue by using "edge preservation heuristic rules"(not other drawbacks free though). He is also providing a neater approach for solving the self-intersecting faces problem based on convex/concave analysis, whereas Ju uses edge-polygon intersection tests phase.

Looking forward to seeing something like sharp features in PolyVox !

Yeah, I'm still interested in this though I'm not planning to implement it myself in the foreseeable future. I need to get up to speed on the trade offs between the different algorithms, because as well as Dual Contouring there is also Dual Marching Cubes which appears to include automatic level of detail. There's been an interesing Google Summer of Code project on the Ogre forums which has been integrating these approaches into Ogre: http://www.ogre3d.org/forums/viewtopic.php?f=13&t=69449

I think the performance of DC would be ok but it looks like the data storage is more difficult? In particular it seems that normal vectors are stored per-edge rather than per-voxel, and PolyVox does not provide a way to represent this kind of data at present. PolyVox only stores a grid of voxel values so some additional data structure would be needed here.

It's good to know there is an open source implementation though, and I'd be interested if anyone can get it working with PolyVox.

Dual MC looks indeed very nice too.

For DC, minimizing the quadratic error function is also a step that has a substantial cost when extracting the surface, beside the problem of having to carry data on edges.

I am not sure but I think that the minimizer position inside the voxel could be possibly baked offline since we need the edge normal data only for computing this point position.

This way, we could perhaps have a voxel carrying signs at corners and a single value corresponding to a minimizer's position offset inside the voxel's own space.
We would then just have the quads generation for edges exhibiting sign changes and split to tri's left.

I may try to keep an eye on it while still playing with MC's for now.

It sounds like this will limit the ability to modify the volume in real time though, which is undesirable for many applications. We'll just have to see how fast it can be.

The MC side of PolyVox has been a bit neglected becuase we didn't need it for Voxeliens, but I've been making use of it again over the last week or so. I'm coming back to the problem of blending between multiple materials as we don't really have a good solution to this. Hopefully I come up with something over the next few weeks.

I inspected dual MC a bit more in depth and you are right, at first glance, the mesh seems to be extracted with a quite less quantity of polys which is pretty attractive.

Solving QEF for a reasonable number of impacted voxels and surrounding ones at destruction time should not be that expensive, but we could even get the new position in a probably more hackish manner for the destruction case.

I am quite new to Polyvox, do you have a repro snapshot or link to your issue/scenario with materials ? Is it for example related to adding some localized dirt on destruction or something ?
I am not yet familiar with your material policy at this time.

Some great discussion here!

Regarding Dual MC - Correct me if I am wrong but the key advantage Dual Contouring has over Dual MC is that you can output both smooth and sharp edges, whereas no other solution can provide.

Hi there,


MC, Dual MC and DC are surface approximation and reconstruction techniques. The goal is to get a shape as close as possible to the sampled density's one.

MC's smooth edges are generally unwanted approximation artifacts.

Both Dual MC and DC preserve sharp edges which solve this MC's major issue(I guess they worked out those approaches specifically for that problem).

The normals used on DC's edges serve mainly as volume information for surface approximation rather than for shading the extracted model.
Although this data must definitely be also used to feed the vertex normal's and other streams of the corresponding area, for further shading/lighting purposes.

Best,
K