JIAYIN (KAY) LU 卢嘉茵
Applied Mathematician & Computational Artist & Freelance Photographer
2D Multi-threaded geometry meshing using the Delaunay Triangulation
Fall 2019-Fall 2023
Advisor: Prof. Christopher Rycroft
Status: The project led to a paper currently in submission to Computer Physics Communications:
Jiayin Lu and Chris H. Rycroft. TriMe++: Multi-threaded triangular meshing in two dimensions, 2023.
Working with my advisor Prof. Christopher Rycroft, I am currently developing software libraries in the computational geometry field. The software libraries can serve as useful tools for other researchers in the analysis of large-scale particle systems and in large-scale numerical simulations using the finite element method.
Recently, I used OpenMP to implement a multi-threaded parallel extension of Voro++ [1], a software library developed by my advisor to generate Voronoi diagrams. I showed that the parallel computation achieved near-perfect parallel efficiency.
Using multi-threaded Voro++, we have developed in C++ a 2D multi-threaded meshing software using Delaunay triangulation, TriMe++. It is designed for large-scale quality meshing with thousands of millions of particles on complicated shapes.
Three iterative meshing algorithms are implemented, DistMesh [2], CVD meshing [3], and a hybrid method combining the two. DistMesh has advantage in faster computation time, while CVD meshing tends to generate better quality mesh. By comparing the performances of the three meshing methods, I showed that the hybrid method has
advantages of both, while avoiding disadvantages. I also demonstrated through examples that the software can handle extremely complicated shapes well, and generate high quality meshes in a short time, using parallel computing.
As an example of meshing on an extremely complicated shape, we use the North America continent map (shape contour line segments) as the shape input to TriMe++. As shown in the figure below, the software read in the input, and automatically generated the signed distance field (SDF) to represent the shape, and the element density field that defines the geometry adaptivity of the mesh.
Figure: Numerical example to test the order of accuracy of the numerical scheme.
(a) SDF of the North America continent map, with shape boundaries overlaid.
(b) Element Density field for N = 70, 000 points.
Based on the SDF and the density field, TriMe++ then generates a high quality mesh of the shape. The mesh shown in the figure below is of high quality and was generated with 70,000 particles in 4.67 seconds with 28 parallel threads, each thread uses a low-power core with a 1.7 GHz base clock speed.
(a) Overview of the whole mesh for the North American continent, with shape boundaries overlaid using blue lines.
Zoomed-in views of
(b) Michigan and Ontario,
(c) western Alaska,
(d) and Nunavut are also shown, with their locations highlighted on the whole map using dotted pink lines
The multi-threaded 2D meshing software can be useful in computer graphics and scientific computing, such as for simulations using the Finite Element Method (FEM). It is especially useful for applications that require large-scale meshing due to its computational efficiency and significant speed-up from parallelization.
Reference
[1] Jiayin Lu, Emanuel Lazar, and Chris Rycroft. An extension to Voro++ for multithreaded computation of voronoi cells. Computer Physics Communications, 291. 108832, 2023.
[2] P.-O. Persson and G. Strang. A simple mesh generator in matlab. SIAM Review, 46 (2):329–345, June 2004. http://persson.berkeley.edu/distmesh/.
[3] Q. Du and D. Wang. Tetrahedral mesh generation and optimization based on centroidal voronoi tessellations. International Journal on Numerical Methods in Engineering, 56(9):1355–1373, 2003.