Dual Contouring Help
category: code [glöplog]
I'm trying to implement dual contouring. Currently, I just average the edge intersections of the current cube and use that as the vertex for the quad.
I'm looking for some trick to compute the vertex within the cube directly from the isovalues at the cube corners. I'm not getting that enlightened from the gazillion dual contouring papers out there.
Someone experimented with this and has a good approximation?
I'm looking for some trick to compute the vertex within the cube directly from the isovalues at the cube corners. I'm not getting that enlightened from the gazillion dual contouring papers out there.
Someone experimented with this and has a good approximation?
Just from cube _corners_? what? That's not how it works. The nice thing about DC is that it is able to preserve sharp corners and that will only work if you compute the actual intersections with the cube edges and the SDF gradient at those intersections, which are both not hard to get. The idea is that for each edge intersection, the gradient defines a plane that describes the local surface at that point and you want your discretized surface to continue with that gradient as much as possible (and also to have the same intersection with the edge).
If you want to do it right, you have to solve (find the minimum of) what the papers call the quadratic error function. In some cases it does have an actual solution (three edge intersections including normals -> three planes to intersect -> one point, done), but in the general case it doesn't and you'll have to minimize the error. I tried getting around writing a real solver by fudging around, but that didn't work too well. One thing the papers never assume is that you might have the actual SDF around during QEF solving, which might make more things possible, but I haven't found a good way to actually use it. One paper I found really helpful was Dual Contouring: The Secret Sauce. What I didn't find at the time is this full implementation by Nick Gildea and a clean version of a QEF solver by paniq.
After that works, making it use the adaptive approach instead of a simple grid will be fun. I quit before that.
If you want to do it right, you have to solve (find the minimum of) what the papers call the quadratic error function. In some cases it does have an actual solution (three edge intersections including normals -> three planes to intersect -> one point, done), but in the general case it doesn't and you'll have to minimize the error. I tried getting around writing a real solver by fudging around, but that didn't work too well. One thing the papers never assume is that you might have the actual SDF around during QEF solving, which might make more things possible, but I haven't found a good way to actually use it. One paper I found really helpful was Dual Contouring: The Secret Sauce. What I didn't find at the time is this full implementation by Nick Gildea and a clean version of a QEF solver by paniq.
After that works, making it use the adaptive approach instead of a simple grid will be fun. I quit before that.
Yeah... the reason for trying some dual scheme is in my case not to preserve sharp edges, but to get a better mesh (those darn tiny vertices) than with marching cubes. So some "fake" approximation would be enough for me. Approximating by averaging the edge intersections gives a reasonable good looking mesh, the process just feels wrong. So I thought, someone has a nice idea, some trilinear whatever trick...
Shame on me, I have not used the correct wording. I interchanged "Dual Contouring" with "Dual Scheme" and what I have actually implemented is more in line with Surface Nets. It works well, but as I said, the placement is simple, looks good, but feels wrong.
To be honest, the mesh doesn't automatically get better. It will just fail in different cases than MC and in a different way. At first sight DC looks like it will always produce reasonable meshes, but even with proper QEF solving (and probably even more with simple averaging of intersection points), there will always be cases where it is not manifold (e.g "hourglass"-like points where it touches itself). My initial idea was to start with simplified DC (averaging without QEF solving) to get the topology roughly right and then using tessellation to move subdivided vertices to their actual positions on the SDF. It worked okay in some cases and while the mesh was not that nice it looked fine since the the SDF normal is used for shading:
but it broke horribly in others:
the problem with those cone-spikes is that no matter the DC grid resolution, you can always just zoom in to the tip of the cone and it will look like this :/ I'm about 70% sure that this is an inherent problem with DC and not due to a bug in my prototype implementation.
but it broke horribly in others:
the problem with those cone-spikes is that no matter the DC grid resolution, you can always just zoom in to the tip of the cone and it will look like this :/ I'm about 70% sure that this is an inherent problem with DC and not due to a bug in my prototype implementation.
(reading post with interest / liking the the pretty pictures / thumbs up for sharing info / wish i could help / +1 encouragement :) )
Uhhh, very nice. Yeah, for the case where you really want to have sharp features, this may hold. But for tesselating the common "demoscenish" objects you have a smooth densitiy field. And as I said, I want to use it as a marching cubes replacement with better meshing and it works out quite well. I only wish there would be some faky interpolation using the the cube corners and it's isovalues to skip the marching cubes alike edge interpolation...
And yes, I suck at math.
And yes, I suck at math.
Has anybody tired out other algorithms like Cubical Marching Squares or Marching Triangles?
I use MC here for polygonizing a scalar field. Ca somebody recommend an algo that builds better meshes, is relatively easy-to-implement, robust, and ideally fast too (and brings world peace while we're at it)?
I use MC here for polygonizing a scalar field. Ca somebody recommend an algo that builds better meshes, is relatively easy-to-implement, robust, and ideally fast too (and brings world peace while we're at it)?
... and is also adaptive (produces smaller triangles only where they are needed) without going through "hierarchical data structures on the GPU"-hell? I wasn't aware of those two methods, but both look complicated with lots of special cases.
Maybe there is something possible that the usual literature has not explored: The papers all assume that you just have the grid values (possibly augmented by the gradients at certain points). You just try to make the best of that bunch of discrete values, probably because building meshes from some medical scanning data is the most common use case. But I've never seen one that explores the possibility of evaluating the volume as needed at all steps of the algorithm. Lifting that restriction might make more things possible, but I couldn't think of anything straightforward. My "there's a paper to be written" sense is still tingling though...
Maybe there is something possible that the usual literature has not explored: The papers all assume that you just have the grid values (possibly augmented by the gradients at certain points). You just try to make the best of that bunch of discrete values, probably because building meshes from some medical scanning data is the most common use case. But I've never seen one that explores the possibility of evaluating the volume as needed at all steps of the algorithm. Lifting that restriction might make more things possible, but I couldn't think of anything straightforward. My "there's a paper to be written" sense is still tingling though...
@rear
The simple and naive method I use is actually very easy to implement. You start like marching cubes. Compute the scalar values at the cube corners and place a vertex at the edge intersections. Now things start to be different. Compute the avereage position from this vertices. For every edge that crossed the scalar field, build a quad from the computed average positions of the cubes around that edge. Done.
Hope this makes sense :-D
The simple and naive method I use is actually very easy to implement. You start like marching cubes. Compute the scalar values at the cube corners and place a vertex at the edge intersections. Now things start to be different. Compute the avereage position from this vertices. For every edge that crossed the scalar field, build a quad from the computed average positions of the cubes around that edge. Done.
Hope this makes sense :-D
Yeah. MT looks like it produces better meshes, but is slower, meshes are not manifold and the triangle count is still pretty high. CMS looks a bit better, because meshes are supposedly manifold...
If you want to give CMS a shot, there are implementations here and here.
There's also Isosurfaces Over Simplicial Partitions of Multiresolution Grids, which seems to be a improved DC algo generating adaptive meshes.
If you want to give CMS a shot, there are implementations here and here.
There's also Isosurfaces Over Simplicial Partitions of Multiresolution Grids, which seems to be a improved DC algo generating adaptive meshes.
Quote:
Compute the avereage position from this vertices. For every edge that crossed the scalar field, build a quad from the computed average positions of the cubes around that edge. Done.
So average the vertices -> new (single) position. Then build quads to the neighbouring cubes averaged positions?
Sound like you get cracks with that, or I don't quite get it... :)
Here is a blog page that lists different surface extraction methods btw.
You dont get cracks. Damn, I'm not good at explaing things. Okay, for every cube, which has an one or more edges crossing the isosurface you build a weighted vertex - for my naive implementation I just average the edge intersections. If you have marching cubes already working - just average the vertices you would emit for that cube. So we now have a weighted vertex for each "cube that intersects the isosurface".
Implementation hint, for testing, place the vertex in the center of the cube. You then get a minecraft world. You can cache the intersections flags, and vertex locations to make the next step very simple.
Now, iterate over the cubes again (or use your cache). For every edge that intersects the isosurface, build a quad using the weighted vertices from the cubes that share this edge (that is, one edge is always shared by four cubes, so we get a quad). Now the fun part, you just have to build the quad for three edges... the rest is done by the other cubes, I usually use +X, +Y, +Z directed edges - just very small lookup tables needed here.
The nice thing is, you get a tight mesh, with shared vertices. Ready for subdivision, perlin noise wobbel terror, whatever. When you split the quad into triangles, just split the longest diagonal to make the surface look better.
Implementation hint, for testing, place the vertex in the center of the cube. You then get a minecraft world. You can cache the intersections flags, and vertex locations to make the next step very simple.
Now, iterate over the cubes again (or use your cache). For every edge that intersects the isosurface, build a quad using the weighted vertices from the cubes that share this edge (that is, one edge is always shared by four cubes, so we get a quad). Now the fun part, you just have to build the quad for three edges... the rest is done by the other cubes, I usually use +X, +Y, +Z directed edges - just very small lookup tables needed here.
The nice thing is, you get a tight mesh, with shared vertices. Ready for subdivision, perlin noise wobbel terror, whatever. When you split the quad into triangles, just split the longest diagonal to make the surface look better.
Right - that's surface nets you're talking about not dual contouring. And you want to ditch the smoothing step (I apply this multiple times iteratively not once..) and use the isosurface instead.
What about if you just calculate the SDF normal at the initial vertex location in the cube centre, then use that and the distance to isosurface to move towards the surface? I haven't tried it but I guess that's how I'd do it.
What about if you just calculate the SDF normal at the initial vertex location in the cube centre, then use that and the distance to isosurface to move towards the surface? I haven't tried it but I guess that's how I'd do it.
I haven´t read all of those techniques up yet, but i thought Dual Contouring was what smash just suggested?! :/
Man, now i´m confused, guess i got to dive into these techniques asap, so i know what to decide for once i need it!
Oh wait, not quite...my understanding of dual contouring so far is having one point per voxel, this having a normal and that´s about it. the normal gives you inside/outside already, while the position of the vertex defines the shape (averaged with the surrounding voxels vertex-positions), something about that, right?! I should read it up asap as said! I am still missing techniques i couldn´t implement between 1997 and 2007 thanks to not having a computer at all (got my first PC in 2005 and had no idea how to code until i jumped back into it in 2007.) That´s why i haven´t delved into newer techniques at all yet. :(
Man, now i´m confused, guess i got to dive into these techniques asap, so i know what to decide for once i need it!
Oh wait, not quite...my understanding of dual contouring so far is having one point per voxel, this having a normal and that´s about it. the normal gives you inside/outside already, while the position of the vertex defines the shape (averaged with the surrounding voxels vertex-positions), something about that, right?! I should read it up asap as said! I am still missing techniques i couldn´t implement between 1997 and 2007 thanks to not having a computer at all (got my first PC in 2005 and had no idea how to code until i jumped back into it in 2007.) That´s why i haven´t delved into newer techniques at all yet. :(
Smash correct, and welcome to the discussion :-D
What dual contouring and surface nets have in common is that they use the same tesselation scheme. That is, spit out quads, the only difference is how they compute the vertex location. I will give your idea a try. And as a side note, I'm using classic density fields... SDFs are somehow absolutely not my cup of tea. But, let's assume on small scales the universe is flat, hehehe. That is, take a sample one cube away in the normal direction and try the midpoint.
Another simple idea... place a vertex at the center and think about the cube corner values as forces, apply some iterative relexation scheme. Will see if my math skills are good enough - but probably not. At least, this should converge after very few iterations (or explode).
And now, time to shave off some Child-Free-Time[TM] - but first: Beer!!!
What dual contouring and surface nets have in common is that they use the same tesselation scheme. That is, spit out quads, the only difference is how they compute the vertex location. I will give your idea a try. And as a side note, I'm using classic density fields... SDFs are somehow absolutely not my cup of tea. But, let's assume on small scales the universe is flat, hehehe. That is, take a sample one cube away in the normal direction and try the midpoint.
Another simple idea... place a vertex at the center and think about the cube corner values as forces, apply some iterative relexation scheme. Will see if my math skills are good enough - but probably not. At least, this should converge after very few iterations (or explode).
And now, time to shave off some Child-Free-Time[TM] - but first: Beer!!!
Thanks EvilOne. Got it now :) Will try that out when I have time. It sounds like it generates more triangles than MC though...
How about temporal coherence? I've got a pretty nice-ish dual contourer, but if I make the SDF animated it can produce pretty horrible results (say, with a rotating cube the new corner vertices appear way outside the previous approximation..) I'm slightly cheating with the QEF (just doing tikhonov regularization instead of an actual pseudoinverse), there might not be a problem if the numerics were perfect.. I'm more interested in smooth movement than exact corners though.
