Article

Delaunay refinement for piecewise smooth complexes

Authors:

Siu-Wing Cheng,

Edgar A. RamosAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 1096 - 1105

Published: 07 January 2007 Publication History

Abstract

We present a Delaunay refinement algorithm for meshing a piecewise smooth complex in three dimensions with correct topology. The small angles between the tangents of two meeting manifold patches pose difficulty. We protect these regions with weighted points. The weights are chosen to mimic the local feature size and to satisfy a Lipschitz-like property. A Delaunay refinement using the weighted Voronoi diagram is shown to terminate with the recovery of the topology of the input. To this end, we present new concepts and results including a new definition of local feature size and a proof for a generalized topological ball property.

References

[1]

N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discr. Comput. Geom., 22 (1999), 481--504.

[2]

J.-D. Boissonnat and S. Oudot. Provably good sampling and meshing of Lipschitz surfaces. Proc. 22nd Ann. Sympos. Comput. Geom., 2006, 337--346.

Digital Library

[3]

J.-D. Boissonnat and S. Oudot. Provably good surface sampling and meshing of surfaces. Graphical Models, 67 (2005), 405--451.

Digital Library

[4]

S.-W. Cheng and S.-H. Poon. Graded conforming tetra-hedralization with bounded radius-edge ratio. Proc. 14th Annu. ACM-SIAM Sympos. Discrete Algorithms, 2003, 295--304.

Digital Library

[5]

S.-W. Cheng, T. K. Dey, E. A. Ramos and T. Ray. Quality meshing for polyhedra with small angles. Internal. J. Comput. Geom. Appl, 15 (2005), 421--461.

[6]

S.-W. Cheng, T. K. Dey, E. A. Ramos and T. Ray. Sampling and meshing a surface with guaranteed topology and geometry. Proc. 20th Annu. Sympos. Comput. Geom., 2004, 280--289.

Digital Library

[7]

L. P. Chew. Guaranteed-quality triangular meshes. Report TR-98-983, Comput. Sci. Dept., Cornell Univ., Ithaca, New York, 1989.

[8]

L. P. Chew. Guaranteed-quality mesh generation for curved surfaces. Proc. 9th Annu. Sympos. Comput. Geom., 1993, 274--280.

Digital Library

[9]

D. Cohen-Steiner, E. C. de Verdière and M. Yvinec. Conforming Delaunay triangulations in 3D. Proc. Annu. Sympos. Comput. Geom., 2002, 199--208.

Digital Library

[10]

T. K. Dey, C. Bajaj and K. Sugihara. On good triangulations in three dimensions. Internat. J. Comput. Geom., 2 (1992), 75--95.

[11]

T. K. Dey, G. Li, and T. Ray. Polygonal surface remeshing with Delaunay refinement. Proc. 14th Internat. Meshing Roundtable, 2005, 343--361.

[12]

H. Edelsbrunner and N. Shah. Triangulating topological spaces. Internat. J. Comput. Geom. Appl., 7 (1997), 365--378.

[13]

S.-H. Lee and K. Lee. Partial entity structure: a compact non-manifold boundary representation based on partial topological entities. Proc. 6th ACM Sympos. Solid Modeling and Application, 2001, 159--170.

Digital Library

[14]

M. Murphy, D. M. Mount and C. W. Gable. A point placement strategy for conforming Delaunay tetrahedralization. Internat. J. Comput. Geom. Appl., 11 (2001), 669--682.

[15]

S. Pav and N. Walkington. Robust three dimensional Delaunay refinement. 13th Internat. Meshing Roundtable 2004.

[16]

A. A. G. Requicha and J. R. Rossignac. Solid modeling and beyond. Computer Graphics and Applications, 12 (1992), 31--44.

Digital Library

[17]

J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J. Algorithms, 18 (1995), 548--585.

Digital Library

[18]

J. R. Shewchuk. Tetrahedral mesh generation by Delaunay refinement. Proc. 14th Annu. Sympos. Comput. Geom. 1998, 86--95.

Digital Library

[19]

J. R. Shewchuk. Mesh generation for domains with small angles. Proc. 16th Annu. Sympos. Comput. Geom., 2000, 1--10.

Digital Library

Cited By

