Interesting matrix->mesh problem, can you find the solution?

[triwebb1]

What I have is a matrix, say 100x100x100, with values ranging between 0 and 1.  What I want to do is create meshes that outlines groups of similar values in 3d space.  So I want the values from 0-.2 to be one group, .2-.4 to be another, and .4-6 another, and so one up to 1.  The different groups will be different colors, and the material that the meshes are made of will have a low alpha so that you can see through them.

The problem I have is that I can't figure out how to programatically analyze the matrix and create the corresponding meshes from it.

Here is a simple 2d analogue to what I am trying to do:

2d matrix 16x8:

1111111111111111
1111111011111111
1111110001111111
1111100000111111
1111000000011111
1110000000001111
1100000000000111
1111111111111111

So the solution to this would be to draw a triangle with vertices at (8,2), (3,7), and (13,7).  This is what I want to do, but I need it in 3d.


This is harder to see, but here are three slices of a 3d matrix 16x8x3 (x,y,z):

        z=0                z=1                z=2
 
   1111111111111111  1111111111111111  1111111111111111 
   1111111011111111  1111111111111111  1111111111111111 
   1111110001111111  1111111011111111  1111111111111111 
   1111100000111111  1111110001111111  1111111011111111 
^  1111000000011111  1111100000111111  1111110001111111 
|  1110000000001111  1111000000011111  1111111111111111
|  1100000000000111  1111111111111111  1111111111111111
|  1111111111111111  1111111111111111  1111111111111111
y   x--->

The solution to this would be a pyramid with verticies at (2,1,0), (13,2,0), (8,7,0), and (8,4.5,3).


I hope I have been clear enough in describing what I need.  Does anybody have any ideas on how to do this (without using gobs of memory)?

[Stiggie]

Are the meshes you're trying to create always convex? Or always triangular?
If so i believe (atleast for triangles) you could look at each point and if it has more than 4 neighbours with the value of "1" then its a vertex of the mesh.

-Stig

[Zaknafein]

That's pretty much a 3D texture / voxel array, and the classic way of triangulating voxels is using Marching Cubes.
Don't expect to have very low-poly results, but there's surely a way to optimize the resulting mesh after the triangulation.

I remember that Sylvain made a voxel/marching cubes demo a couple of years ago in C++ using TV 6.5... I wonder if it's still up somewhere?

[triwebb1]

The marching cubes approach is almost exactly what I want, but the problem is that I think it creates a whole bunch of little cubes, building a solid representation of the matrix.  What I need is just a skin of the solid that would be created by this method, and then I would set the alpha to about 0.1 on that skin so that you can see through it.  There would then be other smaller skins inside the first one, and skins inside that skin, etc...  If this generated a bunch of cubes, it would be impossible to see the inner cubes through the outer ones because it there would be to many cubes in the way.  For example, if I wanted to look at a cube at (0,0,0) and the camera was at (100,100,100) and the solid generated was a sphere with radius 50, I would have to look through 49 cubes to see the one at (0,0,0).

I think I may be able to use a modification of this concept to create a skin though.  Thanks for pointing me in this direction - I was pretty much stuck on this, but now I have a way to approach it.

[Zaknafein]

...but the problem is that I think it creates a whole bunch of little cubes, building a solid representation of the matrix.  What I need is just a skin of the solid that would be created by this method...

I think you're mistaken. The marching cubes method creates an isosurface, so a "skin" like you say, that represents the 2D exterior surface of the model. It only creates polygons in areas that share empty space and filled space.

Also, even if it's called "cubes", it doesn't just create cubes like, say, my trixel engine.
It actually tries to mimic the curves of the model by using 15 possible cube configurations, that map to different polygon generation cases.
The screenshot on wikipedia uses flat shading, which makes it look pretty rough, but with vertex normals or phong shading it can generate very smooth/organic models.

[triwebb1]

Ok, I guess that helps me understand how it works.  I was confused by the different "cube configurations".  I will see if I can use the examples I have found to implement this in my program.  It is a little confusing right now, but I'm sure I can sort it out.  This is exactly what I wanted, thanks again.