We have investigated many algorithms for representing, constructing, and manipulating surface meshes. Today, we’re going to consider a slightly different problem. Suppose that we want to build a quality mesh for use in finite element applications. How can we do this?
There is a fairly extensive literature on this topic. First, we have to decide what we mean by “quality”. Then we need to figure out how to actually build such a mesh. We will only scratch the surface of this area.
One of the more popular approaches for producing high quality planar meshes is based on Delaunay refinement. Namely, we want to compute a constrained Delaunay triangulation of the domain and then iteratively add points until the mesh is “good”.
Focus particularly on the first 3 sections.
Here are two useful survey articles that cover the broader problem of mesh generation.
S. J. Owen. A survey of unstructured mesh generation technology. Proceedings of the 7th Intl. Meshing Roundtable, October 1998. [PS.gz]
M. Bern and D. Eppstein. Mesh generation and optimal triangulation. Computing in Euclidean Geometry, 2nd ed., 1995, pp. 47–123. [PDF]
One of the fundamental early results in the area of Delaunay refinement was the algorithm developed by Ruppert. It was probably the first method with strong theoretical guarantees that also worked well in practice.
Triangle is a nice — and freely available — implementation of a Delaunay refinement algorithm. You can grab the software, and read about the implementation in this paper: