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 180o) 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 applies a subset of the topological operations described in Kinney's paper and the angle-based smoothing described in Zhou and Shimada's paper:

1. •Kinney, P. "Clean Up: Improving Quadrilateral Finite Element Meshes", in Proceedings of the 6th International Meshing Roundtable, pp. 449-461, 1997.
   

2. •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 the generation of convex quadrilateral which are not necessarily strictly convex. While I do not change my CQMesh implementation to exactly reflect its underlying algorithm, QMPP is need for obtaining a quadrilateral mesh we can use in practical applications, such as FE-based simulations. After I change my CQMesh implementation, QMPP will be needed only for the purpose of smoothing the mesh.

Early versions of QMPP were based on double precision arithmetic only, which caused a lot of problems to QMPP users. In this current version of QMPP, I relied on the "exact predicate inexact construction kernel" of CGAL for point-line classification and line intersection calculations. According to several tests, my code became a lot more robust. However, if you find any problems, I would really appreciate if you report them to me. In general, I try to maintain this code in my free time. You can freely download and use QMPP for non-commercial purposes, but you do so at your own risk. Neither I nor the University of Pennsylvania give any warranty or whatsoever for the installation and use of this program.

How to Use It

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 learn about the format of these three types in the home page of Triangle, which is a public domain application for generating triangle meshes of planar polygonal domains. Triangle was developed by Jonathan Shewchuk, who also defined its mesh file formats. The output of QMPP consists of three files sharing the same name, but with distinct extensions: a node file, edge file, and element file. The common name of the files is a concatenation of the common name of the input mesh files and the suffix "-post".

QMPP has a graphics interface in which you can visualize both the input and the output quadrilateral meshes. I actually intend 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 quite flexible and powerful, but its construction procedure slows down the input file reading step.

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.

Experimentally, I realized that 5-to-10 is a good range for the number of iterations 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 indeed produce some poorly-shaped elements, and the overall quality of the mesh may end up getting worse rather than better. 

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 my code to Windows-based PCs. While this should be possible, I would appreciate if you do not ask me to do it for you. Sorry!

Download

Download QMPP.

Compilation and Installation

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 QMPP should be straightforward.

To compile the code, uncompress the tar ball, enter directory qmpp, edit "makefile" to modify the X11, OpenGL, CGAL and GMP paths (if needed), and run make. If everything goes smooth, you should see the executable file "qmpp" in the subdirectory bin.

Last time I compiled QMPP, I used the GNU g++ compiler (version 4.2.1),  CGAL (version 3.5.1) and GMP (version 4.3.2).

There are currently newer versions of g++, CGAL, and GMP. You should have no problem compiling the code with the newer ones. However, if you do, please, let me know and I will see what I can do. For quite some time, some earlier versions of the GNU g++ did not like the way my code used a template-based class for smart pointers. I found a way of overcoming the shortcomings without changing my code in a drastic way. Hopefully, the "trick" will work for future g++ versions.

Last Update

QMPP was last updated on April 22, 2010.