Marching Cubes

Blitz3D Forums/Blitz3D Programming/Marching Cubes

ClayPigeon(Posted 2011) [#1]
OK, I need some way of creating a mesh from voxel data (stored in a 3D bank) and the best method I've found is marching cubes. Am I correct in assuming that I have to make my own lookup table, or is there one that you can find somewhere? I'm reluctant to just jump right in without some prior knowledge on the technique and try to make a lookup table that could potentially take me forever to make and end up being useless anyway. So, can someone please point me in the right direction as to how the marching cubes algorithm is implemented. And don't say Google - I've gone far past page 10 of Google without any concrete info showing up. (just research papers with a vague concept of it)

Last edited 2011


Matty(Posted 2011) [#2]
http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/

First link in "external links" section of the wikipedia marching cubes entry, found via google.


ClayPigeon(Posted 2011) [#3]
I saw that page and it was the closest I got to a firm, clear explaination of how the algorithm works. Could this work in B3D? And if so, would it make more sense to create 256 meshes for each setup, or just look them up and generate the mesh for each cube?

Last edited 2011


Rroff(Posted 2011) [#4]
IIRC theres a rather neat metaballs example on here somewhere that has some marching cubes stuff in it thats quite a good refernce for implementation in blitz.


Oiduts Studios(Posted 2011) [#5]
Here it is http://www.blitzbasic.com/Community/posts.php?topic=89213#1018952


Axel Wheeler(Posted 2011) [#6]
How big is the array you are starting with? And do you need to do this periodically throughout the game/program or just at startup?

Reason for questions: Marching cubes may be optimal in terms of speed, but the complexity of implementation (debugging, etc.) may make it more sensible to iterate through the array and generally brute force it. With marching cubes you need to ensure that every point of the surface is visited. Also, if there are multiple 'solids' within you have to account for that.

If you do need the speed you might want to start with implementing marching squares algorithm:

http://en.wikipedia.org/wiki/Marching_squares

which is the basis of marching cubes, just to wrap your head around the concepts and steps involved.

Good luck Clay..


ClayPigeon(Posted 2011) [#7]
Actually, it only needs to be done at startup, as I'm experimenting with complex terrains, and I need a way of converting the volume data into a mesh. So, after the mesh is generated at the start, I don't need to run it again.

How big is the array you are starting with?

The array is 256x256x256. Using a bank and the equation for poking/peeking data is 'z*x_size*y_size + y*x_size + x'.

Last edited 2011


Matty(Posted 2011) [#8]
Just a simple point...given most terrain meshes are broader and wider than they are tall - couldn't you assign more 'cubes' to the horizontal axes and less to the vertical.

Eg 512x64x512 for example...takes up the same size array as 256x256x256 but allows for a larger horizontal space to be taken up.


ClayPigeon(Posted 2011) [#9]
couldn't you assign more 'cubes' to the horizontal axes and less to the vertical.

Yeah that's what I plan on, this is just for testing's sake. Although eventually I might have ridiculously tall mountains form or underground caves or something that takes up a large amount of vertical space. I also might not even use volume data and just have it calculate the data at each position checked, though that is less likely.

Last edited 2011