Jump to content

  • Log In with Google      Sign In   
  • Create Account


Marching cubes, Octree, and LOD seams


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
21 replies to this topic

#1 colinhect   Members   -  Reputation: 193

Like
0Likes
Like

Posted 01 January 2011 - 01:30 PM

I have implemented marching cubes for a large volumetric surface. The surface is contained in an octree which splits as you get closer to each cell, making a large (4096^3) area to explore. The problem is the seams between cells of different LOD. Here is a screenshot of the issue (there are also normal issues between cells of the same LOD, but I can fix that):



I have searched quite a bit for a solution to this issue but I haven't found anything. Has anyone successfully implemented seamless LOD with marching cubes before?

Sponsor:

#2 XeonXT   Members   -  Reputation: 208

Like
0Likes
Like

Posted 01 January 2011 - 05:21 PM

I've read a substantial amount of literature on MC, and don't believe I have ever encountered someone doing chunked LOD terrain with it.

Quick question: are you running MC on the CPU or GPU?

You might have a look at this article, which mentions "adaptive refinement," though this method is far more complex than vanilla MC: Cubical Marching Squares

You might try just running a full-quality MC and then using an adaptive mesh simplification algorithm to generate the LOD mesh for each patch. Definitely more expensive, but you'll get better-looking LOD that way and (if you tell the algorithm not to touch any vertices on the boundary of the patch) have no cracks.

And a quick note about normals - I'm assuming, based on the fact that your normals aren't all correct, that you're computing them after the mesh has been generated by summing and averaging the face normals for each vertex. If you want really good-looking normals for an implicit surface, consider calculating the normals by sampling the density field at each vertex with a slight dx, dy, and dz in both directions (i.e. compute the partial derivatives in each direction). It looks very nice (but, as I said, is costly, and probably only viable on the GPU, depending on how much loading time is acceptable).

#3 colinhect   Members   -  Reputation: 193

Like
0Likes
Like

Posted 01 January 2011 - 05:48 PM

Thanks for the reply. The chunks are generated on the CPU. There is no way I could do a full-quality MC on my density field (it a perlin-noise based function over 4096^3).

I will read that article to see if I can apply it to my implementation.

For the normals, I actually just implemented the method of normal generation you mentioned. I read about it in the GPU Gems 3 article and it makes the normals look much better. It is running pretty good on the GPU (the terrain chunk generation is threaded, but there are minor hiccups).

Thanks for the info... I really hope I could find a decent solution for this.

#4 PolyVox   Members   -  Reputation: 708

Like
0Likes
Like

Posted 02 January 2011 - 02:33 AM

Have a look at this:

http://www.terathon.com/lengyel/Lengyel-VoxelTerrain.pdf

I haven't looked in detail, but I believe he is introducing new MC cases which straddle the different LOD levels.

#5 swiftcoder   Senior Moderators   -  Reputation: 9761

Like
0Likes
Like

Posted 02 January 2011 - 03:07 AM

Welcome to my (least) favourite topic!
Quote:
Original post by PolyVox
http://www.terathon.com/lengyel/Lengyel-VoxelTerrain.pdf

I haven't looked in detail, but I believe he is introducing new MC cases which straddle the different LOD levels.
I can't download the 50 MB PDF over my ghetto internet connection, but if I recall correctly, C4 does all of its voxel tessellation offline, which gives you a lot more choices in how you resolve inter-tile edge dependencies. Eric is somewhere around the forums though - perhaps he will weigh in at some point.

Regardless, there are a number of advancements on marching cubes that ought to solve the problem (dual-manifold contouring, adaptive skeleton climbing, etc.). I haven't thus far had the time to implement any of them to check if they really do provide a solution...

Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#6 colinhect   Members   -  Reputation: 193

Like
0Likes
Like

Posted 02 January 2011 - 06:09 AM

Thanks for the replies. I now have a lot of articles to read and consider.

#7 Eric Lengyel   Crossbones+   -  Reputation: 2215

Like
1Likes
Like

Posted 02 January 2011 - 02:00 PM

