Provably good sampling and meshing of Lipschitz surfaces

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 ensure a good reconstruction of a given surface S from a finite subset E of S. The sampling conditions proposed so far offer guarantees provided that E is sufficiently dense with respect to the local feature size of S, which can be true only if S is smooth since the local feature size vanishes at singular points.In this paper, we introduce a new measurable quantity, called the Lipschitz radius, which plays a role similar to that of the local feature size in the smooth setting, but which is 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 deviation is not too large around singular points.Our main result is that, if S is a Lipschitz surface and E is a sample of S such that any point of S is at distance 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 bounded Hausdorff distance from S, provided that its facets are not too skinny.We further extend this result to the case of loose samples. As an application, the Delaunay refinement algorithm we proved correct for smooth surfaces works as well and comes with similar guarantees when applied to Lipschitz surfaces.

REFERENCES

• 1: N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom., 22(4):481--504, 1999.
• 2: N. Amenta, S. Choi, T. K. Dey, and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. Internat. Journal of Comput. Geom. and Applications, 12:125--141, 2002.
• 3: M. Berger and B. Costiaux. Differential Geometry: Manifolds, Curves, and Surfaces, volume 115 of Graduate Texts in Mathematics Series. Springer, 1988. 474 pages.
• 4: Jean-Daniel Boissonnat , Leonidas J. Guibas , Steve Oudot, Learning smooth objects by probing, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064124]
• 5: Jean-Daniel Boissonnat , Steve Oudot, Provably good sampling and meshing of surfaces, Graphical Models, v.67 n.5, p.405-451, September 2005 [doi>10.1016/j.gmod.2005.01.004]
• 6: Frédéric Chazal , David Cohen-Steiner , André Lieutier, A sampling theory for compact sets in Euclidean space, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137904]
• 7: F. Chazal and A. Lieutier. Weak feature size and persistent homology: Computing homology of solids in Rn from noisy data samples. Technical Report 378, Institut de Mathématiques de Bourgogne, 2004. Partially published in {9}.
• 8: Frédéric Chazal , André Lieutier, The "λ-medial axis", Graphical Models, v.67 n.4, p.304-331, July 2005 [doi>10.1016/j.gmod.2005.01.002]
• 9: Frédéric Chazal , André Lieutier, Weak feature size and persistent homology: computing homology of solids in Rⁿ from noisy data samples, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064132]
• 10: L. Paul Chew, Guaranteed-quality mesh generation for curved surfaces, Proceedings of the ninth annual symposium on Computational geometry, p.274-280, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161150]
• 11: F. H. Clarke. Optimization and Nonsmooth Analysis. Classics in applied mathematics. SIAM, 1990.
• 12: David Cohen-Steiner , Herbert Edelsbrunner , John Harer, Stability of persistence diagrams, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064133]
• 13: T. K. Dey, G. Li, and T. Ray. Polygonal surface remeshing with {Delaunay refinement. In Proc. 14th Internat. Meshing Roundtable, 2005.
• 14: H. Federer. Geometric Measure Theory. Classics in Mathematics. Springer-Verlag, 1996. Reprint of the 1969 ed.
• 15: M. W. Hirsch. Differential Topology. Springer-Verlag, New York, NY, 1976.
• 16: A. Lieutier. Any open bounded subset of Rn has the same homotopy type as it medial axis. Computer-Aided Design, 36(11):1029--1046, September 2004.
• 17: J. Nečas. Les méthodes directes en théorie des équations elliptiques. Masson, 1967.
• 18: S. Oudot. Sampling and Meshing Surfaces with Guarantees. Thèse de doctorat en sciences, ècole Polytechnique, Palaiseau, France, 2005. Preprint available at ftp://ftp-sop.inria.fr/geometrica/soudot/preprints/thesis.pdf.
• 19: S. Oudot, L. Rineau, and M. Yvinec. Meshing volumes bounded by smooth surfaces. In Proc. 14th Internat. Meshing Roundtable, pages 203--219, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Theory

Keywords:
Lipschitz radius, Lipschitz surfaces, local feature size, sampling conditions, surface meshing