Automatic generation of multiblock decompositions of surfaces. (English) Zbl 1352.65606

Summary: Multiblock-structured meshes have significant advantages over fully unstructured meshes in numerical simulation, but automatically generating these meshes is considerably more difficult. A method is described herein for automatically generating high-quality multiblock decompositions of surfaces with boundaries. Controllability and flexibility are useful capabilities of the method. Additional alignment constraints for forcing the appearance of particular features in the decomposition can be easily handled. Also, adjustments are made according to input metric tensor fields that describe target element size properties. The general solution strategy is based around using a four-way symmetry vector-field, called a cross-field, to describe the local mesh orientation on a triangulation of the surface. Initialisation is performed by propagating the boundary alignment constraints to the interior in a fast marching method. This is similar in a way to an advancing-front or paving method but much more straightforward and flexible because mesh connectivity does not have to be managed in the cross-field. Multiblock decompositions are generated by tracing the separatrices of the cross-field to partition the surface into quadrilateral blocks with square corners. The final task of meshing the decomposition requires solving an integer programming problem for block division numbers.


65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65D17 Computer-aided design (modeling of curves and surfaces)
Full Text: DOI Link


[1] Hallquist JO LS-DYNA3D theoretical manual 1991 http://www2.nsysu.edu.tw/csmlab/fem/dyna3d/theory.pdf
[2] Jensen M Du Bois P Ho P LS-Dyna analysis for structural mechanics 2011 http://www.predictiveengineering.com/Solutions/products/training/
[3] Chen, A unstructured nodal spectral-element method for the Navier-Stokes equations, Communications in Computational Physics 12 (1) pp 315– (2012) · Zbl 1373.76024
[4] Komatitsch, The Spectral-Element Method in Seismology pp 205– (2013)
[5] Aftosmis, Behavior of linear reconstruction techniques on unstructured meshes, AIAA Journal 33 pp 2038– (1995) · Zbl 0856.76070
[6] Ait-Ali-Yahia, Anisotropic mesh adaptation: towards user-independent, mesh-independent and solver-independent CFD. Part II: Structured grids, International Journal for Numerical Methods in Fluids 39 (8) pp 657– (2002) · Zbl 1101.76350
[7] Rumsey CL HiLiftPW-2 summary 2nd AIAA CFD High Lift Prediction Workshop San Diego, CA, USA 2013 http://hiliftpw.larc.nasa.gov/Workshop2/ParticipantTalks/HLPW2-ru
[8] Blacker, Paving: a new approach to automated quadrilateral mesh generation, International Journal for Numerical Methods in Engineering 32 (4) pp 811– (1991) · Zbl 0755.65111
[9] Staten, Unconstrained plastering-hexahedral mesh generation via advancing-front geometry decomposition, International Journal for Numerical Methods in Engineering 81 (2) pp 135– (2010) · Zbl 1183.74318
[10] Schneiders, A grid-based algorithm for the generation of hexahedral element meshes, Engineering with Computers 12 (3-4) pp 168– (1996) · Zbl 05474590
[11] White DR Automatic quadrilateral and hexahedral meshing of pseudo-cartesian geometries using virtual subdivision Master’s Thesis 1996
[12] Tam, 2-D finite element mesh generation by medial axis subdivision, Advances in Engineering Software 13 (5/6) pp 313– (1991) · Zbl 0754.65098
[13] Rigby DL TopMaker: a technique for automatic multi-block topology generation using the medial axis Technical Report NASA/CR-213044 2004
[14] Hertzmann A Zorin D Illustrating smooth surfaces Proceedings of SIGGRAPH 2000 New Orleans, LA, USA 2000 517 526
[15] Wei L-Y Levoy M Texture synthesis over arbitrary manifold surfaces Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques New York, NY, USA 2001 355 360 10.1145/383259.383298
[16] Alliez, Anisotropic polygonal remeshing, ACM Transactions on Graphics 22 (3) pp 485– (2003) · Zbl 05457177
[17] Palacios, Rotational symmetry field design on surfaces, ACM Transactions on Graphics 26 (3) pp 55-1– (2007) · Zbl 05457806
[18] Ray, N-symmetry direction field design, ACM Transactions on Graphics 27 (2) pp 10-1– (2008) · Zbl 05457844
[19] Bunin, A continuum theory for unstructured mesh generation in two dimensions, Computer Aided Geometric Design 25 (1) pp 14– (2008) · Zbl 1172.65320
[20] Hon, Inverse source identification by Green’s function, Engineering Analysis with Boundary Elements 34 (4) pp 352– (2010) · Zbl 1244.65162
[21] Shewchuk JR What is a good linear element? - Interpolation, conditioning, and quality measures In 11th International Meshing Roundtable Ithaca, New York, USA 2002 115 126
[22] Gray, Modern Differential Geometry of Curves and Surfaces with Mathematica, 3. ed. (2006) · Zbl 1123.53001
[23] Marinov M Kobbelt L Direct anisotropic quad-dominant remeshing Proceedings of the 12th Pacific Conference n Computer Graphics and Applications Seoul, Korea 2004 207 216
[24] Kälberer, Quadcover-surface parameterization using branched coverings, Computer Graphics Forum 26 (3) pp 375– (2007) · Zbl 1259.65025
[25] Ben-Chen, Conformal flattening by curvature prescription and metric scaling, Computer Graphics Forum 27 (2) pp 449– (2008) · Zbl 05653266
[26] Bunin G Towards unstructured mesh generation using the inverse poisson problem 2008
[27] Hildebrandt K Polthier K Wardetzky M Smooth feature lines on surface meshes Proceedings of the Third Eurographics Symposium on Geometry Processing Aire-la-Ville, Switzerland, Switzerland 2005 85 90 http://dl.acm.org/citation.cfm?id=1281920.1281935
[28] Pouget, CGAL user and reference manual, in: Approximation of Ridges and Umbilics on Triangulated Surface Meshes (2013)
[29] Bommes, Mixed-integer quadrangulation, ACM Trans. Graph. 28 (3) pp 77:1– (2009)
[30] Kowalski, Proceedings of the 21st International Meshing Roundtable pp 137– (2013)
[31] Liu, General planar quadrilateral mesh design using conjugate direction field, ACM Trans. Graph. 30 (6) pp 140:1– (2011)
[32] Bommes, Integer-grid maps for reliable quad meshing, ACM Trans. Graph. 32 (4) pp 98:1– (2013) · Zbl 1305.68209
[33] Bommes, Global structure optimization of quadrilateral meshes, Computer Graphics Forum 30 (2) pp 375– (2011)
[34] Li, Shape optimization of quad mesh elements, Comput. Graph. 35 (3) pp 444– (2011)
[35] Tam, Finite element mesh control by integer programming, International Journal for Numerical Methods in Engineering 36 (15) pp 2581– (1993) · Zbl 0800.73462
[36] Möhring, Mesh refinement via bidirected flows: modeling, complexity, and computational results, J. ACM 44 (3) pp 395– (1997) · Zbl 0891.68122
[37] Mitchell, High fidelity interval assignment, Int. J. Comput. Geometry Appl 10 (4) pp 399– (2000) · Zbl 1074.68645
[38] Mitchell, Proceedings of the 22nd International Meshing Roundtable pp 203– (2014)
[39] Sethian, Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science, 2. ed. (1999) · Zbl 0973.76003
[40] do Carmo, Riemannian Geometry (2011)
[41] Frey, Mesh generation, in: Ch. 10. Quadratic Forms and Metrics (2010)
[42] Alauzet F Metric-based anisotropic mesh adaptation 2010 http://www-roc.inria.fr/gamma/Frederic.Alauzet/cours/cea2010_V2.pdf
[43] Tchon, Three-dimensional anisotropic geometric metrics based on local domain curvature and thickness, Computer-Aided Design 37 (2) pp 173– (2005) · Zbl 05861185
[44] Vyas, Proceedings of the 18th International Meshing Roundtable pp 377– (2009)
[45] Makem, Automatic decomposition and efficient semi-structured meshing of complex solids, Engineering with Computers pp 1– (2012)
[46] ITI T CADfix website http://www.transcendata.com/products/cadfix
[47] Elias, Simple finite element-based computation of distance functions in unstructured grids, International Journal for Numerical Methods in Engineering 72 (9) pp 1095– (2007) · Zbl 1194.65145
[48] Python SF 8.4. heapq - Heap queue algorithm, Python Language Reference, version 2.5 http://www.python.org
[49] Jones E Oliphant T Peterson P et al SciPy: open source scientific tools for Python 2001 http://www.scipy.org/
[50] Dorobantu M Efficient streamline computations on unstructured grids Technical Report TRITA-NA-9709 1997
[51] Carpenter, Accuracy of shock capturing in two spatial dimensions, AIAA Journal 37 (9) pp 1072– (1999)
[52] Qin, Flow feature aligned grid adaptation, International Journal for Numerical Methods in Engineering 67 (6) pp 787– (2006) · Zbl 1113.76059
[53] Harris M Flow feature aligned mesh generation and adaptation Ph.D. Thesis 2013
[54] Baals DD Corliss WR Wind tunnels of NASA 1981 http://history.nasa.gov/SP-440/cover.htm
[55] Shahpar S Lapworth L Padram: parametric design and rapid meshing system for turbomachinery optimisation Asme turbo expo 2003, collocated with the 2003 international joint power generation conference 2003 579 590
[56] SIMULIA. DS Abaqus 6.11 User’s Manual
[57] Spekreijse SP Boerstoel JW An algorithm to check the topological validity of multi-block domain decompositions Numerical grid generation in computational field simulations 1998 161 170
[58] Brewer ML Diachin LF Knupp PM Leurent T Melander DJ The mesquite mesh quality improvement toolkit Sante Fe. New Mexico. USA 2003 http://dblp.uni-trier.de/db/conf/imr/imr2003.html#BrewerDKLM03
[59] Akin, Finite Element Analysis with Error Estimators: An Introduction to the FEM and Adaptive Error Analysis for Engineering Students, 1. ed. (2005) · Zbl 1086.65104
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.