User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Blossom-Quad: A non-uniform quadrilateral mesh generator using a minimum-cost perfect-matching algorithm

Primary tabs

Remacle, Jean-François [UCL] Lambrechts, Jonathan [UCL] Seny, Bruno [UCL] Marchandise, Emilie [UCL] Johnen, Amaury [ULG] Geuzaine, Christophe [ULG]

A new indirect way of producing all-quad meshes is presented. The method takes advantage of a wellknown 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.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 2012
Language Anglais
Journal information "International Journal for Numerical Methods in Engineering" - Vol. 89, no. 9, p. 1102-1119 (02/03/2012)
Peer reviewed yes
Publisher JohnWiley & Sons Ltd. ((United Kingdom) Bognor Regis)
issn 0029-5981
e-issn 1097-0207
Publication status Publié
Affiliations ULG - Département d'Electricité, Electronique et Informatique (Institut Montefiore)/Applied and Computational Electromagnetics (ACE)
UCL - SST/IMMC/MEMA - Applied mechanics and mathematics
Keywords Quadrilateral meshing ; Surface remeshing ; Graph theory ; Optimization ; Perfect matchin
Links
  1. Hausner A Simulating decorative mosaics Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques 2001 573 580
  2. Constantinescu Emil M., Sandu Adrian, Multirate Timestepping Methods for Hyperbolic Conservation Laws, 10.1007/s10915-007-9151-y
  3. Lambrechts Jonathan, Hanert Emmanuel, Deleersnijder Eric, Bernard Paul-Emile, Legat Vincent, Remacle Jean-François, Wolanski Eric, A multi-scale model of the hydrodynamics of the whole Great Barrier Reef, 10.1016/j.ecss.2008.03.016
  4. Lévy B Liu Y Lp centroidal Voronoi tessellation and its applications ACM Transactions on Graphics (SIGGRAPH Conference Proceedings) 2010
  5. Guennebaud Gaël, Germann Marcel, Gross Markus, Dynamic Sampling and Rendering of Algebraic Point Set Surfaces, 10.1111/j.1467-8659.2008.01163.x
  6. Marchandise E., de Wiart C. Carton, Vos W. G., Geuzaine C., Remacle J.-F., High-quality surface remeshing using harmonic maps-Part II: Surfaces with high genus and of large aspect ratio, 10.1002/nme.3099
  7. 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
  8. Sarrate J., Huerta A., An improved algorithm to smooth graded quadrilateral meshes preserving the prescribed element size, 10.1002/1099-0887(200102)17:2<89::aid-cnm357>3.0.co;2-e
  9. Oum S Perfect matchings in claw-free cubic graphs ArXiv e-prints 2009
  10. Kasteleyn P. W., Dimer Statistics and Phase Transitions, 10.1063/1.1703953
  11. Pemmaraju Sriram, Skiena Steven, Computational Discrete Mathematics : Combinatorics and Graph Theory withMathematical, ISBN:9781139164849, 10.1017/cbo9781139164849
  12. Tutte W. T., A family of cubical graphs, 10.1017/s0305004100023720
  13. 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
  14. Geuzaine Christophe, Remacle Jean-François, Gmsh: A 3-D finite element mesh generator with built-in pre- and post-processing facilities, 10.1002/nme.2579
  15. Cook William, Rohe André, Computing Minimum-Weight Perfect Matchings, 10.1287/ijoc.11.2.138
  16. 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
  17. Galil Zvi, Micali Silvio, Gabow Harold, An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs, 10.1137/0215009
  18. Gabow H Implementation of algorithms for maximum matching on nonbipartite graphs PhD Thesis 1973
  19. Lawler, Combinatorial Optimization: Networks and Matroids (1976)
  20. Edmonds Jack, Paths, trees, and flowers , 10.4153/cjm-1965-045-4
  21. Frey, Mesh Generation-Application to Finite Elements (2008)
  22. Edmonds J Johnson EL Lockhart SC Blossom I: a computer code for the matching problem Report 1969
  23. Edmonds Jack, Maximum matching and a polyhedron with 0,1-vertices, 10.6028/jres.069b.013
  24. Owen S. J., Staten M. L., Canann S. A., Saigal S., Q-Morph: an indirect approach to advancing front quad meshing, 10.1002/(sici)1097-0207(19990330)44:9<1317::aid-nme532>3.0.co;2-n
  25. Borouchaki Houman, Frey Pascal J., Adaptive triangular-quadrilateral mesh generation, 10.1002/(sici)1097-0207(19980315)41:5<915::aid-nme318>3.0.co;2-y
  26. Lee C.K., Lo S.H., A new scheme for the generation of a graded quadrilateral mesh, 10.1016/0045-7949(94)90070-1
  27. Blacker Ted D., Stephenson Michael B., Paving: A new approach to automated quadrilateral mesh generation, 10.1002/nme.1620320410
Bibliographic reference Remacle, Jean-François ; Lambrechts, Jonathan ; Seny, Bruno ; Marchandise, Emilie ; Johnen, Amaury ; et. al. Blossom-Quad: A non-uniform quadrilateral mesh generator using a minimum-cost perfect-matching algorithm. In: International Journal for Numerical Methods in Engineering, Vol. 89, no. 9, p. 1102-1119 (02/03/2012)
Permanent URL http://hdl.handle.net/2078.1/108188