Blossom-Quad: a non-uniform quadrilateral mesh generator using a minimum-cost perfect-matching algorithm. (English) Zbl 1242.74155
Summary: A new indirect way of producing all-quad meshes is presented. The method takes advantage of a well-known algorithm of the graph theory, namely the Blossom algorithm, that computes the minimum-cost perfect matching in a graph in polynomial time. The new Blossom-Quad algorithm is compared with standard indirect procedures. Meshes produced by the new approach are better both in terms of element shape and in terms of size field efficiency.
MSC:
| 74S05 | Finite element methods applied to problems in solid mechanics |
| 76M10 | Finite element methods applied to problems in fluid mechanics |
| 65N50 | Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs |
| 65M50 | Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs |
References:
| [1] | Blacker, Paving: a new approach to automated quadrilateral mesh generation, International Journal for Numerical Methods in Engineering 32 pp 811– (1991) · Zbl 0755.65111 · doi:10.1002/nme.1620320410 |
| [2] | Lee, A new scheme for the generation of a graded quadrilateral mesh, Computers and Structures 52 pp 847– (1994) · Zbl 0894.73159 · doi:10.1016/0045-7949(94)90070-1 |
| [3] | Borouchaki, Adaptive triangular-quadrilateral mesh generation, International Journal for Numerical Methods in Engineering 45 (5) pp 915– (1998) · Zbl 0905.65111 · doi:10.1002/(SICI)1097-0207(19980315)41:5<915::AID-NME318>3.0.CO;2-Y |
| [4] | Owen, Q-morph: an indirect approach to advancing front quad meshing, International Journal for Numerical Methods in Engineering 9 pp 1317– (1999) · Zbl 0946.74067 · doi:10.1002/(SICI)1097-0207(19990330)44:9<1317::AID-NME532>3.0.CO;2-N |
| [5] | Edmonds, Maximum matching and a polyhedron with 0-1 vertices, Journal of Research of the National Bureau of Standards 69B pp 125– (1965) · Zbl 0141.21802 · doi:10.6028/jres.069B.013 |
| [6] | Edmonds J Johnson EL Lockhart SC Blossom I: a computer code for the matching problem Report 1969 |
| [7] | Frey, Mesh Generation-Application to Finite Elements (2008) · Zbl 1156.65018 |
| [8] | Edmonds, Paths, trees, and flowers, Canadian Journal of Mathematics 17 pp 449– (1965) · Zbl 0132.20903 · doi:10.4153/CJM-1965-045-4 |
| [9] | Lawler, Combinatorial Optimization: Networks and Matroids (1976) · Zbl 0413.90040 |
| [10] | Gabow H Implementation of algorithms for maximum matching on nonbipartite graphs PhD Thesis 1973 |
| [11] | Gabow, An o(ev log v) algorithm for finding a maximal weighted matching in general graphs, SIAM Journal on Computing 15 pp 120– (1986) · Zbl 0589.68050 · doi:10.1137/0215009 |
| [12] | Gabow HN Data structures for weighted matching and nearest common ancestors with linking Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms 1990 434 443 |
| [13] | Cook, Computing minimum-weight perfect matchings, INFORMS Journal on Computing 11 (2) pp 138– (1999) · Zbl 1040.90539 · doi:10.1287/ijoc.11.2.138 |
| [14] | Geuzaine, Gmsh: a three-dimensional finite element mesh generator with built-in pre- and post-processing facilities, International Journal for Numerical Methods in Engineering 79 (11) pp 1309– (2009) · Zbl 1176.74181 · doi:10.1002/nme.2579 |
| [15] | Bommes D Zimmer H Kobbelt L Mixed-integer quadrangulation SIGGRAPH ’09: ACM SIGGRAPH 2009 papers ACM New York, NY, USA 2009 1 10 10.1145/1576246.1531383 |
| [16] | Tutte, A family of cubical graphs, Proceedings of the Cambridge Philosophical Society 43 pp 459– (1947) · Zbl 0029.42401 · doi:10.1017/S0305004100023720 |
| [17] | Pemmaraju, Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica (2003) · Zbl 1067.05001 · doi:10.1017/CBO9781139164849 |
| [18] | Kasteleyn, Dimer statistics and phase transitions, Journal of Mathematical Physics 4 pp 287– (1963) · doi:10.1063/1.1703953 |
| [19] | Oum S Perfect matchings in claw-free cubic graphs ArXiv e-prints 2009 |
| [20] | Sarrate, An improved algorithm to smooth graded quadrilateral meshes preserving the prescribed element size, Communications in Numerical Methods in Engineering 17 (2) pp 89– (2001) · Zbl 0993.65139 · doi:10.1002/1099-0887(200102)17:2<89::AID-CNM357>3.0.CO;2-E |
| [21] | Daniels J , II Silva CT Cohen E Localized quadrilateral coarsening SGP ’09: Proceedings of the Symposium on Geometry Processing Eurographics Association Aire-la-Ville, Switzerland 2009 1437 1444 |
| [22] | Marchandise, High-quality surface remeshing using harmonic maps-part III: surfaces with high genus and of large aspect ratio, International Journal for Numerical Methods in Engineering 86 pp 1303– (2011) · Zbl 1235.65142 · doi:10.1002/nme.3099 |
| [23] | Guennebaud, Dynamic sampling and rendering of algebraic point set surfaces, Computer Graphics Forum 27 pp 653– (2008) · doi:10.1111/j.1467-8659.2008.01163.x |
| [24] | Lévy B Liu Y Lp centroidal Voronoi tessellation and its applications ACM Transactions on Graphics (SIGGRAPH Conference Proceedings) 2010 |
| [25] | Lambrechts, A high-resolution model of the whole great barrier reef hydrodynamics, Estuarine, Coastal and Shelf Science 79 (1) pp 143– (2008) · doi:10.1016/j.ecss.2008.03.016 |
| [26] | Constantinescu, Multirate timestepping methods for hyperbolic conservation laws, Journal of Scientific Computing 33 pp 239– (2007) · Zbl 1127.76033 · doi:10.1007/s10915-007-9151-y |
| [27] | Hausner A Simulating decorative mosaics Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques 2001 573 580 |
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.
