1 Introduction

Flattening of free-form surfaces has been widely used in the field of mechanical engineering, such as blank estimation in sheet metal forming, computer-aided design for mechanical product and surface reconstruction in reverse engineering. It involves computing a mapping between surface in three-dimensional space and a planar parameter domain. Because of its simplicity and flexibility, surface mesh composed of triangular elements, quadrilateral elements and their combination has become the main expression of three-dimensional models. Both triangular and quadrilateral surface meshes are considered in this surface flattening algorithm.

In recent years, a variety of methods on surface flattening has been developed [1], and the related methods can be divided into linear solution-based method [2,3,4,5,6] and iterative solution-based method by their solving strategies. The most common used method based on linear solution is shape-preserving method [2, 3], which determines the position of each vertex in the flattened mesh by solving a linear system based on convex combination. The main disadvantage of this method is that it requires predefined and convex two-dimensional boundaries. Levy et al. [5] presented a Least- Squares Conformal Mapping (LSCM) method by a least-squares approximation of the discrete Cauchy-Riemann equations to minimize angle deformation. Yavuz [6] uses the dynamic virtual boundary method to reduce the deformation of triangles near the boundary caused by convex combination. While linear solution-based method is easy to use and has high efficiency, it may produce flattening results with local or global overlaps. Iterative solution-based method methods perform the surface flattening by iteratively solving the minimum energy or equilibrium state, which are defined by different mesh properties. Sheffer et al [7] proposed a method based on angle optimization to calculate the parameterization of mesh surface. This method aims to optimize the angular deformation of triangular mesh by solving a nonlinear system, which usually requires many calculations. The mass-spring model is often used to construct energy function for surface flattening [8,9,10,11]. Zhong et al. [8] divided the three-dimensional surface into several almost developable patches, and then flatten them by solving the energy function via mass-spring model. With the similar mass-spring model based stretching energy, Bing et al. [9] project the element locally to planar, and then combines the results of a single projection by solving a simplified global matrix. Wang et al. [11] also use a mass-spring model-based energy function to flatten 3D mesh surfaces into 2D patterns, which can obtain result with flexible surface boundaries. A local to global operation [12, 13] is proposed to ensure the minimum distortion between input meshes and flattened meshes by iteratively solving a global energy function, which is superposition of local energy. One-step Inverse Forming Theory in sheet metal forming is introduced to solve the surface flattening problem [14, 15]. However, the one-step inverse forming theory is complex, which leads to the complex parameters and time-consuming of the mesh surface flattening algorithm. Zhuang et al. [16] defined the energy model based on the change of edge length by using Young's modulus. By minimizing this energy model, the flattening results for computer aided garment design are obtained. Zhang et al. [17] proposed a strain constraint method to flatten the triangular surface mesh by morphing the original element to an approximate equidistant triangular mesh, which is a good approximation of the input surface model. Bouaziz et al. [18] adopt shape proximity function and shape projection operator to optimize the geometry processing, which can be used for shape preserving deformation and conformal parameterization of geometric models. While iterative solution-based methods yield better results with natural flattened boundaries, they have high computational cost and will lead to non-convergence results in some cases.

Most of the surface flattening algorithms are only for triangular meshes, in order to obtain the flattening results for surfaces composed of triangular elements or quadrilateral elements, a free-form surface flattening method is proposed based on local rigid registration and global energy optimization, mainly consist of two steps: (1) Local rigid registration for single element: each surface element is best align to its correspondence planar element by minimizing their distance; (2) Global stitching operation for all elements: linear elastic finite element energy is used to stitching the transformed element to ensure the validity of the mesh connectivity. The proposed method is mainly based on rigid registration and elastic energy optimization, can be abbreviated as RR/EO method. The rest of this paper is organizing as follows. Section 2 gives the detailed steps of surface flattening, including local alignment of single element and global "stitch" operation. Several experimental results of surface flattening are given in Sect. 3, and the conclusions are finally discussed in Sect. 4.

2 Free-Form Surface Flattening

