What is the best (scalability and efficiency) algorithms for generating unstructured quad meshes in 2D? Where can I find a good unstructured quad mesh-generator? (open-source preferred)
Unstructured quad mesh-generation?
mesh generation;computational geometry
The are essentially two approaches to free quad meshing:Direct methods generate a quad mesh directly, usually by some advancing front method. The Paving paper is a standard reference and is the method used by CUBIT, so you have seen these meshes in many publications.Indirect methods generate some intermediate decomposition of the domain (e.g. triangles) and then produce an all-quad mesh through recombination and/or further decomposition. Q-Morph is an example that is used by ANSYS.Note that smoothing is necessary for both approaches, sometimes with alternating topology fix-up and smoothing steps. Some open source tools have built-in smoothing facilities and the LGPL-licensed Mesquite package is designed as a library specifically for mesh quality improvement.I know of two open source free-quad meshers:Gmsh (GPL with linking exception) can generate quad meshes using a recombination algorithm described in this paper.The Jaal component of MeshKit (LGPL) is based on recombination similar to Q-Morph above, read the IMR-2011 paper for more details. You can download the source through the link above, but it is not ready for production use yet.LBIE generates quad and hex meshes from volumetric data. From what I can tell, it is an interactive environment rather than a library. The site says that the source is available under GPL upon request.CUBIT is not open source (and although not expensive compared to commercial software, acquiring a license takes a long time), but produces high quality meshes and can be linked into other applications.