# 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