Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The finite element method (FEM) has been a very popular numerical approach for solving partial differential equations (PDEs) in many applications. In the method, the domain over which the PDEs are defined is partitioned into a mesh containing a large number of simple elements, such as triangles and quadrilaterals in 2D cases and tetrahedra and hexahedra in 3D cases [1–6]. The quality of the mesh, typically measured by the minimum and maximum angles, can significantly affect the interpolation accuracy and solution stability of the FEA [7, 8]. Therefore, improving the mesh quality has been an active research area in computational mathematics and computer science. Due to the great popularity in the FEM, 3D tetrahedral meshes will be the focus of our present work.

The methods of mesh quality improvement can be classified into three categories as follows. (1) topology optimization, which modifies the connectivity between mesh vertices while keeping vertex positions unchanged. The edge- or face-swapping methods are commonly used in topology optimization [9, 10]. (2) vertex insertion/deletion, which inserts/deletes vertices to/from the mesh [10–13]. (3) vertex smoothing, which repositions the coordinates of the vertices while keeping the connectivity unchanged [14–16]. Generally speaking, mesh quality improvement is best achieved when all the three methods are properly combined in the mesh smoothing scheme [10]. In our method described below, we shall focus on the vertex repositioning strategy, i.e. vertex smoothing.

One of the most popular vertex smoothing method is Laplacian smoothing, which moves a mesh vertex to the weighted average of its incident vertices [17–19]. If the neighborhood of the vertex is not a convex polyhedron, the Laplacian smoothing may not lead to a well-positioned mesh. Some angle-based methods were proposed for smoothing 2D triangular and 3D surface meshes [20–22]. However, these methods are difficult to extend to 3D tetrahedral meshes. [23] presented a method based on the Centroid Voronoi Tessellation (CVT) concept that is restricted to inner vertices of a mesh. A peeling off operation has to be taken to improve bad tetrahedra on boundaries. [24] proposed a method of smoothing planar quadrilateral meshes. Some researchers presented methods for smoothing hexahedral mesh [25–29]. More recently, some new techniques of vertex smoothing were proposed. [30, 31] presented methods of stretching the vertices of a tetrahedron at one time. The methods were extended by [32] to hexahedral mesh. [33] assigned a quality coordinate for every vertex and calculated the new position by maximizing the combined quality of tetrahedra incident to it. [34] used a metric non-conformity driven method to smooth hybrid meshes such as a mesh with hexahedral and tetrahedral elements.

In addition to the above methods, approaches using numerical optimization to compute the new position of a vertex has been an important branch of the vertex smoothing category. The new position of a vertex is computed by optimizing a function that measures the local or global quality of the mesh [35–44]. In particular, the optimal Delaunay triangulation (ODT) approach [45] tries to minimize the \(\mathcal{L}^{1}\) error between a paraboloid function and its piecewise linear interpolation over the neighborhood of a vertex. This idea has been extended to 3D tetrahedral mesh smoothing in [46]. Despite its great success in mesh quality improvement, the original ODT method was derived to optimize the positions of inner vertices only. In other words, the tetrahedral mesh to be smoothed must possess quality triangles on boundaries. In many real mesh models, however, “bad” tetrahedra often occur near or on the boundaries of a domain [47, 48]. Therefore, in our previous work, we provided an analytical method named boundary-optimized Delaunay triangulation (B-ODT) to find the optimal positions of all mesh vertices, including those on boundaries, by minimizing an \(\mathcal{L}^{1}\) error function that is defined in the incident neighborhood of each vertex. The minimization is an unconstrained quadratic optimization problem and has an exact analytic solution when the coefficient matrix of the problem is positive definite.

In this work, we extend our previous B-ODT method by performing it edge by edge. The new method achieves better results than the original B-ODT method by considering the local configuration of every vertex before performing the B-ODT algorithm. The remainder of the present work is organized as follows. In Sect. 2, we start with a brief introduction to our tetrahedral mesh generation from an initial triangular surface mesh. We then review the ODT and B-ODT methods, provide the edge-based B-ODT (so-called eB-ODT) method. We present some experimental results and quality analysis in Sect. 3, followed by our conclusions in Sect. 4.

