Jump to content
  • Advertisement
Sign in to follow this  
Relfos

Voxel terrain and marching cubes

This topic is 3411 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

I'm implementing a voxel terrain editor. I use a 3d array of boolean values that store if a point (x,y,z) is empty or not. Now, to convert this array to a 3d mesh I have implemented marching cubes. But when I add a sphere, marching cubes output a mesh that is blocky and ugly. The possible cause of the problem, when creating a new "cube", I'm supposed to interpolate the new vertices from the voxel density data, but for all marching cubes examples that I found in google, they either used density values loaded from disk, or used metaballs which the density can be calculated using the metaball radius and distance. Since there is no density data avaliable, I interpolate all vertices using 0.5 as interpolation value. I could go with metaballs, and indeed, my first demo used those, but I want to be able to build both organic curved surfaces, and flat surfaces, and metaballs only produce the former.

Share this post


Link to post
Share on other sites
Advertisement
Well this is a fairly standard problem, which I'm having in my engine as well. Personally I'm looking into mesh smoothing algorithms which can be applied after the surface has been extracted.

Otherwise, is there any reason why you can't make a density field? That way you should be able to have both smooth curve sand flat surfaces.

You might also find the link in my signature interesting.

Share this post


Link to post
Share on other sites
Ah, Polyvox, I had already found your work before, actually it was one of the inspirations I had for starting my project. I looked at your lib source code, but I had some trouble to understand the surface triangulation part.

Can you explain me what actually is the meaning of a density value in our case (I presume you're also using binary voxels) and how to calculate it?

Share this post


Link to post
Share on other sites
Quote:
Since there is no density data avaliable, I interpolate all vertices using 0.5 as interpolation value.


What do you mean by this?

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
Quote:
Since there is no density data avaliable, I interpolate all vertices using 0.5 as interpolation value.


What do you mean by this?


In marching cubes, after calculating the edges using the lookup tables, to get the vertices positions, we need to interpolate between the voxels density, at least every implementation seems to do this.

And since I dont have density values per voxel, I use 0.5 when interpolating the positions. But this gives the "blocky" result.

Share this post


Link to post
Share on other sites
Quote:
Original post by Relfos
Ah, Polyvox, I had already found your work before, actually it was one of the inspirations I had for starting my project. I looked at your lib source code, but I had some trouble to understand the surface triangulation part.


Yes, it's a little complex. Plus I'm reworking that part at the moment anyway. It was originally based on Paul Bourke's page (http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/) but even the marching cubes tables are different now.

Quote:
Original post by RelfosCan you explain me what actually is the meaning of a density value in our case (I presume you're also using binary voxels) and how to calculate it?


I do have a binary volume, and I'm doing the same as you. All vertices are placed halfway along the cube edge. Actually I do have the same problem as you, that the mesh is blocky:



I get around it by smoothing the normals. As I mentioned above, I'm also looking at ways to smooth the mesh after it has been generated.

One other trick you can use is to average the voxels on-the-fly. Each time you try to retrieve a voxel you can instead return the average of that voxel and its neighbours. This is then a floating point value which you could use as the density. It might be slow though, with all that averaging...

Quote:
Original post by Relfos
What do you mean by this?

Marching cubes is normally applied to a density volume, where the density might vary between (for example) 0-1000. Depending on the value of the isosurface you are trying to find you use interpolation to place the generated vertex the desired distance along the edge of the cube. But in the case of a binary volume you are always interpolating between 0 and 1, so you just place it halfway.

Share this post


Link to post
Share on other sites
Ah, you also have the same problem. I already tried messing the normals, and yes, it somehow looks better, but the project I'm working is a terrain editor that should be able to export a mesh. I'm going to add some mesh simplification via edge collapsing, but with the current hard edges it just doesnt work.

I'm now doing research for alternate methods to marching cubes, the ideal algoritm should receive a array of points, basically a vertex cloud, and triangulate it. However, I can only find algoritms that work with convex surfaces, and here we can have holes, so it doesnt work..

Share this post


Link to post
Share on other sites
PolyVox's comment

Quote:
Original post by PolyVoxAll vertices are placed halfway along the cube edge.


helped a little to clear things up re:

Quote:
Original post by Emergent
Quote:
Since there is no density data avaliable, I interpolate all vertices using 0.5 as interpolation value.

What do you mean by this?


so now I almost get what's going on.

But the thing is... Really, marching cubes works with a continuous density function; it computes an isosurface of that function. How you go from your binary voxel grid to a continuous function is the key thing we're not talking about here adequately (besides saying "interpolation"). That's what this discussion really needs to be about.

I feel like the way marching cubes is being thought of in this thread is too tied to the underlying representation of the density function. All your grid of booleans really is, is a bunch of samples of some underlying continuous density function. The "cubes" in marching cubes do not need to line up with these samples or anything. Part of the problem is the use of this word "voxel." I know it's traditional in computer graphics, but the problem is that it conjures images of cubes. All your grid really is, is samples.

So what's the continuous function that you're doing marching cubes on? The function that trilinearly-interpolates between sample values? Some other function? That's what you need to get clear on.

When PolyVox says,
Quote:
One other trick you can use is to average the voxels on-the-fly.

he is suggesting a particular continuous function. It's not super-clear what exactly that function is, but one that meets this description would be,

f(x,y,z) = average value of all the samples contained in a sphere of radius R centered at (x,y,z)

for instance.

Now that we've got this out of the way, surely we can be more sophisticated about the way we select this function? B-splines spring to mind, for instance...

Share this post


Link to post
Share on other sites
The key point in my case (and I assume also Relfos) is that I need the marching cubes algorithm to run as fast as possible, because it is being run on a data set which is being modified in real time. It's already slower than I would like, and implementing higher order reconstruction filters is likely to be very expensive.

The averaging I describe is not a mathematically correct approach - instead it is analogous to applying a low-pass filter over the data set, essentially blurring it. It does work, but isn't that fast. You also wouldn't want to do this on medical data for example, but it's ok if you just want a terrain that 'looks nice'.

Using higher order filters should allow for nice smooth surfaces (and it's a mathematically 'valid' approach), but I don't know how high you would have to go. I did have a nice paper on value and gradient reconstruction filters but I can't find it now. Anyway, I do worry it would be prohibitively slow...

I'm currently hoping that smoothing as a post process will be a good solution. Early results are promising but it's too early to say for sure.

Share this post


Link to post
Share on other sites
Well, I actually read more about those functions to represent the density.
I removed binary voxels for now, and used the ones that use a floating point to represent density.

This is the result, altough I need to improve the normals generation.
Also, I did some optimizations to the marching cube algoritm, now it runs in real time, as a octree is used to determine the parts that need updates (still need to fix this, tough).

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!