Quote:
Original post by c_olin
Has anyone successfully implemented seamless LOD with marching cubes before?
Quote:
Original post by XeonXT
I've read a substantial amount of literature on MC, and don't believe I have ever encountered someone doing chunked LOD terrain with it.


The C4 Engine has been rendering voxel-based terrain with Marching Cubes and chunked LOD for about a year now.

Quote:
Original post by swiftcoder
Welcome to my (least) favourite topic!
Quote:
Original post by PolyVox
http://www.terathon.com/lengyel/Lengyel-VoxelTerrain.pdf

I haven't looked in detail, but I believe he is introducing new MC cases which straddle the different LOD levels.
I can't download the 50 MB PDF over my ghetto internet connection, but if I recall correctly, C4 does all of its voxel tessellation offline, which gives you a lot more choices in how you resolve inter-tile edge dependencies. Eric is somewhere around the forums though - perhaps he will weigh in at some point.


Here's a version with low-resolution images -- it's 4.87 MB:

http://www.terathon.com/lengyel/Lengyel-VoxelTerrain-Low.pdf

The C4 terrain is designed for real-time interactive modification, so the triangles generated along the transition between LODs depend only on very localized data.

To implement all of this requires some look-up tables of nontrivial size. I plan to release mine in the near future.

#8 Lloydg   Members   -  Reputation: 114

Like
0Likes
Like

Posted 02 January 2011 - 02:44 PM

I read in here that they just use "crack patching" to fill those gaps.

So I guess that means they put a or some pollys in the cracks to fill them. Simple as that?

#9 Eric Lengyel   Crossbones+   -  Reputation: 2215

Like
0Likes
Like

Posted 02 January 2011 - 03:22 PM

Quote:
Original post by Lloydg
I read in here that they just use "crack patching" to fill those gaps.

So I guess that means they put a or some pollys in the cracks to fill them. Simple as that?


This paper does not define what "crack patching" means, but it's probably referring to a number of techniques that have been proposed that are either (a) not truly robust or (b) require analysis of an arbitrarily large swath of the voxel data. Not being robust means that not all cracks are filled in correctly, so you still have cracks. Analyzing arbitrarily large swaths of the voxel data is bad for two reasons: it has an unpredictable running time, and changes to the terrain in one place can affect how it looks far away from that place.

The method used in C4 is 100% robust, meaning that it will correctly fill cracks for any possible crazy voxel data you might encounter. And like Marching Cubes, the triangulations it outputs depend only on the immediately surrounding voxel data, so it has a constant per-cell running time, and local changes only have local effects. This is good for real-time terrain modification, like blowing craters in the ground.

#10 swiftcoder   Senior Moderators   -  Reputation: 9761

Like
0Likes
Like

Posted 04 January 2011 - 11:23 AM

Quote:
Original post by Eric Lengyel
Here's a version with low-resolution images -- it's 4.87 MB: http://www.terathon.com/lengyel/Lengyel-VoxelTerrain-Low.pdf
Thanks for that.
Quote:
To implement all of this requires some look-up tables of nontrivial size. I plan to release mine in the near future.
Let me know when you do so - I have no immediate desire to try and generate them from scratch [smile]

#11 zzzz....   Members   -  Reputation: 88

Like
0Likes
Like

Posted 05 January 2011 - 05:21 AM

Why not use the mathematical description (force field) of the landscape directly and raytrace or ray-march it? Your graphical detail would go up a 1000-fold and you could even make it dynamic. Polygons are so oldschool... ;-)


Edited by jbadams, 13 April 2014 - 01:56 AM.
Restored post contents from history.


#12 swiftcoder   Senior Moderators   -  Reputation: 9761

Like
0Likes
Like

Posted 05 January 2011 - 06:13 AM

Quote:
Original post by spinningcube
Why not use the mathematical description (force field) of the landscape directly and raytrace or ray-march it? Your graphical detail would go up a 1000-fold and you could even make it dynamic.

Polygons are so oldschool... ;-)
Have you ever tried this yourself?

My (admittedly naive) implementation is lucky to break 5 fps for un-shaded terrain, on an high-end gaming machine, because of the cost of evaluating the noise functions many times per ray.

#13 zzzz....   Members   -  Reputation: 88

