Approximate Delaunay mesh reconstruction and quality estimation from point samples

•We present proof for mesh reconstruction from points that gives the upper and lower bounds of mesh quality.•A practical approximate Delaunay mesh reconstruction method is proposed.•Experiments show that our method works well on real-world point cloud.

Several sampling criteria had been proposed for C2C2 smooth surfaces such that the reconstructed meshes from point samples are homeomorphic to the original surfaces. In this paper, based on a widely used sample criterion, we present proofs that give the upper and lower bounds of mesh quality (in terms of several triangle aspect ratios) for the reconstructed mesh. To make the proposed theoretical bounds useful in practical applications with real-world point data, we propose a novel mesh reconstruction method that works in three steps: (1) approximate Delaunay mesh reconstruction; (2) point data upsampling and (3) hole filling. Finally, examples are presented, which illustrate the effectiveness of the proposed method.