[en] 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.
Disciplines :
Computer science
Author, co-author :
Remacle, Jean-François
Lambrechts, Jonathan
Seny, Bruno
Marchandise, Emilie
Johnen, Amaury ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Applied and Computational Electromagnetics (ACE)
Geuzaine, Christophe ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Applied and Computational Electromagnetics (ACE)
Language :
English
Title :
Blossom-Quad: a non-uniform quadrilateral mesh generator using a minimum cost perfect matching algorithm
Publication date :
February 2012
Journal title :
International Journal for Numerical Methods in Engineering
Blacker TD, Stephenson MB. Paving: a new approach to automated quadrilateral mesh generation. International Journal for Numerical Methods in Engineering 1991; 32:811-847.
Lee CK, Lo SH. A new scheme for the generation of a graded quadrilateral mesh. Computers and Structures 1994; 52:847-857.
Borouchaki H, Frey P. Adaptive triangular-quadrilateral mesh generation. International Journal for Numerical Methods in Engineering 1998; 45(5):915-934.
Owen SJ, Staten ML, Canann SA, Saigal S. Q-morph: an indirect approach to advancing front quad meshing. International Journal for Numerical Methods in Engineering 1999; 9:1317-1340.
Edmonds J. Maximum matching and a polyhedron with 0-1 vertices. Journal of Research of the National Bureau of Standards 1965; 69B:125-130.
Edmonds J, Johnson EL, Lockhart SC. Blossom I: a computer code for the matching problem. Report, IBM T.J. Watson Research Center, Yorktown Heights, New York, 1969.
Frey P, George PL. Mesh Generation-Application to Finite Elements. Wiley: Hoboken, 2008.
Edmonds J. Paths, trees, and flowers. Canadian Journal of Mathematics 1965; 17:449-467.
Lawler EL. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston: New York, NY, 1976.
Gabow H. Implementation of algorithms for maximum matching on nonbipartite graphs. PhD Thesis, Stanford University, 1973.
Gabow H, Galil Z, Micali S. An o(ev log v) algorithm for finding a maximal weighted matching in general graphs. SIAM Journal on Computing 1986; 15:120-130.
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.
Cook W, Rohe A. Computing minimum-weight perfect matchings. INFORMS Journal on Computing 1999; 11(2):138-148.
Geuzaine C, Remacle JF. Gmsh: a three-dimensional finite element mesh generator with built-in pre- and post-processing facilities. International Journal for Numerical Methods in Engineering 2009; 79(11):1309-1331.
Bommes D, Zimmer H, Kobbelt L. Mixed-integer quadrangulation. SIGGRAPH '09: ACM SIGGRAPH 2009 papers. ACM: New York, NY, USA, 2009; 1-10, DOI: 10.1145/1576246.1531383.
Tutte WT. A family of cubical graphs. Proceedings of the Cambridge Philosophical Society 1947; 43:459-474.
Pemmaraju S, Skiena S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica Cambridge University Press: New York, NY, USA, 2003.
Kasteleyn PW. Dimer statistics and phase transitions. Journal of Mathematical Physics 1963; 4:287-293. DOI: 10.1063/1.1703953.
Oum S. Perfect matchings in claw-free cubic graphs. ArXiv e-prints, Jun 2009.
Sarrate J, Huerta A. An improved algorithm to smooth graded quadrilateral meshes preserving the prescribed element size. Communications in Numerical Methods in Engineering 2001; 17(2):89-99.
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.
Marchandise E, de Wiart C, Vos W, Geuzaine C, Remacle J. 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 2011; 86:1303-1321.
Guennebaud G, Germann M, Gross M. Dynamic sampling and rendering of algebraic point set surfaces. Computer Graphics Forum 2008; 27:653-662.
Lévy B, Liu Y. Lp centroidal Voronoi tessellation and its applications. ACM Transactions on Graphics (SIGGRAPH Conference Proceedings), 2010.
Lambrechts J, Hanert E, Deleersnijder E, Bernard PE, Legat V, Wolanski JFRE. A high-resolution model of the whole great barrier reef hydrodynamics. Estuarine, Coastal and Shelf Science 2008; 79(1):143-151. DOI: 10.1016/j.ecss.2008.03.016.
Constantinescu EM, Sandu A. Multirate timestepping methods for hyperbolic conservation laws. Journal of Scientific Computing 2007; 33:239-278. DOI: 10.1007/s10915-007-9151-y.
Hausner A. Simulating decorative mosaics. Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, ACM, 2001; 573-580.
