Jump to content
  • Advertisement
  • entries
  • comments
  • views

A Novel Approach To (Non-Manifold) Dual Contouring



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)

You can find out more about it in this thread right here.

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.
You can read about the pro's in the thread linked above, so here is the stuff that I dislike now:

  • 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.


Recommended Comments

  • 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.


Share this comment

Link to comment

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.

Share this comment

Link to comment

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.

Share this comment

Link to comment

@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.

Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!