Faraj NThiery JBoubekeur T(2016)Multi-material adaptive volume remesherComputers and Graphics10.1016/j.cag.2016.05.01958:C(150-160)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.cag.2016.05.019
Jamin CAlliez PYvinec MBoissonnat J(2015)CGALmeshACM Transactions on Mathematical Software10.1145/269946341:4(1-24)Online publication date: 12-Oct-2015
https://dl.acm.org/doi/10.1145/2699463
Bhattacharya AWenger RScheuermann G(2013)Constructing isosurfaces with sharp edges and corners using cube mergingProceedings of the 15th Eurographics Conference on Visualization10.1111/cgf.12088(11-20)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1111/cgf.12088
Show More Cited By

Delaunay refinement for piecewise smooth complexes
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Delaunay Refinement for Piecewise Smooth Complexes

We present a Delaunay refinement algorithm for meshing a piecewise smooth complex in three dimensions. The algorithm protects edges with weighted points to avoid the difficulty posed by small angles between adjacent input elements. These weights are ...
Localized delaunay refinement for piecewise-smooth complexes
SoCG '13: Proceedings of the twenty-ninth annual symposium on Computational geometry

Delaunay refinement, a versatile method of mesh generation, is plagued by memory thrashing when required to generate large output meshes. To address this space issue, a localized version of Delaunay refinement was proposed for generating meshes for ...
Quality Meshing with Weighted Delaunay Refinement

Delaunay meshes with bounded circumradius to shortest edge length ratio have been proposed in the past for quality meshing. The only poor quality tetrahedra, called slivers, that can occur in such a mesh can be eliminated by the sliver exudation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
212
Total Downloads

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

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Faraj NThiery JBoubekeur T(2016)Multi-material adaptive volume remesherComputers and Graphics10.1016/j.cag.2016.05.01958:C(150-160)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.cag.2016.05.019
Jamin CAlliez PYvinec MBoissonnat J(2015)CGALmeshACM Transactions on Mathematical Software10.1145/269946341:4(1-24)Online publication date: 12-Oct-2015
https://dl.acm.org/doi/10.1145/2699463
Bhattacharya AWenger RScheuermann G(2013)Constructing isosurfaces with sharp edges and corners using cube mergingProceedings of the 15th Eurographics Conference on Visualization10.1111/cgf.12088(11-20)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1111/cgf.12088
Boltcheva DYvinec MBoissonnat JPolthier KAlexa MKazhdan M(2009)Feature preserving Delaunay mesh generation from 3D multi-material imagesProceedings of the Symposium on Geometry Processing10.5555/1735603.1735630(1455-1464)Online publication date: 15-Jul-2009
https://dl.acm.org/doi/10.5555/1735603.1735630
Yan DLévy BLiu YSun FWang WPolthier KAlexa MKazhdan M(2009)Isotropic remeshing with fast and exact computation of Restricted Voronoi DiagramProceedings of the Symposium on Geometry Processing10.5555/1735603.1735629(1445-1454)Online publication date: 15-Jul-2009
https://dl.acm.org/doi/10.5555/1735603.1735629
Hudson BMiller GPhillips TSheehy DMathieu C(2009)Size complexity of volume meshes vs. surface meshesProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496883(1041-1047)Online publication date: 4-Jan-2009
https://dl.acm.org/doi/10.5555/1496770.1496883
Busaryev ODey TLevine JBronsvoort WGonsor DRegli WGrandine TVandenbrande JGravesen JKeyser J(2009)Repairing and meshing imperfect shapes with Delaunay refinement2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling10.1145/1629255.1629259(25-33)Online publication date: 5-Oct-2009
https://dl.acm.org/doi/10.1145/1629255.1629259
Tournois JWormser CAlliez PDesbrun MFunkhouser T(2009)Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generationACM SIGGRAPH 2009 papers10.1145/1576246.1531381(1-9)Online publication date: 27-Jul-2009
https://dl.acm.org/doi/10.1145/1576246.1531381
Tournois JWormser CAlliez PDesbrun M(2009)Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generationACM Transactions on Graphics10.1145/1531326.153138128:3(1-9)Online publication date: 27-Jul-2009
https://dl.acm.org/doi/10.1145/1531326.1531381
Dey TLevine JTeillaud M(2008)DelpscProceedings of the twenty-fourth annual symposium on Computational geometry10.1145/1377676.1377712(220-221)Online publication date: 9-Jun-2008
https://dl.acm.org/doi/10.1145/1377676.1377712

View Options

Get Access

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

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents