Hierarchical Marching Cubes

category: code [glöplog]
A while ago, I read papers about marching cubes, but I don't recall reading anything like the idea I got saturday.

One of the main problems with MC is that it samples empty or full space most of the time, producing no triangles. If the sampled field is a (signed) distance field, one can avoid sampling those areas by defining an implicit octree.

The idea is to recursively traverse the octree, evaluating the distance field at the center of the node at each step. If the sampled distance is longer than the radius of the bounding sphere of the node, then we know already that no triangles will be produced inside that node and there is no need to continue the traversal for that branch.

With this optimization, I went from 48ms to 18ms to tesselate a torus in a 128x128x128 grid, producing 86176 triangles.

I call this "Hierarchical Marching Cubes". But the idea is so simple, I can't believe I'm the first one having it. Did anyone already read about it or had it before ?

BB Image

Code: http://bbs.demoscene.fr/code/hierarchical-marching-cubes/?action=dlattach;attach =298
The code is a hacked D3D10 sample. The quickest way to compile it is to put the HierarchicalMarchingCubes folder inside $(DIRECTXSDK)/Samples/C++/Direct3D10.
added on the 2012-08-06 11:42:54 by MsK` MsK`
Yes! I did a similar thing a few months back - but with no hierarchy - I did raw cubes in a x,y,z loop, sample distance at cube if greater than cubes radius - march the x loop by a scaled amount of the sample distance. It's kind of marching the sampler - worked great and was only a tiny tiny modification to standard code. Can't remember the speedup I got - but it was pretty significant.
added on the 2012-08-06 12:17:22 by Shabby Shabby
Lots of people did this optimization already. I remember either plek or stefan (or both) bragging about it ~10 years ago.
added on the 2012-08-06 12:50:54 by kusma kusma
SDF+MC= cool idea! Thumb up!
added on the 2012-08-06 13:42:32 by TLM TLM
Marching cubes make ugly triangluations and is a boring stock algorithm. How about eg. "marching face-centered cubic lattice with automatic alignment" instead?
added on the 2012-08-06 13:46:52 by 216 216
is a boring stock algorithm

As is binary search, A*, raymarching, octree traversal etc. :-)
added on the 2012-08-06 14:18:55 by revival revival
Hierarchical marching has been used for quite a while. For 2D, it can be nicely seen in antifact as well. http://pouet.net/prod.php?which=20160
added on the 2012-08-06 15:44:16 by avoozl avoozl
How about marching tetrahedra or surface nets?
added on the 2012-08-06 17:51:53 by FreeFull FreeFull
FreeFull, marching tetrahedra is more or less the same, with different problems. Marching tets wastes more polygons if using a regular cubic grid, but may produce better results if you use a tetrahedral grid if you manage to make one... it might be tricky to traverse indexes.

Never read about surface nets. Looks good judging the numbers on that site.
added on the 2012-08-06 19:54:47 by xernobyl xernobyl
Coming up: "Mitsubishi" metaballs...
added on the 2012-08-06 19:59:27 by xernobyl xernobyl
the idea is pretty old, but pretty nice you came up with it yourself ;)
also i wasnt aware of it yet, so thanks a lot!
is recursive algorithm ? I wonder how to implement a correct recursive algorithm upon marching cubes...
added on the 2012-08-07 10:12:58 by Bartoshe Bartoshe
Smash / Fairlight (Matt Swoboda) talks abou something similar in http://archive.assembly.org/2012/seminars/advanced-visual-effects-with-directx-1 1
Surface nets are pretty cool indeed. I first heard of them from Statix at SIGGRAPH last year, and been wanting to implement them since then.
added on the 2012-08-07 17:51:26 by kusma kusma
PauloFalcao, are you talking about the histopyramid ? That only computes the number of triangles generated per cell and where they end up in the final buffer. It still samples the signed distance field everywhere.
added on the 2012-08-07 22:53:47 by MsK` MsK`
on the gdc presentation He mentions trees.
added on the 2012-08-09 03:55:03 by xernobyl xernobyl
hArDy^dRUNKeN ? ;)
added on the 2012-08-10 03:02:54 by neoman neoman
kusma: after some experiments i must say surface nets are working out great, and drop in pretty easy over an existing marching cubes implementation. :)
added on the 2012-08-22 02:39:48 by smash smash
this thread looks nice (awesome post, isn't it?)
added on the 2012-08-26 02:43:20 by skarab skarab
Turns out, surface nets are patented...
added on the 2012-11-13 15:20:30 by MsK` MsK`
Discussion about the usefulness of software patents in 3... 2... 1...
added on the 2012-11-13 15:42:57 by raer raer
Marching Cubes are patented too, so no problem there :)
added on the 2012-11-13 15:53:40 by sagacity sagacity
The amount of sceners who give a damn 0...0...0....
added on the 2012-11-13 16:08:07 by Preacher Preacher
The patent on marching cubes expired.
added on the 2012-11-13 16:22:25 by fizzer fizzer