carrier image

Parallel 2D Graded Guaranteed Quality Delaunay Mesh Refinement

Chernikov, Andrey N. and Nikos P. Chrisochoides

Proceedings, 14th International Meshing Roundtable, Springer-Verlag, pp.505-517, September 11-14 2005


14th International Meshing Roundtable
San Diego, CA, USA
September 11-14, 2005

Department of Computer Science
College of William and Mary

We develop a theoretical framework for constructing guaranteed quality Delaunay meshes in parallel for general two-dimensional geometries. This paper presents a new approach for constructing graded meshes, i.e., meshes with element size controlled by a user-defined criterion. The sequential Delaunay refinement algorithms are based on inserting points at the circumcenters of triangles of poor quality or unacceptable size. We call two points Delaunay-independent if they can be inserted concurrently without destroying the conformity and Delaunay properties of the mesh. The contribution of this paper is three-fold. First, we present a number of local conditions of point Delaunay-independence, which do not rely on any global mesh metrics. Our sufficient conditions of point Delaunay-independence allow to select points for concurrent insertion in such a way that the standard sequential guaranteed quality Delaunay refinement procedures can be applied in parallel to attain the required element quality constraints. Second, we prove that a quadtree, constructed in a specific way, can be used to guide the parallel refinement, so that the points, simultaneously inserted in multiple leaves, are Delaunay-independent. Third, by experimental comparison with the well-known guaranteed quality sequential meshing software, we show that our method does not lead to overrefinement, while matching its quality and allowing for code re-use.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article