Recent progress in robust and quality Delaunay mesh generation. (English) Zbl 1096.65016
Summary: Some current issues of Delaunay mesh generation and optimization are addressed, with particular emphasis on the robustness of the meshing procedure and the quality of the resulting mesh. We also report new progress on the robust conforming and constrained boundary recovery in three dimensions, along with the quality mesh generation based on centroidal Voronoi tessellations. Applications to the numerical solution of differential equations and integrations with other softwares are discussed, including a brief discussion on the joint mesh and solver adaptation strategy.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 65N50 | Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs |
Keywords:
mesh generation; Delaunay meshes; robustness and quality; mesh optimization; boundary recovery; centroidal Voronoi tessellations; graphical examplesSoftware:
LBIEReferences:
| [1] | Amenta, N.; Bern, M.; Eppstein, D., Optimal point placement for mesh smoothing, J. Algorithms, 30, 302-322 (1999) · Zbl 0919.65070 |
| [2] | D’Azevedo, E.; Simpson, B., On optimal triangular meshes for minimizing the gradient error, Numer. Math., 59, 321-348 (1991) · Zbl 0724.65006 |
| [3] | Baehmann, P.; Scott, L.; Wittchen, L.; Shephard, M.; Grice, K.; Yerry, M., Robust geometrically based, automatic two-dimensional mesh generation, Internat. J. Numer. Methods Engrg., 24, 1043-1078 (1987) · Zbl 0618.65116 |
| [4] | Bank, R., Mesh smoothing using a posteriori estimates, SIAM J. Numer. Anal., 34, 979-997 (1997) · Zbl 0873.65092 |
| [5] | Barnes, E.; Sloane, N., The optimal Lattice quantizer in three dimensions, SIAM J. Algebraic Discrete Methods, 4, 30-41 (1983) · Zbl 0509.52010 |
| [6] | Berzins, M., A solution-based triangular and tetrahedral mesh quality indicator, SIAM J. Sci. Comput., 19, 2051-2069 (1998) · Zbl 0914.65116 |
| [7] | Bowyer, A., Computing Dirichlet tessellations, Comput. J., 24, 162-166 (1981) |
| [8] | Borouchaki, H.; George, P., Aspects of 2-D Delaunay mesh generation, Internat. J. Numer. Methods Engrg., 40, 1957-1975 (1997) · Zbl 0884.65143 |
| [9] | Borouchaki, H.; George, P.; Hecht, F.; Laug, P.; Saltel, E., Delaunay mesh generation governed by metric specifications. Part I, Algorithms, 25, 61-83 (1997) · Zbl 0897.65076 |
| [10] | Borouchaki, H.; George, P.; Lo, S., Optimal Delaunay point insertion, Internat. J. Numer. Methods Engrg., 39, 3407-3437 (1996) · Zbl 0883.73086 |
| [11] | Borouchaki, H.; Lo, S., Fast Delaunay triangulation in three dimensions, Comput. J. Numer. Methods. Engrg., 128, 153-167 (1995) · Zbl 0859.65149 |
| [12] | Borouchaki, H.; Patrick, L.; George, P., Parametric surface meshing using a combined advancing-front generalized Delaunay approach, Internat. J. Numer. Methods Engrg., 49, 233-259 (2000) · Zbl 0981.65025 |
| [13] | Buscaglia, G.; Dari, E., Anisotropic mesh optimization and its application in adaptivity, Internat. J. Numer. Methods Engrg., 40, 4119-4136 (1997) · Zbl 0899.76264 |
| [14] | Chew, L., Guaranteed quality mesh generation for curved surfaces, (Proceedings of the Ninth Annual Computer Geometry (1993)), 274-280 |
| [15] | Ciarlet, P., Finite Element Methods (1975), North-Holland: North-Holland Amsterdam |
| [16] | Q. Du, M. Emelianenko, Uniform convergence of a nonlinear energy-based multilevel quantization scheme, preprint, 2005.; Q. Du, M. Emelianenko, Uniform convergence of a nonlinear energy-based multilevel quantization scheme, preprint, 2005. · Zbl 1171.65011 |
| [17] | Q. Du, M. Emelianenko, Acceleration schemes for computing centroidal Voronoi tessellations, preprint, 2005; Q. Du, M. Emelianenko, Acceleration schemes for computing centroidal Voronoi tessellations, preprint, 2005 · Zbl 1174.05323 |
| [18] | Q. Du, M. Emelianenko, L. Ju, Convergence properties of the Lloyd algorithm for computing the centroidal Voronoi tessellations, SIAM J. Numerical Analysis, 2005, accepted for publication.; Q. Du, M. Emelianenko, L. Ju, Convergence properties of the Lloyd algorithm for computing the centroidal Voronoi tessellations, SIAM J. Numerical Analysis, 2005, accepted for publication. · Zbl 1115.65017 |
| [19] | Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM Rev., 41, 637-676 (1999) · Zbl 0983.65021 |
| [20] | Du, Q.; Gunzburger, M., Grid generation and optimization based on centroidal Voronoi tessellations, Appl. Comput. Math., 133, 591-607 (2002) · Zbl 1024.65118 |
| [21] | Du, Q.; Gunzburger, M.; Ju, L., Probablistic methods for centroidal Voronoi tessellations and their parallel implementations, J. Parallel Comput., 28, 1477-1500 (2002) · Zbl 1014.68202 |
| [22] | Du, Q.; Gunzburger, M.; Ju, L., Meshfree, probabilistic determination of point sets and support regions for meshless computing, Comput. Methods Appl. Mech. Engrg., 191, 1349-1366 (2002) · Zbl 0993.65009 |
| [23] | Du, Q.; Gunzburger, M.; Ju, L., Constrained centroidal Voronoi tessellations on general surfaces, SIAM J. Sci. Comput., 24, 5, 1499-1506 (2003) · Zbl 1036.65101 |
| [24] | Q. Du, Z. Huang, D. Wang, Mesh and solver coadaptation in finite element methods for anisotropic problems, Numer. Methods for Differential Equations 21 (2005) 859-874.; Q. Du, Z. Huang, D. Wang, Mesh and solver coadaptation in finite element methods for anisotropic problems, Numer. Methods for Differential Equations 21 (2005) 859-874. · Zbl 1075.65137 |
| [25] | Q. Du, L. Ju, Finite volume methods and spherical centroidal Voronoi tessellations, SIAM J. Numer. Anal., accepted for publication.; Q. Du, L. Ju, Finite volume methods and spherical centroidal Voronoi tessellations, SIAM J. Numer. Anal., accepted for publication. · Zbl 1099.65107 |
| [26] | Du, Q.; Wang, D., Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations, Internat. J. Numer. Methods Engrg., 56, 1355-1373 (2003) · Zbl 1106.74431 |
| [27] | Du, Q.; Wang, D., Boundary recovery for three dimensional conforming Delaunay triangulation, Comput. Methods Appl. Mech. Engrg., 193, 2547-2563 (2004) · Zbl 1063.65135 |
| [28] | Du, Q.; Wang, D., Constrained boundary recovery for three dimensional Delaunay triangulation, Internat. J. Numer. Methods Engrg., 61, 1471-1500 (2004) · Zbl 1073.65511 |
| [29] | Q. Du, D. Wang, Mesh optimization based on centroidal Voronoi tessellation, Internat. J. Numer. Anal. Modelling, 2004, accepted for publication.; Q. Du, D. Wang, Mesh optimization based on centroidal Voronoi tessellation, Internat. J. Numer. Anal. Modelling, 2004, accepted for publication. |
| [30] | Q. Du, X. Wang, Centroidal Voronoi tessellation based algorithms for vector fields visualization and segmentation, IEEE Proceedings of Visualization 2004 (VIS2004), Austin, TX, 2004, pp. 43-50.; Q. Du, X. Wang, Centroidal Voronoi tessellation based algorithms for vector fields visualization and segmentation, IEEE Proceedings of Visualization 2004 (VIS2004), Austin, TX, 2004, pp. 43-50. |
| [31] | Q. Du, D. Wang, On the optimal centroidal Voronoi tessellations and the Gersho’s conjecture in the three dimensional space, Comput. Math. Appl. 49 (2005) 1355-1373.; Q. Du, D. Wang, On the optimal centroidal Voronoi tessellations and the Gersho’s conjecture in the three dimensional space, Comput. Math. Appl. 49 (2005) 1355-1373. · Zbl 1077.65019 |
| [32] | Du, Q.; Wang, D., Anisotropic centroidal Voronoi tessellations and their applications, SIAM J. Sci. Comput., 26, 737-761 (2005) · Zbl 1121.65306 |
| [33] | Edelsbrunner, H.; Guoy, D., Sink insertion for mesh improvement, Internat. J. Foundations Comput. Sci., 13, 223-242 (2002) · Zbl 1066.65137 |
| [34] | Frey, P.; Borouchaki, H., Geometric surface mesh optimization, Comput. Visualization Sci., 1, 113-121 (1998) · Zbl 0911.68202 |
| [35] | Frey, P.; Borouchaki, H.; George, P., 3D Delaunay mesh generation coupled with an advancing-front approach, Comput. Methods Appl. Mech. Engrg., 157, 115-131 (1998) · Zbl 0947.65130 |
| [36] | Frey, P.; Marechal, L., Fast adaptive quadtree mesh generation, (Proceedings of the Seventh International Meshing Roundtable (1998)), 211-222 |
| [37] | A. George, Computer implementation of the finite element method, Ph.D. thesis, Standford University, STAN-CS-71-208, 1971.; A. George, Computer implementation of the finite element method, Ph.D. thesis, Standford University, STAN-CS-71-208, 1971. |
| [38] | P. George, Gamanic3d, adaptive anisotropic tetrahedral mesh generator, Technical Report, INRIA, 2002.; P. George, Gamanic3d, adaptive anisotropic tetrahedral mesh generator, Technical Report, INRIA, 2002. |
| [39] | P. George, H. Borouchaki, Delaunay triangulation and meshing, Application to Finite Elements Methods, Hermès, Paris, 1998.; P. George, H. Borouchaki, Delaunay triangulation and meshing, Application to Finite Elements Methods, Hermès, Paris, 1998. · Zbl 0908.65143 |
| [40] | George, P.; Borouchaki, H.; Saltel, E., Ultimate robustness in meshing an arbitrary polyhedron, Internat. J. Numer. Methods Engrg., 58, 1061-1089 (2003) · Zbl 1035.65019 |
| [41] | George, P.; Hecht, F.; Saltel, E., Automatic mesh generation with specified boundary, Comput. Methods Appl. Mech. Engrg., 92, 169-188 (1991) · Zbl 0756.65133 |
| [42] | Gersho, A., Asymptotically optimal block quantization, IEEE Trans. Inform. Theory, 25, 373-380 (1979) · Zbl 0409.94013 |
| [43] | Hermeline, F., Triangulation automatique d’un polyèdre en dimension, N.R.A.I.R.O., 16, 211-242 (1982) · Zbl 0567.65083 |
| [44] | Hitschfeld, N.; Villablanca, L.; Krause, J.; Rivara, M. C., Improving the quality of meshes for the simulation of semiconductor devices using Lepp-based algorithms, Internat. J. Numer. Methods Engrg., 58, 333-347 (2003) · Zbl 1033.82003 |
| [45] | Hoppe, H.; DeRose, T.; Duchamp, T.; McDonald, J.; Stuetzle, W., Mesh optimization, ACM Comput. Graphics, 27, 19-26 (1993) |
| [46] | Karamete, B.; Beall, M.; Shephard, M., Triangulation of arbitrary polyhedra to support automatic mesh generators, Internat. J. Numer. Methods Engrg., 49, 167-191 (2000) · Zbl 0981.65024 |
| [47] | Knupp, P., Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities, I—a framework for surface mesh optimization, Internat. J. Numer. Methods Engrg., 48, 401-420 (2000) · Zbl 0964.65140 |
| [48] | F. Labelle, J. Shewchuk, Anisotropic Voronoi Diagrams and Guaranteed-Quality Anisotropic Mesh Generation, SoCG 2003, San Diego.; F. Labelle, J. Shewchuk, Anisotropic Voronoi Diagrams and Guaranteed-Quality Anisotropic Mesh Generation, SoCG 2003, San Diego. · Zbl 1375.68154 |
| [49] | Lee, C., Automatic metric advancing front triangulation over curved surfaces, Eng. Comput., 17, 48-74 (2000) · Zbl 0957.65011 |
| [50] | Leibon, G.; Letscher, D., Delaunay triangulations and Voronoi diagrams for Riemannian manifolds, (Proceedings of the 16th Annual Symposium on Computational Geometry (HK) (June 2000), ACM: ACM New York), 341-349 · Zbl 1375.68156 |
| [51] | X. Li, Sliver-free three dimensional Delaunay mesh generation, Ph.D thesis, UIUC, 2000.; X. Li, Sliver-free three dimensional Delaunay mesh generation, Ph.D thesis, UIUC, 2000. |
| [52] | Liu, A.; Baida, M., How far flipping can go towards 3D conforming/constrained triangulation, (Proceedings of the Ninth International Meshing Roundtable (2000)) |
| [53] | Lloyd, S., Least square quantization in PCM, IEEE Trans. Inform. Theory, 28, 129-137 (1982) · Zbl 0504.94015 |
| [54] | Lo, S., Volume discretization into tetrahedra-I, Verification and orientation of boundary surfaces, Comput. Structures, 36, 493-500 (1991) · Zbl 0764.65072 |
| [55] | Lo, S., Volume discretization into tetrahedra-II, 3D triangulation by advancing front approach, Comput. Structures, 36, 501-511 (1991) · Zbl 0764.65073 |
| [56] | Lohner, R., Progress in grid generation via the advancing front technique, Engrg. Comput., 12, 186-199 (1996) |
| [57] | Lohner, R.; Juan, C., Generation of non-isotropic unstructured grids via directional enrichment, Internat. J. Numer. Methods Engrg., 49, 1, 219-232 (2000) · Zbl 0970.76058 |
| [58] | Lohner, R.; Parikh, P., Generation of three-dimensional unstructured grids by the advancing-front method, Internat. J. Numer. Methods Engrg., 8, 1135-1149 (1988) · Zbl 0668.76035 |
| [59] | MacQueen, J., Some methods for classification and analysis of multivariate observations, (LeCam, L.; Neyman, J., Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, I (1967), University of California), 281-297 · Zbl 0214.46201 |
| [60] | Marcum, D.; Weatherill, N., Unstructured grid generation using iterative point insertion and local reconnection, AIAA J., 33, 9, 1625 (1995) · Zbl 0851.76041 |
| [61] | Mavriplis, D., Directional coarsening and smoothing for anisotropic Navier-Stokes problems, Electron. Trans. Numer. Anal., 6, 182-197 (1997) · Zbl 0901.76068 |
| [62] | K. Nakahashi, D. Sharov, Direct surface triangulation using the advancing front method, AIAA paper 95-1686-CP, 1995.; K. Nakahashi, D. Sharov, Direct surface triangulation using the advancing front method, AIAA paper 95-1686-CP, 1995. |
| [63] | Newman, D., The Hexagon theorem, IEEE Trans. Inform. Theory, 28, 137-139 (1982) · Zbl 0476.94006 |
| [64] | Peraire, J.; Peiro, J.; Formaggia, L.; Morgan, K.; Zienkiewicz, O., Finite element Euler computations in three dimensions, Internat. J. Numer. Methods Engrg., 26, 2135-2159 (1988) · Zbl 0665.76073 |
| [65] | Rassineux, A., Generation and optimization of tetrahedral meshes by advancing front technique, Internat. J. Numer. Methods Engrg., 41, 651-674 (1998) · Zbl 0905.65110 |
| [66] | Rippa, S., Long and thin triangles can be good for linear interpolation, SIAM J. Numer. Anal., 29, 257-270 (1992) · Zbl 0748.65011 |
| [67] | Schroeder, W.; Shephard, M., A combined octree/Delaunay method for fully automatic 3D mesh generation, Internat. J. Numer. Methods Engrg., 29, 37-55 (1990) · Zbl 0719.68086 |
| [68] | Shephard, M.; Georges, M., Automatic three-dimensional mesh generation by the finite Octree technique, Internat. J. Numer. Methods Engrg., 32, 709-749 (1991) · Zbl 0755.65116 |
| [69] | J. Shewchuk, What is a good linear finite element? Interpolation, conditioning, anisotropy and quality measures. CS report, UC Berlekey.; J. Shewchuk, What is a good linear finite element? Interpolation, conditioning, anisotropy and quality measures. CS report, UC Berlekey. |
| [70] | Shewchuk, J., Tetrahedral mesh generation by Delaunay refinement, (14th Annual ACM Symposium on Computational Geometry (1998)), 86-95 |
| [71] | Schewchuk, J., Constrained Delaunay tetrahedralization and provably good boundary recovery, (Proceedings of the11th International Meshing Roundtable (2002)), 193-204 |
| [72] | Tchon, K.; Mohammed, K.; Francois, G.; Ricardo, C., Constructing anisotropic geometric metrics using octrees and skeletons, (Proceedings of the 12th International Meshing Roundtable (2003)), 293-304 |
| [73] | Thompson, J.; Soni, B.; Weatherill, N., Handbook of Grid Generation (1999), CRC Press LLC: CRC Press LLC Boca Raton, FL · Zbl 0980.65500 |
| [74] | Watson, D., Computing the \(n\)-dimensional Delaunay tessellation with applications to Voronoi polytopes, Comput. J., 24, 167-172 (1981) |
| [75] | Weatherill, N., The integrity of geometrical boundaries in the two-dimensional Delaunay triangulation, Comput. Appl. Numer. Methods, 6, 101-109 (1990) · Zbl 0696.65083 |
| [76] | Weatherill, N.; Hassan, O., Efficient three dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints, Internat. J. Numer. Methods Engrg., 37, 2005-2039 (1994) · Zbl 0806.76073 |
| [77] | Wright, J.; Jack, A., Aspects of three-dimensional constrained Delaunay meshing, Internat. J. Numer. Methods Engrg., 37, 1841-1846 (1994) · Zbl 0806.65116 |
| [78] | Y. Zhang, C. Bajaj, B. Sohn, 3D Finite Element Meshing from Imaging Data, Comput. Methods Appl. Mech. Eng., 2005, in press.; Y. Zhang, C. Bajaj, B. Sohn, 3D Finite Element Meshing from Imaging Data, Comput. Methods Appl. Mech. Eng., 2005, in press. · Zbl 1093.65019 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
