carrier image

A Frontal Delaunay Quad Mesh Generator Using the L-Infinity Norm

Remacle, J.-F., F. Henrotte, T. Carrier Baudouin, C. Geuzaine, E. Bechet, Thibaud Mouton and E. Marchandise

20th International Meshing Roundtable, Springer-Verlag, pp.455-472, October 23-26 2011


20th International Meshing Roundtable
Paris, France
October 23-26, 2011

Universitie de Liege, Department of Electrical Engineering and Computer Science, Montefiore Institute B28, Grande Traverse 10, 4000 Liege, Belgium
Institute of Mechanics, Materials and Civil Engineering, Universite catholique de Louvain, Avenue Georges-Lematre 4, 1348 Louvain-la-Neuve, Belgium
Universitie de Liege, Aerospace and Mechanical Engineering Department, Chemin des Chevreuils, 1, 4000 Liege, Belgium
Email:,fjean-francois.remacle,emilie.marchandise, tristan.carrier,, feric.bechet,

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. Then, the triangulation itself is taylored with the aim of producing right triangles in the domain. This is done using the infinity norm to compute dis- tances in the meshing process. The alignement of the triangles is controlled by a cross field that is defined on the domain. Meshes constructed this way have their points aligned with the cross field direction and their triangles are almost right everywhere. Then, recombination with our Blossom-based approach yields quadrilateral meshes of excellent quality.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article