views:

785

answers:

1

i currently writing a program to implement Marching Cube using C++ and Opengl.

However, my best reference is only from http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/

in the web, the provided codes are written in C.
my problem here is that i don't understand the triTable and edgeTable
and how they are related.

can anyone help me on the explanation or guide me on converting the algorithm into codes?

+6  A: 

These Tables are used for finding out how to tesselate the surface:

The first table gives you the necessary edges to interpolate. The second table gives you the way you have to tesselate, meaning, which triangles you have to make inside the cube.

A little example:

let's assume, vertex one and 2 are below the iso level, the cubeindex should be 3.

The whole intersection should look like a wedge.

If you think about it, you have to interpolate values on the edges: 0 and 9 , and 2 and 10. If you enter this into a bitfield, each bit corresponding to "is edge intersected?" you would end up with something like this:

10 9 8 7 6 5 4 3 2 1  edge
 1 1 0 0 0 0 1 0 1 0  intersected?

wouldn't you?

Which is exactly the value from edgeTable[3] in binary ;) 0x30A = 1100001010

Now you can write a function that linearly interpolates the points on those edges to fit your isolevel. These points will become your surface inside this cell.

But how to tesselate this cell/surface?

if you look into triTable[3] a smile should creep over your face :)

Addit after statement of residual puzzlement in comment: ;-)

What Marching Cubes does: Imagine you have a dark room with one point light source in it. It is the center of a volumetric light intensity field of scalar intensity values. You can go to point (x,y,z) and measure the intensity there, e.g. 3 candela.

You now want to render a surface through all points that have a certain light intensity. You can Imagine that this Isosurface would look like a sphere around the point light source. That is what we hope that Marching cubes will provide us with.

Now running through all points in the room and marking every point as a vertex that has roughly the iso value, will be algorithmically very complex and would result in a hughe number of vertices. Which we would then have to tesselate somehow.

So: First Marching cubes disects the whole volume into cubes of equal size. If the underlying data has some kind of underlying discreteness, multiples of that are used. I will not go into the other case, since that is rare. For instance we put a grid with the density of 1mm into a 2mx5mx5m room

We use cubes of 5mmx5mmx5mm. Running through them should be much cheaper.

You can imagine now, that the edges of some of the cubes intersect the isosurface. These are the interesting ones. This code identifies them:

cubeindex = 0;
   if (grid.val[0] 
if cubeindex stays zero, this particular cube is not intersected by the isosurface. If cubeindex is > 0 you now know that the isosurface goes through this cube and you want to render the piece of the isosurface that is inside it. Please picture this in your mind. See http://en.wikipedia.org/wiki/Marching_cubes for examples of intersected cubes. The vertices that you could get easily are those on the edges of the cube. Just interpolate linearly between 2 corner points to find the position of the isovalue and put a vertex there. But which edges are intersected??? That is the information in edgeTable[cubeindex]. That is the big piece of code with all the ifs, that stores the interpolated points as vertices in an array of xyz points: vertlist[]. This piece reads as follows:
get the bitfield = edgeTable[cubeindex]
 if edge 1 is marked in bitfield (bit 1 set to 1 in bitfield)
    vertlist[0] = interpolated point, somewhere on edge 1
... and so on.

You now have an array full of vertices, but how to connect them to triangles? That's an info that tritable provides.

The rest is pretty much what I explained above.

Well should there still be problems, please be specific about the piece of code that gives you trouble.

AndreasT
If that smile doesn't want to happen, think about how you would put the triangles in there, and then compare that to the proposal in triTable.Have fun! ;-)
AndreasT
hey thanks, AndreasTactually i'm a bit lost. for your information i have no knowledge about the algorithm.i kind of understand how triTable works now, however i still don't understand how edgeTable works and how to determine which surface to use..
noob88
ok, now the thing got really big :)
AndreasT
somehow the code formatting does not work here. The code snippet gets truncated :( . But if you compare with your source website, it should be manageable.
AndreasT
thanks a lot! working on it now!
noob88
btw, what value does the grid.val[0] and isolevel in "grid.val[0]<isolevel" holds? and is 'grid' an operator?
noob88
Good answer! Good explanation too
Nathan Fellman