|
J.-D. Boissonnat, S. Y. Oudot. Provably Good Surface Sampling
and Approximation. Proc. 1st Symposium on Geometry Processing,
pp. 9-18, 2003.
Abstract:
We present an algorithm for meshing surfaces that is a simple
adaptation of a greedy "farthest point" technique proposed by
Chew. Given a surface S, it progressively adds points on S and updates
the 3-dimensional Delaunay triangulation of the points. The method is
very simple and works in 3d-space without requiring to parameterize
the surface. Taking advantage of recent results on the restricted
Delaunay triangulation, we prove that the algorithm can generate good
samples on S as well as triangulated surfaces that approximate S. More
precisely, we show that the restricted Delaunay triangulation Dels of
the points has the same topology type as S, that the Hausdorff
distance between Dels and S can be made arbitrarily small, and that
we can bound the aspect ratio of the facets of Dels. The algorithm
has been implemented and we report on experimental results that
provide evidence that it is very effective in practice. We present
results on implicit surfaces, on CSG models and on polyhedra. Although
most of our theoretical results are given for smooth closed surfaces,
the method is quite robust in handling smooth surfaces with
boundaries, and even non-smooth surfaces.
Bibtex:
@inproceedings{bo-pgssa-03,
author = {J. D. Boissonnat and S. Y. Oudot},
title = {Provably Good Surface Sampling and Approximation},
booktitle = {Proc. 1st Symposium on Geometry Processing},
year = {2003},
pages = {9--18}
}
|
 |