The Crust Algorithm
for
3D Surface Reconstruction from Scattered Points

Nina Amenta - Marshall Bern - Manolis Kamvysselis
University of Texas at Austin - Xerox PARC - Massachusetts Institute of Technology

Xerox PARC, summer 97

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.

Paper:

The work was published in Siggraph '98
Download Siggraph paper in pdf format (521K) or ps.gz (1180K)

Slides:

Some slides (7 jpgs) from a talk i gave last summer (aug 97)

Pictures:

Hypersheet (gif) Medial Axis and Medial Surface (jpg)

Intersecting planes (jpg)

Voronoi Cells (gif)

Questions on computing voronoi centers?

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