marching cubes tuto and applet

the applet gives you the opportunity to view the algorithm running on different cases:

http://www.polytech.unice.fr/~lingrand/MarchingCubes/applet.html

http://www.polytech.unice.fr/~lingrand/MarchingCubes/algo.html

another tuto with codes:

http://www.cfxweb.net/modules.php?name=News&file=article&sid=199

"human visible project" impact on 3D ...

http://www.marchingcubes.org/index.php/The_Visible_Human_Project

----------

Marching Cubes: Polygonisation

First we define a space size, this space is where the points in consideration for inclusion in our surface must reside. We could use a space of x-y-z size 320x320x320 for example.

Next we subdivide the space into a designated number of cubes in each direction, it doesn't have to be the same number in each direction, but it's advisable to keep the length of side of the cubes constant, otherwise you can get skewing of the surface.

A typical number of cubes might be 32x32x32, for our space above this gives us cubes of dimensions 10x10x10. Note that even small looking numbers of cubes like 32x32x32 are very large, 32x32x32 = 2^15 = 32,768 cubes.

The number of cubes and space size define how exact our constructed surface will be. The length of side of a cube is what counts in how accurate the constructed surface is, above 10x10x10 would probably give a pretty crappy looking surface. However, if we made our space a bit smaller, e.g. 160x160x160 it'd probably be very accurate.

Now, for marching cubes to work, we must be able to answer one question given any point and a surface: Is this point inside the surface? We'll discuss answering this question in a moment, suppose for now, we always can.

We now generate the mesh of triangles to represent our surface.

Here is how it is done: for every vertex of every cube, we check is that vertex inside or outside the surface. This results in the fundamental cube configurations:

(i)	The cube is totally inside the surface.
(ii)	The cube is totally outside the surface.
(iii)	Some of the cube's vertices are inside, and some are outside of the surface (i.e. it intersects it).

The first two cases give us no information about rendering the surface. The third, however, if some are inside and some are outside, lets us find the intersection of the surface and the sides of the cube and generate some triangles to represent the surface at that intersection. To understand this here's a diagram:

(btw, the surface is just represented by a line in this image, of course, it should be drawn in 3D)

So, if we can find the intersection of the surface and the cube sides, we're all set to generate the mesh. There are two ways to do this, we'll see the second one when we implement metaballs, the first one is binary search. Binary search works since we can always ask is the point inside or outside, and so we refine the estimate of the intersection of the surface and cube in the normal way.

So now we can generate those triangles to represent the surface as follows: Since every vertex of a cube can be either inside or outside the surface there are 256 possible triangulations, two of these are trivial, all outside, and all inside. So we have 254, as it turns out, by reflections and rotations of the cube there are only 15 different triangulations we have to special case in our code (e.g. we'd only have one special case for any one vertex of the cube outside the surface only, cutting our work down by 8 cases).

It sounds pretty boring to code the 15 special cases, the kind of boring code I try to avoid, so instead I do it a simpler way.

On Paul Bourke's home page he uses some look up tables to get the triangulation. Here is how we do it: Each vertex outside is represented by a 1 and each vertex inside is represented by a 0, in binary, and we must have a consistent labeling system for our vertices. Then we generate an 8-bit index into the edge intersection table.

An example: Suppose vertices 5, 0 and 6 were outside (we number the vertices of a cube 0, 1, ..., 7). Then we'd generate this index: 01010001. We then index an edge intersection table with that, and it gives us a 12 bit number (since a cube has twelve sides) telling us which sides of the cube are intersected, e.g. if edges 0, 1 and 2 were intersected then this number would pop out of the table: 000000000111. A '1' representing an intersected edge for each bit of the number. Now we have to actually find the intersection and we have the mesh.

Finally we use our index again this time to index a triangulation table, which tells us which vertices to join to which in the mesh. These tables are provided with the sample source, and we'll see below exactly how to do the above.

We've been doing things on a cube by cube basis, does this mean to actually generate the surface we have to go through EVERY cube in the space and check if its vertices are inside or outside the surface? Wouldn't that be very slow? We don't go through every cube in the space, because doing so would be too slow for realtime apps. Instead we use depth first search.

We simply note that every cube which intersects the surface is incident to at least one other cube which intersects the surface. So, given one intersecting cube we can just test all of the cubes touching it, and all the ones touching them, etc. So it'll be recursive. Notice that each cube has eighteen incident cubes BUT we don't need to recursively check all of them, only the ones stuck to its 6 faces, since when they recurse they will test the ones that it would have tested if we called it with all eighteen incident cubes. The termination condition for this recursive algorithm is when we reach a cube we have already encountered. Essentially what we are doing here is drawing the connected components of a graph.