The purpose of surface flattening is to minimize the parametric deformation between the original surface and the flattened surface as much as possible. To this end, a local to global surface flattening strategy is adopted in this paper. Each surface element (Triangular or Quadrilateral) is transformed to its corresponding planar parametric element by finding the best rotation and translation transform. In order to stich the transformed elements together, the linear elastic finite element energy is used to find an equilibrium state of internal force. The steps of the proposed RR/EO flattening algorithm are summarized in Algorithm 1.

figure a

2.1 Local Alignment of Single Element

Most surfaces are composed of triangular elements, quadrilateral elements and their combination, while most surface flattening algorithms are only for surfaces composed of triangular meshes. This leads to the need for additional split operation for quadrilateral elements, and different element splitting strategies will affect the flattening results. Therefore, the proposed method in this paper needs to be applied to triangular and quadrilateral elements. At the same time, the given element needs to be transformed to make it as close as possible to its corresponding planar parameterization element.

Given a surface element \(E = \left( {v_{{1}} , \ldots ,v_{ne} } \right),\;\;v_{i} = \left( {x_{i} ,y_{i} ,z_{i} } \right) \in {\text{R}}^{{3}}\) is the nodes of the given element, ne is the number of node in element E, and its corresponding planar element is \(E_{t} = \left( {p_{{1}} , \ldots ,p_{ne} } \right),\;\;p_{i} = \left( {x_{i} ,y_{i} } \right) \in {\text{R}}^{{2}}\). The goal is to find a transformation that best superposes the given element E with elements Et. The first step is to transform the three-dimensional element E to the OXY plane and obtain a planar element \(E^{\prime} = \left( {v^{\prime}_{1} , \ldots ,v^{\prime}_{ne} } \right)\). Then, the planar element E′ is aligned to its corresponding planar element Et by minimizing the Euclidean distance between planar element E′ and Et. The mean square objective function to be minimized is:

$$f({\varvec{R}},{\varvec{T}}) = {\raise0.7ex\hbox{$1$} \!\mathord{\left/ {\vphantom {1 {n{\text{e}}}}}\right.\kern-\nulldelimiterspace} \!\lower0.7ex\hbox{${n{\text{e}}}$}}\sum\nolimits_{i = 1}^{{n{\text{e}}}} {\left| {p_{i} - {\varvec{R}}v^{\prime}_{i} - {\varvec{T}}} \right|^{2} }$$
(1)

where R is the 2 × 2 rotation matrix and T is the 2 × 1 translation matrix. This minimizing problem can be solved by many non-iterative optimization methods [19, 20], such as singular value decomposition (SVD) method, quaternion method, etc. Here, the singular value decomposition method is used to get the rigid transformation matrix R and T. The solution of Eq. (1) can be converted into the SVD decomposition of the following matrix:

$${\varvec{H}} = \sum\nolimits_{i = 1}^{{n{\text{e}}}} {(v^{\prime}_{i} - \overline{v})(p_{i} - \overline{p})^{{\text{T}}} }$$
(2)

where \(\overline{v}\) and \(\overline{p}\) are the center of element E′ and Et respectively, calculated by: \(\overline{v} = {1}/n{\text{e}}\sum\nolimits_{i = 1}^{{n{\text{e}}}} {v^{\prime}_{i} }\), \(\overline{p} = {1 \mathord{\left/ {\vphantom {1 {ne}}} \right. \kern-\nulldelimiterspace} {ne}}\sum\nolimits_{i = 1}^{ne} {p_{i} }\). In particular, using SVD, H can be written as

$${\varvec{H}} = {\varvec{USV}}^{{\text{T}}}$$
(3)

The best fit rotation matrix R and translation matrix T can be obtained by

