HIDIHO!

giving something back to the Flash community

Marching cubes algorithm: 3d isosurface and metaballs

Tags: , , , , , , , ,

cover
here we go for a new exciting and damn useless piece of code

I’ve always been fascinated by metaballs.
long ago in 3DS MAX they had a highly unstable 3d metaballs plugin that could keep me stuck for hours watching.
never quite understood the math behind it but the result was hypnotic.

now rejoyce here’s a highly unstable 3d metaballs and isodurface actionscript set of classes !!!

so what is a marching cube ? thanks to Wikipedia you’ll be less stupid tonight. usually they use it in medical imagery to modelize the ‘IRM’ scans (?! you know the ‘slices’ of brain, actually they don’t slice up the brain).
you can also check this one out: http://users.polytech.unice.fr/~lingrand/MarchingCubes/accueil.html

finally I found an implementation and some explainations by Paul Bourke (of course) :
http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/
this is the one I ported.

so it is an isosurface generation algorithm. the ‘skin’ will bound the values of a 3D array of values under a given threshold (isoLevel).
isotropic surface is the contrary of anisotropic which might ring a bell to 3D artists for you can have both types of reflections in nowadays 3d sofwares textures.
for example a glass marble is isotropic while the clouds are anisotropic: in the clouds you can’t tell where the light will go out even if you know where it comes from. it’s also fascinating even if it’s not the point.

so you start with a Dataset ; a 3D Array containing scalar values ( = Numbers ) think of it as those famous greyscale 2D maps where lumisnosity represents the height. in the dataset, the height is the third dimension of the array.

the isotropic surface involves an isoLevel which will create the ‘skin’.
the algorithm slices up the Dataset in GridCells (an 8 values cube) then performs the polygonisation for each gridcell.
it uses the isolevel to choose whether an edge of the cube will belong to a triangle…

well I’m not very strong for explainations so here are two pictures with different datasets and a varying isolevel
here’s a 30,30,30 sphere with an isolevel smaller and smaller:
sphere

here’s a blob (20,60,20) with an isolevel bigger and bigger:
blob

the ‘holes’ appear when the isolevel crosses the sides of the bounding cube.

not knowing what more to say here you go with a demo:

so:

  • the isolevel slider changes the isolevel
  • you should use animate only with the NOISE generator ; it is a 4,4,4 dataset(small)
  • liverender will render the 3D object while dragging (can be lethal for CPU)
  • under the generator label you can try different datasets
  • the color swatches change the colors of the mesh

as I wanted to keep the 3D out of the business so that one can implement it with any 3D engine, the package has its own Vector3D class which is just a dataholder with x, y, z coordinates. when rendering, a Triangle array is returned by the MarchingCube.compute() function containing all the triangles to build. check the build() function of the PaperObject class. a modelScale is passed to the renderer (PaperObject class) to resize the model otherwise it would be very small.

the best is to have a look at the Main class. it contains a single marching cube instance.
the Dataset.as class is a bit fat, I put some generators in it but they should be fed from outside.

there are still some bugs, holes appear in some configurations and sometimes all the triangle link to the last GridCell.
I tried to work it around but couldn’t find a clue: it’s god’s mighty hand ;)
an alternate way of making 3d isosurfaces is to use the marching tetrahedra.
I guess it should be the next step
enjoy

/! update: I was talking about the fact that it ‘s not bound to a specific 3D engine.
here’s a Sandy3D version of the PaperObject class


instanciation works the same as in Main.as with small changes due to the Sandy API:

var mc:MarchingCubes = new MarchingCubes( data );
var so:SandyObject = new SandyObject( mc, modelScale, false );
addChild( so );
so.group.rotateX = 45;
so.group.rotateY = -35;
so.group.rotateZ = 0;
so.boundingBox = true;
so.liveRender = true;
so.build();

you can grab the class here:

cheers :)

Tags: , , , , , , , ,

© 2009 HIDIHO!. All Rights Reserved.

This blog is powered by Wordpress and Magatheme by Bryan Helmig.