pouët.net

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 ?



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.

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.

Lots of people did this optimization already. I remember either plek or stefan (or both) bragging about it ~10 years ago.

SDF+MC= cool idea! Thumb up!

Marching cubes make ugly triangluations and is a boring stock algorithm. How about eg. "marching face-centered cubic lattice with automatic alignment" instead?

As is binary search, A*, raymarching, octree traversal etc. :-)

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

https://0fps.wordpress.com/2012/07/12/smooth-voxel-terrain-part-2/
How about marching tetrahedra or surface nets?

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.

Coming up: "Mitsubishi" metaballs...

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

Smash / Fairlight (Matt Swoboda) talks abou something similar in http://archive.assembly.org/2012/seminars/advanced-visual-effects-with-directx-11

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.

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.

on the gdc presentation He mentions trees.

SUKKZ!

hArDy^dRUNKeN ? ;)

kusma: after some experiments i must say surface nets are working out great, and drop in pretty easy over an existing marching cubes implementation. :)

this thread looks nice (awesome post, isn't it?)

Turns out, surface nets are patented...
http://www.ronaldperry.org/US06933939B2.pdf
http://www.google.com/patents/US6943789

Discussion about the usefulness of software patents in 3... 2... 1...

Marching Cubes are patented too, so no problem there :)

The amount of sceners who give a damn 0...0...0....

The patent on marching cubes expired.