The maching cube algorithm is quite easy, but hard to grasp, and badly documented.
Basically it’s the extraction of isosurfaces from a three dimensional scalar field using it’s density.
You have a 3d grid representing the density as voxels. You parse this grid with a vertex grid, and depending on how many vertices of those parsing/marching cubes are inside the isosurface, you get a matching part of the polygon surface.
As with 8 corners of a cube you can have 2^8 cases, resulting in 256 cases matching the “lit” vertices.
This is handy for several reasons, you can use bitarrays for the voxeldata, and bitarrays for the cube cases, which immensly speeds up the process.
Out of this 256 cases, there are originally 15 matching cases of polygons to fill the cube. Those 15 cases can be inverted and mirrored along their axis to produce those 256 matches.
One problem in the original implementation from 1987(!) creates ambiguous cases, possibly producing holes. There are several dissertations out there, enhancing the original implementation to prevent that. You might want to google for transvoxel implementations, or a combined marching cubes-marching tetrahedon implementation, where the corners of the cubes are parsed with tetrahedons.
A lot of possibilities, and with todays memory bandwith and cpu speeds there are lot’s of possibilities, not to mention you can do a lot on the GPU.
But it’s not an easy task nonetheless. I am currently attempting to write an infinite transvoxel landscape engine with adaptive LOD and it’s going along slooooow.
But, for your case there’s very easy C++ source available, public domain, ready to use. You just need to enhance the code to feed it your pointcloud data:
(only needs glut/freeglut)
If you want I can provide a compiled .exe
Here’s information on the original implementation:
You could also consider to simply use a 3rd party tools like Meshlab (which is FOSS):
One problem is the correct implementation of marching cubes for real pointclouds. It works really great for real voxels occupying the grid densly. I guess for pointclouds you’d have to create a 3d grid of dense voxels, and give them a density value based on the amount of points inside the cube, and then use a linear interpolation to match the triangles along the edges of the marching cubes, intersecting the “iso surface”, which is a non trivial matter and could be used to write a dissertation