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

Min-Bin Chen () and Chih-Hsueh Yang
Additional contact information
Min-Bin Chen: China University of Technology, Department of Computer Science and Information Engineering
Chih-Hsueh Yang: National Tsing Hua University, Department of Computer Science

A chapter in Computational Mechanics, 2007, pp 331-331 from Springer

Abstract: Abstract 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.

Date: 2007
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-75999-7_131

Ordering information: This item can be ordered from
http://www.springer.com/9783540759997

DOI: 10.1007/978-3-540-75999-7_131

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().