2 Methods

The framework of our mesh quality improvement method is shown in Fig. 1. The vertex insertion operation is performed prior to the vertex repositioning. We try to insert as few vertices as possible in order to maintain the size of the original mesh. We give a brief introduction to our tetrahedral mesh generation using an octree-based method in Sect. 2.1. As for vertex smoothing, the algorithms of original B-ODT and eB-ODT are given in Sects. 2.2 and 2.3 respectively.

Fig. 1
figure 1

The framework of our mesh quality improvement method

Full size image

2.1 Tetrahedral Mesh Generation Algorithm

Our tetrahedral mesh generation algorithm is based on the body centered cubic (BCC) tetrahedral lattice, a common crystal structure in nature with many desirable properties [49]. The BCC lattice is constructed by adding a new node at each cell center and connecting it to the eight vertices of the cell and six neighboring cell centers. The BCC lattice is highly structured and computationally efficient, and has been utilized in various types of numerical simulation. When dealing with a bounded domain, however, the BCC lattice must be carefully remeshed near the domain boundary so that the tetrahedral mesh generated agrees with the given boundary. To this end, our method consists of the following four steps (see Fig. 2 for a two dimensional illustration):

  1. 1.

    Subdivide the octree of an input surface mesh based on Euclidean distance transformation. A few geometric properties of the input mesh are utilized to refine the subdivision adaptively from interior to boundary, and from low curvature to high curvature areas.

  2. 2.

    Compute the sign of every node in the BCC lattice. For each edge of the BCC grid, if the corresponding signs of the two endpoints are different, then calculate the cutting (intersecting) point where the edge crosses the input surface mesh.

  3. 3.

    Detect the cutting points that are “too close” to the original BCC nodes and snap them to the corresponding nodes. Equivalently, we adjust the sign of that node to zero. We refer to this process as cutting point snapping.

  4. 4.

    Decompose the boundary polyhedra into tetrahedra. For each BCC tetrahedron, if all signs of its vertices are negative (meaning “outside”), we ignore it (we assume that only the interior tetrahedralization is of interest). If all signs are positive (meaning “inside”), we leave it as the final tetrahedron. Otherwise, the tetrahedron is split by the input surface mesh into inside and outside parts and we further decompose the inside part (a polyhedron) into tetrahedra.

Fig. 2
figure 2

A two dimensional illustration of our tetrahedral generation algorithm. Note that the octree subdivision is adaptive in our algorithm. However, we do not show the adaptivity here for simplicity. (a) Computing the signs for each BCC grid; (b) Calculating the cutting points; (c) Detecting the “too close” cutting points; (d) Snapping the “too close” cutting points to the corresponding BCC lattice grids; (e) Decomposing the boundary polyhedra into tetrahedra; (f) Obtaining the final tetrahedral mesh

Full size image

2.2 ODT and B-ODT Algorithms

For any vertex x 0 in a tetrahedral mesh \(\mathcal{T}\), suppose the neighborhood of x 0 is Ω 0 consisting of a set of tetrahedra {τ}. Let x ∗ be the smoothing result of x 0 and Ω ∗ the neighborhood of x ∗ (or the union of tetrahedra incident to x ∗) in \(\mathcal{T}\).

If x 0 is an inner vertex, x ∗ can be computed by the following ODT formula [45]:

$$ \mathbf{x}_\ast= \mathbf{x}_0 - \frac{1}{2|\varOmega _0|}\sum_{\tau\in \varOmega _0} \Biggl( \frac{1}{3}S_\tau\mathbf{n}_\tau\sum _{i = 1}^3 \|\mathbf{x}_{\tau,i} - \mathbf{x}_0\|^2 \Biggr) . $$
(1)

Here S τ and n τ are the area and unit normal vector of t τ , which is the opposite triangle of x 0 in τ, n τ points to the inside of τ, x τ,i are the (three) vertices of t τ .

If x 0 is a boundary vertex, x ∗ can be computed by the following B-ODT formula:

$$ \mathbf{x}_\ast= \mathbf{x}_0 + u \mathbf{s} + v\mathbf{t} $$
(2)

where s and t are two orthonormal vectors in the tangent plane of the boundary surface of \(\mathcal{T}\) at x 0, the coefficients u and v are computed by solving the following linear equation system:

$$ \left [ \begin{array}{c@{ \quad }c} 2E & G\\ G & 2F \end{array} \right ] \left [ \begin{array}{c} u \\ v \end{array} \right ] = \left [ \begin{array}{c} -H \\ -I \end{array} \right ]. $$
(3)

The calculations of E, F, G, H, I are given below in Algorithm 1. Here, we directly give the algorithm of smoothing inner and boundary vertices of \(\mathcal{T}\) using ODT and B-ODT methods respectively (Algorithm 1). Note that the tangent plane restriction of x ∗ guarantees the volume of the smoothed mesh coincides with that of the original mesh.

Theoretically, both (1) and (2) are the unique solutions of the optimization problem which minimizes the \(\mathcal{L}^{1}\) interpolation error between a paraboloid function f I (x)=∥x−x 0∥2 and its piecewise linear interpolation over Ω ∗:

$$ Error_\ast= \|f - f_I \|_{L^1} = \int_{\mathbf{x}\in \varOmega _\ast} \bigl|f(\mathbf{x}) - f_I(\mathbf{x})\bigr| \,\mathrm{d}\mathbf{x} . $$
(4)

Algorithm 1

(ODT and B-ODT smoothing for inner and boundary vertices)

  • for every vertex x 0 do

    1. a.

      if x 0 is an inner vertex, then

      x ∗ is computed by (1).

    2. b.

      else

      x ∗ is computed using the following scheme:

      1. i.

        Compute the normal vector of the tangent plane at x 0, then select two orthogonal unit vectors s, t on the tangent plane.

      2. ii.

        Compute the following coefficients:

        1. A.

          \(E = \frac{1}{4}|\varOmega _{0}| - \frac{1}{60}\sum_{i=1}^{m}\mathbf{s}(\mathbf{Y}_{i}+\mathbf{Y}_{i+1}) \mathbf{s}(\mathbf{Y}_{i}\times\mathbf{Y}_{i+1})\)

        2. B.

          \(F = \frac{1}{4}|\varOmega _{0}| - \frac{1}{60}\sum_{i=1}^{m}\mathbf{t}(\mathbf{Y}_{i}+\mathbf{Y}_{i+1})\mathbf{t}(\mathbf {Y}_{i}\times\mathbf{Y}_{i+1})\)

        3. C.

          \(G = -\frac{1}{60}\sum_{i=1}^{m} [\mathbf{s}(\mathbf {Y}_{i}+\mathbf{Y}_{i+1})\mathbf{t}(\mathbf{Y}_{i}\times\mathbf{Y}_{i+1}) +\mathbf{t}(\mathbf{Y}_{i} + \mathbf{Y}_{i+1})\*\mathbf{s}(\mathbf {Y}_{i}\times\mathbf{Y}_{i+1})]\)

        4. D.

          \(H = \frac{1}{12}\mathbf{s}\sum_{\tau\in \varOmega _{\ast}} S_{\tau}\mathbf{n}_{\tau}L_{\tau}- \frac{1}{60}\sum_{i=1}^{m} (\mathbf{Y}_{i}^{2}+\mathbf{Y}_{i+1}^{2}+\mathbf{Y}_{i}\mathbf {Y}_{i+1})\*\mathbf{s}(\mathbf{Y}_{i} \times\mathbf{Y}_{i+1})\)

        5. E.

          \(I = \frac{1}{12}\mathbf{t}\sum_{\tau\in \varOmega _{\ast}} S_{\tau}\mathbf{n}_{\tau}L_{\tau}- \frac{1}{60}\sum_{i=1}^{m} (\mathbf{Y}_{i}^{2}+\mathbf{Y}_{i+1}^{2}+\mathbf{Y}_{i}\mathbf {Y}_{i+1})\mathbf{t}(\mathbf{Y}_{i} \times\mathbf{Y}_{i+1})\)

      3. iii.

        Solve the linear system (3).

      4. iv.

        Compute x ∗ using x ∗=x 0+u s+v t.

