Triangle removes extraneous triangles from holes and concavities before the refinement stage. This presents no problem for the refinement algorithm; the requirement that no segment be encroached and the Delaunay property together ensure that the circumcenter of every triangle lies within the mesh. (Roundoff error might perturb a circumcenter to just outside the mesh, but it is easy to identify the conflicting edge and treat it as encroached.) An advantage of removing triangles before refinement is that computation is not wasted refining triangles that will eventually be deleted.

A more important advantage is illustrated in Figure 13. If extraneous triangles remain during the refinement stage, overrefinement can occur if very small features outside the object being meshed cause the creation of small triangles inside the mesh. Ruppert suggests solving this problem by using the constrained Delaunay triangulation, and ignoring interactions that take place outside the region being triangulated. Early removal of triangles provides a nearly effortless way to accomplish this effect. Segments that would normally be considered encroached are ignored (Figure 13, right), because encroached segments are diagnosed by noticing that they occur opposite an obtuse angle in a triangle.

Another determinant of the number of triangles in the final mesh is
the order in which bad triangles are split, especially when a strong
angle constraint is used. Figure 14 demonstrates
how sensitive the refinement algorithm is to the order.
For this example with a 33^{o} minimum angle, a heap
of bad triangles indexed by their smallest angle confers a 35% reduction
in mesh size over a first-in first-out queue.
(This difference is
typical for large meshes with a strong angle constraint, but
thankfully disappears for small meshes and small constraints.)
The discrepancy probably occurs because circumcenters of
very bad triangles are likely to split more bad triangles than circumcenters
of mildly bad triangles.
Unfortunately, a heap is slow for large meshes, especially when small area
constraints force all of the triangles into the heap.
Delaunay refinement usually takes *O(n)* time in practice, but use of
a heap increases the complexity to *O(n* log *n)*.

Triangle's solution, chosen experimentally, is to use
64 FIFO queues, each representing a different interval of angles.
It is counterproductive (in practice) to order
well-shaped triangles by their worst angle,
so one queue is used for well-shaped but too-large
triangles whose angles are all roughly larger than 39^{o}.
Triangles with smaller angles are partitioned among the remaining queues.
When a bad triangle is chosen for splitting, it is taken from the
``worst'' nonempty queue. This method yields meshes comparable with
those generated using
a heap, but is only slightly slower than using a single queue.
During the refinement phase, about 21,000 new vertices are generated per second
on a DEC 3000/700. These vertices are inserted
using the incremental Delaunay algorithm, but are inserted much more quickly
than Table 1 would suggest because a triangle's circumcenter can
be located quickly by starting the search at the triangle.

Mon Aug 12 10:28:49 EDT 1996