QMPP

QMPP is a C++ program for post-processing convex quadrilateral meshes generated by CQMesh (although it is applicable to any quadrilateral mesh of planar polygonal domains). Its main goal is to eliminate "triangular-shaped" quadrilaterals (quads with an angle of 180^o) and improve the overall mesh quality. The output of QMPP is a strictly convex quadrilateral mesh of the same polygonal domain as the one of the input quadrilateral mesh. In order to eliminate "triangular-shaped" quadrilaterals and improve the overall mesh quality, QMPP makes use of some topological operations and the angle-based smoothing described in the following papers:

Kinney, P. "Clean Up: Improving Quadrilateral Finite Element Meshes", in Proceedings of the 6th International Meshing Roundtable, pp. 449-461, 1997.
Zhou, T. and Shimada, K. "An Angle-Based Approach to Two-Dimensional Mesh Smoothing", Proceedings of the 9th International Meshing Roundtable, pp. 373-384, 2000.

The quadrilateral meshing algorithm CQMesh is based on generates strictly convex quadrilateral meshes, but its implementation in CQMesh relaxes the strictly convexity restriction and allows for the generation of convex quadrilaterals which are not necessarily strictly convex. I plan to change my CQMesh implementation so that it exactly reflects its underlying algorithm. But for the time being, QMPP must be used if you need a quadrilateral mesh that can be used in practical applications, such as FE-based simulations. After I change my CQMesh implementation, QMPP will only serve the purpose of smoothing the mesh to improve the shape quality of its quads.

Early versions of QMPP were based on double precision arithmetic only, which caused a lot of numerical issues. In the current version of QMPP, I relied on the exact predicate inexact construction kernel of CGAL for point-line classification and line intersection calculations. After performing several tests, I can say that the code became a lot more robust. However, since the code does need to compute line intersections with inexact arithmetic, the numerical issues have not gone away for good. I also plan to incorporate some new advances on line intersections algorithms using (exact) rational arithmetic, but again I still have not had the time to do it. If you use QMPP and run into numerical issues, I would really appreciate if you report them to me. In general I can only maintain the QMPP code during my free time. So, be patient!

How to execute QMPP

QMPP is really simple to use. You just have to type
qmpp input-mesh-filename number-of-iterations
where
input-mesh-filename
is the name of the input files describing the input quadrilateral mesh, and
number-of-iterations
is the number of iterations used by the angle-based smoothing procedure. QMPP requires three input files: a node file, an edge file, and an element file, all of which share the same name and have extensions .node, .edge and .ele, respectively. For instance,
qmpp quad-mesh 5
causes QMPP to read in the files quad-mesh.node, quad-mesh.edge and quad-mesh.ele and execute 5 iterations of the smoothing procedure. A .node file contains information about the vertices of a triangular mesh, a .edge file contains information about the edges of a triangular mesh, and a .ele file contains information about the triangles of a triangular mesh. You can find more details about the format of these three types in the home page of the software Triangle, which is a public domain application for generating triangle meshes of planar polygonal domains. The output of QMPP consists of three files sharing the same name but consisting of different extensions: a node file, an edge file, and an element file. The common name of the output files of QMPP is a concatenation of the common name of its input mesh files and the suffix -post.

QMPP has a rudimentary graphics interface in which you can visualize both the input and the output quadrilateral meshes. I actually plan to remove this feature from QMPP in order to remove this graphics dependency, as the MeshView application can be used to visualize the meshes. QMPP is based on the the same data structure CQMesh uses to represent planar meshes. This data structure is very flexible and powerful, but its construction procedure slows down the step that reads in the input mesh file.

To improve a mesh, place the mouse on the visualization window, press and hold its secondary button, and choose one option from the menu. You can improve the mesh (which means that the topological operations and the smoothing will take place), save the current quadrilateral mesh, and generate statistics about the shape quality of the current mesh elements. I noticed that a number of iterations in the interval [5,10] of the angle-based smoothing. Since some mesh vertices can never be moved (the ones on the constrained edges of the mesh), a larger number of iterations may end up producing poorly-shaped elements, degrading the overall quality of the mesh.

Portability

QMPP was developed for Unix-based systems. It relies on standard features of C++, CGAL, GMP, X11, and OpenGL. As far as I know, all those components are available for PCs running Linux or Mac OS X. However, I've never tried to port QMPP to Windows. While this should be possible, please do not ask me to do it for you.

Download

Get a ZIP file.

Compilation and instalation

In order to install QMPP, you will need to install the Computational Geometry and Algorithms Library (CGAL) and the GNU Multiple Precision Arithmetic Library (GMP). Once you have them installed, the compilation of CQMesh should be very straightforward. To compile the code, uncompress the tar ball, enter directory qmpp, edit the file makefile to modify the X11, OpenGL, CGAL and GMP paths (if needed), and run make. If everything goes well, you should see the executable qmpp in the subdirectory bin.

Last time I compiled QMPP, I used g++ 4.2.1, CGAL 3.5.1 and GMP 4.3.2. There are newer versions of g++, CGAL, and GMP. You should have no problem compiling my code, unless the back compatibility of the CGAL features used by QMPP is broken. But, if you still run into problems, please let me know and I will see what I can do.

Last update

QMPP was last updated on April 22, 2010.

Last update: March 27, 2016