Surface reconstruction by Voronoi filtering. (English) Zbl 0939.68138

Summary: We give a simple combinatorial algorithm that computes a piecewise-linear approximation of a smooth surface from a finite set of sample points. The algorithm uses Voronoi vertices to remove triangles from the Delaunay triangulation. We prove the algorithm correct by showing that for densely sampled surfaces, where density depends on a local feature size function, the output is topologically valid and convergent (both pointwise and in surface normals) to the original surface. We briefly describe an implementation of the algorithm and show example outputs.


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W05 Nonnumerical algorithms
Full Text: DOI