Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator

Published: 04 February 2015 Publication History

Abstract

TetGen is a C++ program for generating good quality tetrahedral meshes aimed to support numerical methods and scientific computing. The problem of quality tetrahedral mesh generation is challenged by many theoretical and practical issues. TetGen uses Delaunay-based algorithms which have theoretical guarantee of correctness. It can robustly handle arbitrary complex 3D geometries and is fast in practice. The source code of TetGen is freely available.
This article presents the essential algorithms and techniques used to develop TetGen. The intended audience are researchers or developers in mesh generation or other related areas. It describes the key software components of TetGen, including an efficient tetrahedral mesh data structure, a set of enhanced local mesh operations (combination of flips and edge removal), and filtered exact geometric predicates. The essential algorithms include incremental Delaunay algorithms for inserting vertices, constrained Delaunay algorithms for inserting constraints (edges and triangles), a new edge recovery algorithm for recovering constraints, and a new constrained Delaunay refinement algorithm for adaptive quality tetrahedral mesh generation. Experimental examples as well as comparisons with other softwares are presented.

References

[1]
P. Alliez, D. Cohen-Steiner, M. Yvinec, and M. Desbrun. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617--625.
[2]
N. Amenta, S. Choi, and G. Rote. 2003. Incremental construction con BRIO. In Proceedings of the 19th ACM Symposium on Computational Geometry. ACM, 211--219.
[3]
F. Aurenhammer. 1991. Voronoi diagrams -- A study of fundamental geometric data structures. ACM Comput. Surv. 23, 345--405.
[4]
T. J. Baker. 1989. Automatic mesh generation for complex three-dimensional regions using a constrained delaunay triangulation. Eng. Comput. 5, 161--175.
[5]
C. B. Barber, D. P. Dobkin, and H. T. Huhdanpaa. 1996. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 4, 469--483.
[6]
M. W. Bern and D. Eppstein. 1995. Mesh generation and optimal triangulations. In Computing in Euclidean Geometry (2nd Ed.), D.-Z. Du and F. K.-M. Hwang (Eds.), Number 4 in Lecture Notes Series on Computing. World Scientific, 47--123.
[7]
D. K. Blandford, G. E. Blelloch, D. E. Cardoze, and C. Kadow. 2005. Compact representations of simplical meshes in 2 and 3 dimensions. Internat. J. Comput. Geom. Appl. 15, 3--24.
[8]
J.-D. Boissonnat, O. Devillers, and S. Hornus. 2009. Incremental construction of the delaunay triangulation and the Delaunay graph in medium dimension. In Proceedings of the 25th Annual Symposium on Computational Geometry. ACM, 208--216.
[9]
H. Borouchaki, P. L. George, and S. H. Lo. 1996. Optimal Delaunay point insertion. Int. J. Numer. Methods Engrg. 39, 3407--3437.
[10]
A. Bowyer. 1987. Computing Dirichlet tessellations. Comput. J. 24, 2, 162--166.
[11]
H. Broennimann, C. Burnikel, and S. Pion. 1998. Interval arithmetic yields efficient dynamic filters for computational geometry. In Proceedings of the 14th Annual Symposium on Computational Geometry. ACM, 165--174.
[12]
C. Burnikel, S. Funke, and M. Seel. 2001. Exact geometric computations using cascading. Internat. J. Comput. Geom. Appl. 11, 245--266.
[13]
B. Chazelle. 1984. Convex partition of polyhedra: A lower bound and worst-case optimal algorithm. SIAM J. Comput. 13, 3, 488--507.
[14]
B. Chazelle and L. Palios. 1990. Triangulating a non-convex polytope. Disc. Computat. Geom. 5, 3, 505--526.
[15]
J. Chen, D. Zhao, Z. Huang, Y. Zheng, and S. Gao. 2011. Three-dimensional constrained boundary recovery with an enhanced steiner point suppression procedure. Comput. Struct. 89, 5--6, 455--466.
[16]
L. Chen and J.-C. Xu. 2004. Optimal Delaunay triangulations. J. Comput. Math. 22, 2, 299--308.
[17]
S.-W. Cheng, T. K. Dey, H. Edelsbrunner, M. A. Facello, and S.-H. Teng. 2000. Sliver exudation. J. ACM 47, 883--904.
[18]
S.-W. Cheng, T. K. Dey, and J. A. Levine. 2007. A practical Delaunay meshing algorithm for a large class of domains. In Proceedings of the 16th International Meshing Roundtable. Sandia National Laboratories. Springer, 477--494.
[19]
S.-W. Cheng, T. K. Dey, E. A. Ramos, and T. Ray. 2005. Quality meshing for polyhedra with small angles. Int. J. Comput. Geom. Appl. 15, 421--461.
[20]
L. P. Chew. 1989a. Constrained Delaunay triangulation. Algorithmica 4, 97--108.
[21]
L. P. Chew. 1989b. Guaranteed-quality triangular meshes. Tech. Rep. TR 89-983. Department of Computer Science, Cornell University.
[22]
K. L. Clarkson and P. W. Shor. 1989. Applications of random sampling in computational geometry, II. Disc. Computat. Geom. 4, 387--421.
[23]
D. Cohen-Steiner, É. C. de Verdière, and M. Yvinec. 2004. Conforming Delaunay triangulations in 3D. Comput. Geom. Theory Appl. 28, 2--3, 217--233.
[24]
B. N. Delaunay. 1934. Sur la sphère vide. Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk 7, 793--800.
[25]
O. Devillers and S. Pion. 2003. Efficient exact geometric predicates for Delaunay triangulations. In Proceedings of the 5th Workshop on Algorithm Engineering and Experiments. SIAM, 37--44.
[26]
O. Devillers, S. Pion, and M. Teillaud. 2002. Walking in triangulation. Int. J. Found. Comput. Sci. 13, 2, 181--199.
[27]
D. P. Dobkin and M. J. Laszlo. 1989. Primitives for the manipulation of three-dimensional subdivisions. Algorithmica 4, 3--32.
[28]
Q. Du, V. Faber, and M. Gunzburger. 1999. Centroidal Voronoi tessellations: Applications and algorithms. SIAM Rev. 41, 4, 637--676.
[29]
Q. Du and D. Wang. 2003. Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations. Int. J. Numer. Meth. Eng. 56, 1355--1373.
[30]
Q. Du and D. Wang. 2004. Constrained boundary recovery for the three dimensional Delaunay triangulations. Int. J. Numer. Methods Eng. 61, 1471--1500.
[31]
H. Edelsbrunner. 2001. Geometry and Topology for Mesh Generation. Cambridge University Press, Cambridge, UK.
[32]
H. Edelsbrunner and E. P. Mücke. 1990. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithm. ACM Trans. Graph. 9, 1, 66--104.
[33]
H. Edelsbrunner and N. R. Shah. 1996. Incremental topological flipping works for regular triangulations. Algorithmica 15, 223--241.
[34]
H. Edelsbrunner and N. R. Shah. 1997. Triangulating topological spaces. Int. J. Computat. Geom. Appl. 7, 4, 365--378.
[35]
S. Fortune and C. J. Van Wyk. 1996. Static analysis yield efficient exact integer arithmetic for computational geometry. ACM Trans. Graph. 15, 3, 223--248.
[36]
L. A. Freitag and C. Ollivier-Gooch. 1997. Tetrahedral mesh improvement using swapping and smoothing. Int. J. Numer. Methods Eng. 40, 21, 3979--4002.
[37]
P. J. Frey and P. L. George. 2000. Mesh Generation - Application to Finite Elements (1st Ed.). Hermes Science Publishing, Oxford, UK, 814 pages. ISBN 1-903398-00-2.
[38]
R. V. Garimella. 2002. Mesh data structure selection for mesh generation and FEA applications. Int. J. Numer. Methods Eng. 55, 4 (Oct. 2002), 451--478.
[39]
P. L. George and H. Borouchaki. 2003. Back to edge flips in 3 dimensions. In Proceedings of the 12th International Meshing Roundtable. Sandia National Laboratories, 393--402.
[40]
P. L. George, H. Borouchaki, and E. Saltel. 2003. Ultimate robustness in meshing an arbitrary polyhedron. Int. J. Numer. Methods Eng. 58, 1061--1089.
[41]
P. L. George, F. Hecht, and E. Saltel. 1991. Automatic mesh generator with specified boundary. Comput. Methods Appl. Mech. Eng. 92, 269--288.
[42]
L. Guibas and J. Stolfi. 1985. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph. 4, 4, 75--123.
[43]
W. Huang. 2005. Measuring mesh qualities and application to variational mesh adaption. SIAM J. Sci. Comput. 26, 1643--1666.
[44]
B. Hudson. 2007. Dynamic mesh refinement. Ph.D. dissertation, CMU-CS-07-162. School of Computer Science, Carnegie Mellon University, Pittsburgh, PA.
[45]
C. Jamin, P. Alliez, M. Yvinec, and J.-D. Boissonnat. 2013. CGALmesh: A generic framework for Delaunay mesh generation. Tech. Rep. 8256. INRIA.
[46]
B. Joe. 1995. Construction of three-dimensional improved-quality triangulations using local transformations. SIAM J. Sci. Comput. 16, 6, 1292--1307.
[47]
B. M. Klinger and J. R. Shewchuk. 2007. Aggressive tetrahedral mesh improvement. In Proceedings of the 16th International Meshing Roundtable. Springer, 3--23.
[48]
M. Kremer, D. Bommes, and L. Kobbelt. 2012. OpenVolumeMesh - A versatile index-based data structure for 3D polytopal complexes. In Proceedings of the 21st International Meshing Roundtable. Springer, 531--548.
[49]
C. L. Lawson. 1977. Software for C1 Surface Interpolation. In Mathematical Software III, Academic Press, New York, 164--191.
[50]
D. T. Lee and A. K. Lin. 1986. Generalized Delaunay triangulations for planar graphs. Disc. Computat. Geom. 1, 201--217.
[51]
X.-Y. Li and S.-H. Teng. 2001. Generating well-shaped Delaunay meshes in 3D. In Proceedings of the 12th Annual Symposium on Discrete Algorithms. SIAM, 28--37.
[52]
A. Liu and M. Baida. 2000. How far flipping can go towards 3D conforming/constrained triangulation. In Proceedings of the 9th International Meshing Roundtable. Sandia National Laboratories, 307--315.
[53]
Y. Liu and J. Snoeyink. 2005. A comparsion of five implementations of 3D Delaunay tessellation. In Combinatorial and Computational Geometry, vol. 52, J. E. Goodman, J. Pach, and E. Welzl (Eds.), MSRI Publications, New York, 439--458.
[54]
G. L. Miller, D. Talmor, S.-H. Teng, N. Walkington, and H. Wang. 1996. Control volume meshes using sphere packing: Generation, refinement and coarsening. In Proceedings of the 5th International Meshing Roundtable. Sandia National Laboratories, 47--61.
[55]
J.-M. Mirebeau. 2012. Optimally adapted meshes for finite elements of arbitrary order and W1,p norms. Numer. Math. 120, 271--305.
[56]
S. A. Mitchell and S. A. Vavasis. 2000. Quality mesh generation in higher dimensions. SIAM J. Comput. 29, 4, 1334--1370.
[57]
E. P. Mücke. 1993. Shapes and implementations in three-dimensions geometry. Ph.D. Dissertation, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois.
[58]
M. Murphy, D. M. Mount, and C. W. Gable. 2000. A point-placement strategy for conforming Delaunay tetrahedralizations. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. Sandia National Laboratories, 69--93.
[59]
A. Nanveski, G. Blelloch, and R. Harper. 2003. Automatic Generation of staged geometric predicates. High. Ord. Symb. Computat. 16, 4, 379--400.
[60]
C. Ollivier-Gooch. 2005. GRUMMP -- Generation and Refinement of Unstructed, Mixed-Element Meshes in Parallel. http://tetra.mech.ubc.ca/GRUMMP/. (2005). (Last accessed November 2009.)
[61]
S. Oudot, L. Rineau, and M. Yvinec. 2005. Meshing volumes bounded by smooth surfaces. In Proceedings of the 14th International Meshing Roundtable. Sandia National Laboratories, Springer, 203--220.
[62]
S. J. Owen. 1998. A survey of unstructed mesh generation technology. In Proceedings of the 7th International Meshing Roundtable. Sandia National Laboratories, 239--267.
[63]
S. E. Pav and N. Walkington. 2004. Robust three dimensional Delaunay refinement. In Proceedings of the 13th International Meshing Roundtable. Springer, 145--156.
[64]
D. M. Priest. 1991. Algorithms for arbitrary precision floating point arithmetic. In Proceedings of the 10th Symposium on Computer Arithmetic. IEEE, 132--143.
[65]
J. Radon. 1921. Mengen Konvexer Körper, die Einen Gemeinschaftlichen Punkt Enthalten. Math. Ann. 83, 113--115.
[66]
V. T. Rajan. 1994. Optimality of the Delaunay triangulation in ℝd. Disc. Computat. Geom. 12, 189--202.
[67]
A. Rand and N. Walkington. 2009. Collars and intestines: Practical conforming Delaunay refinement. In Proceedings of the 18th International Meshing Roundtable. Springer, 481--497.
[68]
M.-C. Rivara. 1997. New longest-edge algorithms for the refinement and/or improvement of unstructured triangulations. Int. J. Numer. Methods Eng. 40, 3313--3324.
[69]
J. Ruppert. 1995. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J. Algor. 18, 3, 548--585.
[70]
J. Ruppert and R. Seidel. 1992. On the difficulty of triangulating three-dimensional nonconvex polyhedra. Disc. Computat. Geom. 7, 227--253.
[71]
J. Schöberl. 1997. NETGEN, An advancing front 2D/3D-mesh generator based on abstract rules. Comput. Visual. Sci. 1, 41--52.
[72]
E. Schönhardt. 1928. Über die Zerlegung von Dreieckspolyedern in Tetraeder. Math. Ann. 98, 309--312.
[73]
J. R. Shewchuk. 1996a. Robust adaptive floating-point geometric predicates. In Proceedings of the 12th Annual Symposium on Computational Geometry. ACM, 141--150.
[74]
J. R. Shewchuk. 1996b. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering, M. C. Lin and D. Manocha (Eds.). Lecture Notes in Computer Science, vol. 1148, Springer, Berlin Heidelberg, 203--222. http://www.cs.cmu.edu/~quake/triangle.html.
[75]
J. R. Shewchuk. 1998a. A condition guaranteeing the existence of higher-dimensional constrained Delaunay triangulations. In Proceedings of the 14th Annual Symposium on Computational Geometry. ACM, 76--85.
[76]
J. R. Shewchuk. 1998b. Tetrahedral mesh generation by Delaunay refinement. In Proceedings of the 14th Annual Symposium on Computational Geometry. ACM, 86--95.
[77]
J. R. Shewchuk. 2002a. Constrained Delaunay tetrahedralizations and provably good boundary recovery. In Proceedings of the 11th International Meshing Roundtable. Springer, 193--204.
[78]
J. R. Shewchuk. 2002b. Two discrete optimization algorithms for the topological improvement of tetrahedral meshes. www.cs.berkeley.edu/~jrs/papers/edge.pdf.
[79]
J. R. Shewchuk. 2002c. What is a good linear element? Interpolation, Conditioning, and quality measures. In Proceedings of 11th International Meshing Roundtable. Springer, 115--126.
[80]
J. R. Shewchuk. 2003. Updating and constructing constrained Delaunay and constrained regular triangulations by flips. In Proceedings of the 19th Annual Symposium on Computational Geometry. ACM, 86--95.
[81]
J. R. Shewchuk. 2008. General-dimensional constrained Delaunay and constrained regular triangulations, I: Combinatorial properties. Disc. Computat. Geom. 39, 580--637.
[82]
J. R. Shewchuk and H. Si. 2014. Higher-quality tetrahedral mesh generation for domains with small angles by constrained Delaunay refinement. In Proceedings of the 30th Annual Symposium on Computational Geometry. ACM.
[83]
H. Si. 2008. Three dimensional boundary conforming Delaunay mesh generation. Ph.D. Dissertation, Institut für Mathematik, Technische Universität Berlin, Strasse des 17. Juni 136, D-10623, Berlin, Germany. http://opus.kobv.de/tuberlin/volltexte/2008/1966/.
[84]
H. Si. 2009. An analysis of Shewchuk's Delaunay refinement algorithm. In Proceedings of the 18th International Meshing Roundtable. Springer, UT, 499--517.
[85]
H. Si. 2010. Constrained Delaunay tetrahedral mesh generation and refinement. Finite Elem. Anal. Des. 46, 1, 33--46.
[86]
H. Si. 2013. TetGen, A quality tetrahedral mesh generator and a 3D Delaunay triangulator, version 1.5, user's manual. Tech. Rep. 13. Weierstrass Institute for Applied Analysis and Stochastics (WIAS).
[87]
H. Si, J. Fuhrmann, and K. Gärtner. 2010. Boundary conforming Delaunay mesh generation. Comput. Math. Math. Phys. 50, 1, 38--53.
[88]
H. Si and K. Gärtner. 2005. Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations. In Proceedings of the 14th International Meshing Roundtable. Springer, CA, 147--163.
[89]
H. Si and K. Gärtner. 2011. 3D Boundary recovery by constrained Delaunay tetrahedralization. Int. J. Numer. Methods Eng. 85, 1341--1364.
[90]
H. Si and J. R. Shewchuk. 2014. Incrementally constructing and updating constrained Delaunay tetrahedralizations with finite-precision coordinates. Eng. Comput. 30, 2, 253--269.
[91]
TetMesh-GHS3D. 2010. A powerful isotropic tet-mesher, Version 4.2. http://www-roc.inria.fr/gamma/gamma/ghs3d/ghs.php.
[92]
J. F. Thompson, B. K. Soni, and N. P. Weatherill (Eds.). 1999. Handbook of Grid Generation. CRC Press, Boca Raton, FL.
[93]
D. F. Watson. 1987. Computing the n-dimensional Delaunay tessellations with application to Voronoi polytopes. Comput. J. 24, 2, 167--172.
[94]
N. P. Weatherill and O. Hassan. 1994. Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints. Internat. J. Numer. Methods Eng. 37, 2005--2039.
[95]
C.-K. Yap. 1997. Towards exact geometric computation. Comput. Geom. 7, 1, 3--23.

