Very often in computer graphic design, differential equations problems, and numerical analysis, it is necessary to triangulate points in a given problem region. We would like to be able to, given any set of points, triangulate into a high-quality mesh. By high-quality, we mean a triangulation with relatively uniform triangles. That is, we would like to exclude triangles with extremely small (and large) angles. Furthermore, we want to be able to make specific customizations to the final result. For example, we may wish to have non-convex edges, specified holes within the triangulation, or request smaller, more dense triangles in one region as opposed to another. To solve the problem, we chose to implement an algorithm presented by L. Paul Chew, in his paper, "Guaranteed High-quality Mesh Generation for Curved Surfaces."
The Algorithm:
In his paper, Chew first presents an algorithm for the two dimensional case, then gives the necessary adaptation for three dimensions. The user is allowed to input criteria for well-shaped and well-sized triangles. Typically, a triangle would be well-shaped if it had no angles less than a specified minimum (or greater than a specified maximum). Whether or not a triangle is well-sized may depend upon its location in the point set. As we have said, we would like to exert some sort of control over the density of triangles in various regions of the problem space.
The two dimensional algorithm begins with finding the constrained delaunay triangulation (cdt) of the point set. From there, each triangle in the cdt is graded on shape and size according to the user-input criteria.