Water-tight surface reconstruction algorithm for organized point cloud

Question

I have a 3D Cartesian cube. For each point in this cube there is a corresponding density value. When the density changes suddenly it means that there is a cavity. Now to find the cavity I calculate the gradient at each point in the cube. This gives me a point cloud on the surface of the cavity. I would now like to mesh the surface of the cavity given the point cloud.

Unfortunately I don't have any experience with surface reconstruction and was wondering if someone can recommend a suitable algorithm which will produce a closed surface of the cavity?

The cube is quite big so a point cloud of the surface of a cavity can easily be 500.000 points or more. I have read this post: robust algorithm for surface reconstruction from 3D point cloud? which I find useful. However it seems that the problem I am facing is simpler, given that:

1. The coordinates of the points are always integer
2. The point distribution is even
3. The distance from one point to its closest neighbour is either 1, sqrt(2) or sqrt(3)

Answer 1

You probably want the marching cubes algorithm.

Answer 2

The Marching Cubes algorithm will do exactly what you want. For a working implementation (using Three.js for rendering the graphics), check out:

http://stemkoski.github.com/Three.js/Marching-Cubes.html

For more details on the theory, I think the best article is the website:

http://paulbourke.net/geometry/polygonise/