aCute
A premium quality meshing software.

Implemented and licensed at the University of Florida, Gainesville
Partially funded by an NSF CAREER Award and an NSF Regular Grant
Contact: Alper Ungor, CISE Department, University of Florida, Gainesville, FL, 32611 ungoratcisedotufldotedu

Algorithmic Approach Comparison


aCute

Triangle

Our software employs an advancing front approach, inserts locally optimal Steiner points, first near the boundary of the domain.

The original Triangle software employed Ruppert's circumcenter insertion algorithm which is not an advancing front approach.

Below you see an execution of each algorithm/software interrupted after certain number of Steiner point insertion (specified). Desired smallest angle is 34 degrees. Bad triangles are marked red. Initial triangulations are the same.




The Idea

Here, a brief discussion about the idea which helps us to generate premium quality triangulations by using Delaunay refinement as the basis

.

Locally Optimal Steiner Points

Given an ordered pair of points (p,q) in the input domain, consider the circle that goes through p and q, of radius |pq| / (2*sin(alpha)), whose center is on the right side of the directed edge pq. The disk bounded by this circle is called the petal of pq, denoted by petal(pq). Based on this definition, we choose from four different types of points to insert a Steiner point which can be simply shown as follows:

Find a point x inside the (shaded disk) petal of pq that is furthest away from all existing vertices. Such a point can be on a Voronoi edge (top) or a Voronoi vertex (bottom). Type I: on the dual of pq. Type II: on a Voronoi edge other than the dual of pq. Type III: a circumcenter other than that of pqr. Type IV: the circumcenter of pqr. Note that our approach nicely unifies the previously known Steiner point insertion techniques: circumcenter (Type V) of Chew and Ruppert, off-center (Type I) of Ungor, and sink (Type III) of Edelsbrunner and Guoy together with a new one (Type II).

Unlike the previous Delaunay refinement methods, we use circumcenters less frequently. This allows us to reach better minimum angle quality.

Algorithm


Compute the Delaunay triangulation of the input
while there exists a bad triangle pqr with shortest edge pq
      insert a point x is in petal(pq) of its shortest edge pq
         that is furthest from all existing vertices

Refinement and Relocation

Relocating a free vertex of a bad triangle pqr to the intersection of the petals of the link of a = r.

Algorithm


Compute the Delaunay triangulation (DelTri) of the input
Let P denote the maintained point set
while there exists a bad triangle pqr in DelTri(P) with shortest edge pq
      relocated := False
      for each free vertex a of pqr
          if K = intersection of petal(xy), where xy is in link(a), is not empty set
           and there exists a b in K such that all triangles of star(b) in the DelTri(P+{b}-{a}) are good
          then
              delete a; insert b; relocated:=True; break;
      endfor
      if relocated == False then
          insert a point x is in petal(pq) of the bad triangle's shortest edge pq
            that is furthest from all existing vertices
endwhile

Triangulations without Small and Large Angles

Feasible region slice is the intersection of [alpha, gamma]-crescent, alpha- wedge, and gamma-slab. A point x inside this region that is furthest away from all existing vertices is chosen as a refinement point (left). A bad triangle pqa is fixed by relocating one of its vertices a into b which is a point in the intersection (shaded) of the [alpha, gamma]-slices of the edges on the link of a (right).

Algorithm


Compute the Delaunay triangulation (DelTri) of the input
Let P denote the maintained point set
while there exists a bad triangle pqr in DelTri(P) with shortest edge pq
      relocated := False
      for each free vertex a of pqr
         forevery edge xy on the link of a
           Compute alpha-wedge(xy)
           Compute gamma-slab(xy)
           Compute [alpha, gamma]-crescent(xy)
           Compute [alpha, gamma]-slice(xy)
        endfor
        if K = intersection of [alpha, gamma]-slice(xy), where xy is in link(a), is not empty set
           and there exists a b in K such that all triangles of star(b) in the DelTri(P+{b}-{a}) are good
        then
            delete a; insert b; relocated:=True; break;
      endfor
      if relocated == False then
          insert a point x is in [alpha, gamma]-slice(xy) of the bad triangle's shortest edge pq
            that is furthest from all existing vertices
endwhile