Here, Y i =y i −x 0, \(\{\mathbf{y}_{i}\}_{i=1}^{m}\) are the neighboring vertices of x 0 on the boundary of the tetrahedral mesh \(\mathcal{T}\). The order of y i is determined in the following way: for any i=1,…,m, the cross product between \(\overrightarrow{\mathbf{x}_{0}\mathbf{y}_{i}}\) and \(\overrightarrow{\mathbf{x}_{0}\mathbf{y}_{i+1}}\) points to the outside of Ω 0 (let y m+1=y 1), \(L_{\tau}= \sum_{j=1}^{3}\|\mathbf{x}_{\tau,j} - \mathbf{x}_{0}\|^{2}\).

For a boundary vertex x 0, in order to preserve the sharp features, we further restrict x ∗ moving along the features of the mesh. Here, we refer to the feature direction at x 0 as the line that passes through x 0 and has the minimal curvature value among all the directions. This line is on the tangent plane, thus the volume is still preserved when x ∗ moves along this feature line. The direction of the feature line is found by computing the eigenvalues of the following tensor voting matrix at x 0:

$$ M = \sum_{i = 1}^m S_i\mathbf{n}_i\mathbf{n}_i^T . $$
(5)

Here S i is the area of surface triangle Δ x 0 y i y i+1 and n i =(n ix ,n iy ,n iz )T is the unit normal vector of Δ x 0 y i y i+1. The matrix M is a positive definite matrix and has three orthogonal eigenvectors. The feature line is determined in the following way. Suppose that the three eigenvalues of M are μ 0, μ 1, μ 2 with μ 0≥μ 1≥μ 2 and e 0, e 1, e 2 are the corresponding eigenvectors. If μ 0≫μ 1≈μ 2≈0, then the neighborhood of x 0 corresponds to a planar feature. In this case, the above Algorithm 1 is used to smooth x 0. If μ 0≈μ 1≫μ 2≈0, then x 0 lies on an crease (linear) feature and the direction of the crease is e 2. In this case, the following Algorithm 2 is used to smooth x 0. If μ 0≈μ 1≈μ 2≫0, then x 0 is at a corner which should not be changed during the vertex smoothing process.

Algorithm 2

(B-ODT smoothing with feature preserving)

  • for every crease vertex x 0 do

    1. a.

      Set the feature direction at x 0 to be d=e 2/∥e 2∥.

    2. b.

      Compute the following coefficients:

      1. i.

        \(A = \frac{1}{4}|\varOmega _{0}| - \frac{1}{60}\sum_{i=1}^{m}\mathbf{d}(\mathbf{Y}_{i}+\mathbf{Y}_{i+1})\mathbf{d}(\mathbf {Y}_{i}\times\mathbf{Y}_{i+1})\)

      2. ii.

        \(B = \frac{1}{12}\mathbf{d}(\sum_{\tau\in \varOmega _{\ast}} S_{\tau}\mathbf{n}_{\tau}L_{\tau}) - \frac{1}{60}\sum_{i=1}^{m} (\mathbf{Y}_{i}^{2}+\mathbf{Y}_{i+1}^{2}+\mathbf{Y}_{i}\mathbf {Y}_{i+1})\mathbf{d}(\mathbf{Y}_{i} \times\mathbf{Y}_{i+1})\)

    3. c.

      Compute x ∗ as x ∗=x 0+f d with \(f = -\frac{B}{2A}\).

