Surface Reconstruction by Voronoi Filtering

Surface Reconstruction by Voronoi Filtering

1998 | Nina Amenta, Marshall Bern
This paper presents a combinatorial algorithm for surface reconstruction from a finite set of sample points. The algorithm uses Voronoi vertices to remove triangles from the Delaunay triangulation. It is proven to be correct for densely sampled surfaces, where the density depends on the local feature size. The algorithm produces a piecewise-linear approximation of a smooth surface that is topologically valid and converges to the original surface in both pointwise and normal terms. The algorithm is implemented and tested with examples. The paper extends previous work on two-dimensional curve reconstruction to three dimensions, introducing new algorithmic ideas and proof techniques. The algorithm uses only a subset of Voronoi vertices to remove Delaunay triangles, and introduces the concept of "poles" to enable further filtering based on triangle normals. The algorithm is proven to produce a surface that is pointwise convergent to the original surface and has the same topology. The paper also discusses theoretical guarantees for the algorithm, including convergence in surface normals and topological equivalence. The algorithm is implemented and tested with examples, showing its effectiveness in reconstructing surfaces from sample points. The paper concludes with a discussion of future work and open questions in surface reconstruction.This paper presents a combinatorial algorithm for surface reconstruction from a finite set of sample points. The algorithm uses Voronoi vertices to remove triangles from the Delaunay triangulation. It is proven to be correct for densely sampled surfaces, where the density depends on the local feature size. The algorithm produces a piecewise-linear approximation of a smooth surface that is topologically valid and converges to the original surface in both pointwise and normal terms. The algorithm is implemented and tested with examples. The paper extends previous work on two-dimensional curve reconstruction to three dimensions, introducing new algorithmic ideas and proof techniques. The algorithm uses only a subset of Voronoi vertices to remove Delaunay triangles, and introduces the concept of "poles" to enable further filtering based on triangle normals. The algorithm is proven to produce a surface that is pointwise convergent to the original surface and has the same topology. The paper also discusses theoretical guarantees for the algorithm, including convergence in surface normals and topological equivalence. The algorithm is implemented and tested with examples, showing its effectiveness in reconstructing surfaces from sample points. The paper concludes with a discussion of future work and open questions in surface reconstruction.
Reach us at info@study.space