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
The main ideas for aCute have been discussed in the following research papers:
Hale Erten, Alper Üngör,Quality Triangulations with Locally Optimal Steiner Points, SIAM Journal of Scientfic Computing, Vol.31, No.3: 2103-2130 (2009). [pdf]
Abstract: We propose two novel ideas to improve the performance of Delaunay refinement
algorithms which are used for computing quality triangulations. The first idea is
an effective use of the Voronoi diagram and unifies previously suggested Steiner
point insertion schemes (circumcenter, sink, off-center) together with a new
strategy. The second idea is the integration of a new local smoothing strategy
into the refinement process. These lead to two new versions of Delaunay refinement,
where the second is simply an extension of the first. For a given input domain
and a constraint angle $\alpha$, Delaunay refinement algorithms aim to compute
triangulations that have all angles at least $\alpha$. The original Delaunay
refinement algorithm of Ruppert is proven to terminate with size-optimal quality
triangulations for $\alpha \le 20.7^\circ$. In practice, the original and the
consequent Delaunay refinement algorithms generally work for $\alpha \le 34^\circ$
and fail to terminate for larger constraint angles. Our algorithms provide the
same theoretical guarantees as the previous Delaunay refinement algorithms.
The second of the proposed algorithms generally terminates for constraint angles
up to $42^\circ$. Experiments also indicate that our algorithm computes significantly
(about by a factor of two) smaller triangulations than the output of the previous
Delaunay refinement algorithms. Moreover, the new algorithms are experimentally
shown to outperform the previous algorithms even in the existence of additional
constraints, such as the maximum area triangle constraint which is commonly used
for computing uniform triangulations.
Hale Erten, Alper Üngör, Computing Triangulations without Small and Large Angles, International Symposium on Voronoi Diagrams (ISVD) 2009.
Abstract: We propose a heuristic method for computing Steiner triangulations without small and large angles.
Given a two-dimensional domain,
a minimum angle constraint alpha and a maximum angle constraint gamma, our method
computes a triangulation of the domain such that all angles are in the interval [alpha, gamma].
Previously known Steiner triangulation methods generally
consider a lower bound alpha only, and claim a trivial upper bound
(gamma = 180 - 2*alpha).
Available software work for alpha as high as 34 degrees (implying a gamma value of 112 degrees),
However, they fail consistently whenever larger alpha and/or smaller gamma values are desired.
Experimental study shows that the proposed method works for alpha as high as 41 degrees,
and gamma as low as 81 degrees.
This is also the first software for computing high quality acute and non-obtuse triangulations of complex geometry.
Note that, aCute also relies on the previous research cited by the Jonathan Shewchuk's Triangle research credit page. Please refer to that page for more information on Delaunay refinement algorithm.