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 research 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 the tri-to-quad 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 part of a cycle, i.e., each endpoint of an edge must be shared by exactly two edges. If this restriction is not respected by the input triangulation, the mesh produced by CQMesh is unlikely to conform to all constrained edges. The algorithm CQMesh is based on generates strictly convex quadrilateral meshes, but the current implementation of CQMesh does not. So, 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 12 years ago! CQMesh can also generate poorly-shaped quadrilaterals, as it does not have any mechanism to ensure shape quality. A strictly convex quadrilateral mesh of much better quality can be obtained by post-processing the output of CQMesh using another program: 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 initialize the data structure. This may be very annoying when the number of triangles is large. Once the data structure is built, the tri-to-quad conversion is very fast thanks to linear-time complexity of the meshing algorithm. I have long wanted to replace this data structure or its initialization algorithm, but I still have not had the time to do it. Early versions of CQMesh were based on double precision arithmetic only, which caused a lot of numerical issues. In the current version of CQMesh, 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 CQMesh and run into numerical issues, I would really appreciate if you report them to me. In general, I can only maintain this code during my free time. So, be patient! |
|
|
How to execute CQMesh
CQMesh is really simple to use. You just have to type If you choose to use Triangle to generate the input files to be taken in by CQMesh, do not forget to use the Triangle command-line option e, so that it generates the .edge file. You should also be aware of the fact that CQMesh ignores any possible attributes and boundary markers that can eventually be part of the .poly file given to Triangle. 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 rudimentary graphical interface, called MeshView to visualize the qudrilateral meshes and print EPS files of them. It only needs X11 and OpenGL to compile. Hopefully, compilation will not be an issue for you. |
|
|
PortabilityCQMesh 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. |
|
|
DownloadGet a ZIP file. |
|
|
Compilation and instalationIn 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 very straightforward. To compile the code, uncompress the tar ball, enter directory cqmesh, edit the file makefile to modify the CGAL and GMP paths (if needed), and run make. If everything goes well, you should see the executable 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, unless the back compatibility of the CGAL features used by CQMesh is broken. If you do run into problems, please let me know and I will see what I can do. |
|
|
Last updateCQMesh was last updated on April 22, 2010. |
|
|
|
|
|
Last update: March 27, 2016 |
