RMesh – Convex Quadrilateral Meshing.
RMesh was a research project done in C++ using CGAL (Computational Geometry Algorithm Libraries) and OpenGL. The application takes as input either a 2D set of points or a simple polygon of any shape, with or without interior points, and/or interior holes, and then computes a convex quadrangulation, which is a division of a bounded planar surface into convex quadrilaterals.
The Algorithm
The algorithm first constructs a Delaunay triangulation of the input, then creates a spanning tree from the centroid of each triangle. The spanning tree is traversed in reverse order, and a series of case checks is performed while merging faces to create convex quadrilaterals.
There are three cases:
Case 1
The first case is the simplest, and consists of a pair of triangles forming a diamond shape. The shape is already a convex quad if the adjacent edge is removed, so we just remove it. The number of faces decreases by one.
Case 2
This case is the most complicated, and it is a variation of the condition in case 1. This time, the shape formed by the two triangles is concave. When the quad is concave, four Steiner points are added in such a way that the once singular concave quad becomes five new convex quads. A series of ray intersections determines exactly where these points can be added to ensure convexity. The number of faces in this case increases by three.
Case 3
The third case involves three triangles that are grouped together, and a single Steiner point is added to form two quads and a single triangle. The Steiner point is chosen in a way that ensures the two new quads are both convex, again using a series of ray intersections. The number of faces in this case remains the same.
A less sophisticated version of this algorithm (which does not check for convexity) is available for download. For a list of related papers (including that one), check out the research page of Dr. Suneeta Ramaswami at Rutgers University at Camden, who was my research supervisor.
The Application
RMesh is broken up into two parts, a GUI version and a non-GUI version. The GUI version uses the OpenGL API and GLUT. The non-GUI version is a small console application with an interactive menu. Both versions of RMesh have the same meshing functionality, although in the GUI version you can interactively enter point sets and polygons with the mouse. In addition, the GUI version also functions as a graph viewer which can read previously stored quadrangulations and display them.
RMesh works well with a smaller number of faces ( < 2500 ), but in general will work with any number of faces. I’ve run it without fail on input around 15,000 faces, but unfortunately input that large takes about 2 minutes to compute. RMesh uses an exact predicate, exact construction cartesian kernel provided by CGAL which is very precise but also pretty slow.
Before installing RMesh, you’ll need the following. (This is all reiterated
in the README file)…
- A c++ compiler
- CGAL-3.0.1
- OpenGL or Mesa (if you’re planning on running the GUI version)
The Interface
Here are a few pics of RMesh in action:
 |
 |
 |
 |
 |
 |
