A Multi-threaded Parallel Ouality Improvement Algorithm For Tetrahedral Meshes

The finite element methods have been widely used in scientific research and engineering computing.One of its critical steps is the preparation of the input data,that is,the mesh generation.Usually the workload associated with the mesh generation takes up the most part of time in the whole numerical computing procedure,which is the performance bottleneck.On the other hand,the quality of the meshes has a tremendous impact on the accuracy and efficiency of the numerical results.Tetrahedral meshes,which have strong ability of auto generation and self-adaption of complicated geometric shapes,are very popular in finite element analysis.Because of the boundary constraint and the inherent factor of tetrahedral mesh generation methods,there are a lot of mesh elements with poor quality existing in the initial mesh generated by common algorithms such as advancing front,Delaunay and octree methods,which can only be used in finite element analysis after quality improvement.Usually,we use series of quality improvement algorithms to improve the quality of tetrahedra in the original mesh such as topological transformations,vertex smoothing,etc.Additionally we need to do the optimization multiple passes to achieve better effects.As a result,it often consumes much more time than generating the meshes.Experiments show that the mesh improvement procedure can be five times slower than the generating one,becoming the performance bottleneck.In order to solve this problem,a multi-threaded parallel improvement algorithm based on OpenMP is proposed in this paper.Different techniques are developed to parallelize topological algorithms and vertex smoothing ones.For the vertex smoothing operations,the parallelization is based on the graph coloring decomposition technique,which colors the dual graph of the mesh to subdivide mesh points into a few independent sets.Vertexes in the same set are not adjacent,so that they can be operating simultaneously by multiple threads without interferer.For topological algorithms such as edge removal,multiface removal,edge contraction,we propose a task divide strategy for parallelizing those topological transformations,which is the main innovation point in this paper.The main steps are as follows:(1)Calculate the feature point's coordinates of each operational element;(2)Sort all operations using a Hilbert curve based on the feature point's position;(3)Divide the sorted operations into subsets which's number are equal to the number of threads.Topological transformation operations are defined on the cavities composed of tetrahedral elements.When improving the mesh quality,each thread handles the local operation in the assigned subset in order.Only one thread can finish the process if different threads interfere with each other.Since operations handled in different threads simultaneously are far away from each other in the Hilbert curve,the possibility of interference remains at a very low level.Strategies described above are easy to be implemented and the performance loss is proved to be acceptable.Multiple techs used to improve the performance are proposed in this paper,and we developed a multi-threaded parallel quality improvement algorithm for tetrahedral meshes including all topological transformations and vertex smoothing method mentioned above.Typical inputs are chosen to explore the parallel efficiency of this algorithm,which is proved to be efficient and applicative.