# Designing Parallel Adaptive Laplacian Smoothing for Improving Tetrahedral Mesh Quality on the GPU
## 3 Parallel Adaptive Laplacian Mesh Smoothing on the GPU
### Step 3: Adaptive Smoothing Iteration  
When optimizing the tetrahedral meshes using adaptive Laplacian mesh smoothing, the last step is to judge the mesh node locations iteratively until convergence. For adaptive Laplacian mesh smoothing to tetrahedral meshes, the standard for judging tetrahedral mesh quality is the minimum value of the mass of all adjacent tetrahedrons of the node [22]. If the minimum value of the mass obtained in this iteration is greater than the minimum value of the mass calculated in the previous iteration, then we terminate the iteration and keep the smoothing results in this iteration; otherwise, we need to continue the iteration.  
In this paper, we chose the aspect ratio as a metric to evaluate the quality of the tetrahedral meshes, where the aspect ratio is the radius ratio of the inscribed sphere and the circumscribed sphere. The maximum aspect ratio of the tetrahedron is \(1/3\), that is, the regular tetrahedron. For the convenience of statistical analysis, we have expanded all the mesh masses by three times, and the numerical range of the radius ratio is controlled between \(0\sim 1\), where \(1\) represents the tetrahedral element with the best quality, and \(0\) represents the tetrahedral element with the worst quality. The calculations of the inscribed sphere radius and circumscribed sphere radius are shown in Equations (3) and (4).  
Figure 5: Illustration of searching for nodal neighbors.  
Figure 6 simply shows the relationship between a tetrahedron and its inscribed sphere and circumscribed sphere.  
Radius of inscribed sphere \(R_{1}\):  
\[R_{1}=\frac{3V}{S} \tag{3}\]  
where \(V\) is the volume of the tetrahedron and \(S\) is the sum of the side areas of the tetrahedron.  
Radius of inscribed sphere \(R_{2}\):  
\[R_{2}=\frac{\sqrt{(a+b+c)*(a+b-c)*(a+c-b)*(b+c-a)}}{24V} \tag{4}\]  
where \(a\), \(b\), and \(c\) are the products of three pairs of opposite edges of the tetrahedron and \(V\) is the volume of the tetrahedron.  
There is a clear data dependency in the iteration process. In the smoothing iteration, the \(q+1\) iteration calculation requires the results of the \(q\) iteration, and the computation must ensure that all nodes in the mesh have completed the \(q\) iteration before the \(q+1\) iteration can be performed. However, in GPU computing, there are no synchronization barriers in a block, and it is not always guaranteed that the current iteration must have started after all nodes have completed the previous calculation. A practical solution to this problem is to distribute only one block for a single iteration. Each thread in the block is responsible for the smoothing calculation of several nodes in this iteration, including (1) updating the locations of nodes and (2) updating the mass value of all neighboring tetrahedrons in memory by the new node coordinates and determining whether the mass minimum has increased.  
Obviously, when distributing a block for a location updating process, it is guaranteed that the \(q+1\) iteration must start after the \(q\) iteration completely finishes. However, this iteration method cannot make efficient use of the parallel computing power of GPUs. In this paper, we adopted a multiple block iterative method [29] where the multiple blocks complete an iteration at the same time. The maximum number of threads allowed on the GPU is 1024 at the moment; thus, all simultaneous starts of multiple blocks can achieve the maximum parallel strategy. In the implementation, we distribute a thread to each node to complete its smoothing calculation. If there are a total of 4096 internal nodes in the mesh that need to be calculated, when 1024 threads are allocated to a block, 4 blocks need to be designed to work at the same time. Figure 7 briefly illustrates the process of the single block iteration and the multiple block iteration.  
Figure 6: The inscribed sphere and circumscribed sphere of a tetrahedron.