Coarse-to-fine surface simplification with geometric guarantees

Let PC be a 3D point cloud and ε be a positive value called tolerance. We aim at constructing a triangulated surface S based on a subset PCU of PC such that all the points in PCL=PC∖PCU are at distance at most ε from a facet of S. (PCU and PCL respectively stand for Point Cloud Used and Point Cloud Left.) We call this problem simplification with geometric guarantees. This paper presents a new framework to simplify with geometric guarantees. The approach relies on two main ingredients. First an oracle providing information on the surface being reconstructed even though the triangulated surface itself has not been computed. Second, a reconstruction algorithm providing incremental updates of the reconstructed surface, as well as a fast point-to-triangles distance computation. The oracle is used to guess a subset of the point cloud from which a triangulated surface is reconstructed. It relies on an implicit surface the triangulated surface is an approximation of, and is therefore available before the triangle mesh. The point-to-triangles distance computation and the local updates are then invoked to insert new vertices until the tolerance is met. We also present a detailed experimental study which shows the efficiency of the simplification process both in terms of simplification rate and running time. To the best of our knowledge, this algorithm is the first one performing coarse-to-fine surface simplification with geometric guarantees