Marching Cube algorithm question(s)

Marching cubes is an algorithm to create a polygonal mesh that resembles the contour of a surface defined as the set of points where a particular function is 0. In your situation, you would need to figure out how to convert your cube data into a smooth surface defined by the zeroes of a function and then use marching cubes to find a polygonal approximation to that surface.

For instance, pick a smooth function F that has positive values near the origin and is zero if you go far away enough. Then define a function that is the sum of translated versions of F centered around each point in the 3D grid where your cubes live, with the sign being determined by whether the point in the grid is a cube in your terrain or not. Play around with the width and the shape of the decay of F until it looks reasonable.

Anyway, that's one possible plan. Hopefully others will suggest other possibilities.

When you say a "world made of cubes", how complicated is the world? Does it contain arbitrarily complex geometry with disconnected non-convex objects, holes, caves, overhangs, etc. Or can it be represented with a height map? Since you're talking about perlin noise I'm guessing you have a height map...


Do you want polygons as output rather than cubes? If not, isn't the perlin noise generated terrain already supposed to be smooth,

Thanks for the replies!

jwezorek - I'm using a 3D noise field for the world generation, so overhangs/caves/holes etc are present.

Also, to your second question, my current output is in the form of cubes, but what I'd like to do is produce something more similar to this or this. Basically what I'd like to do is smooth the cubes together somehow... although my understanding of marching cubes is limited, so I don't know if such a thing is possible.

Thanks again,
Matt.

Thanks for the replies!

jwezorek - I'm using a 3D noise field for the world generation, so overhangs/caves/holes etc are present.

Also, to your second question, my current output is in the form of cubes, but what I'd like to do is produce something more similar to this or this. Basically what I'd like to do is smooth the cubes together somehow... although my understanding of marching cubes is limited, so I don't know if such a thing is possible.

Thanks again,
Matt.

Okay, well those two examples you provide don't look that smooth to me, so this is a different problem than what I thought. I thought you had a discrete height map and wanted to generate polygonal terrain that was seriously smooth...

But for what you want to do, I think you do want polygons as output. For each discrete object of "cubular" geometry i.e. if your cube world is a 3D array of booleans, for each connected component in that array, you need to do a traversal of the surface cubes outputting the vertices and faces of a polygonal mesh as you go. You could have a lookup table mapping all possible configurations of local cube neighborhoods surrounding a cube corner to what to generate in terms of polygons -- clipping ears, smoothing corners, etc. -- for some small neighborhood size ... I'm not sure if that is the marching cube algorithm or not, but that's basically what you need to do.

So basically, do something very similar to marching cubes (e.g. 256? cases for the cubes), but simply detect the configurations based upon the cubes surrounding the current cube?

Also, if I were to go down the road of having smooth polygonal terrain (using the height map, for example), how would you suggest I implement the algorithm (using a 3D noise field)?

Thanks for the help,
Matt.

So basically, do something very similar to marching cubes (e.g. 256? cases for the cubes), but simply detect the configurations based upon the cubes surrounding the current cube?

Also, if I were to go down the road of having smooth polygonal terrain (using the height map, for example), how would you suggest I implement the algorithm (using a 3D noise field)?

Thanks for the help,
Matt.

Marching cubes is similar to what you want to do but not the same thing...

As I understand it, "marching cubes" is an algorithm for generating a polygonal mesh as output where the input is a boolean function, say in-the-object(x,y,z), that returns true if (x,y,z) is in some 3D object that we want to approximate with polygons.

It does this by carving space into cubes, testing the corners of the cubes with the function in-the-object(), for each cube yielding 1 of n possible cases for the cube's eight corners, and then generating polygonal data based on that case for each cube.

Your situation is different in that if you have a 3D boolean array, you essentially already have polygons. I mean you could just iterate over the array and generate vertices and faces for the sides of each cube that isn't adjacent to another cube and that would give you a polygonal mesh. However, you want to smooth this data and that is what I was trying to help with. I'm saying to basically do the straightforward algorithm (i.e. " iterate over the array and generate vertices and faces for the sides of each cube that isn't adjacent to another cube") but to do some simple smoothing as you go such as clipping corners and so forth.

There is some similarity between doing this and marching cubes but I think thinking too much about marching cubes just confuses the issue.