Sign in to follow this  
Rasmadrak

Marching Cubes - how do I generate different cubes?

Recommended Posts

Rasmadrak    196
Hi! I'm currently experimenting with the "marching cubes"-algorithm, but I'm wondering if there's a shortcut to generate the 255 various types of cubes? I know that it boils down to the following: 15 unique cubes. * Rotation by any degree over any of the 3 primary axis * Mirroring the shape across any of the 3 primary axis * Inverting the state of all corners and flipping the normals of the relating polygons. I'm currently doing bitwise comparisons so I know which cube I'm supposed to use. The problem I'm having is that I can hardcode the triangles for the 15 boxes, but I would like to describe them / auto-generate them from the binary-number the bitwise operation makes. Is this possible? If so, how? Also, when inverting the state - should this be done for each rotation step or simply once from the original state of that perticular cube? [Edited by - Rasmadrak on December 18, 2008 5:23:12 AM]

Share this post


Link to post
Share on other sites
PKLoki    1492
Advice 1: think about using marching simplex (tetrahedra in 3D) instead - there are only 2 kinds of possible triangle configurations in a tetrahedron, not 15 as in a cube, and the degenerate case problem (which is tricky to solve in general for cubes) doesn't occur. The downside is that you likely end up with a denser mesh than with cubes since you will have 6 tetrahedra where before there was 1 cube.

Advice 2: I wouldn't worry about how you create your cube types. If you come up with a way of auto-generating them in code then all you gain is a pat on the back from yourself. Hard-coding them may seem primitive, but it's something you'll write once and then leave fixed. Just put the cube types in a std::map and look up the one you need from the 8-bit number created from the signs of the cube corners.

Share this post


Link to post
Share on other sites
Nyarlath    104
Quote:
Original post by PKLoki
Just put the cube types in a std::map

Not the best idea. Put them a fixed length array (for constant time element access and... are you using c++?).

You'd better to copy-paste the entire look-up tables from e.g. here.

Share this post


Link to post
Share on other sites
Rasmadrak    196
I did the, rather dirty, act of ripping the face-indices from the page you submitted. Works as expected :)

Now the next problem would be to smooth the vertices while still maintaining the edge-vertices, but that's another story...

Thanks both of you!

Share this post


Link to post
Share on other sites
PKLoki    1492
Quote:
Original post by Nyarlath
Quote:
Original post by PKLoki
Just put the cube types in a std::map

Not the best idea. Put them a fixed length array (for constant time element access and... are you using c++?).

Or put them in a fixed length array... ;)

Regarding smoothing, are you talking about a local or global effect? For local 'abnormalities' in the surface such as collapsed (near-zero-area) triangles you can either apply a local smoothing to expand the vertices of the bad triangle towards its neighbours, or you could collapse the neighbouring degenerate vertices into one, though this will require you to reorder the connectivity of the local topology, i.e. replace indices of the removed vertices with that of the new single vertex in all triangles affected by the change.

If you apply a global smoothing - i.e. replacing each vertex with the weighted average position of itself and it's neighbours (possibly including next-nearest neighbours etc. to some chain depth through the edges of the triangulation) weighted by spatial distance to try to preserve local detail, you can end up with very regular triangulations, and as a byproduct also fix any unusual surface abnormalities like the degenerate triangles mentioned above in the local case. But this comes at the expense of a loss of absolute spatial correctness which (depending on your requirements) may be unacceptable. If the mesh is used for visualisation, and has a fairly low curvature relative to the mesh resolution, the results may be perfectly acceptable even with several iterations of global smoothing.

Share this post


Link to post
Share on other sites
Rasmadrak    196
What I need is probably referred to as global smoothing, since the entire mesh is "stair-cased" at the moment. I thought about this a bit and in theory, it should be a matter of creating a new mesh from the old where each vertice gets blended with its neighbours (As you suggested).

However - Won't this produce cracks in the mesh?
I'm currently using regular triangles and vertices are therefor duplicated.
I may replace this further on with an indexed version so that vertices are shared.

Since the geometry can be of any shape, I need a smoothing algorithm that doesn't need to know what shape it's creating.
The smoothing is not needed to be 100%, or even 70%, accurate as it is for non-scientific use, just enough to prevent unwanted aliasing/stair-casing.

Is there any (free/gnu) library that can transform a regular mesh into a indexed mesh? Or am I better off simply hardcoding a function that gets each vertexs neighbour vertices?

Share this post


Link to post
Share on other sites
PKLoki    1492
It shouldn't be too difficult to index into the point set as you go along. Just make sure you only create one vertex per required cube edge, and treat the edges as shared between cubes. That eliminates the issue of degenerate vertices, and indexing the vertices is simpler because you know that all edges can only contain maximum one vertex and therefore index the edges instead.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this