Cited By

View all
  • (2024)Perspectives on Optimized Transcranial Electrical Stimulation Based on Spatial Electric Field Modeling in HumansJournal of Clinical Medicine10.3390/jcm1311308413:11(3084)Online publication date: 24-May-2024
  • (2024)Meshfree modelling of magnetotelluric and controlled-source electromagnetic data for conductive earth models with complex geometriesFrontiers in Earth Science10.3389/feart.2024.143299212Online publication date: 11-Jul-2024
  • (2024)Efficient Polyhedral Gravity Modeling in Modern C++ and PythonJournal of Open Source Software10.21105/joss.063849:98(6384)Online publication date: Jun-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software
ACM Transactions on Mathematical Software  Volume 41, Issue 2
January 2015
173 pages
ISSN:0098-3500
EISSN:1557-7295
DOI:10.1145/2732672
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 February 2015
Accepted: 01 May 2014
Revised: 01 December 2013
Received: 01 March 2013
Published in TOMS Volume 41, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Delaunay
  2. Steiner points
  3. Tetrahedral mesh generation
  4. boundary recovery
  5. constrained Delaunay
  6. edge removal
  7. flips
  8. mesh improvement
  9. mesh quality
  10. mesh refinement

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

  • Weierstrass Institute for Applied Analysis and Stochastics (WIAS), Leibniz Institute in Forschungsverbund Berlin e.V

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)430
  • Downloads (Last 6 weeks)46
