Andrey Chernikov's Home Page

Parallel Generalized Delaunay Mesh Refinement

Summary	We generalize the existing two-dimensional (2D) and three-dimensional (3D) Delaunay refinement algorithms along with theoretical proofs of mesh quality in terms of element shape and mesh gradation. Existing algorithms are constrained by just one or two specific positions for the insertion of a Steiner point inside a circumscribed disk of a poorly shaped element. We derive an entire 2D or 3D region for the selection of a Steiner point (i.e., infinitely many choices) inside the circumscribed disk. The use of the selection disk for the construction of boundary conformal meshes. (Left) An MRI scan showing a cross-section of a body. (Right) A zoom-in of the selected area containing an artery: the inside is white, the outside has different shades of gray and the black zone is an approximate boundary between these regions. The standard Delaunay refinement algorithm would insert the circumcenter c. However, in order to construct a mesh which conforms to the boundary, another point (p) would be a better choice. We develop a novel theory which extends both the 2D and the 3D Generalized Delaunay Refinement methods (see 1) for the concurrent and mathematically guaranteed independent insertion of Steiner points. Previous parallel algorithms are either reactive relying on implementation heuristics to resolve dependencies in parallel mesh generation computations or require the solution of a very difficult geometric optimization problem (the domain decomposition problem) which is still open for general 3D geometries. Our theory solves both of these drawbacks. Challenges in parallel Delaunay refinement. (Left) Concurrent insertion of p_8 and p_9 leads to a non-conformal mesh. (Right) Concurrent insertion of p_8 and p_10 leads to a non-Delaunay mesh. The buffer zone of an octree leaf which is the solid white box in the center. Using our generalization of both the sequential and the parallel algorithms (see 1 and 2) we implemented prototypes of practical and efficient parallel generalized guaranteed quality Delaunay refinement codes for both 2D and 3D geometries using existing state-of-the-art sequential codes for traditional Delaunay refinement methods. On a heterogeneous cluster of more than 100 processors our implementation can generate a uniform mesh with about a billion elements in less than 5 minutes. Even on a workstation with a few cores, we achieve a significant performance improvement over the corresponding state-of-the-art sequential 3D code, for graded meshes. The meshes of the pipe cross-section model and the key model overlayed by the quadrees.
Related papers	Three-Dimensional Semi-Generalized Point Placement Method for Delaunay Mesh Refinement. Andrey Chernikov and Nikos Chrisochoides. 16^th International Meshing Roundtable, pp. 25-44. Seattle, WA, October 2007. Generalized Delaunay Mesh Refinement: From Scalar to Parallel. Andrey Chernikov and Nikos Chrisochoides. 15^th International Meshing Roundtable, pp. 563-580. Birmingham, AL, September 2006. Parallel 2D Graded Guaranteed Quality Delaunay Mesh Refinement. Andrey Chernikov and Nikos Chrisochoides. 14^th International Meshing Roundtable, pp. 505-517. San Diego, CA, September 2005. Parallel Graded Generalized Delaunay Mesh Refinement. Andrey Chernikov and Nikos Chrisochoides. 16^th Annual Fall Workshop on Computational Geometry. Northampton, MA, November 2006. Parallel Guaranteed Quality Planar Delaunay Mesh Generation by Concurrent Point Insertion. Andrey Chernikov and Nikos Chrisochoides. 14^th Annual Fall Workshop on Computational Geometry, pp. 55-56. Cambridge, MA, November 2004. Parallel Guaranteed Quality Delaunay Uniform Mesh Refinement. Andrey Chernikov and Nikos Chrisochoides. SIAM Journal on Scientific Computing (Vol. 28, No. 5, pp. 1907-1926), November 2006.

Summary

We generalize the existing two-dimensional (2D) and three-dimensional (3D) Delaunay refinement algorithms along with theoretical proofs of mesh quality in terms of element shape and mesh gradation. Existing algorithms are constrained by just one or two specific positions for the insertion of a Steiner point inside a circumscribed disk of a poorly shaped element. We derive an entire 2D or 3D region for the selection of a Steiner point (i.e., infinitely many choices) inside the circumscribed disk.

The use of the selection disk for the construction of boundary conformal meshes. (Left) An MRI scan showing a cross-section of a body. (Right) A zoom-in of the selected area containing an artery: the inside is white, the outside has different shades of gray and the black zone is an approximate boundary between these regions. The standard Delaunay refinement algorithm would insert the circumcenter c. However, in order to construct a mesh which conforms to the boundary, another point (p) would be a better choice.
We develop a novel theory which extends both the 2D and the 3D Generalized Delaunay Refinement methods (see 1) for the concurrent and mathematically guaranteed independent insertion of Steiner points. Previous parallel algorithms are either reactive relying on implementation heuristics to resolve dependencies in parallel mesh generation computations or require the solution of a very difficult geometric optimization problem (the domain decomposition problem) which is still open for general 3D geometries. Our theory solves both of these drawbacks.

Challenges in parallel Delaunay refinement. (Left) Concurrent insertion of p_8 and p_9 leads to a non-conformal mesh. (Right) Concurrent insertion of p_8 and p_10 leads to a non-Delaunay mesh.

The buffer zone of an octree leaf which is the solid white box in the center.
Using our generalization of both the sequential and the parallel algorithms (see 1 and 2) we implemented prototypes of practical and efficient parallel generalized guaranteed quality Delaunay refinement codes for both 2D and 3D geometries using existing state-of-the-art sequential codes for traditional Delaunay refinement methods. On a heterogeneous cluster of more than 100 processors our implementation can generate a uniform mesh with about a billion elements in less than 5 minutes. Even on a workstation with a few cores, we achieve a significant performance improvement over the corresponding state-of-the-art sequential 3D code, for graded meshes.

The meshes of the pipe cross-section model and the key model overlayed by the quadrees.

Related papers

Three-Dimensional Semi-Generalized Point Placement Method for Delaunay Mesh Refinement. Andrey Chernikov and Nikos Chrisochoides. 16^th International Meshing Roundtable, pp. 25-44. Seattle, WA, October 2007.

Generalized Delaunay Mesh Refinement: From Scalar to Parallel. Andrey Chernikov and Nikos Chrisochoides. 15^th International Meshing Roundtable, pp. 563-580. Birmingham, AL, September 2006.

Parallel 2D Graded Guaranteed Quality Delaunay Mesh Refinement. Andrey Chernikov and Nikos Chrisochoides. 14^th International Meshing Roundtable, pp. 505-517. San Diego, CA, September 2005.

Parallel Graded Generalized Delaunay Mesh Refinement. Andrey Chernikov and Nikos Chrisochoides. 16^th Annual Fall Workshop on Computational Geometry. Northampton, MA, November 2006.

Parallel Guaranteed Quality Planar Delaunay Mesh Generation by Concurrent Point Insertion. Andrey Chernikov and Nikos Chrisochoides. 14^th Annual Fall Workshop on Computational Geometry, pp. 55-56. Cambridge, MA, November 2004.

Parallel Guaranteed Quality Delaunay Uniform Mesh Refinement. Andrey Chernikov and Nikos Chrisochoides. SIAM Journal on Scientific Computing (Vol. 28, No. 5, pp. 1907-1926), November 2006.