Jump to content
  • Advertisement
Sign in to follow this  
MattCa

Marching Cube algorithm question(s)

This topic is 2124 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey guys,
I've currently got a world made of cubes, and I am looking into ways in which to 'smooth' the terrain.


I've read up on an algorithm called marching cubes, and have looked at a few versions (Paul Bourke's being especially useful), but I noticed that all of the algorithms online focus around creating a version of an already-defined model from triangles.

I was wondering how I would be able to achieve a similar effect, but using cubes? How would I use marching cubes to smooth the terrain generated by a perlin noise generator? Also, if this were possible, what would my 'isolevel' be? I've noticed it often used in the various versions online.

Thanks for the help,
Matt.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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, Edited by jwezorek

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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. Edited by jwezorek

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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. Edited by jwezorek

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!