# CAD Model Segmentation Algorithm Using the Fusion of PERT and Spectral Technology

Authors: Li Hao; Rong Mo; Binbin Wei
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

For complex CAD models, model segmentation technology is an important support for model retrieval and reuse. In this article, we first propose a novel CAD model segmentation method that uses the fusion of the program/project evaluation and review technique (PERT) and the Laplacian spectrum theory. By means of PERT, spectral theory, and the CAD models’ geometrical and topological information, we transform the b-rep model faces into two-dimensional coordinate points corresponding to the nodes of the attributed adjacent graph (AAG). Thek-means approach with the Silhouette coefficient was employed to conduct unsupervised learning of the coordinate points. The experimental results demonstrate that (1) the proposed approach can effectively transform the b-rep model into a two-dimensional coordinate point set; (2) the k-means algorithm can efficiently cluster points to achieve segmentation; and (3) in view of human cognition, the segmentation results are more reasonable. It can effectively divide the point set into several groups to achieve the model segmentation.


---

## Body

## 1. Introduction

In terms of the CAD model retrieval, model decomposition as important support technology has been a concerned issue in computational geometry. For complex CAD models, model segmentation technology is an important support for model retrieval and reuse. Especially in partial retrieval, it aims at dividing the complex CAD model into several simple components. That is to say, a CAD model will be converted into a set with all components as elements. Subsequently, the efficiency of the partial retrieval is determined by the granularity of the model elements. When the models are complex, the triangles in mesh models are not sufficiently large as the face in b-rep models [1]. Therefore, it is imperative to introduce model segmentation, where models are divided into several model components with some basic shape features, replacing triangles or faces.Traditional segmentation methods are primarily used for mesh models instead of general mechanical CAD models [1]. Their core idea is to divide the model surface into a group of connected subgrids with a simple shape, i.e., by calculating the discrete curvature [2, 3]. This kind of segmentation could be interpreted only in a purely geometric sense without any semantic meaning. It is difficult for the segmented regions to be used for model retrieval. Furthermore, these methods require more computational cost which limits the algorithm usage for mechanical CAD models.To solve the issue mentioned above, we introduce a novel segmentation approach using the fusion of the program (or project) evaluation and review technique (PERT) and the spectral theory.The PERT is used in project management to analyze and schedule the tasks involved in completing a given project. It is a statistical tool based on network diagram to calculate the time parameters and allocate resources for each task [4]. Castro et al. presented how to use the PERT to control the project [5]. Ballesteros-Pérez updated the PERT and proposed a refined M-PERT to conduct the modeling of real-life projects and deal with activities that have uncertain durations [6].Spectral theory is a branch of mathematics that relates the eigenvalue spectra of the adjacency matrix or Laplacian matrix of graphs with other geometric invariants of the graph [7, 8]. Graph spectrum is an ordered sequence of eigenvalues of adjacency matrices, which can describe topological structure information of graphs in vector form, and the computation time is polynomial. The Laplacian matrix can be used to find many useful properties of a graph [9]. Chung proposed a refined version of the graph spectra, which is based on the Laplacian matrix of the graph and correlates with the graph invariants better than the spectra of the original adjacency matrix [10].In this article, we propose an innovative method for b-rep model: employing the PERT and spectral theory to preprocess the CAD models to transform each face of the b-rep model into a two-dimensional coordinate point, and taking use of hek-means approach with the Silhouette coefficient to conduct unsupervised learning of the coordinate points. The clustering results are evaluated by the Silhouette coefficient, which could ensure the accuracy and uniqueness. In this study, we mitigate the problem by means of a new partitioning method, and the research results show that the partitioning results are more reasonable boundary regions.


## 2. Related Works

3D CAD model segmentation has been an important issue in the computer design area. Various algorithms have been proposed for segmentation.Most 3D mesh model segmentation algorithms are based on 2D image segmentation, i.e., the 2D space extends to the 3D space. The approaches can be broadly classified into three categories: (1) Region-based: based on features of models (e.g., surface), divide the model into different and nonoverlaping regions using methods such as the region growing method [11, 12] and the watershed algorithm [13, 14]. (2) Graph-based: it generally represents the model in terms of an undirected graph (dual graph [3] and attributed adjacent graph [15]) and segmented by graph cuts [16], normalized cuts [17], and spectral theory [18]. (3) The extracted features of the model are clustered, and the points or surfaces of a model having similar property can be obtained according to the clustering result [3, 19, 20].Especially for the mesh model and the point cloud model, clustering-based methods are typical and widely used. The clustering algorithm is an unsupervised learning method; it does not require training samples. Many clustering methods are critical for model segmentation. Examples include hierarchical clustering [21, 22], fuzzy clustering with graph cuts [23], and spectral clustering [24], and Shlafman et al. introduced the steps of applying the k-means clustering algorithm to 3D polyhedral models segmentation systematically [25]. Garland proposed a hierarchical clustering methodology such that the clusters can be well approximated with planar elements, which can be used for CAD model segmentation [26]. Katz and Tal used a hierarchical fuzzy k-means algorithm to segment the objects [21]. As in Shlafman et al., their algorithm clusters triangles with a distance function that is a weighted sum of the geodesic distance of the barycenter and the angle between the triangles [25]. In the binary partitioning case, their algorithm partitions the mesh into two segmentation areas and a fuzzy area.Previous literature on problems related to mesh model segmentation abound. However, for mechanical 3D CAD solid models, segmentation methods are rare.Hitherto, few segmentation methods for CAD models have appeared. Wang et al. proposed a feature-based partitioning algorithm that extracts features from the attributed adjacency graphs using ant colony clustering to conduct the multiobjective optimization. The segmentation effect is achieved by optimizing the partitioning face and partitioning order [27]. From the assembly point of view, Wang et al. likewise developed a graph partitioning method based on ant clustering. The complicated CAD model was first represented and simplified by the attributed adjacent graph, and subsequently the connection mode and part attribute of the model were analyzed to construct the correlation degree matrix, according to the model topological connection relations to reconstruct the local range and density function of ant clustering algorithm [15]. Ma employed a surface region segmentation method for CAD models. According to the boundary concavity, the model is divided into a region set of the least number of areas, which is composed of a few interconnected surfaces [28].For the sake of clarity, we present the visual comparison of each segmentation method which was analyzed before in Table1.Table 1
Summary of the model segmentation method.
Author
Input model
Method
Limitation
Zhang et al. [11]
Mesh model
Using Gaussian curvature to mark vertices and detect the boundaries of model, then segmented by region growing algorithm
The boundaries detected may not be correct, because only vertices are considered
Lavoué et al. [12]
Mesh model
Using the standardk-means algorithm to classify vertex principal curvatures, then segmented based on the region growing and merging of the labeled mesh vertex
It is difficult to get the reasonable curvature tensor on the sparse region, and the output depends heavily on the choice of the user defined threshold
Mangan and Whitaker [13]
Mesh model
Partitioning a mesh model by the total curvature of the surface as an indication of region boundaries, segmented along high curvature regions
The boundaries between components are often jagged
Sun et al. [14]
Mesh model
Detecting the edge based on the eigen analysis of the surface normal vector in a geodesic window, then used to segment the surface mesh using a watershed algorithm
The boundaries detected may not be correct, because only vertices are considered
Brown et al. [16]
Mesh model
Treating the mesh model as a weighted graph, then achieving segmentation by minimum graph cut
It needs user to interact where he wants the partition
Golovinskiy and Funkhouser [17]
Mesh model
Dual graph is first built, then segmentation is achieved by clustering similar meshes and obtaining minimum graph cuts
This method is not usual in CAD models
Mejia et al. [18]
Mesh model
Treating the mesh model as a connected and undirected graph and relabeling the vertices of the graph based on the Fiedler vector; then, segmentation will be defined by cutting thresholds on it
Geometric information is not considered and requiring mesh need to be homogeneous
Miandarhoie et al. [3]
Mesh model
Partitioning the point clouds of mesh model into individual regions can be approximated using extruded surface
It lacks semantic meaning
Xiao et al. [29]
Mesh model
Dividing the triangles into sparse and dense regions by the agglomerative hierarchical clustering method, using gauss sphere and mean shift method to segment sparse and dense regions into primary surfaces
Segmentation information loss occurs when the method is used for CAD models [30]
Shlafman et al. [25]
CAD model
Using ak-means clustering algorithm to segment model, and the meaningful components of the objects are found
The boundaries between the patches are often jagged and not always correct
Lavoué et al. [31]
Mesh model
Classify the vertices according to the absolute values of their principal curvatures intok clusters using the k-means algorithm
The parameterk needs to be defined manually
Wang et al. [27]
CAD model
Partitioning by clustering based on multiobjective optimization
The result is affected by partitioning the face selected and partitioning the order
Wang et al. [15]
CAD model
Represented by the attributed adjacent graph and segmented by ant clustering algorithm
Parameter settings are subjective to be changed according to different types of models
Ma [28]
CAD model
Employed a surface region segmentation method for CAD models
Segmented region is impacted by the order of the merging and lack of semantic meaningThese segmentation methods may encounter both the resulting uncertainty problem and the efficiency problem. The region-based algorithms exhibit satisfying efficiency, but the results may not be unique, since the algorithm starts with different seed faces [1]. The cluster-based algorithms can yield a certain result, but their costs are high [1]. Meanwhile, they are less effective to find the meaningful components. Additionally, the b-rep model shape is prominent, the boundary between the surfaces is obvious, and the partitioning result is not ideal by a simple curvature dividing [32].


## 3. Model Description

In this section, we will present several basic concepts that are related to the model decomposition; subsequently, the concrete steps of the segmentation method are given.


### 3.1. Attributed Adjacency Graph for CAD Models

The b-rep model is typically used for the description and analysis of solid models, since the b-rep models could present a visualized boundary of the models and also could represent the 3D model unambiguity [33, 34].CAD systems often use some form of b-rep as their internal representation. Most of them generate and express the AAG of the model faces from a STEP file, as presented by El-Mehalawi and Miller [33]. A labeled typical mechanical model with its AAG is shown in Figure 1. An AAG represents the b-rep structure of an entity. In this context, the AAG is four-tuple and could be formulated as(1)G=V,E,A,D,where V is a set of nodes in AAG that represents the model faces; E is a set of edges in AAG that represent the model edges; A is a set of properties containing the face properties and edge properties; and D is the node degree. One-to-one correspondence occurs between the faces of a model and its AAG nodes and between its edges and its AAG links.Figure 1
Example of an attributed adjacency graph: (a) a solid model with face code; (b) an AAG of the solid model.
(a)
(b)


### 3.2. Basic Conceptions

The geometric information of the b-rep model primarily concludes the face and edge information. Herein, the descriptions of the faces and edges are based on the geometric information.


#### 3.2.1. Faces Code Representation

The AAG nodes’ attributes contain the geometrical and topological information of a face in a CAD model. We present a codeFcode that describes the properties of a face-like face type, i.e., convexity. These two properties are represented as follows:(2)Fcode=ftype,fcon,where ftype and fcon are both integers that represent the face type and face convexity. In particular, ftype=1,2,3,4or5 if the face is a plane, cylinder, cone, sphere, or others, respectively; and fcon=1,2,3or4 if the face is planar, convex, concave, or others, respectively.


#### 3.2.2. Edges Code Representation

The AAG’s edges represent the adjacency relationship between two surfaces in a 3D CAD model. They, as the intersection boundaries, correspond to one or more edges connecting the two faces. An external edge angle is designed as an angle between the two outside faces of two adjacent surfaces, while the angle between the two inside faces of two adjacent surfaces is called as an internal edge angle. The external edge angleφ and internal edge angle ψ are presented in Figure 2, respectively. Here, the value of edge convexity econ is determined by the external angle φ (shown in Figure 2):(3)econ=1,ifφ<180°,−1,ifφ>180°.Figure 2
External and internal edge angles.(1) Convex Edge. If the external edge angle φ is greater than 180° (or the internal edge angle ψ is less than 180°), the edge intersected by two adjacent surfaces is called a convex edge. The two adjacent surfaces can be any convex or concave surfaces. Figure 3(a) shows a convex edge between two adjacent surfaces [35].Figure 3
Edge taxonomy: (a) convex edge; (b) concave edge.(2) Concave Edge. If the external edge angle φ of the two adjacent surfaces is less than 180° (or the internal edge angle ψ is greater than 180°). The case is shown in Figure 3(b) [35].(3) Adjacency Matrix. The adjacency matrix AM is a square n×n symmetric matrix; its elements of the matrix indicate whether pairs of nodes are adjacent in the attributed adjacency graph G. In this special case, using econ, the AM is defined as follows:(4)AM=aij,aij=econ,vi,vj∈E,0,others,i,j=1,2,…,n.For an AM,aii=0 and aij=aji for all i,j∈1,2,…,n.


### 3.3. Model Description

By means of AAG, a b-rep model in 3D Euclidean spaceE3 could map into a 2D description space S. In AAG, nodes and edges are represented by shape parameters that can be extracted from the STEP and used for further calculation. Each surface of the 3D CAD model is transformed into a 2D coordinate point fvt by the PERT and the graph theory.In a single code network, the calculation principle of the earliest start time (ES) is as follows: the maximum value of the earliest finish time (EF) of the front closely activities, wherein the earliest start time plus duration is the earliest finish time of the work.For example, the ES of activityD depends on the EF of B and C; according to the maximum value principle, the ES of D is 9 (see in Figure 4).Figure 4
Single code network calculation.Likewise, the AAG of CAD models can be seen as a single node network (see in Figure5). Weight is equivalent to duration. The duration is 0 or D, respectively, if the weight is 1 or −1. The horizontal coordinate of node 3 depends on the maximum value of x1 and x2+D.Figure 5
Horizontal coordinates calculation diagram.


#### 3.3.1. Horizontal Coordinates Computation

According to the PERT, geometry, and topological information of each surface of the model, the horizontal coordinate is determined as follows:Step 1: the coordinate matrix corresponding to the AM is computed line by line as follows:(5)ifi≤j,Cori,j=ω1ftype,j+ω2fcon,j,aij=0,1,ω1ftype,j+ω2fcon,j+numaij⋅D,aij=−1,ifi>j,Cori,j=Conj,i,where Cori,j represents the i-th horizontal coordinate of a point corresponding to node vi. ω1 and ω2 are weights. ftype,j is the j-th face type, and fcon,j is the j-th face convexity. numaij is the number of −1 from the first to the i-th row in the j-th column of the AM. D is constant. In this article, the value of D is 10.Step 2: calculate the temporary coordinates of a node point-by-point. For thei-th node, obtain the j value of all ai,j=1 in the i-th row of the AM. Record the j values in the temporary array ip. Subsequently, the horizontal coordinate of the i-th node pix is computed as follows:(6)pix=maxmaxCorcoli,i,maxCorcoli,n,wherecoli represents the 1∼i-th row, maxCorcoli,i is the maximum value in the 1∼i-th row of the i-th column, n represents the n-th value in the temporary array ip, and maxCorcoli,n is the maximum value in the 1∼i-th row of the n-th column.


#### 3.3.2. Vertical Coordinates Computation

The graph theory is introduced to describe the topological information of the graphs in vector form. A graph spectrum is an ordered sequence of eigenvalues of the AM and can describe the topological structure information of the graphs in vector form; additionally, the computation time is polynomial.The Laplacian matrixL of the model is calculated based on the AM as follows:(7)L=lu,v=1,ifu=v,du≠0,−1du⋅dv,ifuandvare adjacent,0,otherwise,where u and v are the nodes of the attributed adjacency graph G and du and dv represent the degrees of node u and node v, respectively.(1) Spectral Vector. SpV: the spectral vector is the eigenvalue of the Laplacian matrix L in a descending order. SpV=λ1λ2⋯λm,λ1≥λ2≥⋯≥λm. In fact, λt is the corresponding point vertical coordinate.Thus, a facef can be described by two-dimensional point coordinates pfi=px,py, where px is the horizontal coordinate and py is the vertical coordinate.


## 3.1. Attributed Adjacency Graph for CAD Models

The b-rep model is typically used for the description and analysis of solid models, since the b-rep models could present a visualized boundary of the models and also could represent the 3D model unambiguity [33, 34].CAD systems often use some form of b-rep as their internal representation. Most of them generate and express the AAG of the model faces from a STEP file, as presented by El-Mehalawi and Miller [33]. A labeled typical mechanical model with its AAG is shown in Figure 1. An AAG represents the b-rep structure of an entity. In this context, the AAG is four-tuple and could be formulated as(1)G=V,E,A,D,where V is a set of nodes in AAG that represents the model faces; E is a set of edges in AAG that represent the model edges; A is a set of properties containing the face properties and edge properties; and D is the node degree. One-to-one correspondence occurs between the faces of a model and its AAG nodes and between its edges and its AAG links.Figure 1
Example of an attributed adjacency graph: (a) a solid model with face code; (b) an AAG of the solid model.
(a)
(b)


## 3.2. Basic Conceptions

The geometric information of the b-rep model primarily concludes the face and edge information. Herein, the descriptions of the faces and edges are based on the geometric information.


### 3.2.1. Faces Code Representation

The AAG nodes’ attributes contain the geometrical and topological information of a face in a CAD model. We present a codeFcode that describes the properties of a face-like face type, i.e., convexity. These two properties are represented as follows:(2)Fcode=ftype,fcon,where ftype and fcon are both integers that represent the face type and face convexity. In particular, ftype=1,2,3,4or5 if the face is a plane, cylinder, cone, sphere, or others, respectively; and fcon=1,2,3or4 if the face is planar, convex, concave, or others, respectively.


### 3.2.2. Edges Code Representation

The AAG’s edges represent the adjacency relationship between two surfaces in a 3D CAD model. They, as the intersection boundaries, correspond to one or more edges connecting the two faces. An external edge angle is designed as an angle between the two outside faces of two adjacent surfaces, while the angle between the two inside faces of two adjacent surfaces is called as an internal edge angle. The external edge angleφ and internal edge angle ψ are presented in Figure 2, respectively. Here, the value of edge convexity econ is determined by the external angle φ (shown in Figure 2):(3)econ=1,ifφ<180°,−1,ifφ>180°.Figure 2
External and internal edge angles.(1) Convex Edge. If the external edge angle φ is greater than 180° (or the internal edge angle ψ is less than 180°), the edge intersected by two adjacent surfaces is called a convex edge. The two adjacent surfaces can be any convex or concave surfaces. Figure 3(a) shows a convex edge between two adjacent surfaces [35].Figure 3
Edge taxonomy: (a) convex edge; (b) concave edge.(2) Concave Edge. If the external edge angle φ of the two adjacent surfaces is less than 180° (or the internal edge angle ψ is greater than 180°). The case is shown in Figure 3(b) [35].(3) Adjacency Matrix. The adjacency matrix AM is a square n×n symmetric matrix; its elements of the matrix indicate whether pairs of nodes are adjacent in the attributed adjacency graph G. In this special case, using econ, the AM is defined as follows:(4)AM=aij,aij=econ,vi,vj∈E,0,others,i,j=1,2,…,n.For an AM,aii=0 and aij=aji for all i,j∈1,2,…,n.


## 3.2.1. Faces Code Representation

The AAG nodes’ attributes contain the geometrical and topological information of a face in a CAD model. We present a codeFcode that describes the properties of a face-like face type, i.e., convexity. These two properties are represented as follows:(2)Fcode=ftype,fcon,where ftype and fcon are both integers that represent the face type and face convexity. In particular, ftype=1,2,3,4or5 if the face is a plane, cylinder, cone, sphere, or others, respectively; and fcon=1,2,3or4 if the face is planar, convex, concave, or others, respectively.


## 3.2.2. Edges Code Representation

The AAG’s edges represent the adjacency relationship between two surfaces in a 3D CAD model. They, as the intersection boundaries, correspond to one or more edges connecting the two faces. An external edge angle is designed as an angle between the two outside faces of two adjacent surfaces, while the angle between the two inside faces of two adjacent surfaces is called as an internal edge angle. The external edge angleφ and internal edge angle ψ are presented in Figure 2, respectively. Here, the value of edge convexity econ is determined by the external angle φ (shown in Figure 2):(3)econ=1,ifφ<180°,−1,ifφ>180°.Figure 2
External and internal edge angles.(1) Convex Edge. If the external edge angle φ is greater than 180° (or the internal edge angle ψ is less than 180°), the edge intersected by two adjacent surfaces is called a convex edge. The two adjacent surfaces can be any convex or concave surfaces. Figure 3(a) shows a convex edge between two adjacent surfaces [35].Figure 3
Edge taxonomy: (a) convex edge; (b) concave edge.(2) Concave Edge. If the external edge angle φ of the two adjacent surfaces is less than 180° (or the internal edge angle ψ is greater than 180°). The case is shown in Figure 3(b) [35].(3) Adjacency Matrix. The adjacency matrix AM is a square n×n symmetric matrix; its elements of the matrix indicate whether pairs of nodes are adjacent in the attributed adjacency graph G. In this special case, using econ, the AM is defined as follows:(4)AM=aij,aij=econ,vi,vj∈E,0,others,i,j=1,2,…,n.For an AM,aii=0 and aij=aji for all i,j∈1,2,…,n.


## 3.3. Model Description

By means of AAG, a b-rep model in 3D Euclidean spaceE3 could map into a 2D description space S. In AAG, nodes and edges are represented by shape parameters that can be extracted from the STEP and used for further calculation. Each surface of the 3D CAD model is transformed into a 2D coordinate point fvt by the PERT and the graph theory.In a single code network, the calculation principle of the earliest start time (ES) is as follows: the maximum value of the earliest finish time (EF) of the front closely activities, wherein the earliest start time plus duration is the earliest finish time of the work.For example, the ES of activityD depends on the EF of B and C; according to the maximum value principle, the ES of D is 9 (see in Figure 4).Figure 4
Single code network calculation.Likewise, the AAG of CAD models can be seen as a single node network (see in Figure5). Weight is equivalent to duration. The duration is 0 or D, respectively, if the weight is 1 or −1. The horizontal coordinate of node 3 depends on the maximum value of x1 and x2+D.Figure 5
Horizontal coordinates calculation diagram.


### 3.3.1. Horizontal Coordinates Computation

According to the PERT, geometry, and topological information of each surface of the model, the horizontal coordinate is determined as follows:Step 1: the coordinate matrix corresponding to the AM is computed line by line as follows:(5)ifi≤j,Cori,j=ω1ftype,j+ω2fcon,j,aij=0,1,ω1ftype,j+ω2fcon,j+numaij⋅D,aij=−1,ifi>j,Cori,j=Conj,i,where Cori,j represents the i-th horizontal coordinate of a point corresponding to node vi. ω1 and ω2 are weights. ftype,j is the j-th face type, and fcon,j is the j-th face convexity. numaij is the number of −1 from the first to the i-th row in the j-th column of the AM. D is constant. In this article, the value of D is 10.Step 2: calculate the temporary coordinates of a node point-by-point. For thei-th node, obtain the j value of all ai,j=1 in the i-th row of the AM. Record the j values in the temporary array ip. Subsequently, the horizontal coordinate of the i-th node pix is computed as follows:(6)pix=maxmaxCorcoli,i,maxCorcoli,n,wherecoli represents the 1∼i-th row, maxCorcoli,i is the maximum value in the 1∼i-th row of the i-th column, n represents the n-th value in the temporary array ip, and maxCorcoli,n is the maximum value in the 1∼i-th row of the n-th column.


### 3.3.2. Vertical Coordinates Computation

The graph theory is introduced to describe the topological information of the graphs in vector form. A graph spectrum is an ordered sequence of eigenvalues of the AM and can describe the topological structure information of the graphs in vector form; additionally, the computation time is polynomial.The Laplacian matrixL of the model is calculated based on the AM as follows:(7)L=lu,v=1,ifu=v,du≠0,−1du⋅dv,ifuandvare adjacent,0,otherwise,where u and v are the nodes of the attributed adjacency graph G and du and dv represent the degrees of node u and node v, respectively.(1) Spectral Vector. SpV: the spectral vector is the eigenvalue of the Laplacian matrix L in a descending order. SpV=λ1λ2⋯λm,λ1≥λ2≥⋯≥λm. In fact, λt is the corresponding point vertical coordinate.Thus, a facef can be described by two-dimensional point coordinates pfi=px,py, where px is the horizontal coordinate and py is the vertical coordinate.


## 3.3.1. Horizontal Coordinates Computation

According to the PERT, geometry, and topological information of each surface of the model, the horizontal coordinate is determined as follows:Step 1: the coordinate matrix corresponding to the AM is computed line by line as follows:(5)ifi≤j,Cori,j=ω1ftype,j+ω2fcon,j,aij=0,1,ω1ftype,j+ω2fcon,j+numaij⋅D,aij=−1,ifi>j,Cori,j=Conj,i,where Cori,j represents the i-th horizontal coordinate of a point corresponding to node vi. ω1 and ω2 are weights. ftype,j is the j-th face type, and fcon,j is the j-th face convexity. numaij is the number of −1 from the first to the i-th row in the j-th column of the AM. D is constant. In this article, the value of D is 10.Step 2: calculate the temporary coordinates of a node point-by-point. For thei-th node, obtain the j value of all ai,j=1 in the i-th row of the AM. Record the j values in the temporary array ip. Subsequently, the horizontal coordinate of the i-th node pix is computed as follows:(6)pix=maxmaxCorcoli,i,maxCorcoli,n,wherecoli represents the 1∼i-th row, maxCorcoli,i is the maximum value in the 1∼i-th row of the i-th column, n represents the n-th value in the temporary array ip, and maxCorcoli,n is the maximum value in the 1∼i-th row of the n-th column.


## 3.3.2. Vertical Coordinates Computation

The graph theory is introduced to describe the topological information of the graphs in vector form. A graph spectrum is an ordered sequence of eigenvalues of the AM and can describe the topological structure information of the graphs in vector form; additionally, the computation time is polynomial.The Laplacian matrixL of the model is calculated based on the AM as follows:(7)L=lu,v=1,ifu=v,du≠0,−1du⋅dv,ifuandvare adjacent,0,otherwise,where u and v are the nodes of the attributed adjacency graph G and du and dv represent the degrees of node u and node v, respectively.(1) Spectral Vector. SpV: the spectral vector is the eigenvalue of the Laplacian matrix L in a descending order. SpV=λ1λ2⋯λm,λ1≥λ2≥⋯≥λm. In fact, λt is the corresponding point vertical coordinate.Thus, a facef can be described by two-dimensional point coordinates pfi=px,py, where px is the horizontal coordinate and py is the vertical coordinate.


## 4. Segmentation Method

Based on the analysis of 3D CAD models, we propose a clustering-based segmentation approach. The main flow chart is shown in Figure6. It contains five phases: (1) taking b-rep model as input, (2) building the corresponding face attributed adjacency graphs of the 3D CAD models that are introduced in the literature [33], (3) transforming 3D CAD models into 2D coordinate point sets by using the fusion of PERT technology and spectral theory, (4) clustering 2D coordinate points by using of k-means algorithm based on the Silhouette coefficient, and (5) segmenting the 3D CAD model according to the result of clustering.Figure 6
The flow chart of the proposed segmentation method.


### 4.1. Thek-Means Clustering Algorithm

Clustering is an iterative process of separating a set of samples into a number of groups with no supervised learning [36]. In general, k-means is widely used owing to its simplicity, versatility, and relatively higher efficiency over other clustering methods. Therefore, we make use of the k-means method to cluster two-dimensional coordinate points.Thek-means clustering algorithm gathers data points into k clusters. The cluster Sii=1,2,…,k is associated with the cluster centroids Ci [37]. We denote the set of data points as P=P1,P2,…,Pn, and let dPs,Pt be the distortion between any two points Ps and Pt. Herein, dPs,Pt denotes the Euclidean distance between Ps and Pt.The vital part of the proposed algorithm is to construct and utilize the Laplacian matrix to reduce the dimensionality of the dataset. Furthermore, the former transforms the 3D model into a point set in a lower-dimensional eigenspace by utilizing the eigenvectors of a Laplacian matrix derived from the AAG. Subsequently, thek-means algorithm can be performed on this point set to obtain the final clustering result.The clustering problem can be taken as partitioning an undirected graph, which is an unsupervised learning process. Suppose that an undirected graph is an AAG, i.e.,G=V,E,A,D. Here, E is represented by an adjacent matrix [38]. The evaluation criteria are to render the correlation of the two nodes larger in the same subgraph and smaller between different subgraphs [24].In general, the isolated point affects the effect of the algorithm significantly. Fortunately, in a CAD model, an isolated face does not exist, and each face is adjacent to one or more faces.


### 4.2. Construction of the Silhouette Coefficient

The Silhouette coefficient is a method of interpretation and validation of consistency within clusters of data. This is to say, it is a type of evaluation method for the performance of clustering algorithms, which provides a parsimonious graphical representation of how well each sample data lies within its cluster [39].The Silhouette coefficient value can measure how similar a sample data is to its own cluster (cohesion) compared to other clusters (separation). It ranges from −1 to +1, where a high value indicates that the sample data is well matched to its own cluster and poorly matched to neighboring clusters [39]. Amid the specified iteration times, once the Silhouette coefficient reaches the maximum value, the clustering configuration is appropriate. Conversely, the clustering configuration may have too many or too few clusters with a low Silhouette value.The Silhouette coefficient of pointi is calculated as follows:(8)si=bi−aimaxai,bi,where ai is a measure of how well i is matched to its cluster (the smaller the value, the better the matching) and bi is the lowest average distance of i to all points in any other cluster, of which i is not a member [40].The global Silhouette coefficientS is the average of the Silhouette coefficient for all points, which can be calculated as follows:(9)S=1N∑i=1Nsi,where N is the number of sample points.


### 4.3. The Primary Process ofk-Means Based on the Silhouette Coefficient

Thek-means algorithm is used to cluster the point set corresponding to the 3D CAD model to achieve model segmentation. The experimental results show that the optimal cluster is less than 10, so the value of k is [2, 10]. The specific steps are as follows:Step 1: given the number of clusteringk, initially set k = 2.Step 2: initialize the cluster centroidcx0,y0 randomly for k clusters.Step 3: calculate the Euclidean distance between each pointpix,y and the cluster centroid c to classify; the distance is defined as(10)di,t=pix−x0,t2+piy−y0,t2.The nearest cluster centroid is determined by the minimum value of the Euclidean distance.Step 4: According to the previous results, recalculate the mean value of all points in each cluster; subsequently, determine a new cluster centroid and the formulas are as follows:(11)x0,tm=1Nt∑s=1Ntpsx,y0,tm=1Nt∑s=1Ntpsy,wherem represents the iterated times and cx0m,y0m is the cluster centroid iterated m times.Step 5: proceed to steps 3 and 4, until the cluster centroid position (i.e., thresholdτ) does not change significantly τ≤10−6(12)τ=∑n=1tx0,tm−x0,tm−12+y0,tm−y0,tm−12.Step 6: calculate the Silhouette coefficientS of the k clusters based on equation (8).Step 7: setk=k+1 , if k≤10, proceed to steps 2–7; if k>10, then stop.Step 8: proceed to steps 2–5, obtain thek0 value corresponding to the maximum of the Silhouette coefficient S; it is considered the optimal cluster number.Step 9: output the cluster result.


## 4.1. Thek-Means Clustering Algorithm

Clustering is an iterative process of separating a set of samples into a number of groups with no supervised learning [36]. In general, k-means is widely used owing to its simplicity, versatility, and relatively higher efficiency over other clustering methods. Therefore, we make use of the k-means method to cluster two-dimensional coordinate points.Thek-means clustering algorithm gathers data points into k clusters. The cluster Sii=1,2,…,k is associated with the cluster centroids Ci [37]. We denote the set of data points as P=P1,P2,…,Pn, and let dPs,Pt be the distortion between any two points Ps and Pt. Herein, dPs,Pt denotes the Euclidean distance between Ps and Pt.The vital part of the proposed algorithm is to construct and utilize the Laplacian matrix to reduce the dimensionality of the dataset. Furthermore, the former transforms the 3D model into a point set in a lower-dimensional eigenspace by utilizing the eigenvectors of a Laplacian matrix derived from the AAG. Subsequently, thek-means algorithm can be performed on this point set to obtain the final clustering result.The clustering problem can be taken as partitioning an undirected graph, which is an unsupervised learning process. Suppose that an undirected graph is an AAG, i.e.,G=V,E,A,D. Here, E is represented by an adjacent matrix [38]. The evaluation criteria are to render the correlation of the two nodes larger in the same subgraph and smaller between different subgraphs [24].In general, the isolated point affects the effect of the algorithm significantly. Fortunately, in a CAD model, an isolated face does not exist, and each face is adjacent to one or more faces.


## 4.2. Construction of the Silhouette Coefficient

The Silhouette coefficient is a method of interpretation and validation of consistency within clusters of data. This is to say, it is a type of evaluation method for the performance of clustering algorithms, which provides a parsimonious graphical representation of how well each sample data lies within its cluster [39].The Silhouette coefficient value can measure how similar a sample data is to its own cluster (cohesion) compared to other clusters (separation). It ranges from −1 to +1, where a high value indicates that the sample data is well matched to its own cluster and poorly matched to neighboring clusters [39]. Amid the specified iteration times, once the Silhouette coefficient reaches the maximum value, the clustering configuration is appropriate. Conversely, the clustering configuration may have too many or too few clusters with a low Silhouette value.The Silhouette coefficient of pointi is calculated as follows:(8)si=bi−aimaxai,bi,where ai is a measure of how well i is matched to its cluster (the smaller the value, the better the matching) and bi is the lowest average distance of i to all points in any other cluster, of which i is not a member [40].The global Silhouette coefficientS is the average of the Silhouette coefficient for all points, which can be calculated as follows:(9)S=1N∑i=1Nsi,where N is the number of sample points.


## 4.3. The Primary Process ofk-Means Based on the Silhouette Coefficient

Thek-means algorithm is used to cluster the point set corresponding to the 3D CAD model to achieve model segmentation. The experimental results show that the optimal cluster is less than 10, so the value of k is [2, 10]. The specific steps are as follows:Step 1: given the number of clusteringk, initially set k = 2.Step 2: initialize the cluster centroidcx0,y0 randomly for k clusters.Step 3: calculate the Euclidean distance between each pointpix,y and the cluster centroid c to classify; the distance is defined as(10)di,t=pix−x0,t2+piy−y0,t2.The nearest cluster centroid is determined by the minimum value of the Euclidean distance.Step 4: According to the previous results, recalculate the mean value of all points in each cluster; subsequently, determine a new cluster centroid and the formulas are as follows:(11)x0,tm=1Nt∑s=1Ntpsx,y0,tm=1Nt∑s=1Ntpsy,wherem represents the iterated times and cx0m,y0m is the cluster centroid iterated m times.Step 5: proceed to steps 3 and 4, until the cluster centroid position (i.e., thresholdτ) does not change significantly τ≤10−6(12)τ=∑n=1tx0,tm−x0,tm−12+y0,tm−y0,tm−12.Step 6: calculate the Silhouette coefficientS of the k clusters based on equation (8).Step 7: setk=k+1 , if k≤10, proceed to steps 2–7; if k>10, then stop.Step 8: proceed to steps 2–5, obtain thek0 value corresponding to the maximum of the Silhouette coefficient S; it is considered the optimal cluster number.Step 9: output the cluster result.


## 5. Implementation and Results

To verify the proposed algorithm in this study, we performed some experiments for the 3D model segmentation. Here, an example is described to illustrate the implementation of the proposed approach.


### 5.1. Implementation

Following the discussion above, the proposed algorithm can be formally described as follows:(1)
Input a set of modelsM=m1,m2,…,mn(2)
Transform all the models inM into AAGs G=g1,g2,…,gn(3)
Transform all the AAGs inG into discrete point set P=pf1,pf2,…,pfn based on equations (5)–(7)(4)
Letk=2, and iterate the following steps until k>10 (the value of k is not fixed; instead, it is according to the number of the model faces)(5)
Initialize the cluster centroidcx0,y0 randomly for k clusters(6)
Compute the centroid for each cluster to obtain a new set of clusters(7)
Calculate the Silhouette coefficientS of the k clusters. Obtain the k0 value corresponding to the maximum of the Silhouette coefficient S(8)
Output the final clustering results in cell arrayCk0Example 1.
The models in Figure1 show a solid model a. The Laplacian matrix of the model a is depicted in Appendix; all eigenvalues are real and positive and each eigenvalue of SpV11 is the corresponding point vertical coordinate as follows:(13)SpV11=1.7981.7161.6071.5001.4161.3351.0001.0001.0001.0001.0001.0001.0001.0001.0000.9500.7030.6650.5360.3100.1620.000.
We now illustrate the determination of the horizontal axis based on a given AM1 and AAG1.(14)AM1=aij=01000100101−100−10010001000−1000−11000000101101−110100−101010000001000.
The AAG is an undirected graph. The edge connects two adjacent nodesn and v and is an undirected edge; therefore, it has no specific direction, i.e., env and evn represent the same edge. To avoid duplicate computations, we only use the upper triangular part of AM1. Using node 2 and node 4 as an example, node 2 connects node 4 and node 7 with a concave edge; therefore, a24 and a27 are equal to −1(in red) and numa24=2. Node 4 connects node 6 with a concave edge; therefore, a46=−1 (in red) and numa46=1.
According to equations (5)∼(7), we transform the model a into a point set, as shown in Figure 7(a), and subsequently employ the k-means algorithm introduced in Section 3.
Finally, the Silhouette coefficients automatically confirm the number of clusters ask = 4 (shown in Figure 8). The horizontal axis is the number of clusters, and the ordinate is the value of Silhouette coefficient. When k = 4, the value of Silhouette coefficient S is maximum.
The final segmentation result is shown in Figure7(b). According to this method, the model a could be decomposed into several significant regions (see in Figure 9), where each color represents one part of the model a.Figure 7
(a) Point set for the modela. (b) Result of k-means cluster.
(a)
(b)Figure 8
The curve of the Silhouette coefficients.Figure 9
Segment result for the modela.


### 5.2. Experiments and Results

We performed some experiments using the library models to validate the approach proposed herein. These tests were implemented on a computer with an Intel 3.20 GHz CPU and a 4.0 GB RAM. The ACIS 3D Geometric Modeler and Visual C++7.1 development environment were used.The efficiency and results of the algorithm proposed in this paper are discussed. The method is not only efficient but also could be used in fields of segmentation of general CAD models overcoming the limitations of model types. As it is seen, with utilization of the proposed approach, it is easy to desirably partition the 3D CAD model, and its segmentation results are more in line with human perception.


#### 5.2.1. Run Time for Segmentation

Time estimation of our approach is visualized in Figure10. From this curve, we can see that the proposed algorithm is efficient. The implementation on average takes less than a second.Figure 10
Run time of segmentation with a different model.Thex-axis represents the number of model faces, and the y-axis represents the computational time. The time cost consists of two parts: one is the coordinates’ calculation of points, and the other one is the k-means clustering algorithm complexity. Actually, the former takes a very short time and is negligible. The latter plays a decisive role. That is to say, the complexity of the proposed algorithm strongly depends on the complexity of the k-means algorithm. Therefore, the complexity of proposed algorithmic is Onkm, where n is the number of model faces, k is the number of clusters, and m is the iterations. As a fast clustering method, k-means clustering algorithm performs quite well, for example, when the size of the AAGs is 587 nodes and the computation time is only 1.374 s.


#### 5.2.2. Effectiveness for Segmentation

Table2 shows the comparison of our approach with method in Ref. [31]. As for each model, the faces of the same color represent the same region and n represents the number of segmentation. The method in Ref. [31] tends to oversegment models. For model 1, it only contains 29 faces. However, the model is divided into 8 regions, and each region does not have sufficient engineering meaning. Furthermore, the segmentations in the four models could not combine the through-hole feature into any other regions, and it also increases the computational complexity of subsequent model comparisons. The segmentation is difficult to apply to model retrieval. All of these models are segmented correctly into meaningful components by our method. Meanwhile, compared with the other methods in Ref. [31], the segmented result in this paper is more consistent with human perception, thus the improving efficiency of model retrieval.Table 2
Comparison of our segmentation algorithm with works in Ref. [31].
Input b-rep model
Methods in Ref. [31]
Method in this article
Model 1
n = 8
n = 3
Model 2
n = 13
n = 4
Model 3
n = 13
n = 5
Model 4
n = 4
n = 2In order to verify the segmentation approach, a set of various models are chosen. The following are some segmentation experiments for the typical mechanical parts using the proposed method, and the segment results are shown in Figure11. Rounds and fillets are ignored, since they will not affect the result. Furthermore, the results show that the method proposed is universal, and it is suitable for the segmentation of most conventional CAD models.Figure 11
The segmentation result of typical mechanical parts. (a) Three segmentation regions. (b) Three segmentation regions. (c) Five segmentation regions. (d) Four segmentation regions. (e) Three segmentation regions. (f) Three segmentation regions. (g) Three segmentation regions. (h) Three segmentation regions. (i) Four segmentation regions.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)Another area that can be benefitted from use of the proposed segmentation method is model reuse. It is possible to get and save meaningful segmented components into the model library for product design. Each segmented component could be conveniently reused by retrieving, copying, and modifying.


## 5.1. Implementation

Following the discussion above, the proposed algorithm can be formally described as follows:(1)
Input a set of modelsM=m1,m2,…,mn(2)
Transform all the models inM into AAGs G=g1,g2,…,gn(3)
Transform all the AAGs inG into discrete point set P=pf1,pf2,…,pfn based on equations (5)–(7)(4)
Letk=2, and iterate the following steps until k>10 (the value of k is not fixed; instead, it is according to the number of the model faces)(5)
Initialize the cluster centroidcx0,y0 randomly for k clusters(6)
Compute the centroid for each cluster to obtain a new set of clusters(7)
Calculate the Silhouette coefficientS of the k clusters. Obtain the k0 value corresponding to the maximum of the Silhouette coefficient S(8)
Output the final clustering results in cell arrayCk0Example 1.
The models in Figure1 show a solid model a. The Laplacian matrix of the model a is depicted in Appendix; all eigenvalues are real and positive and each eigenvalue of SpV11 is the corresponding point vertical coordinate as follows:(13)SpV11=1.7981.7161.6071.5001.4161.3351.0001.0001.0001.0001.0001.0001.0001.0001.0000.9500.7030.6650.5360.3100.1620.000.
We now illustrate the determination of the horizontal axis based on a given AM1 and AAG1.(14)AM1=aij=01000100101−100−10010001000−1000−11000000101101−110100−101010000001000.
The AAG is an undirected graph. The edge connects two adjacent nodesn and v and is an undirected edge; therefore, it has no specific direction, i.e., env and evn represent the same edge. To avoid duplicate computations, we only use the upper triangular part of AM1. Using node 2 and node 4 as an example, node 2 connects node 4 and node 7 with a concave edge; therefore, a24 and a27 are equal to −1(in red) and numa24=2. Node 4 connects node 6 with a concave edge; therefore, a46=−1 (in red) and numa46=1.
According to equations (5)∼(7), we transform the model a into a point set, as shown in Figure 7(a), and subsequently employ the k-means algorithm introduced in Section 3.
Finally, the Silhouette coefficients automatically confirm the number of clusters ask = 4 (shown in Figure 8). The horizontal axis is the number of clusters, and the ordinate is the value of Silhouette coefficient. When k = 4, the value of Silhouette coefficient S is maximum.
The final segmentation result is shown in Figure7(b). According to this method, the model a could be decomposed into several significant regions (see in Figure 9), where each color represents one part of the model a.Figure 7
(a) Point set for the modela. (b) Result of k-means cluster.
(a)
(b)Figure 8
The curve of the Silhouette coefficients.Figure 9
Segment result for the modela.


## 5.2. Experiments and Results

We performed some experiments using the library models to validate the approach proposed herein. These tests were implemented on a computer with an Intel 3.20 GHz CPU and a 4.0 GB RAM. The ACIS 3D Geometric Modeler and Visual C++7.1 development environment were used.The efficiency and results of the algorithm proposed in this paper are discussed. The method is not only efficient but also could be used in fields of segmentation of general CAD models overcoming the limitations of model types. As it is seen, with utilization of the proposed approach, it is easy to desirably partition the 3D CAD model, and its segmentation results are more in line with human perception.


### 5.2.1. Run Time for Segmentation

Time estimation of our approach is visualized in Figure10. From this curve, we can see that the proposed algorithm is efficient. The implementation on average takes less than a second.Figure 10
Run time of segmentation with a different model.Thex-axis represents the number of model faces, and the y-axis represents the computational time. The time cost consists of two parts: one is the coordinates’ calculation of points, and the other one is the k-means clustering algorithm complexity. Actually, the former takes a very short time and is negligible. The latter plays a decisive role. That is to say, the complexity of the proposed algorithm strongly depends on the complexity of the k-means algorithm. Therefore, the complexity of proposed algorithmic is Onkm, where n is the number of model faces, k is the number of clusters, and m is the iterations. As a fast clustering method, k-means clustering algorithm performs quite well, for example, when the size of the AAGs is 587 nodes and the computation time is only 1.374 s.


### 5.2.2. Effectiveness for Segmentation

Table2 shows the comparison of our approach with method in Ref. [31]. As for each model, the faces of the same color represent the same region and n represents the number of segmentation. The method in Ref. [31] tends to oversegment models. For model 1, it only contains 29 faces. However, the model is divided into 8 regions, and each region does not have sufficient engineering meaning. Furthermore, the segmentations in the four models could not combine the through-hole feature into any other regions, and it also increases the computational complexity of subsequent model comparisons. The segmentation is difficult to apply to model retrieval. All of these models are segmented correctly into meaningful components by our method. Meanwhile, compared with the other methods in Ref. [31], the segmented result in this paper is more consistent with human perception, thus the improving efficiency of model retrieval.Table 2
Comparison of our segmentation algorithm with works in Ref. [31].
Input b-rep model
Methods in Ref. [31]
Method in this article
Model 1
n = 8
n = 3
Model 2
n = 13
n = 4
Model 3
n = 13
n = 5
Model 4
n = 4
n = 2In order to verify the segmentation approach, a set of various models are chosen. The following are some segmentation experiments for the typical mechanical parts using the proposed method, and the segment results are shown in Figure11. Rounds and fillets are ignored, since they will not affect the result. Furthermore, the results show that the method proposed is universal, and it is suitable for the segmentation of most conventional CAD models.Figure 11
The segmentation result of typical mechanical parts. (a) Three segmentation regions. (b) Three segmentation regions. (c) Five segmentation regions. (d) Four segmentation regions. (e) Three segmentation regions. (f) Three segmentation regions. (g) Three segmentation regions. (h) Three segmentation regions. (i) Four segmentation regions.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)Another area that can be benefitted from use of the proposed segmentation method is model reuse. It is possible to get and save meaningful segmented components into the model library for product design. Each segmented component could be conveniently reused by retrieving, copying, and modifying.


## 5.2.1. Run Time for Segmentation

Time estimation of our approach is visualized in Figure10. From this curve, we can see that the proposed algorithm is efficient. The implementation on average takes less than a second.Figure 10
Run time of segmentation with a different model.Thex-axis represents the number of model faces, and the y-axis represents the computational time. The time cost consists of two parts: one is the coordinates’ calculation of points, and the other one is the k-means clustering algorithm complexity. Actually, the former takes a very short time and is negligible. The latter plays a decisive role. That is to say, the complexity of the proposed algorithm strongly depends on the complexity of the k-means algorithm. Therefore, the complexity of proposed algorithmic is Onkm, where n is the number of model faces, k is the number of clusters, and m is the iterations. As a fast clustering method, k-means clustering algorithm performs quite well, for example, when the size of the AAGs is 587 nodes and the computation time is only 1.374 s.


## 5.2.2. Effectiveness for Segmentation

Table2 shows the comparison of our approach with method in Ref. [31]. As for each model, the faces of the same color represent the same region and n represents the number of segmentation. The method in Ref. [31] tends to oversegment models. For model 1, it only contains 29 faces. However, the model is divided into 8 regions, and each region does not have sufficient engineering meaning. Furthermore, the segmentations in the four models could not combine the through-hole feature into any other regions, and it also increases the computational complexity of subsequent model comparisons. The segmentation is difficult to apply to model retrieval. All of these models are segmented correctly into meaningful components by our method. Meanwhile, compared with the other methods in Ref. [31], the segmented result in this paper is more consistent with human perception, thus the improving efficiency of model retrieval.Table 2
Comparison of our segmentation algorithm with works in Ref. [31].
Input b-rep model
Methods in Ref. [31]
Method in this article
Model 1
n = 8
n = 3
Model 2
n = 13
n = 4
Model 3
n = 13
n = 5
Model 4
n = 4
n = 2In order to verify the segmentation approach, a set of various models are chosen. The following are some segmentation experiments for the typical mechanical parts using the proposed method, and the segment results are shown in Figure11. Rounds and fillets are ignored, since they will not affect the result. Furthermore, the results show that the method proposed is universal, and it is suitable for the segmentation of most conventional CAD models.Figure 11
The segmentation result of typical mechanical parts. (a) Three segmentation regions. (b) Three segmentation regions. (c) Five segmentation regions. (d) Four segmentation regions. (e) Three segmentation regions. (f) Three segmentation regions. (g) Three segmentation regions. (h) Three segmentation regions. (i) Four segmentation regions.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)Another area that can be benefitted from use of the proposed segmentation method is model reuse. It is possible to get and save meaningful segmented components into the model library for product design. Each segmented component could be conveniently reused by retrieving, copying, and modifying.


## 6. Conclusions

In this paper, we develop a segmentation method that is different from the methods of 3D mesh model segmentation. It is innovative to employ the PERT and spectral theory to transform each face of the b-rep model into a two-dimensional coordinate point. We consider both geometrical and topological information and treat model segmentation as a points-clustering problem, using thek-means approach with silhouette coefficient to conduct unsupervised learning of the coordinate points. Additionally, we mainly focus on the concavity of the boundary, since the division mainly appears in the concave edge. That is, the weight between two nodes is −1. Therefore, this method is suitable for many CAD models.The experimental results clearly show that(1)
According to the interval parameters and transformational rule, the proposed approach can effectively transform the b-rep model into a two-dimensional discrete coordinate point set succinctly.(2)
Thek-means algorithm can efficiently cluster points to achieve segmentation. The silhouette coefficient could ensure the accuracy and uniqueness and clustering automatically.(3)
In view of human cognition, the partitioning results are more reasonable boundary regions with some meaningful engineering semantics.



---

*Source: 4395972-2019-09-25.xml*