Reflects downloads up to 29 Sep 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Perspectives on Optimized Transcranial Electrical Stimulation Based on Spatial Electric Field Modeling in HumansJournal of Clinical Medicine10.3390/jcm1311308413:11(3084)Online publication date: 24-May-2024
  • (2024)Meshfree modelling of magnetotelluric and controlled-source electromagnetic data for conductive earth models with complex geometriesFrontiers in Earth Science10.3389/feart.2024.143299212Online publication date: 11-Jul-2024
  • (2024)Efficient Polyhedral Gravity Modeling in Modern C++ and PythonJournal of Open Source Software10.21105/joss.063849:98(6384)Online publication date: Jun-2024
  • (2024)Can lateral tenodesis improve the rotational stability of the ACL reconstruction? A finite element analysisPLOS ONE10.1371/journal.pone.029316119:2(e0293161)Online publication date: 27-Feb-2024
  • (2024)Effects of base frequency, duty cycle, and waveform repetition on TEM responses: Insights from models of a deep-buried conductorGEOPHYSICS10.1190/geo2023-0671.1(1-53)Online publication date: 10-Apr-2024
  • (2024)Surface geometry inversion of transient electromagnetic dataGEOPHYSICS10.1190/geo2023-0566.189:4(E177-E192)Online publication date: 13-Jun-2024
  • (2024)Large-scale 3D inversion of semi-airborne electromagnetic data — Topography and induced polarization effects in a graphite exploration scenarioGEOPHYSICS10.1190/geo2023-0471.189:5(B339-B352)Online publication date: 5-Aug-2024
  • (2024)Response characteristics and detectability of pegmatitic rare-metal deposits using different grounded-wire configurationsGEOPHYSICS10.1190/geo2023-0445.189:5(E193-E203)Online publication date: 20-Jun-2024
  • (2024)Numerical simulation of high-frequency induction welding in longitudinal welded tubesJournal of Mathematics in Industry10.1186/s13362-024-00147-814:1Online publication date: 11-Jul-2024
  • (2024)Walkin’ Robin: Walk on Stars with Robin Boundary ConditionsACM Transactions on Graphics10.1145/365815343:4(1-18)Online publication date: 19-Jul-2024
  • Show More Cited By

View Options

Get Access

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media