SURFACE RECONSTRUCTION BY VORONOI FILTERING

Marshall Bern

Xerox PARC

Abstract

I will describe a new algorithm for the reconstruction of surfaces from unorganized sample points in 3D. The algorithm uses the well-known notions of Voronoi diagram and Delaunay triangulation. This algorithm is the first algorithm for this problem with provable guarantees. Given a sufficiently dense sample from a smooth surface, the output is guaranteed to be topologically correct and convergent to the original surface as the sampling density increases. The density of samples varies locally, depending upon curvature and proximity of  "other parts" of the surface.


Edited by Leonidas Guibas