A Parallel 3D Delaunay Mesh Generation Method Based on Affected Zone

Mesh generation plays a critical role in scientific modeling and computation. It is also an essential component in finite difference method (FDM), finite element method (FEM), and finite volume method (FVM). In the analysis of complex problems in scientific and engineering domains, it is not unusual to require meshes of tens (or hundreds) of thousands of mesh points. Such large amount of computation requirement makes the mesh generation a problem on the time and storage of a single processor. Therefore, we need the help of parallel computer to generate the mesh of very large data set. Meshes can be classified into two categories according to the connectivity between mesh points: structured vs. unstructured. In general, generation of unstructured meshes is more sophisticated, and more difficult to parallelize, because the structure of the mesh and the computation on the mesh are usually irregular and may depend on input data or rentime-computed values. Dalaunay triangulation is a famous unstructured mesh. The mas-min angle criterion of Delaunay triangulation makes the triangulation a well-shaped mesh. (Note: The max-min angle criterion is that the minimum angle of all the triangles is the maximized.) In this work, we design and implement the algorithm of parallel 3D Delaunay triangulation. In the literaures, there are two strategies in parallel Delaunay triangulation: parallelize the sequential algorithm and parallelize the merge of the sub-problem. J. Kohout proposed algorithms for the parallel computers with shared memory. N. Chrisochoides parallelize the Boyer-Watson kernel. There algorithms use the first kind strategy. In the second strategy, they can either marriage before or after the sub-problem triangulation being created. There are two methods for “marriage-before” strategy: generate the interface triangulation first and specify the interface face first. The “marriange-after” is used to parallel generate Delaunay triangulation. This method was based on domain decomposition with marriage-after strategy. To generate large mesh, the main overhead in memory lies in the communication of processors to generate the interface triangulation. At the merge phase, the neighbor triangulation that would be changed in the sub-domain may not be the full sub-domain triangulation. In this paper, we devised an algorithm which finds the neighbor triangulations (called affect zone) for 3D triangulation and the associated mathematicalproperties in O(n) time, where n is the number of points assigned to a processor. With the aid of affected zone, the data communications between processors is about 20-30% of the block triangulation. In the experiments, this method already triangulated IM 3D points onf a PC-cluster. To simulate the real point sets, we also test our method on uniform and non-uniform distributions and report the detailed results.