Installation
Download the tar.gz file from this page. Untar/decompress the file:
- tar zxvf RMesh-1.02.tar.gz
If you haven’t installed CGAL on your system yet, click here for instructions. Once CGAL-3.0.1 is installed on your system, you can make a backup of the mkfile.cgal file located in the RMesh-1.02/ directory:
- cp mkfile.cgal mkfile.cgal.orginal
Then copy the file located in the cgal-install-directory/make directory that includes the name of your architecture to the curent directory as mkfile.cgal: (for instance)
- cp /usr/local/CGAL-3.0.1/make/makefile_athlon_Linux-2.4.18-14_g++-3.2.0 mkfile.cgal
If you happen to be installing this on clam, crab, or hpc (Rutgers Camden network), you can simply download this file which contains a mkfile.cgal and a makefile preconfigured for compilation on these systems. Simply extract the two files and place them in the RMesh-1.02 directory (overwriting the ones provided in the distribution).
If not, you might need to modify your X11 paths and link flags if you plan on using the GUI version. This can be somewhat annoying. Try it first, and if you get any compilation errors mentioning Xblah blah then you know that’s the problem. The X11 link flags in the given mkfile.cgal are from a redhat 8.0 system, and in the previously mentioned mkfile.cgal.clam file are from Solaris 5.9. I’ve included a makefile variable XFLAGS in the actual makefile. The X flags here are what you’ll need to edit:
- XFLAGS = \ -lXmu -lX11 -L/usr/X11R6/lib
I won’t go into detail about how to install OpenGL or Mesa, and assume that either you have it installed or you’re only planning to use the console app.
Now to build it:
To build both the GUI and non-GUI versions
- make or make all
To build only the GUI version
- make RMesh
To build only the non-GUI version
- make RMesh_No_Gui
If everything went well, you can run whatever you built with:
- ./RMesh or ./RMesh_No_Gui
How to use RMesh
This section will explain how to use RMesh as a GUI application and a non-GUI application.
The GUI version:
When RMesh is first started, the default behavior is for it to expect to read in a point set via mouse clicks. This is also true after “Clear” is selected. If you’d like to manually enter a set of points, simply start clicking the screen. Then you can view a triangulation by clicking “Triangulate Point Set”, and a Convex Quadrangulation by clicking “Quadrangulate Point Set” from the right mouse click menu.
To enter a polygon, click “Enter Simple Polygon” and start clicking. Polygons and holes must be entered in order around the hull, although the order can be clockwise or coutnerclockwise. A precondition is set on the user to supply simple polygons when entering polygons. Holes should not intersect the boundaries of the polygon. Interior points should be not lie on the boundary of the interior, and not exist inside the holes of the polygon. If any of these preconditions are voided, the behavior of RMesh is undefined. Most likely, RMesh will simply exit with a failed assertion.
It is a very simple interface and a few minutes of playing with it will probably make you a master.
Now, reading in points from files. Here is a description of the file formats that RMesh can read. Simply click to enter a file, enter the filename at the console, and RMesh will read it. If viewing a previously created quadrangulation, it will be read in as a Polygon, so the second set of tools “Simple Polygon Options” can be used to view statistics, etc. Writing the quadrangulation is done in the same manner, via a selection from the menu and then entering the filename from the console.
The non-GUI version can be used in two ways:
- You can enter into an interactive console menu
- You can skip the menu and simply provide three arguments
The first approach is simple:
- ./RMesh_No_Gui
The second approach takes exactly three arguments:
- ./RMesh_No_Gui inputfile outputfile inputtype
- inputfile is the name of a file containing a point set or a polygon
- outputfile is the name the quadrangulation will be written to
- inputtype is one of two options: “points” or “polygon”. If any other option is given, or the number of arguments is not 3, the interactive console menu will engage.
- An example: ./RMesh_No_Gui data_files/point_set_file new_quad points
RMesh now has the functionality of generating random point sets and compiling the data into HTML and non-HTML formats for you. Simply use the option near the bottom of the menu, which will prompt you to enter some information at the console. You can determine the bounding box, the number of trials, and the number of points per trial. All will be formatted and written to both the HTML file you specified, and a file with the extension .no_format. The no_format file will not have means, just raw data in the same order as in the HTML file (not denoted so you can copy paste into a spreadsheet if you want). Keep in mind that with large numbers of faces, RMesh behaves slowly. If you run 100 trials on sets that could have > 5000 faces, say, it’s going to take a while… For example, the last link in the statistics section took over 40 minutes to compile.
These HTML files have a link to a stylesheet called “styles.css”. If you’d like to style the files, either use the styles.css file provided or create your own.
RMesh Statistics
RMesh now has the functionality of creating these files for you. These are examples it has directly generated.
File Formats
For a look at the basic formats that RMesh can read/write, have a look in the RMesh-1.02/data_files/ directory. The file “point_set_file” is an example of a file containing a point set, “polygon_file” is an example of a file containing a polygon with holes and interior points. If you don’t have holes or interior points, just don’t include “holes” or “points”.
The quadrangulation files are a bit more tricky. They are written out in an XML format that conforms to the simple RMeshQuad.dtd file. However, RMesh does not use an XML parsing engine itself, nor will it ever. RMesh only uses a simple space delimited token reader to get the input. Therefore, each enclosing tag MUST be separated from it’s content by at least one space. The point of the XML format is so that using an XSLT engine, once produced it can be converted easily into any other format with a style sheet. Having said that, every quadrangulation file produced by RMesh is readable by RMesh; if you create one on your own or you alter one, make sure it conforms exactly to what I’ve just stated or the behavior is undefined.
For example:
<point> 2 5 </point> is fine.
<point>2 5</point> is NOT.
Examples are located in the RMesh-1.02/data_files/ directory as well.
How to install CGAL
To install CGAL, first download it here. You’ll need to be root or have superuser privs to do this. Move the tar.gz to /usr/local:
- mv CGAL-3.0.1.tar.gz /usr/local
Then change to that directory and untar/decompress it:
- cd /usr/local; tar zxvf CGAL-3.0.1.tar.gz
Once the directory /usr/local/CGAL-3.0.1 has been created change to it and run the install script:
- cd CGAL-3.0.1; ./install_cgal -i
This will bring up a nice interactive installation menu. Just press ‘b’ and it will build. At this point, you could also install support for LEDA, etc.. but you don’t need it for RMesh so you’re on your own to figure all the other options out…
Once installed, you can proceed with the RMesh installation procedure