×

zbMATH — the first resource for mathematics

Improved boundary constrained tetrahedral mesh generation by shell transformation. (English) Zbl 07166289
Summary: An excessive number of Steiner points may be inserted during the process of boundary recovery for constrained tetrahedral mesh generation, and these Steiner points are harmful in some circumstances. In this study, a new flip named shell transformation is proposed to reduce the usage of Steiner points in boundary recovery and thus to improve the performance of boundary recovery in terms of robustness, efficiency and element quality. Shell transformation searches for a local optimal mesh among multiple choices. Meanwhile, its recursive callings can perform flips on a much larger element set than a single flip, thereby leading the way to a better local optimum solution. By employing shell transformation properly, a mesh that intersects predefined constraints intensively can be transformed to another one with much fewer intersections, thus remarkably reducing the occasions of Steiner point insertion. Besides, shell transformation can be used to remove existing Steiner points by flipping the mesh aggressively. Meshing examples for various industrial applications and surface inputs mainly composed of stretched triangles are presented to illustrate how the improved algorithm works on difficult boundary constrained meshing tasks.

MSC:
65 Numerical analysis
74 Mechanics of deformable solids
Software:
HEDP; TetGen
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ruppert, J.; Seidel, R., On the difficulty of triangulating three-dimensional non-convex polyhedra, Discret. Comput. Geom., 7, 227-254 (1992) · Zbl 0747.52009
[2] Schönhardt, E., Über die zerlegung von dreieckspolyedern in tetraeder, Math. Ann., 98, 309-312 (1928) · JFM 53.0576.01
[3] Chazelle, B., Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM J. Sci. Comput., 13, 488-507 (1984) · Zbl 0545.68031
[4] Weatherill, NP; Hassan, O., Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints, Int. J. Numer. Methods Eng., 37, 2005-2039 (1994) · Zbl 0806.76073
[5] George, PL; Borouchaki, H.; Saltel, E., ’Ultimate’ robustness in meshing an arbitrary polyhedron, Int. J. Numer. Methods Eng., 58, 1061-1089 (2003) · Zbl 1035.65019
[6] Du, Q.; Wang, D., Constrained boundary recovery for three dimensional Delaunay triangulations, Int. J. Numer. Methods Eng., 61, 1471-1500 (2004) · Zbl 1073.65511
[7] George, PL; Hecht, F.; Saltel, E., Automatic mesh generator with specified boundary, Comput. Methods Appl. Mech. Eng., 92, 269-288 (1991) · Zbl 0756.65133
[8] Joe, B., Three-dimensional boundary-constrained triangulations, (Proceedings of the 13th IMACS World Congress on Computation and Applied Mathematics. Proceedings of the 13th IMACS World Congress on Computation and Applied Mathematics, Trinity College, Du blin, Ireland (1991)), 215-222
[9] Lewis, RW; Zheng, Y.; Gethin, DT, Three-dimensional unstructured mesh generation: part 3. volume meshes, Comput. Methods Appl. Mech. Eng., 134, 285-310 (1996) · Zbl 0882.65111
[10] Liu, A.; Baida, M., How far flipping can go towards 3D conforming/constrained triangulation, (Proceedings of the 9th International Meshing Roundtable. Proceedings of the 9th International Meshing Roundtable, New Orleans, LA, USA (2000)), 307-315
[11] Du, Q.; Wang, D., Boundary recovery for three dimensional conforming Delaunay triangulation, Comput. Methods Appl. Mech. Eng., 193, 2547-2563 (2004) · Zbl 1063.65135
[12] Guan, Z.; Song, C.; Gu, Y., The boundary recovery and sliver elimination algorithms of three-dimensional constrained Delaunay triangulation, Int. J. Numer. Methods Eng., 68, 192-209 (2006) · Zbl 1131.65019
[13] Chen, J.; Zheng, Y., Redesign of a conformal boundary recovery algorithm for 3D Delaunay triangulation, J. Zhejiang Univ. SCIENCE A, 7, 2031-2042 (2006) · Zbl 1121.65019
[14] Liu, J.; Chen, B.; Chen, Y., Boundary recovery after 3D Delaunay tetrahedralization without adding extra nodes, Int. J. Numer. Methods Eng., 72, 744-756 (2007) · Zbl 1194.74556
[15] Chen, J.; Zhao, D.; Huang, Z.; Zheng, Y.; Gao, S., Three-dimensional constrained boundary recovery with an enhanced Steiner point suppression procedure, Comput. Struct., 89, 455-466 (2011)
[16] Shewchuk, JR., Constrained Delaunay tetrahedralizations and provably good boundary recovery, (Proceedings of the 11th International Meshing Roundtable. Proceedings of the 11th International Meshing Roundtable, Ithaca, NY, USA (2002)), 193-204
[17] Si, H.; Gärtner, K., 3D boundary recovery by constrained Delaunay tetrahedralization, Int. J. Numer. Methods Eng., 85, 1341-1364 (2011) · Zbl 1217.65216
[18] Liu, Y.; Lo, SH; Guan, Z.; Zhang, H., Boundary recovery for 3D Delaunay triangulation, Finite Elem. Anal. Des., 84, 32-43 (2014)
[19] Si, H., TetGen, a Delaunay-based quality tetrahedral mesh generator, ACM Trans. Math. Softw., 41, 11:1-11:36 (2015) · Zbl 1369.65157
[20] Shewchuk, JR., Robust adaptive floating-point geometric predicates, (Proceedings of the 12th Annual Symposium on Computational Geometry. Proceedings of the 12th Annual Symposium on Computational Geometry, Philadelphia, PA , USA (1996)), 141-150
[21] Freitag, LA; Ollivier-Gooch, C., Tetrahedral mesh improvement using swapping and smoothing, Int. J. Numer. Methods Eng., 40, 3979-4002 (1997) · Zbl 0897.65075
[22] Said, R.; Weatherill, NP; Morgan, K.; Verhoeven, NA, Distributed parallel Delaunay mesh generation, Comput. Methods Appl. Mech. Eng., 177, 109-125 (1999) · Zbl 0997.65137
[23] Larwood, BG; Weatherill, NP; Hassan, O.; Morgan, K., Domain decomposition approach for parallel unstructured mesh generation, Int. J. Numer. Methods Eng., 58, 177-188 (2003) · Zbl 1032.76667
[24] Chen, J.; Zhao, D.; Huang, Z.; Zheng, Y.; Wang, D., Improvements in the reliability and element quality of parallel tetrahedral mesh generation, Int. J. Numer. Methods Eng., 92, 671-693 (2012) · Zbl 1352.65605
[25] Hassan, O.; Probert, EJ; Morgan, K.; Peraire, J., Mesh generation and adaptivity for the solution of compressible viscous high speed flows, Int. J. Numer. Methods Eng., 38, 1123-1148 (1995) · Zbl 0822.76053
[26] Hassan, O.; Morgan, K.; Probert, EJ; Peraire, J., Unstructured tetrahedral mesh generation for three-dimensional viscous flows, Int. J. Numer. Methods Eng., 39, 549-567 (1996) · Zbl 0844.76051
[27] Ito, Y.; Murayama, M.; Yamamoto, K.; Shih, AM; Soni, BK, Efficient hybrid surface/volume mesh generation using suppressed marching-direction method, AIAA J., 51, 1450-1461 (2013)
[28] Hassan, O.; Probert, EJ; Morgan, K., Unstructured mesh procedures for the simulation of three-dimensional transient compressible inviscid flows with moving boundary components, Int. J. Numer. Methods Fluids, 27, 41-55 (1998) · Zbl 0905.76046
[29] Tremel, U.; Sørensen, KA; Hitzel, S.; Rieger, H.; Hassan, O.; Weatherill, NP, Parallel remeshing of unstructured volume grids for CFD applications, Int. J. Numer. Methods Fluids, 53, 1361-1379 (2007) · Zbl 1109.76051
[30] Zheng, J.; Chen, J.; Zheng, Y.; Yao, Y.; Li, S.; Xiao, Z., An improved local remeshing algorithm for moving boundary problems, Eng. Appl. Comput. Fluid Mech., 10, 405-428 (2016)
[31] Joe, B., Construction of three-dimensional improved quality triangulations using local transformations, SIAM J. Sci. Comput., 16, 1292-1307 (1995) · Zbl 0851.65081
[33] Shewchuk, JR., Two discrete optimization algorithms for the topological improvement of tetrahedral meshes (2002), Unpublished manuscript. Sep-27-2015. URL https://www.cs.berkeley.edu/ jrs/papers/edge.pdf
[34] De l’Isle, EB; George, PL, Optimization of tetrahedral meshes, IMA Vol. Math. Appl., 75, 97-128 (1995) · Zbl 0831.65127
[35] Liu, J.; Chen, B.; Sun, S., Small polyhedron reconnection for mesh improvement and its implementation based on advancing front technique, Int. J. Numer. Methods Eng., 79, 1004-1018 (2009) · Zbl 1171.74472
[36] Si, H., On 3D indecomposable and irreducible polyhedra and the number of Steiner Points (2002), May-17-2017. URL www.wias-berlin.de/people/si/course/files/talk-numgrid2016.pdf
[37] Goerigk, N.; Si, H., On indecomposable polyhedra and the number of Steiner Points, (Proceedings of the 24th International Meshing Roundtable. Proceedings of the 24th International Meshing Roundtable, Austin, TX, USA (2015)), 343-355
[38] Klincsek, GT., Minimal tiangulations of polygonal dmains, Ann. Discret. Math., 9, 121-123 (1980)
[39] Bowyer, A., Computing Dirichlet tessellations, Comput. J., 24, 162-166 (1981)
[40] Watson, D., Computing the n-dimensional Delaunay tessellation with application to Voronoï polytopes, Comput. J., 24, 167-172 (1981)
[41] George, PL., Improvements on Delaunay-based three-dimensional automatic mesh generator, Finite Elem. Anal. Des., 25, 297-317 (1997) · Zbl 0897.65078
[44] Xie, L.; Zheng, Y.; Chen, J.; Zou, J., Enabling technologies in the problem solving environment HEDP, Commun. Comput. Phys., 4, 1170-1193 (2008) · Zbl 1364.76007
[45] Snyder, DO; Koutsavdis, EK; Anttonen, JS, Transonic store separation using unstructured cfd with dynamic meshing, (Proceedings of the 33rd AIAA Fluid Dynamics Conference and Exhibit. Proceedings of the 33rd AIAA Fluid Dynamics Conference and Exhibit, Orlando, FL, USA (2003), AIAA), 2003-3919
[46] Escobar, JM; Montenegro, R.; Montero, G.; Rodríguez, E.; González-Yuste, JM, Smoothing and local refinement techniques for improving tetrahedral mesh quality, Comput. Struct., 83, 2423-2430 (2005)
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.