• entries
2
5
• views
363

# A Novel Approach To (Non-Manifold) Dual Contouring

829 views

For the sake of "completness", my first entry is about the very first algorithm I came up when I was thinking about new solutions to procedural meshing / extracting a polygon mesh from implicit geometry (e.g. from a signed distance function, SDF)

At first, I liked the idea. However, the more I worked on the algorithm, the more I found characteristics that I dislike about this approach.

• The algorithm is a typical "voxel" algorithm. It relies on a 3D grid.
• It may suffer from floating-point imprecision
• It lost it's simpleness. The idea behind the algorithm was to find a simple alternative to DC. This is still very true for the 2D version of the algorithm, but for the 3D version, not so much...
I had to account for more & more "special cases" during the development of the algorithm, resulting in an algorithm that wasn't simple enough anymore for my taste.

Quote
• The algorithm is a typical "voxel" algorithm. It relies on a 3D grid.

I think this limitation is only acceptable if you aim for realtime generation.

Otherwise i would take a remeshing approach. That's much harder to do, but can produce good results. This is a good example: https://github.com/wjakob/instant-meshes

Really most research here is about irregular mesh to optimized regular mesh, not volume to mesh, but this could be done as well of course.

I want to deform meshs in realtime, so while a precomputation of a general mesh is fine, it should be the same possible in realtime.

But yeah, not really working on this algorithm anymore, anyways.

I've been kind of batting an idea around in my head of adding a sharp comers to marching cubes. This would have the advantage of generating manifold geometry.  I was thinking that you could just add an extra data parameter to each voxel, which the meshing algorithm would use in combination with the 256 case field code, to build commonly used cases like building corners and and stuff like that.  You would implement each case as needed and kind of build up a library of voxel types. In this way you wouldn't have to use a QEF and hopefully it would be reasonably fast.  The down side is I think it would be hard to do the level transitions needed in terrain, but for smaller objects where all the voxels can change size at the same time for LOD, it might be OK.

It's all about time. How much time can you spend generating the mesh? By definition dual contouring is cellular, if you don't want to work with cells, make different sized faces. It's only time that limits your technique. An example: http://www.vrmmorpgordie.com/?page=Client/Terrain/OctTree.html

@Gnollrunner If it suits your needs, go for it. My goal, however, is to develop an algorithm that allows me to completly freely generate a mesh that approximates the underlying surface closely. That is, I don't want to solve specific cases, but find a general solution.

@TeaTreeTim Interesting, but as mentioned above the constraint is that it should run in realtime. (I.e. "game" realtime aka it should take no longer than maybe 2ms.

I actually am playing around with a new idea in my head, that I'm going to try out once I have some time over.

## Create an account

Register a new account