If checko=1 (default), then the program checks that each simplex
has <a href="geom.html#orientation">right-handed orientation</a>.  If checko=2, then the program
checks that each simplex has left-handed orientation.

<p>
This utility performs a series of correctness tests on a meshgenerated for a brep.<a name="checktri_tests">Here is a list of the tests</a> conducted by the 
gmchecktri program.
<ul>
<li>
Each vertex in the simplicial complex must appear in at least one
simplex.
<li>
Each boundary vertex must lie in the 
face of the brep with which it is labeled at
the correct parametric coordinates.
<li>
Every vertex of the brep must have exactly one vertex of the simplicial
complex assigned to it.
<li>
Each simplex must have the correct orientation (if checko&gt;0).
<li>
Each simplex face must lie on the boundary as specified by the
facespec of that simplex face in the mesh.  It is not checked
whether the face actually lies on the boundary, but it is checked
that the vertices of the face all lie on the boundary.

<li>
A simplex facet that lies on an exterior boundary must occur in
exactly one simplex.
<li>
A simplex facet that lies in a region or on an internal boundary
must be adjacent to exactly two simplices in the
complex, and furthermore, these two simplices must lie on opposite
sides of the plane through the facet.
</ul>
These last two conditions are verified using a hashtable on facets.
The <code>gmchecktri</code> program also computes the worst 
<a href="geom.html#aspect_ratio">aspect ratio</a> in the simplicial complex. 
It also computes the globally longest edge length and globally
minimum altitude.

<h2> How the quadtree/octree mesh generator works </h2>

The mesh generator is based on an algorithm due to Mitchell and
Vavasis.  An early version of this algorithm is described in:

<blockquote>
S. A. Mitchell and S. A. Vavasis,
&#8220;Quality mesh generation in three dimensions,&#8221;
Proceedings of the ACM Computational Geometry Conference,
1992, 
pp. 212&#8211;221.
Also appeared as Cornell C.S. TR 92-1267.
</blockquote>

A more recent version of the algorithm is described by the
following two papers by 
Mitchell and Vavasis:

<ul>
<li>
&#8220;Quality mesh generation in higher dimensions,&#8221; 
<a href="http://www.siam.org/journals/sicomp/sicomp.htm"><em>SIAM J. Computing</em></a>, to appear.<li>
&#8220;An aspect ratio bound for triangulating 
a mesh cut by an affine set,&#8221;
Proceedings of the ACM Computational Geometry Conference,
1996.  See the 
<a href="ftp://ftp.cs.cornell.edu/pub/vavasis/papers/asp9.ps.Z">preprint</a>
online in compressed postscript format.
</ul>

The algorithm is a quadtree/octree algorithm, meaning that it covers the brep
with a large box and then subdivides the box into 2<sup><em>d</em></sup> subboxes, where
<em>d</em> is the dimension of the brep (either 2 or 3). 
The subdivision into boxes continues until no box is crowded. A
box is said to be <em>crowded</em> in the following situation.  A neighborhood
of the box <em>b</em> called ex(<em>b</em>) is constructed; 
this is a neighborhood in the <em>l</em><sup>1</sup> norm.  The
size of the neighborhood is given by
the
<a href="#expansion">expansion factor</a>
multiplied by the size of the box.
 Let <em>f</em> be the lowest-dimensional
face of the brep in ex(<em>b</em>).  
If there is more than one such <em>f</em>, or if
there is any other brep face <em>g</em> in ex(<em>b</em>) 
such that <em>g</em> is not a
superface of <em>f</em>, then <em>b</em> 
is crowded, else it is not crowded.

<p>
The splitting of boxes takes place in <em>d</em>+1 
phases.  In phase 0, boxes
are split if they are crowded and if ex(<em>b</em>) 
contains a 0-dimensional
brep face (a vertex).  But if ex(<em>b</em>) 
does not contain a vertex, then <em>b</em>
is made idle until the next phase.  The expansion factors vary
from phase to phase.

<p>
During splitting for separation, the size control and curvature control
conditions are also checked.  

<p>
The operation in the preceding paragraphs is called <em>splitting for
separation</em> 
and there are <em>d</em>+1 phases of this.  There are also <em>d</em>+1
phases of <em>alignment</em> which are interleaved with the
separation phases.  For each phase <em>k</em>, the separation precedes
the alignment. The alignment
part of phase <em>k</em> operates only
on active boxes that have a <em>k</em>-dimensional face
of the brep in ex(<em>b</em>).  
Because of the separation part of the phase, 
for each such box there is unique brep <em>k</em>-face 
to which it is associated.
The box is said to lie in the <em>orbit</em> of this face.  The orbits
are processed independently of one another in the alignment phase.

