The Crust Algorithm
for
3D Surface Reconstruction from Scattered Points

Abstract:

The Crust Algorithm is a new algorithm for the reconstruction of surfaces of arbitrary topology from unorganized sample points in 3d. The algorithm is the first one for this problem with provable guarantees. Given a "good sample" from a smooth surface, the output is guraranteed to be topologically correct and convergent to the original surface as the sampling density increases. The defintion of a good sample is itself interesting: the required sampling density varies locally, rigorously capturing the intuitive notion that featureless areas can be reconstructed from fewer samples. Our algorithm is based on the three-dimensional Voronoi diagram.

Questions on computing voronoi centers?

Interested in implementing convex hull, voronoi diagrams, delaunay triangulations? Some implementations are available at the Geometry center.