Like
0Likes
Like

Posted 05 January 2011 - 09:39 AM

Quote:Original post by swiftcoder
Quote:Original post by spinningcube Why not use the mathematical description (force field) of the landscape directly and raytrace or ray-march it? Your graphical detail would go up a 1000-fold and you could even make it dynamic. Polygons are so oldschool... ;-)
Have you ever tried this yourself? My (admittedly naive) implementation is lucky to break 5 fps for un-shaded terrain, on an high-end gaming machine, because of the cost of evaluating the noise functions many times per ray.

Yup I have. You need good data structures, clever optimizations, parallelization and many simplifications. I do have a good computer i7 Intel and some pretty fast memory. It could run faster on a GPU but I never bothered. And if looking at that polygonal model of his I say he could get away with only rendering the landscape in a 320*200 window or similar and scale all the buffers (colors, z etc...) to match the rest of the scene.


Edited by jbadams, 13 April 2014 - 01:57 AM.
Restored post contents from history.


#14 colinhect   Members   -  Reputation: 193

Like
0Likes
Like

Posted 05 January 2011 - 12:51 PM

Quote:
Original post by spinningcube
Quote:
Original post by swiftcoder
Quote:
Original post by spinningcube
Why not use the mathematical description (force field) of the landscape directly and raytrace or ray-march it? Your graphical detail would go up a 1000-fold and you could even make it dynamic.

Polygons are so oldschool... ;-)
Have you ever tried this yourself?

My (admittedly naive) implementation is lucky to break 5 fps for un-shaded terrain, on an high-end gaming machine, because of the cost of evaluating the noise functions many times per ray.


Yup I have. You need good data structures, clever optimizations, parallelization and many simplifications. I do have a good computer i7 Intel and some pretty fast memory. It could run faster on a GPU but I never bothered.

And if looking at that polygonal model of his I say he could get away with only rendering the landscape in a 320*200 window or similar and scale all the buffers (colors, z etc...) to match the rest of the scene.


