Parallel volume meshing using face removals and hierarchical repartitioning

doi:10.1016/S0045-7825(98)00300-4

Computer Methods in Applied Mechanics and Engineering

Volume 174, Issues 3–4, 25 May 1999, Pages 275-298

https://doi.org/10.1016/S0045-7825(98)00300-4 Get rights and content

Abstract

Parallel unstructured three-dimensional mesh generation is a challenging problem for many reasons, the most obvious coming from the complexity of ‘partitioning’ the problem such that meshing is load balanced at all times. In this paper, a parallel volume meshing procedure whose input is a surface mesh (distributed or not) is presented. In order to help drive the parallel execution, a distributed octree is built considering the surface mesh and meshing size attributes. The tree is partitioned in parallel using the Recursive Bisection methodology and ‘portions of space’ are handed out to processors for meshing. Volume meshing operates on two techniques: (i) octant template meshing for interior octants; and (ii) face removals (advancing front) to fill the space in between the surface mesh and the ‘templated’ octants. Due to the mesh being distributed, domains corresponding to the interfaces of the initial partitioning are left unmeshed. To complete volume meshing, it is necessary to repartition the interface domains. A hierarchical repartitioning procedure has been developed to effectively mesh face, edge, and vertex interfaces. It is the focus of this paper.

References (24)

M. Saxena et al.
Parallel FEM algorithms based on recursive spatial decomposition I. Automatic mesh generation
Comput. Struct.
(1992)
M.W. Beall et al.
A general topology-based mesh data structure
Int. J. Numer. Methods Engrg.
(1997)
A. Bowyer
Computing dirichlet tessellations
The Computer J.
(1981)
N. Chrisochoides et al.
Task parallel implementation of the Bowyer—Watson algorithm
H.L. de Cougny
Parallel unstructured distributed three-dimensional mesh generation
H.L. de Cougny et al.
Parallel unstructured grid generation
H.L. de Cougny et al.
Parallel three-dimensional mesh generation on distributed memory MIMD computers
Engrg. Comput.
(1996)
R. Van Drieeche et al.
Load balancing computational fluid dynamics calculations on unstructured grids
C. Farhat et al.
Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics
Int. J. Numer. Methods Engrg.
(1993)
A. Gaither et al.
A paradigm for parallel unstructured grid generation

J. Galtier et al.

Prepartitioning as a way to mesh subdomains in parallel

J. JaJa

An introduction to Parallel Algorithms

(1992)

Cited by (36)

