
J.D. Boissonnat, S. Y. Oudot. Provably Good Sampling and
Meshing of Surfaces. Graphical Models, volume 67, issue 5, pages 405451, September 2005.
Abstract:
The notion of rsample, introduced by Amenta and Bern, has
proven to be a key concept in the theory of sampled surfaces. Of
particular interest is the fact that, if E is an
rsample of a C^2continuous surface S for a
sufficiently small r, then the Delaunay triangulation of
E restricted to S is a good approximation of S, both in a
topological and in a geometric sense. Hence, if one can construct an
rsample, one also gets a good approximation of the
surface. Moreover, correct reconstruction is ensured by various
algorithms.
In this paper, we introduce the notion of loose rsample. We show
that the set of loose rsamples contains and is asymptotically
identical to the set of rsamples. The main advantage of loose
rsamples over rsamples is that they are easier to check and to
construct. We also present a simple algorithm that constructs
provably good surface samples and meshes. Given a C^2continuous
surface S without boundary, the algorithm generates a sparse rsample
E and at the same time a triangulated surface Dels(E). The
triangulated surface has the same topological type as S, is close to S
for the Hausdorff distance, and can provide good approximations of
normals, areas and curvatures. A notable feature of the algorithm is
that the surface 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 surfaces.
Bibtex:
@article{bopgsms05,
author = {J.D. Boissonnat and S. Y. Oudot},
title = {Provably good sampling and meshing of surfaces},
journal = {Graphical Models},
volume = {67},
number = {5},
month = {September},
year = {2005}
}

