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.
Voxel terrain and marching cubes
Author
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.
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.
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.
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.
Author
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?
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?
Quote:Since there is no density data avaliable, I interpolate all vertices using 0.5 as interpolation value.
What do you mean by this?
Author
Quote:Original post by EmergentQuote: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.
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.
Author
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..
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..
PolyVox's comment
helped a little to clear things up re:
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,
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...
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 EmergentQuote: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...
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.
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.
Author
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).
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).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
