Article

Provably good surface sampling and approximation

Authors:

J. D. Boissonnat,

S. OudotAuthors Info & Claims

SGP '03: Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing

Pages 9 - 18

Published: 23 June 2003 Publication History

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 Del_\S of the points has the same topology type as S, that the Hausdorff distance between Del_\S and S can be made arbitrarily small, and that we can bound the aspect ratio of the facets of Del_\S. 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.

References

[1]

P. Agarwal and S. Suri. Surface approximation and geometric partitions. Proc. 5th Annu. ACM Sympos. Discrete Algorithms, 1994. pp 24--33.

Digital Library

[2]

P. Alliez, E. Colin de Verdière, O. Devillers and M. Isenburg. Isotropic Surface Remeshing. Solid Modelling and Applications, 2003.

[3]

N. Amenta and M. Bern. Surface Reconstruction by Voronoi Filtering. Proc. 14th Annu. ACM Sympos. Comput. Geom., 1998, pp 39--48.

Digital Library

[4]

D. Attali, J-D Boissonnat and A. Lieutier. Complexity of the Delaunay Triangulation of Points on Surfaces: the Smooth Case. Proc. 19th Annu. ACM Sympos. Comput. Geom., 2003.

Digital Library

[5]

J-D Boissonnat and F. Cazals. Natural Neighbour Coordinates of Points on a Surface. Comp. Geom. Theory and Appl., 155--174, 2001.

Digital Library

[6]

J-D Boissonnat and S. Oudot. Restricted Delaunay Triangulation and Point Samples. In preparation.

[7]

H-L Cheng, T. K. Dey, H. Edelsbrunner and J. M. Sullivan. Dynamic Skin triangulations. Proc. 12th Annu. ACM Sympos. Discrete Algorithms, 2001, pp 47--56.

Digital Library

[8]

E. V. Chernyaev. Marching Cubes 33: Construction of Topologically Correct Iso-surfaces. Technical report CERN CN 95--17, 1995.

[9]

L. P. Chew. Guaranteed-Quality Mesh Generation for Curved Surfaces. Proc. 9th Annu. ACM Sympos. Comput. Geom., 1993, pp 274--280.

Digital Library

[10]

M. Desbrun, N. Tsingos and M-P Gascuel. Adaptive Sampling of Implicit Surfaces for Interactive Modeling and Animation. Proc. Implicit Surfaces, pp 171--185, 1995.

[11]

O. Devillers. The Delaunay hierarchy. Internat. Journal Found. Comput. Sci., 2002, vol 283/1, pp 203--221.

[12]

G. Dos Reis, B. Mourrain, R. Rouillier and Ph. Trébuchet. An environment for Symbolic and Numeric Computation. Proc. Internat. Conf. on Mathematical Software, 2002, pp. 239--249.

[13]

H. Edelsbrunner, N.R. Shah. Triangulating topological spaces. International Journal of Computational Geometry and Applications, Vol. 7, No. 4 (1997), pp 365--378.

[14]

J. Erickson. Nice point sets can have nasty Delaunay Triangulations. Proc. 17th Annu. Sympos. Comput. Geom., pp 96--105, 2001.

Digital Library

[15]

I. Guskov, W. Sweldens and P. Schröder. Multiresolution Signal Processing for Meshes. Proc. SIGGRAPH, pp 325--334, 1999.

Digital Library

[16]

J. Hart and B. T. Stander. Guaranteeing the Topology of an Implicit Surface Polygonization for Interactive Modeling. Proc. SIGGRAPH, 1997.

Digital Library

[17]

H. Hoppe, T. DeRose, T. Duchamp, J. McDonald and W. Stuetzle. Mesh Optimization. Proc. SIGGRAPH, pp 19--26, 1993.

Digital Library

[18]

K. Hormann, U. Labsik and G. Greiner. Remeshing Triangulated Surfaces with Optimal Parameterizations. Computer-Aided Design 33, pp 779--788, 2001.

[19]

K. Hormann, U. Labsik, M. Meister and G. Greiner. Hierarchical Extraction of Iso-Surfaces with Semi-Regular Meshes. Solid Modelling and Applications, 2002.

Digital Library

[20]

W. E. Lorensen and H. E. Cline. Marching Cubes: a High-Resolution 3D Surface Construction Algorithm. Proc. SIGGRAPH, 1987.

Digital Library

[21]

S. A. Mitchell. Cardinality bounds for triangulations with bounded minimum angle. Proc. 6th Annu. Canadian Conference Comput. Geom., pp 326--331, 1994.

[22]

J-M Morvan and B. Thibert. On the Approximation of the Area of a Surface. INRIA RR-4375, 2002.

[23]

J. Ruppert. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation. Journal of Algorithms, May 1995.

Digital Library

[24]

J. R. Shewchuk. Delaunay Refinement Algorithms for Triangular Mesh Generation. Comput. Geom. Theory & Applications, 22 (1--3): 21--74, may 2002.

Digital Library

[25]

G. Turk. Generating Textures for Arbitrary Surfaces using Reaction-diffusion. Proc. SIGGRAPH, pp 289--298, 1991.

Digital Library

[26]

G. Turk. Re-tiling Polygonal Surfaces. Proc. SIGGRAPH, pp 55--64, 1992.

