HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Sampling and Meshing Surfaces with Guarantees

Steve Y. Oudot 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In the last decade, a great deal of work has been devoted to the elaboration of a sampling theory for smooth surfaces. The goal was to work out sampling conditions that ensure a good reconstruction of a given smooth surface S from a finite subset E of S. Among these conditions, a prominent one is the e-sampling condition of Amenta and Bern, which states that every point p of S is closer to E than e times lfs(p), where lfs(p) is the distance of p to the medial axis of S. Amenta and Bern proved that it is possible to extract from the Delaunay triangulation of E a PL surface that approximates S both topologically and geometrically. Nevertheless, the important issues of checking whether a given point set is an e-sample, and constructing e-samples of a given smooth surface, have never been addressed. Moreover, the sampling conditions proposed so far offer guarantees only in the smooth setting, since lfs vanishes at points where the surface is not differentiable. In this thesis, we introduce the concept of loose e-sample, which can be viewed as a weak version of the notion of e-sample. The main advantage of loose e-samples over e-samples is that they are easier to check and to construct. Indeed, checking that a finite set of points is a loose e-sample reduces to checking whether a finite number of spheres have small enough radii. When the surface S is smooth, we prove that, for sufficiently small e, e-samples are loose e-samples and vice-versa. As a consequence, loose e-samples offer the same topological and geometric guarantees as e-samples. We further extend our results to the nonsmooth case by introducing a new measurable quantity, called the Lipschitz radius, which plays a role similar to that of lfs in the smooth setting, but which turns out to be well-defined and positive on a much larger class of shapes. Specifically, it characterizes the class of Lipschitz surfaces, which includes in particular all piecewise smooth surfaces such that the normal variation around singular points is not too large. Our main result is that, if S is a Lipschitz surface and E is a point sampling of S such that any point p of S has a distance to E that is less than a fraction of the Lipschitz radius of S, then we obtain similar guarantees as in the smooth setting. More precisely, we show that the Delaunay triangulation of E restricted to S is a 2-manifold isotopic to S lying at Hausdorff distance O(e) from S, provided that its facets are not too skinny. We also extend our previous results on loose samples. Furthermore, we are able to give tight bounds on the size of such samples. To show the practicality of the concept of loose e-sample, we present a simple algorithm that constructs provably good surface meshes. Given a compact Lipschitz surface S without boundary and a positive parameter e, the algorithm generates a sparse loose e-sample E and at the same time a triangular mesh extracted from the Delaunay triangulation of E. Taking advantage of our theoretical results on loose e-samples, we can guarantee that this triangular mesh is a good topological and geometric approximation of S, under mild assumptions on the input parameter e. A noticeable feature of the algorithm is that the input surface S needs only to be known through an oracle that, given a line segment, detects whether the segment intersects the surface and, in the affirmative, returns the intersection points. This makes the algorithm useful in a wide variety of contexts and for a large class of shapes. We illustrate the genericity of the approach through a series of applications: implicit surface meshing, polygonal surface remeshing, unknown surface probing, and volume meshing.
Document type :
Complete list of metadata

Cited literature [109 references]  Display  Hide  Download

Contributor : Steve Oudot Connect in order to contact the contributor
Submitted on : Thursday, November 13, 2008 - 1:42:19 AM
Last modification on : Friday, February 4, 2022 - 3:19:43 AM
Long-term archiving on: : Monday, June 7, 2010 - 10:54:54 PM


  • HAL Id : tel-00338378, version 1



Steve Y. Oudot. Sampling and Meshing Surfaces with Guarantees. Software Engineering [cs.SE]. Ecole Polytechnique X, 2005. English. ⟨tel-00338378⟩



Record views


Files downloads