Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Voxel / Marching Cubes


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
5 replies to this topic

#1 Shael   Members   -  Reputation: 277

Like
0Likes
Like

Posted 24 May 2011 - 09:51 PM

G'day,

I've recently seen some pretty cool demos showing Voxel/Marching Cube terrain and have a few general questions about it. I'll just list them out and hopefully someone with some experience in the area can answer them.

1. How is Voxel data usually stored? Is it similar to height-mapped terrain where you can just specify heights and then generate the vertices during run-time?

2. How is the large memory footprint handled in a real-time simulation? Are there "chunks" which can be streamed in and out depending on view distance?

3. What sort of partitioning/culling methods can apply? Octree/Frustum, Occlusion Culling?

4. What sort of LOD techniques work well? (This could kind of apply to question 2 I guess)

5. Know of any simple examples I can examine?


Thanks!

Sponsor:

#2 psquare   Members   -  Reputation: 180

Like
1Likes
Like

Posted 25 May 2011 - 12:52 AM

1. How is Voxel data usually stored? Is it similar to height-mapped terrain where you can just specify heights and then generate the vertices during run-time?

It could be as simple as a raw 3D array with an associated value. This value can be density (e.g. 0 for air, 1 for solid), or multiple values like density, opacity, material id, etc. It depends on what all scalar quantities you need to represent in the 3D structure.

Marching cubes 'walks' this volume and generates meshes which is what you render with ultimately.

2. How is the large memory footprint handled in a real-time simulation? Are there "chunks" which can be streamed in and out depending on view distance?

A voxel based data structure can run time compress/decompress the stored values using an algorithm like rle, etc, so that run time memory consumption is kept at a minimum. If RAM is not an issue, just disk space, then merely zipping up the raw serialized voxel data suffices.

3. What sort of partitioning/culling methods can apply? Octree/Frustum, Occlusion Culling?

This is sort of orthogonal to voxel/marching cubes, but you can use any method. It depends on what you want really/application domain. For example, in medical applications, you can't really use occlusion culling, because the volumes' color may need to be alpha blended with volumes occluding them. Usually however, if you have multiple volumes, at a minimum, you would do view frustum culling.

4. What sort of LOD techniques work well? (This could kind of apply to question 2 I guess)
5. Know of any simple examples I can examine?


PolyVox is a very good library that is used to work with voxel data. There's a lot of information on all of your above questions on the forums there.

http://www.thermite3d.org/phpBB3/

C4 engine is another:

http://www.terathon....ngine/index.php

#3 Shael   Members   -  Reputation: 277

Like
0Likes
Like

Posted 25 May 2011 - 06:00 PM

Thanks for the response. PolyVox looks pretty good and I might end up using it instead of writing my own routines.

#4 Eric Lengyel   Crossbones+   -  Reputation: 2604

Like
0Likes
Like

Posted 29 May 2011 - 02:09 PM

For voxel terrain LOD, take a look at this:

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

#5 spacerat   Members   -  Reputation: 761

Like
0Likes
Like

Posted 30 May 2011 - 01:47 PM

also worth a look:

Efficient voxel octrees
http://code.google.c...-voxel-octrees/
(code included, eventhough its not polygon based)

this engine using marching cubes with LOD
http://lugtug.com/dev/2008/09/22/more-terrain/
(techniques linked below)

Cubical Marching Squares (CMS)
http://graphics.csie.ntu.edu.tw/CMS/

Dual Marching Cubes
http://faculty.cs.tamu.edu/schaefer/research/dmc.pdf

and another list of engines, where you can compare different technologies
http://www.jonof.id....hp?topic=1664.0

#6 robotichrist   Members   -  Reputation: 193

Like
-2Likes
Like

Posted 02 June 2011 - 12:49 PM

Here is a really dead simple/bone headed algorithm that I've used to do level-set surface reconstruction. Unlike marching cubes/tets/whatever it has no special cases, though the trade off is that it can end up being a bit slower. This is how it works:

1. First, generate an initial coarse mesh that covers the level set. This can be as simple as just covering it with uniform boxes and then gluing them together along coplanar faces, throwing out the ones which do not cross the boundary.

2. Next, take your coarse mesh and perturb the vertices so that they lie on the level set boundary. To do this, you just use a non-linear root finding method, such as Newton's method/gradient descent.

3. Take the resulting mesh that you got from step 2 and apply a surface subdivision algorithm.

4. Go to step 2 and repeat until your mesh is reasonably fine.

Of course where this can get into trouble is if your initial guess/mesh was too coarse (ie you cover up a hole or something). So, there are probably some ways to refine this to make it a bit more efficient and robust. However, the general idea is to just solve the problem like you would any ordinary type of non-linear root finding problem; which is to just do gradient descent and iterate until it converges.


EDIT: -2 ? Really? I never claimed this method was particular good or even that original ( I am sure that someone has tried doing this before... ), but it is simple and it works. Could someone please explain what their issue is with this post? I would be happy to stand corrected if there is something wrong with what I wrote.




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