GO BACK TO MY SOFTWARE PAGESoftware.htmlshapeimage_4_link_0
 

CQMesh

CQMesh is a C++ program for generating convex quadrilateral meshes of arbitrary polygonal domains. CQMesh takes as input a triangulation of a polygonal domain, and then converts this triangulation into a convex quadrangulation of the same domain.

CQMesh is based on an algorithm for generating strictly convex quadrilateral meshes from triangulations of polygonal domains. A detailed description of this algorithm can be found in the paper "Constrained Quadrilateral Meshes of Bounded Size" (see my publications page). Quadrilateral meshes generated by CQMesh have bounded size: If the input triangulation has t triangles, then the corresponding output quadrangulation has at most floor(3t/2) + 2 quadrilaterals. Furthermore, CQMesh inserts at most t+2 extra vertices (Steiner points) in the triangulation domain during its conversion process. These bounds are better than the ones provided by previous conversion-based quadrilateral meshing algorithms of polygonal domains.

The triangulation given as input to CQMesh may contain constrained edges. Although the algorithm CQMesh is based upon can deal with any constrained triangulation, its implementation in CQMesh is a little bit less powerful: constrained edges must always be in a cycle, i.e., their endpoints must be shared with two other edges. If this restriction is not respected by the input triangulation, the mesh produced by CQMesh is unlikely to satisfy all constrained edges.

The algorithm CQMesh is based on generate strictly convex quadrilateral meshes, but the current implementation of CQMesh does not, and hence the output meshes may have the so-called "triangular-shaped" quadrilaterals. It is not difficult to modify CQMesh to enforce strictly convexity, but that was not my intention when I coded it.

CQMesh can also generate a few poorly-shaped quadrilaterals, as it does not have any mechanism for guaranteeing shape quality.

A strictly convex quadrilateral mesh of much better quality can be obtained by post-processing the output of CQMesh using QMPP, which is a quadrilateral mesh post-processor. But, QMPP is likely to output a slightly larger quadrilateral mesh, and the time spent by it to post-process a mesh is a lot longer than the time spent by CQMesh to produce the  mesh.

CQMesh uses a very flexible and powerful data structure to store the input triangulation. However, it takes a while to read in the input triangulation data and build such a data structure. This may be very annoying when the number of triangles is large. Once the data structure is built, the triangulation -> quadrangulation conversion is very fast thanks to the meshing algorithm.

Early versions of CQMesh were based on double precision arithmetic only, which caused a lot of problems to CQMesh users. In this current version of CQMesh, 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

CQMesh is really simple to use. You just have to type

cqm input-mesh-filename

where input-mesh-filename is the name of the input files describing the triangular mesh. CQMesh uses three input files: a  node, an edge, and an element file. These files have the same name, and their extensions are ".node", ".edge" and ".ele", respectively. For instance, the following command-line causes CQMesh to read in files "tri-mesh.node", "tri-mesh.edge", and "tri-mesh.ele":

cqm tri-mesh

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.

You do not have to use Triangle in order to use CQMesh, but if you do so, you will not have to care about directly editing  ".node", ".edge" and ".ele" files or converting files from other triangle mesh generators into ".node", ".edge" and ".ele" ones. For one, I enjoy using Triangle to generate input meshes for CQMesh. I found it very powerful, fast, and easy to use.

The output of CQMesh consists of four files: the ".node" file containing information about the vertices of the output quadrilateral mesh, the ".edge" file containing information about the edges of the output quadrilateral mesh, and the ".ele" file containing information about the quadrilaterals of the output quadrilateral mesh. The name of the output files is the same and it consists of a concatenation of the input file name with the suffix "-quad". I developed a simple graphical interface, called MeshView to visualize the meshes and print EPS files of quad meshes. It only needs X11 and OpenGL to compile.


Portability

CQMesh was developed for Unix-based systems. However, it only relies on standard features of C++, and on CGAL and GMP. So, the code should compile in a Windows-based PC as well. But, please, do not ask me to do that for you. Sorry!

There is now a binary version of CQMesh for Windows. If you like, you can give it a try.


Download

Download CQMesh.


Compilation and Installation

In order to install CQMesh, 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 straightforward.

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

Last time I compiled CQMesh, 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 with the newer ones. However, if you do, please, let me know and I will see what I can do.


Last Update

CQMesh was last updated on April 22, 2010.