
Title  A New VoronoiBased Surface Reconstruction Algorithm
(Article) 
in  Siggraph 
Author(s) 
Nina Amenta, Marshall Bern, Manolis Kamvysselis 
Keyword(s)  Medial axis, Sampling, Delaunay triangulation, Computational Geometry 
Year 
1998

Pages  415421 
Download  
BibTeX  
Abstract 
We describe our experience with a new algorithm for the reconstruction of surfaces from unorganized sample points in IR3. The algorthim is the first for this problem with provable guarantees. Given a "good sample" from a smooth surface, the output is guaranteed to be topologically correct and convergent to the original surface as the sampling sensity increases. The definition 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. The output mesh interpolates, rather than approximates, the input points.
Our algorithm is based on the threedimensional Voronoi diagram. Given a good program for thsi fundamental subroutine, the algorithm is quite easy to implement.
