Surface Reconstruction by Voronoi Filtering

By Nina Amenta, M. Bern. 1998

Abstract. 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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

PCPNet Learning Local Shape Properties from Raw Point Clouds (2017, methodology): “…osculating jets [CP03] based on ﬁtting higher-order primitives robustly, the algebraic point set surface approach based on ﬁtting algebraic spheres [GG07], and approaches based on analyzing the distribution of Voronoi cells in the neighborhood of a point [AB99, ACSTD07, MOG11], among many others.”
Voronoi-based variational reconstruction of unoriented point sets (2007, unknown): “Moreover, as described in [ AB99 ], the confidence in the estimate is related to how long and thin the Voronoi cell is, i.e., to the anisotropy of the covariance tensor.”
A Survey of Surface Reconstruction from Point Clouds (2017, background): “Conditions on sampling are relaxed in [CLCL11] where inconsistencies are detected by observing that if one point’s Voronoi pole [AB99] lies in the exterior, the other Voronoi pole should be in the interior.”
Provable surface reconstruction from noisy samples (2004, methodology): “[4] F. Bernardini, J. Mittleman, H. Rushmeier, C. Silva and G. Taubin.”
The 3D Model Acquisition Pipeline (2002, methodology): “Attempts so far have been mostly restricted to the 2D case [55–57], with the exception of [50] and [52].”
Consolidation of unorganized point clouds for surface reconstruction (2009, methodology): “These methods often provide provable guarantees under prescribed sampling criteria [Amenta and Bern 1998] or noise models [Dey and Goswami 2006] that are generally not realizable by real-world data.”
Stability of Persistence Diagrams (2005, background): “How can we exploit the new insights to get improved algorithms for problems like the medial axis [5], surface reconstruction [1, 10], and alike? How far can we relax the requirements on the input data and still guarantee correct construction?”
Three‐dimensional adaptive meshing by subdivision and edge‐collapse in finite‐deformation dynamic–plasticity problems with application to adiabatic shear banding (2002, background): “However, while suIcient conditions for the existence of a constrained-Delaunay volume triangulation consistent with a given surface triangulation are known (e.g., Reference [ 41 ]), in practice, those conditions may not be attained for geometries with very small local feature sizes.”
Estimating surface normals in noisy point cloud data (2003, background): “[3] such algorithms can fail even in cases with arbitrarily dense set of samples.”
Homological illusions of persistence and stability (2008, methodology): “Computational geometry favors combinatorial algorithms based on Delaunay triangulations [33] and provides proofs of correctness under assumptions of dense sampling [3, 20].”
Finding the Homology of Submanifolds with High Confidence from Random Samples (2008, methodology): “Such work has typically focused on the case of surfaces in IR 3 and examples include algorithms associated with the frameworks of alpha shapes [5], CRUST [1] and its variants, and CO- CONE [2] and its generalizations.”
Fast surface reconstruction using the level set method (2001, methodology): “A lot of work has been done along these lines [3, 4, 5, 8, 12, 13] and efficient algorithms are available to compute Delaunay triangulations and Voronoi diagrams.”