I would love to have a clean solution like ray-tracing but I don't think it is possible for what I'm attempting to achieve. And also the screenshot I showed above has the detail set low in order to make the cracks more obvious... Here is a screenshot with higher detail (still haven't gotten around to fixing the cracks):



#15 zzzz....   Members   -  Reputation: 88

Like
0Likes
Like

Posted 05 January 2011 - 01:23 PM

Quote:Original post by c_olin I would love to have a clean solution like ray-tracing but I don't think it is possible for what I'm attempting to achieve. And also the screenshot I showed above has the detail set low in order to make the cracks more obvious... Here is a screenshot with higher detail (still haven't gotten around to fixing the cracks): jb8PAs.png

I still think you can use a ray-marching approach but limit yourself to a low resolution, then scale this resolution up to fit the rest of your scene (like the tree or players etc...), then texture and shade it on the gpu with a deferred shading pass. The result will be much nicer and you can realistically run it with a much lower resolution. There will be trickery in up-scaling the image to fit the higher resolution forward rendered stuff (basically an upsampling problem) but you can also use it to do early culling for example. I would go with ray marching as it's the simplest one and distance calculations boil down to dist square tests. But ok who would like to have a completely dynamic terrain anyway ;-)


Edited by jbadams, 13 April 2014 - 01:57 AM.
Restored post contents from history.


#16 colinhect   Members   -  Reputation: 193

Like
0Likes
Like

Posted 05 January 2011 - 02:28 PM

Quote:
Original post by spinningcube
I still think you can use a ray-marching approach but limit yourself to a low resolution, then scale this resolution up to fit the rest of your scene (like the tree or players etc...), then texture and shade it on the gpu with a deferred shading pass. The result will be much nicer and you can realistically run it with a much lower resolution. There will be trickery in up-scaling the image to fit the higher resolution forward rendered stuff (basically an upsampling problem) but you can also use it to do early culling for example. I would go with ray marching as it's the simplest one and distance calculations boil down to dist square tests. But ok who would like to have a completely dynamic terrain anyway ;-)


Are there any examples that you know of that use real-time ray-marching on a large scale persistent terrain isosurface? I Googled for it a bit and haven't found anything to convince me that what you are proposing is a better solution than my current one. Implementations I have seen have simple texturing, noticeable aliasing (not as bad as popping), and do not show how the terrain looks with polygon models in the scene. And what about terrain self-shadowing and polygon models casting shadows on the terrain?

Thanks for the reply.

Edit: I just realized that it is funny that you call polygons old-school. I remember the early Novalogic games (Camanche, Delta-force) that used volume ray-casting for terrain. :p

#17 zzzz....   Members   -  Reputation: 88

Like
0Likes
Like

Posted 05 January 2011 - 02:52 PM

Quote:Original post by c_olin
Quote:Original post by spinningcube I still think you can use a ray-marching approach but limit yourself to a low resolution, then scale this resolution up to fit the rest of your scene (like the tree or players etc...), then texture and shade it on the gpu with a deferred shading pass. The result will be much nicer and you can realistically run it with a much lower resolution. There will be trickery in up-scaling the image to fit the higher resolution forward rendered stuff (basically an upsampling problem) but you can also use it to do early culling for example. I would go with ray marching as it's the simplest one and distance calculations boil down to dist square tests. But ok who would like to have a completely dynamic terrain anyway ;-)
Are there any examples that you know of that use real-time ray-marching on a large scale persistent terrain isosurface? I Googled for it a bit and haven't found anything to convince me that what you are proposing is a better solution than my current one. Implementations I have seen have simple texturing, noticeable aliasing (not as bad as popping), and do not show how the terrain looks with polygon models in the scene. And what about terrain self-shadowing and polygon models casting shadows on the terrain? Thanks for the reply. Edit: I just realized that it is funny that you call polygons old-school. I remember the early Novalogic games (Camanche, Delta-force) that used volume ray-casting for terrain. tongue.png

The terrain you are looking at is 4096 cube and already encoded in a very good structure for distance calculations. As for texturing, lighting etc... That is easier to do in a deferred pass as you can extract normals and uvs and any other parameters from the emitters directly. Terrain self shadowing would be easy as you can shoot out an extra ray into the light direction and check for intersections, but easier still is an AO approach as it is almost "for free" using raymarching. (See Inigo Quilez trick originally by guys from Little Big Planet) Mixing it with other geometry is as easy as you just populate the z buffer from your ray marched image, with a texture uploaded on the GPU. Now why there are not more examples? Hmmm how about this one, granted not pure ray marching but still It uses ray marching for the details in the landscape. I think there are not more examples because people have not tried it enough that's all. Also I think there was in fact an image of the day here with a ray marcher of sorts a year ago on a landscape with overhangs. But like I said you don't have to go full resolution as it's overkill and you only have to extract the landscape using ray marching. The rest can be calculated on the GPU. But you can do it on the GPU with some clever octree packing for example, still in a lower resolution. For the voxel rendering approach (Commanche) that is pretty cool but not the smooth look you are shooting for I guess, so it's not really the same but yeah the idea is not far away.


Edited by jbadams, 13 April 2014 - 01:58 AM.
Restored post contents from history.


#18 colinhect   Members   -  Reputation: 193

Like
0Likes
Like

Posted 05 January 2011 - 03:24 PM

What about physics? I will need to have localized areas where objects can interact with the terrain. Wouldn't those areas have to be polygonized for the physics system?

#19 zzzz....   Members   -  Reputation: 88

Like
0Likes
Like

Posted 05 January 2011 - 03:30 PM

Quote:Original post by c_olin What about physics? I will need to have localized areas where objects can interact with the terrain. Wouldn't those areas have to be polygonized for the physics system?

Nope, no need as you can as well there shoot rays for contacts with the surface or just do distance tests. But hey, if you want just finish it with polys for now and then as a fun experiment check how it would be with raymarching. No hurt in that, right?


Edited by jbadams, 13 April 2014 - 01:58 AM.
Restored post contents from history.


#20 Eric Lengyel   Crossbones+   -  Reputation: 2215

Like
3Likes
Like

Posted 08 February 2011 - 04:37 PM

The look-up tables that I said I would release are now available here:

http://www.terathon.com/voxels/




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS