1 Introduction

Mesh segmentation has become an important task in many CAD CAM CAE areas. Its applications range widely in topics such as mesh animation [1, 2], surface parameterization [3, 4], mesh compression [5, 6] and shape processing [7, 8].

The problem is as follows: given the mesh of a (connected) surface, break it up into a set of smaller sub-meshes which together compose the initial mesh. Solving this problem becomes crucial when some procedure must be carried on surfaces with particular properties, such as developability for parameterization or decomposition into primitive shapes for shape processing or mesh animation.

Usually a geometric approach is followed to face this problem as geometric constraints can be easily defined on the surface based on the user desired result. However, there are cases in which geometry transitions are not strong enough to trigger a mesh partition, while the topology of the mesh indicates a clear discontinuity, that should result in a mesh partition.

Since a mesh can be seen as an undirected graph, study of graph topology and methods of graph partitioning can be almost immediately extrapolated to mesh segmentation. Graph and mesh Laplacians have been a topic of extensive research and their spectra have shown to be a powerful tool for segmentation [9–12].

Finally, mixed approaches have also been proposed. Mixed approaches define schemes based on graph theory, but including geometric data. For example, finite elements schemes of the Laplace-Beltrami operator lead to the cotangent weights method [13]. These schemes are strong in terms of both geometric and topologic information which makes them so reliable for mesh processing.

Despite the advantages that mixed schemes may have, we believe that there should be first a deep understanding of relevant topological information for mesh segmentation.

Since there are voids in the understanding of Topological and Geometrical mesh properties, human interaction is still required to supervise these automatic mesh segmentation methods. In this article we illustrate how the second eigenvector of the Laplacian (Fiedler vector) carries important features for graph and mesh segmentation. We use the monotonically increasing permutation of the Fiedler vector to re-label the mesh nodes. This re-labeling reflects strength of connectivity among graph components and therefore determines a partition of the mesh.

Figure 1 shows 3 scenarios of application of our mesh partition algorithm. Figure 1a presents a fully automatic scenario. Figure 1b displays our algorithm steered by a human operator, via direct setting of the mesh separation parameters. Figure 1c depicts our algorithm parameters being controlled via a Graphic User Interface (GUI) which would set the mesh separation parameters. In all 3 cases, some sub-meshes are removed from the source mesh in iteration i. The remaining mesh becomes the source mesh for iteration \(i+1\). The iterations proceed until the input mesh is null or should not be split further.

Fig. 1
figure 1

Scenarios of mesh segmentation

Full size image

The remainder of this article is organized as follows: Sect. 2 reviews the relevant literature. Section 3 presents our segmentation approach. Section 4 discusses results for many datasets. Section 5 concludes the article and introduces what remains for future work.

2 Literature review

Mesh segmentation has been an important research topic for computer design. Different algorithms have been proposed for segmentation based on different foundations of many areas such as statistics, optimization, graph theory and many others. An algorithm lies in one of the following classes depending on which data is relevant for segmentation: (i) geometry-based segmentation, (ii) topology-based segmentation and (iii) mixed-approach segmentation. A brief discussion of current state of the art methods is presented below following the proposed classification.

2.1 Geometry-based segmentation

Geometry-based methods extract geometric data from the mesh such as euclidean and geodesic distances or curvatures. Then, a clustering algorithm is usually applied assuming that geometrically similar points likely belong to the same cluster. In [6] a k-means algorithm is directly applied to the geometry data of the mesh and therefore needs a post-processing algorithm (which they call multiple principal plane analysis) for smooth definition of boundaries between sub-meshes. In [4] tangent curvatures are computed by curve fitting before clustering. In [14] curvatures and normals are computed and then a Student-t mixture model is used for the partition.

Region-growing methods are expansive clustering techniques that define seed points or faces on the mesh and as their name suggest, expand until some geometric constraint is violated. In [15] an angle variation threshold between faces is defined for the algorithm and in [16] a variational formulation is proposed for segmentation by fitting quadric surfaces.

Other statistical techniques have been applied for mesh segmentation. By generating some random field on a mesh, the distribution of some objective function can be used for partitioning. In [17] several segmentation algorithms generate random fields on the surface which are later evaluated by their cost function. In [18] an energy function is first defined and random fields are applied to the mesh. The distribution of the energy field in terms of the random fields is then used to divide the surface.

For these algorithms, we remark two potential drawbacks: (i) most of them are not fully deterministic which does not guarantee the same results for the same surface and (ii) as we mentioned before, topology information is usually discarded which might be important in several cases.

Learning approaches try to replicate shapes from previously learned geometries. This in fact requires the algorithm to be calibrated first using already segmented meshes as can be seen in [19–21]. However, these methods require lots of datasets for training that must be similar to the mesh which limits the algorithm and as can be noted, training meshes must be segmented somehow.

2.2 Topology-based segmentation

Topology-based algorithms on the other hand, rely on the features lying on the structure of the mesh without considering geometric features. Recall that a mesh has a graph representation and the topologic properties of this graph can be used for segmentation. However, some assumptions must be first made on the mesh sampling since the same surface may be represented by different connectivities.

The motorcycle algorithm first proposed by Eppstein et al. [22] consists of following a particle across straight paths that start at what they define an extraordinary vertex and end at vertices visited by other particles. Gunpinar et al. [23, 24] have presented several approaches based on this idea though, this method is currently limited to quadrilateral meshes.

In [17] segmentation is achieved by simultaneous clustering of similar meshes. However, this task requires maximum correspondence between faces which is not usual in CAD models due to meshing procedures and refinements. In [8] the authors propose a segmentation by labeling vertices based on convexity flags.

Graph cuts have been successfully used for mesh segmentation as seen in [25], where an interactive approach is followed by letting the user to draw strokes on areas where he wants the partition.

Reeb graphs have been also explored for mesh segmentation. After a field is defined on the mesh graph, the reeb graph is computed. Correct choice of the field is critical for an adequate segmentation. For example, in [26, 27] the authors propose geodesic-based fields, while in [28] eigenvectors are used instead.

Algorithms that rely solely on the mesh topology are less common in the literature due to the sampling constraints and the lack of geometric features which might be important in many applications leading to the next class of algorithms.

2.3 Mixed-approach segmentation

A mixed approach can be followed by extracting features from both topology and geometry. For example, in [29] an improvement of the motorcycle algorithm is presented. By assigning different velocities to particles the geometry of the surface is taken into account however, the limitation of quadrilateral meshes is still present.

In [7] slippage analysis is used for mesh segmentation. Localities of points are used to compute some measures such as slippage and curvature. Depending on the measured features, primitive shapes such as planes, spheres and cylinders are recognized. The problem with this method is that some surfaces may present complex shapes not recognized by the algorithm. Additionally, since the method is presented for clouds of points, the algorithm is very sensitive to neighbor sizes.

An important operator has been widely used for mesh segmentation: the Laplacian operator. The definition of most mesh Laplacian follow classic graph Laplacian definitions naturally which strongly encodes topologic features. Geometric features are also considered by weighting schemes defined on the graph of the mesh. In [12] and [30] interactive approaches are presented where eigenvectors of the Laplacian are chosen for the segmentation and in [9] eigenvectors are automatically chosen by an empirical criteria and a k-means algorithm is then applied on the selected subset of eigenvectors.

Harmonic functions of the Laplacian operator have been also used. After some region is selected, dirichlet conditions are introduced to the operator and a linear system of equations arises. In [31] an interactive algorithm is presented where the user draws strokes across desired boundaries and in [32] a similar algorithm is presented for segmentation of dental meshes. Heat kernels have been also explored for mesh segmentation [33, 34] where dirac delta initial conditions are imposed.

2.4 Conclusions of the literature review

Significant uncertainty currently exists about how the topology of the mesh encodes relevant features for segmentation. This uncertainty usually leads most researchers to address the mesh segmentation problem from the geometry-based approach. In contrast, we consider that spectral analysis presents large potential for segmentation [9, 12]. However, heavy user-interactivity is required and parameterizations of the algorithms are based on empirical results. Figure 2 shows the result of application of state-of-art software by GeoMagic TM for geometry-based segmentation and parameterization at the same time. To obtain this result, a significant amount of user actions is required, to correct non-manifold situations and to eliminate patches with extreme shape factor. We contend that by separating segmentation from parameterization, it is possible to obtain larger sub-meshes. In addition, we will show that using topologic over of geometric segmentation would better highlight functional features of the object.

Fig. 2
figure 2

Result of mesh segmentation/parameterization with GeoMagic TM. Intensive user editing is required to correct non-manifold situations and patches with extreme shape factor

Full size image

In this article we illustrate how the Fiedler parameters encode connectedness properties of the graph mesh. Based on these results, an intuitive method is presented for exploiting these properties. A topology-based algorithm is introduced by constructing the classic graph Laplacian with constant weights and successful segmentation of homogeneous meshes is achieved. The limitation to homogeneous meshes can be partially overcome by extending the scheme to a mixed approach but the pure topologic nature of the algorithm gives faster and computationally stable results. Also, since the method follows an intuitive result from spectral analysis, a deeper understanding of topology-based implicitly arises and opens the doors for further research.

Our proposed algorithm produces segmentations that obey the connectivity of a homogeneously connected mesh (i.e. with quasi-uniform triangle edge length). Notice that such an algorithm requires a human steering (likely to be interactive), to reject over-fragmentation, or to set the threshold of Fiedler vector discontinuity, that triggers split of a sub-mesh from the source mesh.

3 Methodology

We consider triangular meshes M which are connected, 2-manifolds embedded in \({\mathbb {R}}^3\). M is defined by a set points \(X = \{ x_1,x_2,\ldots ,x_n \}\) which together describe the geometry of M and a set of triangles \({\mathcal {T}} = \{\tau _1,\tau _2,\dots ,\tau _p\}\). Each triangle is a sequence of edges \(\tau _i = (e_a, e_b, e_c)\) where each \(e_j\) belongs to a set of edges \(E=\{e_1,e_2,\ldots ,e_m\}\). This structure describes the connectivity on M.

\(G=(X,E)\) is therefore the (undirected) graph representation of M where X is seen as the set of vertices of the graph and E is the set of edges. Since M is connected, so is G.

The problem of mesh segmentation consists of dividing M into k disconnected components. For solving this problem we propose an algorithm that re-labels the vertices of the graph based on the Fiedler vector. Figure 3 presents the steps of the algorithm. Some preliminary key results of spectral theory are briefly discussed first.

Fig. 3
figure 3

Diagram of the algorithm

Full size image

3.1 Graph Laplacian

In spectral graph theory, the adjacency matrix W of G is defined as:

(1)

where \(w_{ij}\) is the adjacency weight between \(x_i\) and \(x_j\). For our algorithm we take \(w_{ij} = 1\) guaranteeing that only the topology of the graph mesh is considered.

If D is a diagonal matrix with entries \(D_{ii} = \sum _j w_{ij}\), then D is the degree matrix of G. The Laplacian matrix of G is therefore defined as \(L = D-W\). Let \(f : X \rightarrow {\mathbb {R}}\) with \(f(x_i) = f_i\) be a field defined on the vertices of the graph, then Lf acts locally on each vertex in the following manner:

$$\begin{aligned} (Lf)_i = \sum _j w_{ij}\left( f_i-f_j\right) \end{aligned}$$
(2)

Equation (2) defines another field Lf on the vertices of the graph where each \(x_i\) gets assigned the weighted differences between \(f_i\) and its neighboring field i.e. all \(f_j\) such that \(x_j \in N(x_i)\).

3.2 Fiedler vector

We consider the set of eigenvalues \(\lambda _1 \le \lambda _2 \le \cdots \le \lambda _n\) of L and their corresponding eigenvectors \({\varvec{u_1}},{\varvec{u_2}},\ldots ,{\varvec{u_n}}\). There are some important results from graph theory on these eigenvalues and eigenvectors [35, 36]:

  1. 1.

    The first eigenvalue \(\lambda _1\) is equal to 0 and its corresponding eigenvector \({\varvec{u_1}}\) is the constant vector i.e. \(u_1(x_i) = 1\).

  2. 2.

    The second eigenvalue \(\lambda _2\) is known as the Fiedler value (or algebraic connectivity) and its corresponding eigenvector \({\varvec{u_2}}\) is known as the Fiedler vector.

  3. 3.

    Since G is connected, \(\lambda _2 > 0\) and therefore \({\varvec{u_2}}\) is orthogonal to the constant vector i.e. \(\langle {\varvec{u_1}},{\varvec{1}} \rangle = 0\).

  4. 4.

    The Fiedler vector solves the following optimization problem:

    $$\begin{aligned} {\varvec{u_2}} = \mathop {\hbox {argmin}}\limits _{{\varvec{u}}\bot {\varvec{1}}} \frac{{\varvec{u}}^TL{\varvec{u}}}{{\varvec{u}}^T{\varvec{u}}} \end{aligned}$$
    (3)

The algebraic connectivity is highly related to the connectedness of the graph. Figure 4 illustrates how the second eigenvalue of the Laplacian matrix can give us an idea of such connectedness. The loop graph presents less algebraic connectivity than the full graph since it requires less cuts to divide the graph. However, the two full graphs connected by a single edge show the smallest algebraic connectivity since cutting that edge is enough to split the graph despite the high connectedness of both graphs.

Fig. 4
figure 4

Some graphs and their algebraic connectivity: a loop graph with ten vertices, b full graph with ten vertices and c two full graphs of ten vertices connected by an edge

Full size image

Figure 5 shows the Fiedler vector for the connected full graphs (Fig. 4c). Here the Fiedler vector is a positive function in terms of the current vertex labeling. Also, low connectivity regions [edge \((v_{10},v_{11})\)] show high changes in the Fiedler vector compared with high connectivity regions (other vertices). This behaviour is expected since Eq. (3) will see less penalization in low connectivity regions, and motivates our algorithm: by re-labeling the vertices of the graph such that the Fiedler vector becomes a positive function in terms of the re-labeled vertices, we can find low and high connectivity regions based on this intuition and set a segmentation criterion.

Fig. 5
figure 5

Fiedler vector for the two full graphs (Fig. 4c). Vertices labeled from 1 to 10 belong to the first full graph and vertices labeled from 11 to 20 belong to the second full graph. The vertices 10 and 11 connect the graphs

Full size image

3.3 Laplace-Beltrami operator

Let \({\mathcal {M}}\) be an oriented Riemannian 2-manifold embedded in \({\mathbb {R}}^3\). \({\mathcal {M}}\) is connected. The Laplace-Beltrami operator \(\varDelta : L^2({\mathcal {M}}) \rightarrow L^2({\mathcal {M}})\) on \({\mathcal {M}}\) is defined as [37]:

$$\begin{aligned} \varDelta \phi = -(\hbox {div} \circ \nabla ) \phi \end{aligned}$$
(4)

where \(\phi \in L^2({\mathcal {M}})\), \(\nabla \) is the gradient operator on \({\mathcal {M}}\) defined as:

$$\begin{aligned} \nabla \phi = \sum _{i} g^{ij} \frac{\partial \phi }{\partial {\varvec{y^i}}} {\varvec{\frac{\partial }{\partial y^j}}} \end{aligned}$$
(5)

and \(\hbox {div}\) is the divergence operator defined as:

$$\begin{aligned} \hbox {div} {\varvec{Y}} = \frac{1}{\hbox {det}(g)} \sum _i \frac{\partial }{\partial {\varvec{y^i}}} \left( Y^i\sqrt{\hbox {det}(g)}\right) \end{aligned}$$
(6)

g is the metric tensor of \({\mathcal {M}}\), \(g^{ij}=(g_{ij})^{-1}\) are the components of the inverse of the metric tensor, \({\varvec{Y}} \in T M\) is a vectorial field defined on the manifold (local tangent planes) and \(Y^i\) are its corresponding components in local coordinates \({\varvec{\frac{\partial }{\partial y^i}}}\).

The Laplace-Beltrami operator is a generalization of the standard Laplacian taken to manifolds. From this point of view, the differential equation \(\varDelta \phi =\lambda \phi \) on the manifold can be seen as an analogue of the Helmhotz equation. The Helmhotz equation models the time-independent component of the wave equation on a given domain. Schemes for discretization of such operator on triangular surfaces have been presented in the literature [13, 38] resulting in weighted Laplacians of the given mesh graphs. This result motivates our work since the consideration of an homogeneous mesh leads to a scaled solution of Eq. (3).

3.4 Algorithm description

The idea of our approach consists in dividing the mesh into components with uniform connectivity. As we illustrated in Fig. 5, low connectivity areas present higher changes of the Fiedler vector with respect to some labeling of the vertices of the graph. These changes can be described by discrete differences on the Fiedler vector. Also, components with uniform connectivity have uniform differences and high changes in the discrete differences imply relevant topologic changes in the mesh graph. Therefore, high absolute differences of second order on the Fiedler vector with respect to a specific labeling of the vertices define good cut points for segmentation.

The vertices of the mesh must be re-labeled such that the Fiedler vector is an increasing function in terms of the re-labeling since the segmentation will be defined by cutting thresholds on the Fiedler vector. Below the proposed algorithm (Fig. 3) is described:

  1. 1.

    Construction of the Laplacian matrix: Build the sparse Laplacian matrix L of the graph representation G of the connected mesh M as defined in Sect. 3.1.

  2. 2.

    Computation of the Fiedler vector: Compute the Fiedler vector \({\varvec{u_2}}\) of L by using some eigensolver.

  3. 3.

    Sorting of the Fiedler vector: Compute \({\varvec{u'_2}}\) as a sorting of \({\varvec{u_2}}\) in ascending order.

  4. 4.

    Re-labeling of the vertices of the mesh: Compute V where \(V = \{v_1,v_2,\ldots ,v_n\}\) is a re-labeling of X such that \(v_i = x_k\), \(u'_2(v_i) \le u'_2(v_{i+1})\) and \(v_i \ne v_j, \forall i \ne j\).

  5. 5.

    Computation of the Fiedler second differences: Compute the absolute second differences \(d(v')\) of \({\varvec{u'_2}}\) with respect to \(v'\). This is equivalent to compute \(d_i = | 2u'_2(v'_i) - u'_2(v'_{i-1}) - u'_2(v'_{i+1}) |\).

  6. 6.

    Application of a filter: A low-pass filter must be applied to d since the sampling of the mesh can lead to noise in the computed second differences. Compute the filtered second differences \(d'\).

  7. 7.

    Finding local maxima: Compute \(t_1,t_2,\ldots ,t_{k-1}\) where \(t_1\) is the global maximum of \(d'(v')\) and each \(t_i\) is a subsequent (local) maximum (recall that k is the desired number of components to partition the mesh).

  8. 8.

    Setting the segmentation thresholds: The segmentation of the mesh is achieved by setting the thresholds \(u'_2((d')^{-1}(t_i))\) on the Fiedler vector.

4 Results

We now present some results of our algorithm applied to several datasets. In each case the Fiedler vector was computed by the Implicitly Restarted Arnoldi Iteration algorithm which comes implemented in the ARPACK package [39]. Also, a moving average was implemented for the filtering of the second order differences with window sizes ranging between 1–\(10~\%\).

Figure 6 shows the triangular mesh of the iron model. This mesh consists of 35,582 points and 71,164 triangles. Figure 7 shows the Fiedler vector of the iron mesh. Topology of the graph of such (homogeneous) mesh still preserves many geometric properties of the surface. Isolines of the Fiedler vector (Fig. 7b) show how the highly connected areas present low changes in the Fiedler vector with respect to geometry while the lower ones present high changes.

Fig. 6
figure 6

Homogeneous triangular mesh of the iron model

Full size image
Fig. 7
figure 7

Fiedler vector on the iron mesh: a the field goes from blue (lower values) to red (higher values) and b isolines of such of field are drawn in blue (colour figure online)

Full size image

The Fiedler vector is then sorted as described in Sect. 3.4 and re-labeling of the vertices is made. Figure 8 shows the re-labeling results for the iron. As we pointed in Sect. 3 the sorted Fiedler vector shows higher changes in specific regions (Fig. 8a) which correspond to relative changes of the Fiedler isolines in Fig. 7b. The second differences plot (Fig. 8b) shows a concentration of several peaks near desired cut points. Selecting thresholds from this signal would lead to several disconnected components near the same isoline which is not desired. Therefore this signal must be filtered first as described in Sect. 3.4. The filtered signal is presented in Fig. 8c. Such filtering allows the algorithm to automatically detect good cutting isolines. By setting \(k = 3\), global maxima are computed in the filtered differences resulting in two thresholds (red lines) for the Fiedler vector which will divide the surface by the corresponding isolines. These thresholds coincide with high changes in the slope of the sorted Fiedler vector as seen in Fig. 8a. The resulting segmentation is presented in Fig. 9. Notice how the resulting partition divided the mesh into two high connectivity regions (blue and red) and a low connectivity region (green).

Fig. 8
figure 8

Re-labeling of the vertices (x axis) and corresponding function on the iron mesh: a Fiedler vector, b second differences and c filtered second differences. Lines in red show the cut points for segmentation (colour figure online)

Full size image
Fig. 9
figure 9

Segmentation of the iron mesh

Full size image

In contrast with the segmentation of a homogeneous mesh, Fig. 10 presents results for a non-homogeneous mesh of the same model. The Fiedler vector of the graph mesh does not follow adequately the geometry of the surface (Fig. 10a) due to the non-homogeneous sampling as seen in Fig. 10a and as a consequence, the connectivity of the graph does not follow correctly our intuition of the geometry of the mesh anymore. Additionally, isolines present undesired behaviours along the surface which would result into components with more irregular boundaries. The segmentation of this mesh under our approach is presented in Fig. 10c. Notice that the segmentation is less intuitive since the topology of the mesh graph is more discordant with the geometry of the iron model and boundaries of disconnected components are located at more geometrically random places. These results illustrate the importance of the homogeneity of the mesh for adequate results of the proposed algorithm.

Fig. 10
figure 10

Segmentation of a non-homogeneous mesh of the iron model

Full size image

Table 1 presents the results of our algorithm applied to several datasets usually used in CAD applications or Computer Graphics. Since the algorithm only takes into account the topology of the mesh, it is not expected to partition the mesh by its sharp edges. However, the achieved segmentation agrees with some of these sharp edges as can be seen in the gears and crankshaft datasets showing the importance of the topology even in these cases. It is important to emphasize the importance of the user interaction since different results can arise depending on the selection of the parameter k as seen in the flange yoke dataset. The segmentation of the rest of the meshes presents intuitive results which illustrates the fact that high changes in the Fiedler vector can be used as boundaries between different shapes.

Table 1 Appraisal of the results of the segmentation algorithm applied to several datasets
Full size table
Fig. 11
figure 11

Results of our algorithm for several datasets. Princeton datasets [11 (a), 11 (b), 11 (c)]. Laboratorio de CAD CAM CAE U. EAFIT datasets [11 (g), 11 (h), 11(i)]

Full size image

5 Conclusions

We illustrated how the Fiedler vector encodes some features of the surface concerning to the connectivity of the mesh graph. These features allowed us to develop a simple algorithm for automatic segmentation of homogeneous meshes. Keeping the discussion at the topologic level allowed us to intuitively show several important characteristics of the second eigenvector of the mesh graph Laplacian.

For the segmentation a re-labeling of the vertices of the mesh is made in such a way the vector Fiedler is increasing in terms of the re-labeled vertices. The algorithm is still applicable to general graphs given the fact that geometry is not taken into account while using constant weights makes the algorithm faster and more stable computationally. However, this advantage comes with a cost requiring the mesh to be homogeneous as we illustrated in Sect. 4. Adequate results were presented for many complex datasets usually used in the context of CAD CAM CAE and Computer Graphics applications. These results proved to be in concordance with user intuitive partitions which is very important since only topologic aspects are considered. Possible future work could be the adaptation of the method to non-homogeneous meshes. Also, future consideration of the geometry could lead to better results.

The algorithm presented by us would typically work within a Divide— and—Conquer or Iterative scheme. In this manner, each run would subtract some sub-meshes of the source mesh, gradually reducing the size of the problem. Each iteration would take the input of a human user to steer each removal iteration and/or to set the values of discontinuities in the Fiedler vector permutation, which would in turn cause mesh-fragmentation.