## Automatic mesh generation with QMorph

### Quick Guide

This version of Grid3D ships with an implementation of QMorph, a quad mesh generating algorithm.

That means you don't have to create your all-quadrilateral mesh manually anymore but have a tool that does this ugly work for you.

You simply define the boundaries and add edges to them.

The boundaries need not have any particular form, except that they may only consist of SegmentLists with all segments being LineSegments (if you don't know what that means: make sure you don't have circles).

Then you select Coarse Mesh/Quad Mesher/Generate Quad Mesh (QMorph).... This will open up the configuration dialog, which at this point you can safely skip: just click Start Meshing.

Things start off with the creation of an initial triangle mesh in your domain which will then be stepwise morphed into an all-quadrilateral mesh.

The default settings are so that the triangle mesh should be created within a few seconds depending on the size of your domain. Then you should see a window with some statistics about the triangle mesh.

Especially the amount of Mesh Triangles might be interesting for you, since the computation time as well as the amount of quads in the final mesh directly depend on this value:

The amount of quadriliterals in the resulting mesh will be roughly a third of the amount of triangles in the initial mesh.

The time per triangle should be below 10 ms, but for finegrained triangle meshes exceeding 5000 initial elements, the time per triangle might rise above 30 ms.

So it is adviseable to have some rather coarse test runs before trying to generate a very fine quad mesh.

If you think the initial mesh is okay, click the Okay button.

Now the triangle mesh is imported into Grid3D and cloned once to have the original triangle mesh as reference to the resulting quad mesh. If you don't need it, you can safely remove it once the quad mesh is created.

The cloned domain will be changed: in the lower left edge of the Grid3D window you can see a progress bar and the statusbar which display the current state of the algorithm.

Note that after the actual processing of the triangles it still might take some time to smooth and 'proof read' the resulting quadrilateral mesh.

If all went well, you'll end up with an all-quad domain, that you can save. Since the resulting mesh is a normal Grid3D-Domain, of course you can do all the editing and changing you're used to.

### Configuration of QMorph

The configuration dialog consists of four tabs named General, Advanced, Triangulation and Internal.

#### General

This tab contains options everybody should be able to adjust.

- Demo mode: You can enable the demo mode, which opens a dialog while QMorph is calculating. This dialog explains in adjustable detail what happens, but you may not find that interesting unless you know how the algorithm works.
  By default this option is set to OFF.
- Triangulate domain: If you have a domain that consists of triangles, there's no need to have it triangulated, so that it can be turned off. Normally you will have created a domain without triangles so you need to have an intial triangulation to be calculated.
  By default this option is set to triangulate the domain.

#### Advanced

The options of this tab are a bit more advanced, but still manageable for most users.

- Auto-correct invalid fronts QMorph relies on the boundaries to contain an even amount of edges or else there may triangles remain in the finished domain.
  If you want to have odd amounts of boundary-edges automatically detected and corrected, you should enable this option. The correction chooses the longest edge of the invalid boundary and splits it (and the adjacent triangle) in two.
  Generally this is wanted and it is enabled by default.
- Detect invalid points Sometimes singular points which are not attached to an edge or an element are left in the domain after QMorph has finished.
  If you enable this option, these points are detected and removed in the clean-up phase of QMorph.
  Most people want this, so it's enabled by default.
- Choose a smoother There are several smoothers available, both for lokal smoothing (for each created quad) and global smoothing (after all the quads are created and the domain has been cleaned up).
  There are pros and cons to each of them, but the combined smoother generally yields good results, so it's chosen by default.

#### Triangulation

- Path to Triangle This program is responsible for the creation of the initial triangular mesh. It is created by Jonathan Richard Shewchuk and freely available at http://www.cs.cmu.edu/~quake/triangle.html.
  There are binaries distributed for Linux and Solaris OS, both of which should be automatically set. In case you don't work on one of these platforms, you may have to recompile the program and adjust the path.
- Triangle's options The triangulator has some commandline options you can change:
  - -q number
    Ensures a minimum inner angle the created triangles should have.
    At 20.7 degrees Triangle is guaranteed to finish, but values up to 34 have worked fine yet.
  - -a number
    Ensure a maximum area for each triangle.
    The smaller this number is, the finer the initial triangle mesh is and consequently the quad mesh as well.
    The area calculation is based on the size of your domain.
  - -p
    Informs Triangle about the file format that is used.
    You should always have this option if you want to use triangle to generate the triangle mesh for Qmorph!
  By default the options are -pq34a1L. For more Triangle-tweaks see "Tips and Traps".
- Directory for temporary files To be able to generate the initial triangle mesh, Triangle needs to save some temporary files. By default the path always points to a directory the user is allowed to write to. If you change this, make sure you have correct permissions.

#### Internal

These options are for Qmorph-developers.

If you read the original paper on QMorph, you will know what these are about.

### Tips and Traps

- I want to know more about Triangle's options.

  If you want to see all the command line options and a lot of explanation, change triangle's option in the configuration dialog so that it reads -h and click Start meshing.

  The window that normally shows the statistics about the created triangle mesh now contains all the help Triangle is able to give.

  Just remember to click Cancel after you've read through it, because no triangle mesh has been created.

- I want to change the mesh's general density.

  Change Triangle's area-controlling parameter (the number after the character a in the Triangulation tab of the configuration dialog): the smaller this number is, the more (and smaller) triangles the initial mesh has and the more (and smaller) quadriliterals the resulting mesh will have.

- I want to change the mesh density only in some parts of the domain.

  When you have created the boundaries and are ready to start QMorph, you can add InnerNodes to the domain.

  The initial triangle mesh will be adjusted to contain these nodes, normally by making the triangles smaller in this area.

  Consequently the resulting quad mesh will be finer in this area as well.

- It takes forever for the initial triangle mesh to be created and the window for the mesh statistic is still empty.

  If the minimum inner angle if the triangles in the initial mesh is too big, the program may not finish.

  Note that only for values up to 20.7 it is guaranteed to finish, although values of 34 seem to work well in most cases.

  If you want to abort this step just click Cancel in the statistic window and adjust the Triangulation options before you start Qmorph again.

- When the triangle mesh is loaded, QMorph takes forever and the progress bar doesn't move at all.

  In rare cases this implementation of QMorph is in a situation where it can't improve the mesh although the algorithm is not finished yet. This results in an endless loop.

  Using the Abort-Button (see The statusbar (page 5)) in the main window's statusbar, you can quite easily abort QMorph while it is still running.

  Since QMorph tries to abort as soon as possible this might leave you with an unfinished or even invalid mesh!

  Note that QMorph can take very long when the initial triangle mesh contains many triangles: on an Athlon 1800 computing a mesh with initially 3000 triangles takes up to 5 minutes.

- QMorph has left triangles in the mesh. / I had to abort the program.

  You can use a mesh with both triangles and quadriliterals as input to Qmorph.

  Just select the Don't change Domain option in the configuration dialog.

  Sometimes a mesh that resulted in an endless loop can be finished by just re-running QMorph on it, but of course you can edit the mesh if you see obvious errors like inverted elements: selecting some nodes and moving them around often is enough to help QMorph on it's way.

- I still don't get a result I can use.

  File a bug: Grid3D is work in progress and sometimes new features destabilize existing ones.

  If you think the bug is related to Qmorph, make sure to include the original domain as well as the initial triangle mesh. With these two domains we can try to reproduce the error and improve the program.