2.3 Edge-Based B-ODT Algorithm

In practice, the improvement of x 0 is always affected by the configuration of the vertices around x 0. When the vertices around x 0 has good configuration, the quality can be significantly improved. Based on this observation, we presented a modified strategy here to smooth a tetrahedral mesh: smoothing the mesh in an edge-by-edge way. That is, to smooth the two end vertices of each edge recursively. By this way, the angle quality can be improved more than simply performing Algorithm 2. The detail is given in the following algorithm:

Algorithm 3

(eB-ODT smoothing for boundary vertices)

  • for every edge e in the mesh (Let x 0 and x 1 be the two vertices of e), do

    1. a.

      Smooth x 0 using Algorithm 1 or Algorithm 2 according to the type of x 0

    2. b.

      Smooth x 1 using Algorithm 1 or Algorithm 2 according to the type of x 1

    3. c.

      Compute s, which is the sum of the movements of x 0 and x 1

    4. d.

      If s≤ε, go to next edge

      else, go to step a

3 Results

The proposed eB-ODT algorithms were tested on several tetrahedral meshes generated from triangular surface meshes that serve as the boundaries of the domains. For every mesh, the smoothing process shown in Fig. 1 is repeated for 20 times. The mesh smoothing results are summarized in Table 1. The comparisons between the eB-ODT algorithm (Algorithm 3) and several other approaches, including the ODT algorithm, B-ODT algorithm, topology optimization and the Natural ODT algorithm [46], are also provided in Table 1. In Figs. 3–9, the original and smoothed meshes are compared and from the histograms we can see significant improvement of dihedral angles in these meshes.

Fig. 3
figure 3

The original mesh model (a) and the smoothed result (b). In both meshes, the outer and cross-section views are shown. The minimum dihedral angles of these two meshes are 5.86∘ and 18.20∘ respectively, and the maximum dihedral angles are 164.70∘ and 145.56∘ respectively

Full size image
Table 1 Comparisons of dihedral angles using different methods
Full size table

We compare the smoothing results by using the ODT, B-ODT and eB-ODT algorithms. In Table 1, all the minimum and maximum dihedral angles by using the B-ODT algorithm are better than those by the ODT algorithm and the results by using eB-ODT are better than B-ODT, especially on the Retinal model. Note that the minimum dihedral angle in Retinal model is very small and likely occurs on the boundary of the model. Therefore, the B-ODT and eB-ODT algorithm can perform much better than the original ODT method.

Although the topology optimization is utilized in many mesh smoothing algorithms, this technique alone may not always improve the quality of a mesh. To show this, we smooth all the meshes in Table 1 using only the topology optimization and compare the results with those obtained by using our eB-ODT algorithm. From Table 1, we can see that the ability of improving mesh quality by using topology optimization alone is limited, compared to the eB-ODT algorithm.

The tetrahedral mesh in Fig. 3 is generated by tetrahedralizing randomly-sampled point set on a unit sphere [50]. There are 642 points on the sphere and 87 inner vertices are inserted by the tetrahedralization algorithm. The minimum and maximum dihedral angles of this Random Sphere model are 5.86∘ and 164.70∘ respectively. After 20 times of running the eB-ODT algorithm, the minimum and maximum dihedral angles are improved to 18.20∘ and 145.56∘ respectively. Note that the distribution of the boundary vertices of the smoothed mesh is much more uniform than that of the original mesh, demonstrating that the eB-ODT algorithm can smooth both inner and boundary vertices in a tetrahedral mesh.

The eB-ODT algorithm is also tested on tetrahedral meshes generated from several biomedical molecules: 2CMP molecule in Fig. 4, Retinal molecule in Fig. 5 and Ryanodine receptor (RyR) in Fig. 6. The quality of 2CMP and RyR meshes reaches the best after no more than 10 iterations although all the models in Table 1 are processed 20 times. In Fig. 7, we demonstrate the convergence of minimum and maximum dihedral angles with respect to the number of iterations on the Retinal model using the eB-ODT algorithm.