Adaptive surface mesh remeshing based on a sphere packing method and a node insertion/deletion method
2021, Applied Mathematical Modelling
Citation Excerpt :
However, this method requires complicated calculations, such as the intersection of fronts, projection of local areas, and so on. Although Rassineux [21] and Cougny and Shephard [22] have made some acceleration strategies, it is still very time-consuming. The main idea of mapping methods[23–25] is to restore the parametric information of a surface mesh, then generate a mesh in the parametric space of the surface mesh, and finally map it back to the surface mesh.
Triangular mesh has been a prevalent form of 3D model representation in various areas ranging from modeling to finite element analysis due to their simplicity and flexibility. In the paper, we present a triangular mesh remeshing method based on a sphere packing method and a node insertion/deletion method for surface meshes. First, a new set of nodes are generated on the surface mesh via a sphere packing method and added to the original surface mesh. Then, original nodes are deleted through some basic operations. Finally, the mesh is optimized by edge flipping. To regenerate an adaptive mesh, we consider some geometric features to calculate a size field and record and smooth it with an octree background grid. The proposed method remeshes the surface mesh without projection of local areas, the intersection of fronts, Lloyd relaxation, and other complicated calculations, and the proposed method can generate a high-quality mesh without dependence on the quality of the original mesh, which make the method efficient and effective.
Scalable generation of large-scale unstructured meshes by a novel domain decomposition approach
2018, Advances in Engineering Software
Citation Excerpt :
The cavity zones are filled up to an order of meshing non-buffer zones at first, and then meshing face-related, line-related and point-related buffer zones successively. Desirable scalability performance was reported when 32 processes were executed [13]; however, it is not clear how this algorithm would perform when more computing resources are invested. Löhner [2,14] presented two parallel advancing front techniques (AFT) in which the meshing stage of subdomain interiors takes the precedence to that for interfaces.
A parallel algorithm is proposed for scalable generation of large-scale tetrahedral meshes. The key innovation is the use of a mesh-simplification based domain decomposition approach. This approach works on a background mesh with both its surface and its interior elements much larger than the final elements desired, and decomposes the domain into subdomains containing no undesirable geometric features in the inter-domain interfaces. In this way, the most time-consuming part of domain decomposition can be efficiently parallelized, and other sequential parts consume reasonably limited computing time since they treat a very coarse background mesh. Meanwhile, the subsequent parallel procedures of mesh generation and improvement are most efficient because they can treat individual subdomains without compromising element quality. Compared with published state-of-the-art parallel algorithms, the developed parallel algorithm can reduce the clock time required by the creation of one billion elements on 512 computer cores from roughly half an hour to less than 4 minutes.
Thread-parallel mesh improvement using face and edge swapping and vertex insertion
2018, Computational Geometry: Theory and Applications
The purpose of this paper is three-fold. First, we devise a memory model for unstructured mesh data for efficient use of memory on parallel shared memory architectures, with the purpose of lowering the synchronization overhead between threads while avoiding race conditions. Second, we present a new thread-parallel edge and face swapping algorithm for two and three dimensional meshes using OpenMP for shared memory architectures. We show how removing the conflicts from the reconfiguration procedure by applying a vertex locking strategy can result in a near linear speed-up with parallel efficiency of close to one on two threads and 70% with 24 threads on shared-memory processors. Finally, we derive a parallel mesh generation and refinement module for shared memory architectures based on pre-existing serial modules by implementing Chernikov and Chrisochoides' parallel insertion algorithm along with the two above tools. Experiments show a worst case parallel efficiency of 50% for parallel refinement with 24 threads.
Fine-grained parallel algorithm for unstructured surface mesh generation
2015, Computers and Structures
Citation Excerpt :
The submeshes are redistributed at intervals to balance the loads, and their boundaries are changed accordingly. de Cougny and Shephard [7,22] adopted the second domain decomposition approach to parallelise their tetrahedral meshes. Firstly, the octant cells that cover (interior cells) or intersect (boundary cells) the problem domain are distributed evenly on the processors, and then the majority of interior cells is tetrahedralised using the mesh templates in parallel.
A parallel surface meshing algorithm is proposed by exploiting the parallelism within the meshing process of a surface, which is more efficient than the conventional scheme that meshes surfaces individually. One integral part is the domain decomposition approach adopted, which ensures no small inter-domain angles; therefore, the parallel meshing procedure can fix the inter-domain boundary without compromising mesh quality. Combining the parallel surface mesher with the parallel tetrahedral mesher and improver developed previously, a parallel preprocessing pipeline for large-scale simulations is set up. It only consumes minutes to prepare a mesh containing hundreds of millions of elements.
Dynamic grid for mesh generation by the advancing front method
2013, Computers and Structures
The advancing front approach is known to be robust, versatile over domains of different dimensions with diverse geometrical and topological characteristics, and is able to generate elements of various types such as triangles, quadrilaterals, tetrahedra and hexahedra close to the well-shaped ideal geometry in compliance with the specified node spacing specification. However, the main inconvenience with the advancing front approach is its efficiency in handling a large number of elements. Whenever a new element is formed, we have to assure that segments created do not penetrate into the generation front, and the search over the entire generation front to ensure no intersection is a rather time-consuming process.
In this paper, a dynamic grid approach for the advancing front method is presented to generate adaptive triangular meshes of variable element size over arbitrary planar domains. A simple domain partition scheme with little demand on additional memory is proposed, which could drastically reduce the search time over the generation front. Variable number of objects can be stored in an individual cell so that a coarse grid could be employed for relatively complex meshes. A dynamic marking and unmarking of cells intersected by a line segment is devised so as to cope with the changing boundary conditions during mesh generation. From the tests of two series of adaptive meshes with size up to one million elements on a PC, the use of partition grid could substantially reduce the CPU time by more than five times compared to mesh generation by the same procedure without a background grid.
A distributed-memory parallel technique for two-dimensional mesh generation for arbitrary domains
2013, Advances in Engineering Software
Citation Excerpt :
In the three works, the same procedure is performed recursively, generating disconnected fronts, which are advanced in parallel in different processors. In Refs. [8] and [21], the input domain is decomposed by an octree, and an advancing front technique is used in the subdomains. De Cougny and Shephard [8] generate the inner mesh through template meshing in a fine octree.
This work describes a technique for generating two-dimensional triangular meshes using distributed memory parallel computers, based on a master/slaves model. This technique uses a coarse quadtree to decompose the domain and a serial advancing front technique to generate the mesh in each subdomain concurrently. In order to advance the front to a neighboring subdomain, each subdomain suffers a shift to a Cartesian direction, and the same advancing front approach is performed on the shifted subdomain. This shift-and-remesh procedure is repeatedly applied until no more mesh can be generated, shifting the subdomains to different directions each turn. A finer quadtree is also employed in this work to help estimate the processing load associated with each subdomain. This load estimation technique produces results that accurately represent the number of elements to be generated in each subdomain, leading to proper runtime prediction and to a well-balanced algorithm. The meshes generated with the parallel technique have the same quality as those generated serially, within acceptable limits. Although the presented approach is two-dimensional, the idea can be easily extended to three dimensions.

View all citing articles on Scopus

View full text

Parallel volume meshing using face removals and hierarchical repartitioning

Abstract

Comput. Struct.

A general topology-based mesh data structure

Int. J. Numer. Methods Engrg.

Computing dirichlet tessellations

The Computer J.

Task parallel implementation of the Bowyer—Watson algorithm

Parallel unstructured distributed three-dimensional mesh generation

Parallel unstructured grid generation

Parallel three-dimensional mesh generation on distributed memory MIMD computers

Engrg. Comput.

Load balancing computational fluid dynamics calculations on unstructured grids

Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics

Int. J. Numer. Methods Engrg.

A paradigm for parallel unstructured grid generation

Prepartitioning as a way to mesh subdomains in parallel

An introduction to Parallel Algorithms