Abstract
In this paper, we present an algorithm for partitioning any given 2D domain into regions suitable for quadrilateral meshing. It is able to preserve the symmetry of the domain if any, and can deal with inner boundaries and multidomain geometries. Moreover, this method keeps the number of singularities at the junctions of the regions to a minimum. Although each part of the domain, being four-sided, can be easily meshed using a structured method, we provide a meshing process that guarantees near perfect quality for most quadrilaterals of the resulting mesh. The partitioning stage is achieved by solving a PDE-constrained equation based on the geometric properties of the domain boundaries. An analysis of the generated mesh quality is provided at the end, showcasing that the meshes obtained through our algorithm are especially suitable for finite element methods.
Similar content being viewed by others
Notes
Note that results are independent of this choice.
The representation vector used at a \(C^0\) corner of \(\partial \Omega\) is the average of the representation vectors of the two geometrical edges connected to this corner.
We consider a point of \(\partial T_h\) to be a corner if the two incident edges form an angle smaller than \(\frac{3 \pi }{4}\) or greater than \(\frac{5 \pi }{4}\).
A non-isolated singularity actually leads to an infinity of singularities which in turns leads to a much higher energy. As our resolution minimized it, it automatically removed such configurations.
We remind the reader here that this means that the representation vector field of \(F\) is continuous, and not that any of the \({\mathbf {v}}_i\) field is continuous.
This can be understood easily: if there were a majority of negative singularities, at the minimum there were only negative singularities, and one of them could merge with this positive singularity we added and disappear. It is to be noted, though, in this case we can be sure that our algorithm would not reach the minimum, as it would not merge this singularity with another, because it would distort the representation vector field too much. If the majority of singularities were positive, on the contrary, we added one to the minimum.
References
Cook RD, Malkus DS, Plesha ME (1989) Concepts and applications of finite element analysis, 3rd edn. Wiley, New York
Faux ID, Pratt MJ (1979) Computational geometry for design and manufacture. Ellis Horwood, Chichester
Whiteley M, White D, Benzley S, Blacker T (1994) Two and three-quarter dimensional meshing facilitators. Eng Comput 12:144–145
Schneiders R (1996) A grid-based algorithm for the generation of hexahedral element meshes. Eng Comput 12:168–177
Staten ML, Owen SJ, Blacker T (2005) Unconstrained paving and plastering: a new idea for all hexahedral mesh generation. Proc Int Mesh Roundtable 14:399–416
Borouchaki H, Frey PJ (1998) Adaptive triangular-quadrilateral mesh generation. Int J Numer Methods Eng 41:915–934
Owen SJ, Staten ML, Canann SA, Saigal S (1999) Q-morph: an indirect approach to advancing front quad meshing. Int J Numer Methods Eng 44:1317–1340
Lévy B, Liu Y (2010) Lp centroidal voronoi tesselation and its applications. ACM Trans Graph 29. doi:10.1145/1778765.1778856
Remacle JF, Lambrechts J, Seny B, Marchandise E, Johnen A, Geuzaine C (2012) Blossom-quad: a non-uniform quadrilateral mesh generator using a minimum cost perfect matching algorithm. Int J Numer Methods Eng 89:1102–1119
Lin W, Tang Y, Zhao C, Liu X, Zhu G, Jiang F (2011) An algorithm for automatic 2D finite element mesh generation with line constraints. Comput Aided Des 43:1803–1813
Park C, Noh JS, Jang IS, Kang JM (2007) A new automated scheme of quadrilateral mesh generation for randomly distributed line constraints. Comput Aided Des 39:258–267
Tam TKH, Armstrong CG (1991) 2D finite element mesh generation by medial axis subdivision. Adv Eng Softw Workstn 13:313–324
Bommes D, Lévy B, Pietroni N, Puppo E, Silva C, Tarini M (2013) Zorin D quad-mesh generation and processing: a survey. Comput Graph Forum 32:51–76
Durst F, Schfer M (1996) A parallel block-structured multigrid method for the prediction of incompressible flows. Int J Numer Methods Fluids 22:549–565
Lions PL (1990) On the Schwarz alternating method III: a variant for nonoverlapping subdomains. In: Third international symposium on domain decomposition methods for partial differential equations, Philadelphia
Romé C, Glockner S, Caltagirone JP (2007) Resolution of the Navier–Stokes equations on block-structured meshes. Int J Numer Methods Fluids 54:1239–1268
Wulf WA, McKee SA (1995) Hitting the memory wall: implications of the obvious. Computer architecture and news, Association for Computing
Rude U (1997) Iterative algorithms on high performance architectures. In: Proceedings of Europar’97, Lecture notes in computer science, Springer, pp 57–71
Ray N, Vallet B, Li W, Lévy B (2008) N-Symmetry direction field design. ACM Trans Graph 27. doi:10.1145/1356682.1356683
Palacios J, Zhang E (2007) Rotational symmetry field design on surfaces. ACM Trans Graph 26. doi:10.1145/1239451.1239506
Strang G, Fix G (1973) An analysis of the finite element method. Wellesley-Cambridge Press
Alouges F (1997) A new algorithm for computing liquid crystal stable configurations: the harmonic mapping case. SIAM J Numer Anal 34:1708–1720
Saad Y (2003) Iterative methods for sparse linear systems. SIAM, Philadelphia
Bramble JH (1981) The Lagrange multiplier method for Dirichlet’s problem. Math Comput 37:1–11
Tricoche X (2002) Vector and tensor fields topology simplification, tracking and visualization. Ph.D thesis
Tricoche X, Scheuermann G, Hagen H (2001) Continuous topology simplification of planar vector fields. In: Proceedings of IEEE visualization, pp 159–166
Helman JL, Hesselink L (1991) Vizualizing vector field topology in fluid flows. IEEE Comput Graph Appl 11:36–46
White DR (1995) Automated hexahedral mesh generation by virtual decomposition. In: Proceedings, 4th international meshing roundtable, pp 165–176
Ascher UM, Petzold LR (1998) Computer methods for ordinary differential equations and differential-algebraic equations. SIAM, Philadelphia
Liu Y, Xing HL, Guan Z (2011) An indirect approach for automatic generation of quadrilateral meshes with arbitrary line constraints. Int J Numer Methods Eng 87:906–922
Fogg H, Armstrong C, Robinson TT (2013) MultiBlock decomposition using cross-fields. In: ADMOS 2013—international conference on adaptive modeling and simulation
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kowalski, N., Ledoux, F. & Frey, P. Automatic domain partitioning for quadrilateral meshing with line constraints. Engineering with Computers 31, 405–421 (2015). https://doi.org/10.1007/s00366-014-0387-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00366-014-0387-5