next up previous

3 Model Construction and Mesh Generation     continued...

The Delaunay criterion is a method for minimizing the occurrence of obtuse angles in the mesh, yielding elements which have aspect ratios as close to 1 as possible, given the available point set. While the ideas behind Delaunay triangulation are straightforward, the programming is nontrivial and is the primary drawback to this method. Fortunately, there exist several public domain, two-dimensional versions, including one from netlib called sweep2.c from the directory Voronoi and at least one three-dimensional package [46].

Another drawback of the Delaunay method of mesh generation is that it can produce elements that lie within the convex hull of the point set but outside the bounding surface (contour). For example, if one is triangulating a two-dimensional kidney-shaped object, the Delaunay method will construct triangles outside the bounding contour in the concave C-shaped region. One simple way to rid the mesh of unwanted triangles (or tetrahedra) is to supplement the mesh generator with the following algorithm, based on the Gauss-Bonnet (GB) theorem of topology [23]. If one calculates the angles subtended by the points bounding a two-dimensional area about a point P (adding consecutive angles with some sign convention), the sum will equal if P is inside the enclosed contour, if P is on the boundary, and 0 if P lies outside. Thus it is a simple matter to test a questionable element by checking to see if its centroid is inside or outside the contour.