pouët.net

Mesh generation from signed distance function

category: code [glöplog]
 
So idea is this : you provide a signed distance function (like in raymarchers) then give it to a method that evaluate it and returns a triangular mesh.

It could be useful for 4k, 64k intros where complex scenes could be rendered using polygons , which in a lot of cases is faster than raymarching (i know this is not applicable everywhere and there is many downsides but in some cases it will give many advantages to raymarching)

It could also be also useful as a small object mesh generator (these small objects combined together could make a more complex scenes). Doing CSG using distance functions is trivial. something similar to what is done in werkkzeug using object primitives and operators.

What i have tried so far is to use marching cubes algorithm against some 3D grid (like metaballs were rendered in the 90's demos). It works but result is poor (unless you increase grid resolution which lead to many triangles). Maybe there is smarter algorithms which optimize the mesh after generation (for example it merge duplicates triangle in flat surfaces)

As anyone tried something related to this ?
added on the 2014-08-25 16:40:12 by Tigrou Tigrou
There are tons of (re-)meshing techniques for the generation of triangle meshes from implicit functions (with lots of different features e.g. preserving sharp edges).

Nevertheless, you will get some problems with 4k, because most of these methods are not simple enough regarding their implementation.
added on the 2014-08-25 16:55:57 by las las
implicit functions... I meant implicit surfaces. I really need a coffee.
added on the 2014-08-25 16:56:34 by las las
Tigrou, can you share the results (screenshots) you got with marching cubes algorithm?
added on the 2014-08-25 17:25:55 by TLM TLM
Yes, i dont have access to computer where it is now but i will try to provide stuff when possible. It is total crap anyway (i try just a bunch of combined spheres, that looks very angular)
added on the 2014-08-25 17:31:34 by Tigrou Tigrou
It will not help with the triangle count, but the nice thing you can do when you march-cubes sdf, is that you can define an implicit octree and avoid trying to mesh huge parts of the grid that are full/empty. I started a thread about that with some code a while ago...
added on the 2014-08-25 19:20:53 by MsK` MsK`
I wonder how effective it could be just to do marching cubes in some huge resolution and then perform a number of reduction passes after. Would probably be slow as shit, unless there're some clever shader pipeline tricks I'm not thinking of :)

Not entirely sure it would give you better results than some smart polygonization scheme would right off the bat, but it's an idea nonetheless and would probably be fairly simple to implement, at least if it were based on some sort of edge collapsing scheme or similar.
added on the 2014-08-25 19:53:32 by ferris ferris
To find some of the thousand papers on this topic search for example for "triangle mesh implicit function" other good buzzwords might be "surface reconstruction" "remeshing" plus "implicit" and random combinations of these. You will find a lot of stuff.
added on the 2014-08-25 20:00:02 by las las
Might want to look at dual contouring: http://www.tatwood.net/articles/7/dual_contour
added on the 2014-08-25 20:19:21 by dr_evil dr_evil
doesn't that depend on how much detail? for simple: would a screenspace triangle grid do? dunno pipelining but doesn't the function recycle. one can shove a preliminary iteration count and some approximate edge factors in the tesselator and do silhouetes in the gs into the parallel view plane direction. what more silhouettes are there then the ones that are parallel to the view plane? the rest is per pixel whatever is left.

but it's just thinking. i didn't try that.
added on the 2014-08-25 20:26:34 by yumeji yumeji
if you're fine with about 256^3, that's pretty easy on the GPU with histopyramids and marching cubes or surface nets (voxel-like, then smoothed) - smash gave a talk covering this as well, i believe he used it in numb res and uncovering static. i also used meshing extensively in staring through.
added on the 2014-08-25 20:45:31 by msqrt msqrt
Quote:
As anyone tried something related to this ?


Of course

http://www.pouet.net/prod.php?which=57449

And probably a few dozen more.

Search for Surface Nets, or Marching Cubes, both classic techniques to achieve what you want. One example, here: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html
added on the 2014-08-26 07:11:06 by iq iq
Yes, a bunch of our demos have done it - http://www.pouet.net/prod.php?which=62824 is our state of the art in this area.

i ditched the histopyramids with the move to dx11.
added on the 2014-08-26 15:15:15 by smash smash
We generated meshes from implicit surfaces (though not SDF) in Haumea. To save space, we used the D3DXFillTexture to fill a 3D texture based on a shader. Due to a quirk in D3D9, texture shaders are run on the CPU, which has the beneficial side effect that the noise functions are implemented properly, so you get noise for free. :)

The actual triangles are generated by a tiny Marching Tetrahedrons on the 3D texture and welded using D3DXWeldVertices.

We experimented with reducing the number of triangles using D3DXSimplifyMesh. The result was really nice, but it took several minutes for a reasonable mesh, which was not really acceptable in an intro precalc...
added on the 2014-08-26 16:13:54 by Blueberry Blueberry

login