$$\left\{ \begin{gathered} {\varvec{R}} = {\varvec{VU}}^{{\text{T}}} \hfill \\ {\varvec{T}} = \overline{p} - {\varvec{R}}\overline{v} \hfill \\ \end{gathered} \right.$$
(4)

Figure 1 shows the result of local alignment of triangle element. The original triangle v1v2v3 and its corresponding triangle p1p2p3 are plotted in Fig. 1a, b marked by blue solid lines, while the transformed triangle v′′1 v′′2 v′′3 obtained by alignment operation is shown in Fig. 1b with red dotted lines. Figure 2 is a local alignment example of quadrilateral element. In this example, the original quadrilateral v1v2v3v4 is transformed to v′′1 v′′2 v′′3 v′′4 marked by red dotted lines, shown in Fig. 2b.

Fig. 1
figure 1

Local alignment of triangular element: a Original Triangle; b Best fit result

Full size image
Fig. 2
figure 2

Local alignment of quadrilateral element: a Original quadrilateral; b Best fit result

Full size image

2.2 Global Stitching of Planar Mesh

Due to the shape difference between the 3D element and its corresponding 2D element, the locally transformed 2D mesh is disconnected. Then, a global optimization is used to “stitching” the transformed elements together to a 2D mesh, which is derived by minimizing a quadric energy function. The energy function consists of two terms, including the energy caused by nodal loads and the linear elastic strain energy. The global stitching can be seen as an elastic deformation process from the planar element Et to its corresponding transformed element E′′, and the internal force of the nodes will inevitably be generated during the deformation process.

Suppose a 2D surface element \(E_{t} = \left( {p_{{1}} , \ldots ,p_{ne} } \right),\;\;p_{i} = \, \left( {x_{i} ,y_{i} } \right) \in {\text{R}}^{{2}}\) and its corresponding transformed surface element \(E^{\prime\prime} = \, \left( {v^{\prime\prime}_{{1}} , \ldots ,v^{\prime\prime}_{ne} } \right),\;\;v^{\prime\prime}_{i} = \, \left( {x^{\prime\prime}_{i} ,y^{\prime\prime}_{i} } \right) \in {\text{R}}^{{2}}\). The displacement vectors of the surface mesh in the global coordinate system are \({\varvec{q}}^{{\text{e}}} = \{ \Delta x_{{1}} ,\Delta y_{{1}} , \ldots ,\Delta x_{ne} ,\Delta y_{ne} \}\). The elements of displacement vector qe can be calculated as follows: \(\Delta x_{i} = x^{\prime\prime}_{i} - x_{i} ,\;\Delta y_{i} = y^{\prime\prime}_{i} - y_{i} ,i = { 1}, \ldots ,n{\text{e}}\). Considering that the transformed element E′′ is obtained by the linear elastic deformation of its corresponding planar surface element Et, the stress of the element is

$$\sigma = {\varvec{DBq}}^{{e^{{\text{T}}} }}$$
(5)

where B is strain matrix and D is linear elastic matrix. Therefore, the internal force of the nodes in the global coordinate system of the surface mesh is defined as follows

$${\varvec{F}}_{{{\text{in}}}}^{{\text{e}}} = \int\limits_{{\text{e}}} {{\varvec{B}}^{{\text{T}}} \sigma d{\text{v}}} = {\varvec{k}}^{{\text{e}}} {\varvec{q}}^{{{\text{eT}}}}$$
(6)

The matrix ke is the element stiffness matrix of the quadrilateral element and triangular element which can be calculate by the three-node triangular element and planar four-node isoparametric element [21]. After calculating the node internal forces of each element by formula (6), suppose that \(L\left( i \right) = \left\{ {l_{{1}} , \ldots ,l_{m(i)} } \right\}\) denotes m(i) surface elements adjacent to the node vi. The internal force of node vi is obtained by superposition of its adjacent elements

$${\varvec{F}}_{{{\text{in}}}}^{i} = \sum\nolimits_{i \in L(i)} {{\varvec{F}}_{in}^{{{\text{e}}L{(}i)}} }$$
(7)

\(F_{{{\text{in}}}}^{eL(i)}\) represents the internal force of element eL(i) at node vi. The internal force Fin of the global surface mesh is obtained by the integration of \(F_{{{\text{in}}}}^{i}\) of each node.

According to the linear elastic finite element theory, the linear elastic strain energy is defined as follows:

$${\varvec{E}}_{{\text{B}}} \left( {\varvec{q}} \right)_{{}} = {\varvec{qKq}}^{{\text{T}}}$$
(8)

The energy caused by the external load of the node is:

$${\varvec{E}}_{{\text{F}}} \left( {\varvec{q}} \right)_{{}} = {\varvec{qF}}_{{{\text{in}}}}$$
(9)

Among them, K is a 2n × 2n global stiffness matrix composed of element stiffness matrix ke; \({\varvec{q}} = \, \{ \Delta x_{{1}} ,\Delta y_{{1}} , \ldots ,\Delta x_{{\text{n}}} ,\Delta y_{n} \}\) is a 1 × 2n vector of the node displacements, and n is the number of nodes in the surface mesh. The displacements of all nodes are obtained by minimizing the following sum of all energy terms:

$${\varvec{E}}\left( {\varvec{q}} \right) \, = {\raise0.5ex\hbox{$\scriptstyle 1$} \kern-0.1em/\kern-0.15em \lower0.25ex\hbox{$\scriptstyle 2$}}{\varvec{q}}K{\varvec{q}}^{{\text{T}}} + \theta {\varvec{qF}}_{{{\text{in}}}}$$
(10)

where θ is the weight of nodal load, generally set it to 0.6–08. The above energy function is quadratic, which can be solved by a sparse linear system:

$${\varvec{Kq}}^{{\text{T}}} = \theta {\varvec{F}}_{{{\text{in}}}}$$
(11)

In each iteration of the proposed surface flattening algorithm, the position of all nodes is updated as: Pt+1 = Pt + qt, and new node positions are used as the initial planar mesh of the next iteration. In order to make the iteration converge, the terminal condition for the iterative procedure is determined as:

$$\left\| {{\varvec{q}}_{t} } \right\| = {\raise0.7ex\hbox{$1$} \!\mathord{\left/ {\vphantom {1 {2n}}}\right.\kern-\nulldelimiterspace} \!\lower0.7ex\hbox{${2n}$}}\sum\nolimits_{i = 1}^{2n} {({\varvec{q}}_{t}^{i} )^{2} \le \sigma {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\text{or}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} t \ge } {\kern 1pt} t_{\max }$$

where σ is a given precision and tmax is a given maximal number of iterations.

The surface flattening method proposed in this paper requires an initial parameterization to start the iterative solution. The basic requirement of initial parameterization is that it has a valid mesh connectivity without too much parameterization distortion, and be fast to generate. Therefore, the shape-preserving surface parameterization method proposed by Floater [2] can be used to quickly obtain the plane mesh with fixed convex boundary. An appropriate pre-defined outer boundary can be obtained mainly by the following steps: (1) Calculate the average normal of the surface, and then project the boundary of the surface onto the plane according to the normal direction; (2) Remove unnecessary points in the boundary by the Douglas-Peucker method; (3) Remove all concave points in the boundary iteratively until the boundary is convex.

3 Experimental Results

The proposed surface flattening algorithm have applied to flatten a variety of mechanical models, running on a machine with Core i7 2.6 GHz CPU and 8 GB memory, and here are some of them. Figure 3 shows the main steps of RR/EO surface flattening method. Figure 3a is the original surface mesh. With the automatically created outer boundary, the initial parameterization mesh shown in Fig. 3b is obtained by using Floater's shape-preserving method [2]. The transformed elements with local alignment operation are shown in Fig. 3c. Figure 3d is the final surface flattening result after three iterations. From the example shown in Fig. 3, it can be seen that the initial flattened mesh by shape-preserving method meets the requirements of the proposed iterative surface flattening algorithm, so the shape-preserving method is used to generate the initial solution in the follow-up.

Fig. 3
figure 3

Surface flattening of an oil drain: a Original surface; b Initial flattened mesh; c Local alignment; d Flattened result

Full size image

To demonstrate the effectiveness of the proposed method, the RR/EO method is compared with Local/Global method proposed in [12]. Figure 4 shows the flattening results of a sheet metal part. The original surface mesh of a sheet metal part is shown in Fig. 4a and b is the initial parameterization mesh. The flattened results using RR/EO method and Local/Global method are shown in Fig. 4c and d.

Fig. 4
figure 4

Surface flattening of a sheet metal part: a Original surface; b Initial flattened mesh; c RR/EO method; d Local/Global method

Full size image

Figure 5 is a surface flattening example of rock arm. It is necessary to fill the internal holes of rock arm surface when using shape-preserving surface parameterization method. Figure 5a displays the original rock arm model with 9312 triangular elements and 4952 nodes. Figure 5b shows the flattened result using RR/EO method after four iterations, while the flattened result by Local/Global method is plotted in Fig. 5c. As can be seen from Fig. 5b, the mesh distortion between the flattening result and the original model is small.

Fig. 5
figure 5

Surface flattening of a rock arm: a Original surface; b RR/EO method; c Local/Global method

Full size image

Different with most other surface flattening algorithms, the proposed method can directly flatten surfaces consisting of triangular and quadrilateral meshes. In sheet metal forming simulation, it is usually necessary to flatten the model to predict the size of blank. Then, two flattening examples of automobile body parts composed of triangular and quadrilateral meshes are given in the following. Figure 6a–c are the original surface, initial guess mesh and flattened result of auto-body panel respectively. Figure 7a shows the original surface of a fender model, and the flattened meshes generated by RR/EO method is displayed in Fig. 7b. Since the surfaces are hybrid meshes consisting of triangles and quadrilaterals, it is necessary to subdivide a single quadrilateral into two triangles for operating by Local/Global method.

Fig. 6
figure 6

Surface flattening of an auto-body panel: a Original surface; b Initial flattened mesh; c Flattened result

Full size image
Fig. 7
figure 7

Surface flattening of a fender: a Original surface; b Flattened result

Full size image

In order to measure the flattening distortion, the angle and area distortions are calculated as follows:

$$D^{angle} = {\raise0.7ex\hbox{$1$} \!\mathord{\left/ {\vphantom {1 {3n{\text{Elem}}}}}\right.\kern-\nulldelimiterspace} \!\lower0.7ex\hbox{${3n{\text{Elem}}}$}}\sum\nolimits_{k = 1}^{{n{\text{Elem}}}} {\sum\limits_{i = 1}^{ne} {{\raise0.7ex\hbox{$1$} \!\mathord{\left/ {\vphantom {1 {(\beta_{i}^{k} )^{2} }}}\right.\kern-\nulldelimiterspace} \!\lower0.7ex\hbox{${(\beta_{i}^{k} )^{2} }$}}(\alpha_{i}^{k} - \beta_{i}^{k} )} }^{2}$$
(12)
$$D^{{a{\text{rea}}}} = \sum\limits_{k = 1}^{{n{\text{Elem}}}} {\omega_{k} {\raise0.7ex\hbox{$1$} \!\mathord{\left/ {\vphantom {1 {A(E_{k} )^{2} }}}\right.\kern-\nulldelimiterspace} \!\lower0.7ex\hbox{${A(E_{k} )^{2} }$}}(A(E^{\prime\prime}_{k} ) - A(E_{k} ))}^{2}$$
(13)

where αik and βik denote the angle of elements of flattened surface and original surface respectively; nElem is the number of elements; A(Ek′′) is the area of element in flattened surface and the area of its corresponding element in original surface is A(Ek); ω is a weight defined by \(\omega_{k} = {{A(E_{k} )} \mathord{\left/ {\vphantom {{A(E_{k} )} {\sum {A(E_{k} )} }}} \right. \kern-\nulldelimiterspace} {\sum {A(E_{k} )} }}\). Table 1 shows the statistics of flattening distortion and computational time between the proposed method and Local/Global method proposed in [12]. As can be seen from Table 1, the proposed RR/EO method can achieve better results with lower area distortion and is relatively stable for irregular meshes because of its physical background.

Table 1 Comparisons of flattening distortion and running time
Full size table

4 Conclusions

Surface flattening has been widely used in sheet metal forming simulation and computer aided design. In this paper, a surface flattening algorithm based on local rigid registration and global elastic energy optimization is proposed. The method uses a local-to-global strategy to transform a single element to a parametric space, and the final flattened surface is obtained by using a linear elastic energy optimization model to stitch the elements after local transformation. Experiments show that this method is suitable for surface flattening with arbitrary shape, and the flattening results have the advantages of free boundary and less distortion. Unlike other methods based on geometric feature optimization, this method has definite physical meaning and achieves a good balance in solving time and flattening results. At the same time, unlike most methods only for triangular meshes, the proposed method is suitable for surfaces composed of triangular and quadrilateral meshes. For models with large number nodes, the time consumption of the proposed RR/EO algorithm is not fast enough. In the future, it will be considered to flatten the surface in patches, which can improve the efficiency and speed of flattening.