<p>
Alignment works as follows. Let <em>f</em> 
be the face of the brep of dimension <em>k</em>,
and suppose we are processing the orbit of <em>f</em>.
For a box <em>b</em> in the orbit, 
some subface <em>c</em>
determined to be the close subface to <em>f</em>.  Then
<em>b</em> is further split so that 
boxes that also contain <em>c</em> 
are the same size as <em>b</em> or larger.
Once this condition holds for <em>b</em>, an apex 
is selected on the face of the
brep and near the close subface.  This apex will end up as a vertex
of the triangulation.  Once an apex is assigned, the active box
is changed to a finished box.  This process is carried out for
every box in the orbit.

<p>
During the separation phase, the boxes do not communicate with
one another.  In particular, there is no rule enforced concerning
the size of adjacent boxes (sometimes called a <em>balance 
condition</em>).
Nonetheless, it is proved in the above papers
that there is a bound
on how disparate the size of two adjacent can be.  
(This bound depends on the sharpest angle of the input domain and
on the local variation in the size and curvature control function.)

<p>
After all <em>d</em>+1 
phases of alignment, there are no active boxes remaining
and all boxes are finished.  Furthermore, there are finished boxes
of all possible dimensions 0 to <em>d</em>, 
and each finished box is linked
to the boxes sitting on its surface via pointers.  The finished boxes
are now triangulated recursively; a <em>k</em>-dimensional 
box is triangulated
by taking the convex hull of its apex with the simplices that triangulate
its (<em>k</em>&#8722;1)-dimensional surface boxes.  

<p>
There are many aspects of the algorithm omitted from this overview:
boxes are duplicated if the intersection of ex(<em>b</em>) 
and the brep hasmore than one component,a table is made of all intersections between quadtree entities
and model entities, etc.

<p>
The Mitchell-Vavasis algorithm is not the first to use quadtrees
for mesh generation.  See for instance
<blockquote>
M. A. Yerry and M. S. Shephard, &#8220;Automatic three-dimensional mesh generation
by the modified-octree technique,&#8221; Int. J. Numer. Meth. Eng. 20 (1984)
1965&#8211;1990.
</blockquote>
The Mitchell-Vavasis work is most directly related to 2-dimensional
quadtree work by
<blockquote>
M. Bern, D. Eppstein and J. R. Gilbert, &#8220;Provably good mesh generation,&#8221;
Proc. 31st IEEE Symp.Found of Computer Sci. (1990) 231&#8211;241.
</blockquote>
In particular, the two theoretical properties of the MV algorithm
described below were first established for the two-dimensional
case by this paper.

<a name=guarantees></a>
<h2> Theoretical guarantees</h2>

The bound on the size of adjacent boxes mentioned
above is the basis for a
theoretical result concerning the Mitchell-Vavasis algorithm which is
as follows.  The worst-case aspect ratio of any simplex produced by
the algorithm is within a constant factor of optimal for the given
domain.  Unfortunately, the constant factor is not known explicitly
and could be extremely large.  The Mitchell-Vavasis algorithm has a
second theoretical property: among all possible triangulations of the
domain with bounded aspect ratio, the MV algorithm produces the
triangulation with the fewest number of simplices up to a constant
factor.  Again, the constant factor is presumably very large.

<p>
The actual implementation QMG 2.0 does not have the same mathematical
guarantee as the algorithm in the
papers for several reasons.  First, the warping distances
derived in papers (which are extremely small numbers)
have not implemented; instead, some heuristics
have implemented. It is not known whether these heuristics work in
every case.  If the heuristic fails, you will end up with a mesh
with bad aspect ratio.

<p>
Roundoff error is another
reason why the theoretical guarantees may fail.
Roundoff error can cause the mesh generator
to fail in almost any manner, including sending it into an
infinite loop.  If you
suspect that you have a problem with roundoff, try changing the
<a href="#tolkey">tol</a> setting.

<p>
A third source of difficult is the geometric routines for intersecting
rays with curved patches.  If these routines fail, then the mesh
generator may go into an infinite loop.  In current research with
<a href="http://cam.cornell.edu/jonsson/">G.&nbsp;J&#243;nsson</a>,
we have developed an intersection routine that seems to be
very robust.

<p>
A fourth source of difficulty is curvature in the boundary.  The
routine currently uses heuristics to detect sharp curves; these
heuristics may fail to catch a sharp curve.  In this case, an
incorrect mesh or a mesh with elements of poor aspect ratio 
may be generated.  The cause of the difficulty 
is that computing the maximum curvature of a parametric polynomial
patch requires (expensive) solution of  high-degree polynomial 
systems and is probably impractical for QMG.

<p>
Curvature can cause some subtler problems as well.  If the curvature
tolerance is fairly high and the expansion factors are small,
then it is theoretically possible for the mesh generator to
make a simplex with arbitrarily poor aspect ratio.

<h2> Performance of the mesh generator </h2>

The performance of a mesh generator is measured in three ways: (1)
how long does it take?  (2) what is the aspect ratio of the elements?
(3) how many simplices are generated?
These three measures are sometimes correlated for the quadtree/octree
algorithm, i.e., when one is bad, so are all three.
Naturally, the worst cases in terms of performance are domains
with many faces and many sharp angles.
The mesh generator works better when there are no sharp angles in
the domain. <p>
It works especially well in the case that many of the brep faces are
aligned with the coordinate axes.
A dramatic example of this axis alignment behavior is provided by test8 in
the test set.  This test involves meshing a cube.  First, the unit cube
is meshed in its natural orientation, then it is reoriented randomly
and triangulated again.  The running time
is  less than a second
for the natural orientation versus about 2 seconds
the rotated orientation (Tcl/Tk QMG running on a Pentium Pro).
The number of vertices is 27 versus 228.
The number of simplices is 48 versus 867.  
The aspect ratio is 2.7 versus 78.6.

<p>
To tune the performance, then you can slightly
adjust the tradeoff between mesh quality and number of elements.  
In particular, by decreasing the curvature tolerance and increasing
the expansion factors, you can sometimes improve the mesh quality
(but more elements will be generated).


<h2><a name="gui"> The GUI for the mesh generator</a> </h2>

As the generator runs,
a panel appears on the screen showing
its progress.  This panel can be suppressed with the 
<a href="#showgui">showgui</a>
keyword
option.
The panel is updated once every 1 or 2 seconds.
It displays the number of active boxes (which goes up
and down as the algorithm proceeds; at the end of phase 3 separation
it drops suddenly to zero), 
the number of finished boxes (which goes
up monotonically
during the alignment stages, and goes down monotonically 
to zero during 
the triangulation phase at the end), the number of vertices (which
goes up monotonically during the <em>d</em>+1 phases and then drops
once at the very end of the algorithm), and the number of simplices
(which goes up monotonically during the triangulation phase).

<p>
The control panel also shows the current operation.  The
order of operations is: Phase 0 separation, phase 0 alignment,
phase 1 separation, phase 1 alignment, phase 2 separation,
phase 2 alignment, phase 3 separation (if the brep is three-dimensional),
phase 3 alignment (if the brep is three-dimensional), triangulation.

<p>
During the execution of the mesh generator, a button labeled
<strong>Cancel</strong>
appears in the GUI; the user may press this to terminate
the mesh generation.  Pressing this button terminatesmesh generation.  Sometimes the button does not
respond immediately.  The cancel
button is polled only when the GUI screen is updated, so if the GUI panel
freezes because of some bug in the program, the cancel button won't
work either.  

<p>
When the mesh generation terminates, a second button labeled
<strong>Dismiss</strong> appears 
in the panel.  This button deletes the panel.

<p>
The GUI display is controlled by <code>gm_meshgui.m</code>
in matlab and
<code>gm_meshgui.tcl</code> 
in Tcl/Tk and hence is fairly easy to customize.


<hr>
<p>
This documentation is written by 
<a href="http://www.cs.cornell.edu/home/vavasis/vavasis.html">Stephen A. 
Vavasis</a> and is
copyright &#169;1999 by <a href="http://www.info.cornell.edu/CUHomePage.html">Cornell 
University</a>.
Permission to reproduce this documentation is granted provided this
notice remains attached.  There is no warranty of any kind on
this software or its documentation.  See the accompanying file
<a href="copyright.html">'copyright'</a>
for a full statement of the copyright.
<p>
<address>
Stephen A. Vavasis, Computer Science Department, Cornell University,
Ithaca, NY 14853, vavasis@cs.cornell.edu
</address>
</body>
</html>