Digital Library

[27]

A. Witkin and P. Heckbert. Using Particles to Sample and Control Implicit Surfaces. Computer Graphics, pp 269--278, 1994.

Digital Library

Cited By

Shi XKoehl PWyvill BMagnenat-Thalmann NWyvill B(2009)Adaptive surface meshes coarsening with guaranteed quality and topologyProceedings of the 2009 Computer Graphics International Conference10.1145/1629739.1629746(53-61)Online publication date: 26-May-2009
https://dl.acm.org/doi/10.1145/1629739.1629746
Cheng HShi X(2009)Quality mesh generation for molecular skin surfaces using restricted union of ballsComputational Geometry: Theory and Applications10.1016/j.comgeo.2008.10.00142:3(196-206)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1016/j.comgeo.2008.10.001
Allègre RGalin EChaine RAkkouche S(2008)The HybridTreeHeterogeneous objects modelling and applications10.5555/1806158.1806161(60-89)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/1806158.1806161
Show More Cited By

Index Terms

Provably good surface sampling and approximation
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Point-based models

Recommendations

Provably good sampling and meshing of surfaces
Solid modeling theory and applications

The notion of ε-sample, 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 ε-sample of a C²-continuous surface S for a sufficiently small ε, then the ...
Curvature adaptive surface remeshing by sampling normal cycle
Abstract
Surface meshing plays a fundamental important role in Visualization and Computer Graphics, which produces discrete meshes to approximate a smooth surface. Many geometric processing tasks heavily depend on the qualities of the meshes, ...
Graphical abstract

Display Omitted
Highlights
- Theoretical foundation: discrete optimal mass transportation and surface Ricci flow.
Provably good sampling and meshing of Lipschitz surfaces
SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SGP '03: Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing

June 2003

277 pages

ISBN:1581136870

Conference Chairs:
Leif Kobbelt
Aachen University (RWTH)
,
Peter Schröder
Caltech
,
Hugues Hoppe
Microsoft Research

Sponsors

EUROGRAPHICS: The European Association for Computer Graphics

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 23 June 2003

Check for updates

Qualifiers

Article

Conference

SGP03

Sponsor:

EUROGRAPHICS

SGP03: Symposium on Geometry Processing

June 23 - 25, 2003

Aachen, Germany

Acceptance Rates

Overall Acceptance Rate 64 of 240 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
624
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shi XKoehl PWyvill BMagnenat-Thalmann NWyvill B(2009)Adaptive surface meshes coarsening with guaranteed quality and topologyProceedings of the 2009 Computer Graphics International Conference10.1145/1629739.1629746(53-61)Online publication date: 26-May-2009
https://dl.acm.org/doi/10.1145/1629739.1629746
Cheng HShi X(2009)Quality mesh generation for molecular skin surfaces using restricted union of ballsComputational Geometry: Theory and Applications10.1016/j.comgeo.2008.10.00142:3(196-206)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1016/j.comgeo.2008.10.001
Allègre RGalin EChaine RAkkouche S(2008)The HybridTreeHeterogeneous objects modelling and applications10.5555/1806158.1806161(60-89)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/1806158.1806161
Yaffe EHalperin DTeillaud M(2008)Approximating the pathway axis and the persistence diagram of a collection of balls in 3-spaceProceedings of the twenty-fourth annual symposium on Computational geometry10.1145/1377676.1377722(260-269)Online publication date: 9-Jun-2008
https://dl.acm.org/doi/10.1145/1377676.1377722
Fu YZhou BHaines EMcGuire M(2008)Direct sampling on surfaces for high quality remeshingProceedings of the 2008 ACM symposium on Solid and physical modeling10.1145/1364901.1364919(115-124)Online publication date: 2-Jun-2008
https://dl.acm.org/doi/10.1145/1364901.1364919
Kolluri R(2008)Provably good moving least squaresACM Transactions on Algorithms10.1145/1361192.13611954:2(1-25)Online publication date: 29-May-2008
https://dl.acm.org/doi/10.1145/1361192.1361195
Dyer RZhang HMöller TBelyaev AGarland M(2007)Delaunay mesh constructionProceedings of the fifth Eurographics symposium on Geometry processing10.5555/1281991.1282027(273-282)Online publication date: 4-Jul-2007
https://dl.acm.org/doi/10.5555/1281991.1282027
Saragaglia AFetita CPreteux F(2006)BronWallProceedings of the 10th WSEAS international conference on Communications10.5555/1981726.1981738(50-55)Online publication date: 13-Jul-2006
https://dl.acm.org/doi/10.5555/1981726.1981738
Cheng SDey TRamos EWenger R(2006)Anisotropic surface meshingProceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm10.5555/1109557.1109581(202-211)Online publication date: 22-Jan-2006
https://dl.acm.org/doi/10.5555/1109557.1109581
Mitra NGuibas LPauly MFinnegan JDorsey J(2006)Partial and approximate symmetry detection for 3D geometryACM SIGGRAPH 2006 Papers10.1145/1179352.1141924(560-568)Online publication date: 30-Jul-2006
https://dl.acm.org/doi/10.1145/1179352.1141924
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

Media

Figures

Other

Tables

View Table of Contents