Water-tight surface reconstruction algorithm for organized point cloud

6
votes

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)
2
algorithm3dpolygonpoint-clouds

2 Answers

4
votes

You probably want the marching cubes algorithm.

3
votes

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/