Fig. 4
figure 4

Original and smoothed 2CMP models. The minimum dihedral angles of these two meshes are 5.57∘ and 21.68∘ respectively, and the maximum dihedral angles are 163.24∘ and 145.56∘ respectively

Full size image
Fig. 5
figure 5

Original and smoothed Retinal models. The minimum dihedral angles of these two meshes are 1.25∘ and 19.86∘ respectively, and the maximum dihedral angles are 173.85∘ and 160.14∘ respectively

Full size image
Fig. 6
figure 6

Original and smoothed RyR models. The minimum dihedral angles of these two meshes are 6.19∘ and 22.57∘ respectively, and the maximum dihedral angles are 170.74∘ and 143.56∘ respectively

Full size image
Fig. 7
figure 7

The convergence of minimum and maximum dihedral angles with respect to the number of iterations on the Retinal model using the eB-ODT algorithm. Note that on the left the curves of ODT and topology optimization are almost identical

Full size image

The 2Torus (Fig. 8) and FanDisk (Fig. 9) models show the feature-preserving property of the eB-ODT algorithm. In order to measure the difference between the original and smoothed meshes, we compute the relative Hausdorff distances between the surface meshes of the original and smoothed models, as shown in Table 2. Here, the Hausdorff distance is first computed using the standard definition and then scaled as follows. Let h be the absolute Hausdorff distance between the original and smoothed meshes, and L be the largest side length of the bounding box of the original mesh. The relative Hausdorff distances is defined by \(\frac{h}{L}\), which measures the difference of the original and smoothed models relative to the size of the original model. From Table 2 we can see that the relative Hausdorff distances between the original and smoothed models are very small showing that our eB-ODT algorithm preserves the shape of the original models quite well.

Fig. 8
figure 8

Original and smoothed 2Torus models. The minimum dihedral angles of these two meshes are 5.96∘ and 21.37∘ respectively, and the maximum dihedral angles are 164.92∘ and 146.81∘ respectively

Full size image
Fig. 9
figure 9

Original and smoothed FanDisk models. The minimum dihedral angles of these two meshes are 6.04∘ and 20.32∘ respectively, and the maximum dihedral angles are 164.98∘ and 154.96∘ respectively

Full size image
Table 2 Relative Hausdorff distance between original and smoothed meshes
Full size table

The original ODT has also been extended by [46] to 3D tetrahedral mesh smoothing and the method is called Natural ODT (NODT). The NODT method computes the new position of a boundary vertex x 0 in a tetrahedral mesh \(\mathcal{T}\) by adding a certain amount of compensation to the weighted centroid of the neighborhood of x 0. The compensation is a weighted sum of the normal vectors of the boundary triangles around x 0. Although boundary vertices are considered in the NODT method, the new positions calculated have to be projected onto the boundary of \(\mathcal{T}\) to preserve the volume and shape of the original mesh. Therefore, the NODT method does not optimize the positions for boundary vertices. The smoothing results by using the afore-mentioned NODT method are shown in Table 1, where we can see that our eB-ODT algorithm significantly outperforms the NODT method. Sometimes the results obtained by the NODT method are even worse than the original meshes. The running time of eB-ODT and NODT is compared in Table 3.

Table 3 Comparison of running time (20 iterations)
Full size table

4 Conclusions

We described a method of simultaneously smoothing both inner and boundary vertices of a tetrahedral mesh under a unified optimization framework. The eB-ODT algorithm presented can preserve sharp features very well and is guaranteed to preserve the volume of the original mesh. For every boundary vertex, the optimal position is computed by solving a linear system. The algorithm is numerically robust and easy to implement because the order of the linear equation system is only degree 2. The experimental results have shown the effectiveness of the proposed method.