Marching cubes

As you probably know, the Marching Cubes algorithm works on a regularly spaced grid of density values.

A very primitive solution would be to:
- Snap all of your points (P) to the points on a regularly spaced grid (P'). A good density value for each P' would then be the number of P which were snapped to it.
- Once all P have been snapped to P', find the P' with the maximum density value (e.g., snapped-to count) and then divide all P' density values by that amount. This effectively normalizes the density value range from 0 to 1 for all P'.
- Convert the regularly spaced grid to a mesh using an isovalue of 0.5.

I can provide more specifics if you want to go this route.

Hi Taby

Thank you for your response but still i did not understand you said. I am still beginner for marching cubes. :)

Can you explain me with some more details ? or may be some documents or samples etc. ?


Naresh

Marching cubes probably isn't the algorithm that you want for this. Marching cubes computes an isosurface of a density function, and your points don't really represent a density function.

There are two classes of algorithms I'm aware of that do aim to solve your problem.

1 - Delaunay algorithms.
In a nutshell, compute the Delaunay tetrahedralization of these vertices in 3d and then throw out everything except the faces (triangles) of the tetrahedra that are on the "outside."

2 - Ball pivoting algorithms.
These algorithms "simulate" rolling a ball over your surface and generates triangles based on which points the ball is touching.

I won't describe either of these in any more detail than this (for one thing, I'm not an expert in either of them), but I do know that they are "the algorithms" used for this sort of thing; you can wiki them for more information.

Quote:

Original post by nareshn2008 Hi Taby Thank you for your response but still i did not understand you said. I am still beginner for marching cubes. :) Can you explain me with some more details ? or may be some documents or samples etc. ? Naresh

Well, like Emergent mentions, there may be better algorithms to use if you simply want to find a mesh that encloses all of your points.

... that said ...

If you want me to help out, send me an email at shalayka@gmail.com with the file containing the set of points, so that I can see what data format you are working with. I would essentially retrofit my Marching Cubes code to work with your format.

I've done this for someone else in the past, and it worked out relatively well. The point set they gave me was very large (dense), and the points were all spread relatively uniformly throughout the volumetric object. This resulted in a mesh that was very useful to them. However, if your point set is fairly small (sparse), or if the points all lie close to the surface of the volumetric object, then Emergent's suggestion would be better by default.

The work I would do to help you out wouldn't take more than an hour or two, so we can easily and quickly try Marching Cubes out first before you decide on whether or not a different algorithm is needed to provide a mesh that is useful to you.

Hi everybody, I was reading your advices, and I've got a trouble with marching Cubes, I'm a beginner at this. Well, what I have to do is to reconstruct a surface from a set of particles (those have a point as a center and a radius) that are processed and given, in my case, they are processed by a SPH method. But i dont have a clearly idea about how i'm gonna used MC algorithm for that.

I have to use it, so I cant change to another.

I am starting with something easier, the 2D bro .. I mean, marching squares, so from a set of points (x,y) and a radius r. what are especificly the steps do i have to follow to achieve this?

I hope you to help me with this. I'm kind of hurry to make this up.

PD: sorry if my writing english isn't good.