TetGen, a Delaunay-based quality tetrahedral mesh generator. (English) Zbl 1369.65157


65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65Y15 Packaged methods for numerical algorithms
Full Text: DOI


[1] P. Alliez, D. Cohen-Steiner, M. Yvinec, and M. Desbrun. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617–625. · Zbl 05457178
[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. · Zbl 1373.68423
[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. · Zbl 0884.65145
[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. · Zbl 1060.65555
[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. · Zbl 1380.68382
[9] H. Borouchaki, P. L. George, and S. H. Lo. 1996. Optimal Delaunay point insertion. Int. J. Numer. Methods Engrg. 39, 3407–3437. · Zbl 0883.73086
[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. · Zbl 1074.65509
[13] B. Chazelle. 1984. Convex partition of polyhedra: A lower bound and worst-case optimal algorithm. SIAM J. Comput. 13, 3, 488–507. · Zbl 0545.68031
[14] B. Chazelle and L. Palios. 1990. Triangulating a non-convex polytope. Disc. Computat. Geom. 5, 3, 505–526. · Zbl 0701.68038
[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. · Zbl 1048.65020
[17] S.-W. Cheng, T. K. Dey, H. Edelsbrunner, M. A. Facello, and S.-H. Teng. 2000. Sliver exudation. J. ACM 47, 883–904. · Zbl 1320.68210
[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. · Zbl 1136.65024
[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. · Zbl 1104.68115
[20] L. P. Chew. 1989a. Constrained Delaunay triangulation. Algorithmica 4, 97–108. · Zbl 0664.68042
[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. · Zbl 0681.68060
[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. · Zbl 1054.65018
[24] B. N. Delaunay. 1934. Sur la sphère vide. Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk 7, 793–800. · JFM 60.0946.06
[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. · Zbl 1066.68139
[27] D. P. Dobkin and M. J. Laszlo. 1989. Primitives for the manipulation of three-dimensional subdivisions. Algorithmica 4, 3–32. · Zbl 0664.68023
[28] Q. Du, V. Faber, and M. Gunzburger. 1999. Centroidal Voronoi tessellations: Applications and algorithms. SIAM Rev. 41, 4, 637–676. · Zbl 0983.65021
[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. · Zbl 1106.74431
[30] Q. Du and D. Wang. 2004. Constrained boundary recovery for the three dimensional Delaunay triangulations. Int. J. Numer. Methods Eng. 61, 1471–1500. · Zbl 1073.65511
[31] H. Edelsbrunner. 2001. Geometry and Topology for Mesh Generation. Cambridge University Press, Cambridge, UK. · Zbl 0981.65028
[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. · Zbl 0732.68099
[33] H. Edelsbrunner and N. R. Shah. 1996. Incremental topological flipping works for regular triangulations. Algorithmica 15, 223–241. · Zbl 0840.68050
[34] H. Edelsbrunner and N. R. Shah. 1997. Triangulating topological spaces. Int. J. Computat. Geom. Appl. 7, 4, 365–378. · Zbl 0887.57028
[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. · Zbl 05475108
[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. · Zbl 0897.65075
[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. · Zbl 0968.65009
[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. · Zbl 1017.65096
[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. · Zbl 1035.65019
[41] P. L. George, F. Hecht, and E. Saltel. 1991. Automatic mesh generator with specified boundary. Comput. Methods Appl. Mech. Eng. 92, 269–288. · Zbl 0756.65133
[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. · Zbl 0586.68059
[43] W. Huang. 2005. Measuring mesh qualities and application to variational mesh adaption. SIAM J. Sci. Comput. 26, 1643–1666. · Zbl 1076.65110
[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. · Zbl 1347.65047
[46] B. Joe. 1995. Construction of three-dimensional improved-quality triangulations using local transformations. SIAM J. Sci. Comput. 16, 6, 1292–1307. · Zbl 0851.65081
[47] B. M. Klinger and J. R. Shewchuk. 2007. Aggressive tetrahedral mesh improvement. In Proceedings of the 16th International Meshing Roundtable. Springer, 3–23. · Zbl 1238.65011
[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 forC1Surface 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. · Zbl 0596.52007
[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. · Zbl 0988.65014
[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. · Zbl 1097.68136
[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 andW1,pnorms. Numer. Math. 120, 271–305. · Zbl 1238.65116
[56] S. A. Mitchell and S. A. Vavasis. 2000. Quality mesh generation in higher dimensions. SIAM J. Comput. 29, 4, 1334–1370. · Zbl 0958.65126
[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. · Zbl 0953.65010
[59] A. Nanveski, G. Blelloch, and R. Harper. 2003. Automatic Generation of staged geometric predicates. High. Ord. Symb. Computat. 16, 4, 379–400. · Zbl 1059.68147
[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. · JFM 48.0834.04
[66] V. T. Rajan. 1994. Optimality of the Delaunay triangulation in ℝd. Disc. Computat. Geom. 12, 189–202. · Zbl 0808.52012
[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. · Zbl 0980.65144
[69] J. Ruppert. 1995. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J. Algor. 18, 3, 548–585. · Zbl 0828.68122
[70] J. Ruppert and R. Seidel. 1992. On the difficulty of triangulating three-dimensional nonconvex polyhedra. Disc. Computat. Geom. 7, 227–253. · Zbl 0747.52009
[71] J. Schöberl. 1997. NETGEN, An advancing front 2D/3D-mesh generator based on abstract rules. Comput. Visual. Sci. 1, 41–52. · Zbl 0883.68130
[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. · Zbl 1375.68168
[81] J. R. Shewchuk. 2008. General-dimensional constrained Delaunay and constrained regular triangulations, I: Combinatorial properties. Disc. Computat. Geom. 39, 580–637. · Zbl 1142.52010
[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. · Zbl 1397.68208
[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. · Zbl 1224.65285
[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. · Zbl 1217.65216
[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 then-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. · Zbl 0806.76073
[95] C.-K. Yap. 1997. Towards exact geometric computation. Comput. Geom. 7, 1, 3–23. · Zbl 0869.68104
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.