A flexible framework for surface reconstruction from large point sets

This paper presents a flexible method to reconstruct simplified mesh surfaces from large unstructured point sets, extending recent work on dynamic surface reconstruction. The method consists of two core components: an efficient selective reconstruction algorithm, based on geometric convection, that simplifies the input point set while reconstructing a surface, and a local update algorithm that dynamically refines or coarsens the reconstructed surface according to specific local sampling constraints.A new data structure is introduced that significantly accelerates the original selective reconstruction algorithm and makes it possible to handle point set models with millions of sample points. This data structure mixes a kd-tree with the Delaunay triangulation of the selected points enriched with a sparse subset of landmark sample points. This design efficiently responds to the specific spatial location issues of the geometric convection algorithm. It also permits the development of an out-of-core implementation of the method, so that simplified mesh surfaces can be seamlessly reconstructed and interactively updated from point sets that do not fit into main memory.