RMesh Convex Quadrilateral Meshing

Welcome to the RMesh page. RMesh was a research project done in C++ using CGAL (Computational Geometry Algorithm Libraries) and OpenGL. The application takes as input a 2D set of points or a simple polygon (a polygon whose segments intersect only at endpoints) of any shape, with or without interior points, with or without interior holes, computes a triangulation and then a convex quadrangulation.

A 2D convex quadrangulation is simply a division of a bounded planar surface into convex quadrilaterals. This algorithm is implemented by superimposing a spanning tree consisting of edges connecting the centroid of each face in a triangulation, traversing it in reverse order, and performing a series of case checks while merging faces to create convex quads. A slightly less sophisticated version of this algorithm is well documented here. The algorithm that RMesh uses is an augmented version of the previously mentioned one in which the pairing of triangles to form new quads is tested for convexity.

There are three cases:

Case 1

This case, the simplest one, 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 simply remove it. This scenario lends itself to being the most effective and efficient, as no new points or segments are added to the overall structure, and 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. In this one, however, the shape formed by the two triangles is concave. This calls for the insertion of new points called Steiner points, in a specific manner in order to maintain convexity. If 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. The number of faces in this case increases by three.

Case 3

The final case is slightly less complicated than the second. When three triangles are grouped together, a single Steiner point is added to form two quads and a single triangle. The Steiner point is chosen in a manner that ensures the two new quads are both convex. This is done by slicing the parent triangle with the intersecting rays of the children (if there are intersecting rays). The new Steiner Point is placed at the center of the new bounded plane. In this scenario, the number of faces remains the same.

You can find some statistics of convex quadrilateral meshs generated by RMesh here.

For a list of related papers (including the one just mentioned), check out the research page of Dr. Suneeta Ramaswami. She is a professor of Computer Science at Rutgers University at Camden, and also 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 console menu. Both versions of RMesh have practically the same functionality, although the GUI version allows for interactive entering of point sets and polygons via the mouse. The non-GUI version only allows reading/writing through files. In addition, the GUI version also functions as a graph viewer, and is capable of reading in previously stored quadrangulations and displaying them.

RMesh works well with smaller numbers of faces ( < 2500 ), but in general works with any number of faces. I've run it without fail on input around 15,000 faces, but unfortunately input that large takes @ 2m to compute. RMesh uses an exact predicate, exact construction cartesian kernel provided by CGAL which is very precise but also somewhat slow.

RMesh now generates strictly convex quads; quads can no longer have one angle whose measure is 180 degrees. RMesh also may still produce one final triangle in the quadrangulation. This still may be changed in the next version.

If you would like to try RMesh, it is available for free download from the link below.

NOTE: RMesh is available for free personal use, not to be distributed. It is provided without guarantee from either myself, Dr. Ramaswami, or Rutgers University. Any bug reports can be emailed to: rdb34@drexel.edu

RMesh-1.02.tar.gz

Before installing RMesh, you will need the following. (This is all reiterated in the README file)...

1. A c++ compiler
2. CGAL-3.0.1
3. OpenGL or Mesa (if you're planning on running the GUI version)

What does RMesh look like?

Here are a few pics of RMesh in action:

How to install RMesh

Updated 08/2005 PLEASE NOTE: This was written using CGAL 3.0.1 libraries, and some of the includes etc. will not be valid for other versions of CGAL. Unfortunately it looks as though the CGAL libraries on the Rutgers network have been upgraded so the files below will not compile. If you must have these files compiled you might want to contact Curtis Saal (or whoever is in charge of maintaining the installs) and see about getting CAGL 3.0.1 reinstalled.

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'd need to edit:

• XFLAGS = \ -lXmu -lX11 -L/usr/X11R6/lib

If it helps, look around in mkfile.cgal for any hints on where your X libs are. I will not go into detail about how to install OpenGL or Mesa, I'm assuming either you have it installed or are planning on using the console app only. Okay, assuming your X flags are all good and you now have the correct mkfile.cgal file in your RMesh-1.02 directory, you can build RMesh in one of four ways:

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

Now assuming 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:

1. You can enter into an interactive console menu
2. 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.

• Result Set 1
• Result Set 2
• Result Set 3
• Result Set 4
• Result Set 5

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 implore an XML parsing engine itself, nor will it ever. RMesh only implores a simple space delimited token reader to get the input. Therefore, each enclosing tag MUST be seperated 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