|Nina Amenta -||Marshall Bern||- Manolis Kamvysselis|
|University of Texas at Austin -||Xerox PARC||- Massachusetts Institute of Technology|
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.
Some slides (7 jpgs) from a talk i gave last summer (aug 97)
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.