Coarse-to-fine surface simplification with geometric guarantees

Let PC be a 3D point cloud and epsilon 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 epsilon from a facet of S. (PCU and PCL respectively stand for Point Cloud Used an d Point Cloud Left.) We call this problem simplification with geometric gua rantees. This paper presents a new framework to simplify with geometric guarantees. The approach relies on two main ingredients. First an oracle providing info rmation on the surface being reconstructed even though the triangulated sur face itself has not been computed. Second, a reconstruction algorithm provi ding incremental updates of the reconstructed surface, as well as a fast po int-to-triangles distance computation. The oracle is used to guess a subset of the point cloud from which a triangulated surface is reconstructed It r elies on an implicit surface the triangulated surface is an approximation o f, and is therefore available before the triangle mesh. The point-to-triang les distance computation and the local updates are then invoked to insert n ew 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 runnin g time. To the best of our knowledge, this algorithm is the first one performing co arse-to-fine surface simplification with geometric guarantees.