[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
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
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.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
