Development of the geometrical feature extraction tool using DBSCAN clustering for toolpath generation in incremental forming

doi:10.21203/rs.3.rs-340927/v1

Download PDF

Research Article

Development of the geometrical feature extraction tool using DBSCAN clustering for toolpath generation in incremental forming

https://doi.org/10.21203/rs.3.rs-340927/v1

This work is licensed under a CC BY 4.0 License

Version 1

posted

You are reading this latest preprint version

Incremental forming is an emerging manufacturing technique, which allows the forming of the components without product-specific dies. The process uses Computer Numerical Control (CNC) machine tools to form complicated geometries. A punch, mostly a ball end tool, follows the toolpath obtained from the 3D model of the desired geometry to deform a blank into the desired shape. The objective of the current research is to develop a geometrical feature extraction technology to generate the toolpaths for the incremental forming process. A novel geometrical feature extraction tool, developed using attribute clustering techniques is proposed here. The proposed technology extracts geometrical features from the sliced contoured data of the geometry using Density-Based Spatial Clustering of Applications with Noise (DBSCAN) clustering and convex hull algorithms. Initially, the DBSCAN clustering technique is used for parent feature extraction. Later, child features are extracted from the parent features with the help of a convex hull algorithm. This paper discusses in detail the algorithms developed to extract geometrical features. The performance of the developed algorithms is validated with three different multi-featured geometries representing different types of families like geometries with natural partitions (features are connected with edges), geometries with smoothly connected features, and free form geometries. The results show that the techniques work successfully with different complicated geometries to extract the features. The outcome of this research would help evolve a system for an automatic generation of the feature-based toolpaths for the incremental forming (and similar) processes.

Mechanical Engineering

Incremental forming

Toolpath

Feature extraction

Freeform geometries

DBSCAN clustering

Toolpath planning is vital for various manufacturing processes, including CNC milling, 3D printing, and Incremental Forming (IF). The procedure of toolpath development somewhat differs for these manufacturing processes. Besides, for manufacturing most of the complex free form geometries, except 3D printing, geometrical feature extraction is a critical part of the toolpath development. A variety of methods are reported for geometrical feature extraction using surface mesh or a point cloud. These methods are categorised into seven domains, namely, edge detection methods, region growing methods, attribute clustering methods, shape fitting methods, model-driven methods, deep learning methods, and hybrid methods[1]. In another work of Babic et al. [2], the feature recognition methods were categorised in the domains like syntactic pattern recognition, state transition diagrams and automata, logic (if-then) rules and expert systems, graph-based approach, convex-hull volumetric decomposition, cell-based volumetric decomposition, hint-based approach, and hybrid approach. This paper proposes a novel geometrical feature extraction tool, developed using attribute clustering techniques for toolpath development for IF.

Lu et al. [3] introduced a feature-based toolpath (FBT) generation method for the IF process, in which, unlike the constant Z-height sliced toolpath, equipotential lines based on boundary edges were generated and used for toolpath generation. This method was not suitable for complex parts where the number of boundary edges is more than two. In another work, automatic feature recognition and sequencing strategy were developed by Lingam et al. [4]. In their method, feature separation and recognition steps were performed using silhouette loops on the surface, followed by sequencing of features and toolpath generation. However, finding the silhouette loop involved huge complexity. Ndip-Agbor et al. [5] proposed a new toolpath strategy for toolpath generation for multifeatured parts in case of double-sided incremental forming (DSIF). Their method discussed the strategies of feature separation using a contour relation map and forming using a hierarchical tree structure. Behera et al. [6] had reported optimised toolpath generation algorithms. They proposed a network analysis methodology using topological conceptual graphs to reduce geometrical inaccuracies in the formed part through toolpaths. The FBT strategies mentioned above uses the Stereolithographic (STL) file format for feature extraction. However, the conversion of Computer Aided Design (CAD) surfaces to STL leads to tessellation errors, which cause the loss of topological or geometrical information.

In addition, to minimize the tessellation error (refer Fig. 1), if the number of triangular facets used for the approximation of the geometry is increased, the STL file size becomes large. Thus, feature extraction using STL files makes the process inflexible and computationally expensive, which further increases the lead time of the toolpath development process. Direct slicing uses the exact contours of a CAD model as the input; and thus, is more precise. It eradicates the restrictions of STL and avoids tessellation errors associated with the use of an STL model [7–9].

Several feature extraction techniques are reported in the literature, while some of the relevant papers are discussed here. In the works of Liu et al [10], Bhandarkar and Nagi [11], and Öztürk et al. [12], the automatic part feature extraction technologies were developed based on Initial Graphics Exchange Specification (IGES), neural network approach with boundary representation and Standard for the Exchange of Product model data (STEP) file formats respectively. Lavoué et al.[13] used the curvature values of the triangles of the surface mesh for the geometrical feature extraction using the K-means clustering technique. Zhang et al. [14]used the region growing method for feature extraction using mean-shift clustering to cluster the vertices of the mesh. Nagargoje et al.[15] evaluated the performance evaluation clustering techniques to identify the best technique for toolpath development and rated Density-Based Spatial Clustering of Applications with Noise (DBSCAN) clustering over K-means, Hierarchical, and Spectral clustering techniques.

The DBSCAN [16–18] is a density-based clustering technique in which the clusters are built based on density and connectivity of the points in the dataset. The density-based clustering techniques divide the points in the dataset into three categories, namely, core points, border points, and noise or outliers. Two basic input parameters, i.e., epsilon neighbourhood radius (ε) and the minimum number of points (Minpts) inside the epsilon neighbourhood radius are used to categorize the dataset. Based on the definitions of the points, the clusters are formed. For more details, kindly refer to [16].

In this section, the algorithms developed for the geometrical feature extraction are discussed in detail. The section is organised as follows: the details of the development of sliced contoured datasets are discussed at the starting of the section, this is followed by the formation of parent features using DBSCAN technique, and the section ends with the formation of child features using convex hull algorithms.

2.1. Development of datasets

In this section, the procedure for the development of the datasets is discussed. Figure 2 shows the procedure for the development of the dataset.

The process starts with modelling of the required geometry using a CAD platform. Later, slicing of part geometries is performed. Slicing is a process of contour generation due to the intersection of a plane with the part geometry. In this research, the planes parallel to the Z plane are used as the intersection planes. The slicing of the surface geometry results in densely connected points forming a closed contour(s). In the multifeatured geometries, the number of contours for each slice would be greater than one. The spatial coordinates of the surface-plane intersection are extracted for further processing. Later, this dataset is divided into different subsets based on Z coordinate values of the points (i.e., sorting of the points based on the Z coordinate value of the points). The number of subsets depends on the depth of the component and the distance between two consecutive intersecting planes (step depth).

The steps involved in the development of datasets are shown in Fig. 3; the geometries considered here are shown in Step 1 and the results of slicing are shown in Step 2. The datasets used for clustering in this work are point cloud data stored in the form of multiple closed contours as shown in Step 2 of Fig. 3. Slices at different depths, as shown in Fig. 3, are selected as the input to the DBSCAN clustering algorithm. To get the insight of the slicing process, some randomly selected subsets (slices) are highlighted and shown in Step 2 of Fig. 3.

2.2. Identification of the Parent Features

2.2.1. Contour Clustering by DBSCAN

Here, the focus would be to correctly identify and segregate each contour present in a slice in the dataset using the DBSCAN clustering algorithm. For the geometries, that can be formed incrementally, the contours generated due to slicing are well separated in most of the cases. If at some point, the contours intersect or part intersection occurs, the developed contour can be formed in a single cycle. Thus, the intersecting contours are treated as a single feature and will not affect the toolpath generation. The outliers or noise, in general, does not appear in the clusters to be formed in this application.

The flowchart for the process of contour clustering by DBSCAN is shown in Fig. 4. At the dataset development stage, the dataset is converted into the subset. Initially, the subset one, i.e., the first slice, is chosen for the contour clustering. In the next step, the input parameters of the DBSCAN are calculated for the subset one. As discussed in Sect. 1, there are two input parameters of the DBSCAN algorithm, the lowest possible value of minimum points is two, and the same is chosen here to avoid the merging of two closely spaced contours. The maximum value of the Euclidean distance between pairs of points in the subset is taken as the value of the radius of the epsilon neighbourhood. Using these input parameters, the DBSCAN clustering solutions are obtained for slice 1. The obtained solutions may contain single or multiple clusters based on the contours available in subset 1. In the next step, each of these clusters is stored separately; also, the mean of the points in each cluster and area of the polygon made by points in the cluster is calculated and stored for further processing. The process is repeated for all subsets (slices) and means, and the areas of the clusters on each slice are stored for the process of formation of the parent feature.

Figure 5 shows the output of contour clustering; to get the insight of the process, one slice per dataset is selected randomly and shown here. The mean and area of the polygons are also highlighted. The details of the dataset, the input parameter of the DBSCAN, and the number of clusters identified for contour clustering are given in Table 1. It is visible that for datasets 1 and 3, the means of the clusters can be separable from each other, whereas, for dataset 2, the means of the clusters cannot be distinguished from each other.

Table 1

Dataset and input parameter information for contour clustering
Dataset information					DBSCAN information
Dataset information					Input parameter		Output
Dataset	Step depth (mm)	Selected slice no.	Total height / depth of geometry (mm)	Height / depth of slice (mm)	Radius of neighbourhood (ε)	No. of min. points (Minpts)	No. of clusters
1	0.5	1	32	-32	0.4361	2	3
2	0.1	113	11.3	-0.1	0.5	2	3
3	0.5	27	30	-23	0.6513	2	4

2.2.2. Formation of groups

After the contour clustering operation is performed for each slice, the groups of contours are formed. These groups are called parent features. To form the groups, the matrices of means and the polyarea are used. In this section, the procedure for the formation of parent features is discussed in detail.

Figure 6 shows the flowchart for the procedure of formation of parent features. The matrix of means comprises the means of the multiple contours found as results of the contour clustering for each slice. In the 2D space of X and Y coordinates, the mean of the contour is a parameter that represents the location of the contour. The contours having their means in the close neighbourhood of each other are likely to form a group. Thus, the DBSCAN clustering is used here to form groups based on means of contours. For the groups that are not distinguishable based on the means of the clusters are separated on the basis of the areas of the polygons. The logic is that the areas of the outer clusters would be greater than the areas of the inner clusters. After the formation of the groups based on the means, each group is scanned for slices with concentric clusters. If the slices with concentric clusters are present in the group, the separation of the concentric clusters is performed. After the identification of the slices, the areas of the clusters on the slices are called and DBSCAN clustering applied. As the areas for the outer cluster are greater than the inner ones, DBSCAN easily performs the separation process. Figure 7 shows the procedure for the separation of concentric clusters.

Figure 8 shows the plots of the means for each cluster on all the slices, where the groups of clusters are formed using the DBSCAN clustering of the means of the clusters. The details of the dataset, input parameters of the DBSCAN, and the number of clusters identified for group formation using means are given in Table 2.

Table 2

Dataset and input parameter information for group formation using means
Dataset information		Data from contour clustering		DBSCAN information
Dataset information		Data from contour clustering		Input parameter		Output
Dataset	Total slices	Min. clusters on any slice	Max. clusters on any slice	Radius of neighbourhood (ε)	No. of min. points (Minpts)	No. of groups formed
1	65	3	3	0.5	2	3
2	114	2	3	0.01	2	1
3	61	1	8	0.3	2	7

For the geometries having convex-concave features (2nd geometry in Fig. 3), some of the slices may have concentric contours. For such concentric contours, the mean of the points coincides. In such cases, it is impossible to form two different groups as a convex and concave feature. Thus, the areas of the contours are used for the separation of the concentric features. For the contours developed due to the convex feature, the area of the contours increases with the depth of the component. Whereas, for the concave feature, the area of the contours decreases with the depth of the component. The DBSCAN clustering is applied to separate the contours based on the area of the contours.

From Fig. 8 (b), it is noticed that only 1 group is formed using the means of clusters as means of the clusters are coincident; whereas the maximum clusters on any slice are 3 (refer Fig. 5 (b)). This condition occurs when the clusters are concentric. Thus, this group must follow the step of separation of the concentric clusters. Figure 9 shows the application of the DBSCAN to the areas of the polygons for dataset 2. From Fig. 9, it can be noticed that totally 3 sub-groups are formed. There are 114 slices in the group from slice 1 to slice 111; slice 114 consists of two clusters, whereas slices 112, and 113 have 3 slices each.

2.3. Identification of the Child Features

After identification of the parent features, the child features of the geometries can be extracted using the technique developed with the help of convex hull of the polygon. For a given set of points in the plane, the convex hull of the set is the smallest convex polygon that contains all the points of it. The output of the feature extraction using the DBSCAN clustering is used as the input for the extraction of child feature. The flow chart for the child feature extraction is shown in Fig. 10.

After extraction of the parent feature, each parent feature is analysed separately for child feature extraction, and the points lying inside the convex hull of each slice are extracted. Figure 11 shows the process of application of the convex hull algorithm to polygons. After application of the convex hull algorithm, the points inside the convex hull polygon are selected for further processing. The output of the points inside the convex hull polygon is a single set of points and needs to be separated into distinct sets of points for separate child features. To separate the features, DBSCAN clustering is applied to the extracted points. Figure 12 shows the separate clusters after application of DBSCAN clustering to the extracted points, the asterisk marks are the means of clusters identified. This process is repeated for all slices of the parent feature.

After the application of DBSCAN clustering to the extracted points, the clusters are formed, and the means of clusters are used to form the group. Again, the DBSCAN algorithm is applied to the means of clusters to form groups, these groups are child features of the parent features.

In this section, the final outcomes of the feature extraction using DBSCAN clustering and convex hull algorithm are discussed in detail. Results of the parent feature extraction and the child feature extraction are discussed separately for each dataset.

3.1. Dataset 1

3.1.1. Extraction of the parent features

As discussed in Sect. 2.2, at the stage of formation of groups by the means of clusters; for dataset 1, 3 groups formed are as the parent features. Also, there is no need for further processing for the separation of concentric features. Figure 13 shows the parent features extracted from dataset 1 using DBSCAN clustering. The dog bone shaped feature is termed as parent feature 1, two conical features are termed as parent feature 2 and 3, respectively. Features 1, 2, and 3 in Fig. 13 correspond to the groups 1 (red), 2 (black), and 3 (green) in Fig. 8 (a), respectively.

3.1.2. Extraction of the child feature

Figure 14 shows the application of the convex hull algorithm to the parent features of dataset 1. Here, the child features are extracted from the parent feature 1 only, as for the parent features 2 and 3 do not show any points inside the convex hull of the polygons. Figure 15 shows the child features extracted using parent feature 1 for dataset 1.

3.2. Dataset 2

3.2.1. Formation of the parent features

As shown in Fig. 8 (b), at the stage of group formation using the means of clusters for dataset 2, only one group can be formed as the mean of all clusters coincides. The corresponding feature is shown in Fig. 16. For these kinds of geometries, additional processing, i.e., separation of groups using the areas of clusters is performed. The results of the separation of the features using areas of the clusters are shown in Fig. 17.

3.2.2. Extraction of the child features

Figure 18 shows the application of the convex hull algorithm to the parent features of dataset 2. As shown in Figure 18 for dataset 2, child features can be extracted from all the parent features. Child features extracted from the parent features 1, 2, and 3 for dataset 2 are shown in Figure 19, Figure 20 and Figure 21 respectively.

3.3. Dataset 3

3.3.1. Formation of the parent features

As shown in Fig. 8 (c), at the stage of group formation using the means of clusters for dataset 3, seven groups are formed, and some noise points are also visible. The noise point represents the null group and does not form the features. The parent features formed for dataset 3 based on the means of the clusters are shown in Fig. 22. As there are no concentric groups formed, the groups formed here are distinct, and thus, termed as parent features. As the parent feature 2 consists of only 2 slices and located outside of the main geometry, it is deleted and not considered for child feature extraction.

3.3.2. Extraction of child features

Figure 23 shows the application of the convex hull algorithm to the parent features of dataset 2. For dataset 3, child features are extracted for parent features 1, 5. For the other parent feature in dataset 3, the points inside the convex hull polygon are not enough to constitute a child feature. Child features extracted from the parent features 1 and 5 of dataset 3 are shown in Figure 24 and Figure 25 respectively.

This paper proposes a feature extraction technique for toolpath development for the incremental forming process using DBSCAN clustering and convex hull algorithms. The algorithms to extract the parent and child features from sliced contoured data are developed using DBSCAN clustering and convex hull algorithm, respectively. Three different multifeatured geometries are considered to check the performance of the developed algorithms. From the results obtained the following conclusions are drawn:

It was observed that the DBSCAN clustering technique works successfully for the contour clustering application irrespective of the shape of the contours in the datasets.
The algorithms developed for feature extraction using DBSCAN and convex hull algorithms automatically detect the number of geometrical features, i.e., the number of the features to extract is not given as an input to the algorithm.
The developed process facilitates the advantage of direct slicing of the CAD models and eliminates the errors arising in the toolpaths due to tessellation errors caused by STL slicing.
The developed methodology is suitable for the smoothly connected features (absence of natural boundary or edge between features) as well as for the geometries having more than two boundary edges.
The results show that the developed techniques work successfully with different types of complicated geometries that can be formed by using the IF process.

This technology being a novel approach to extract and represent the geometrical features in complex geometries will provide flexibility while developing the IF toolpaths.

Funding:

This research was financially supported by Impacting Research, Innovation, and Technology (IMPRINT) INDIA through a Project of Government of India (Project Number: 5506). The authors wish to acknowledge the funding agencies.

Conflicts of interest/Competing interests:

There are, however, no conflicts, financial or otherwise that are related to this study or its outcome. The study staffs have no conflicts of interest to report. The authors declare that they have no competing interests.

Availability of data and material:

All the data and material used in the study is given in the manuscript.

Code availability:

The codes are developed using MATLAB^®based on the algorithms described in the manuscript.

Authors' contributions:

The work was primarily done by AN with the support of PKK and PKJ for development of algorithms for parent and child feature extraction respectively. PT reviewed and modified the developed algorithms to get the final versions. AN took the lead in writing the manuscript. All authors provided critical feedback and helped shape the research, finding and manuscript. PKK, PKJ and PT arranged the funding. PT and PKJ supervised the research work.

Ethics approval:

All procedures performed in the work involve no human or animal participants.

Consent to participate:

No external participants have contributed to the work discussed in this manuscript.

Consent for publication:

The authors give their full consent to the editor to publish this article if accepted.

Cai N, Anwer N, Scott PJ et al (2020) A new partitioning process for geometrical product specifications and verification. Precis Eng 62:282–295. https://doi.org/10.1016/j.precisioneng.2019.12.009
Babic B, Nesic N, Miljkovic Z (2008) A review of automated feature recognition with rule-based pattern recognition. Comput Ind 59:321–337
Lu B, Chen J, Ou H, Cao J (2013) Feature-based tool path generation approach for incremental sheet forming process. J Mater Process Technol 213:1221–1233. https://doi.org/10.1016/j.jmatprotec.2013.01.023
Lingam R, Prakash O, Belk JH, Reddy N (2017) Automatic feature recognition and tool path strategies for enhancing accuracy in double sided incremental forming. Int J Adv Manuf Technol 88:1639–1655. https://doi.org/10.1007/s00170-016-8880-1
Ndip-Agbor E, Ehmann K, Cao J (2018) Automated Flexible Forming Strategy for Geometries with Multiple Features in Double-Sided Incremental Forming. Journal of Manufacturing Science Engineering Transactions of the ASME 140:. https://doi.org/10.1115/1.4038511
Behera AK, Lauwers B, Duflou JR (2014) Tool path generation framework for accurate manufacture of complex 3D sheet metal parts using single point incremental forming. Comput Ind 65:563–584. https://doi.org/10.1016/j.compind.2014.01.002
Jamieson R, Hacker H (1995) Direct slicing of CAD models for rapid prototyping. Rapid Prototyping Journal 1:4–12. https://doi.org/10.1108/13552549510086826
Zhou MY, Xi JT, Yan JQ (2004) Adaptive direct slicing with non-uniform cusp heights for rapid prototyping. Int J Adv Manuf Technol 23:20–27. https://doi.org/10.1007/s00170-002-1523-8
Sun SH, Chiang HW, Lee MI (2007) Adaptive direct slicing of a commercial CAD model for use in rapid prototyping. Int J Adv Manuf Technol 34:689–701. https://doi.org/10.1007/s00170-006-0651-y
Liu SC, Gonzalez M, Chen JG (1996) Development of an automatic part feature extraction and classification system taking CAD data as input. Comput Ind 29:137–150. https://doi.org/10.1016/0166-3615(95)00081-X
Bhandarkar MP, Nagi R (2000) STEP-based feature extraction from STEP geometry for Agile Manufacturing. Comput Ind 41:3–24. https://doi.org/10.1016/S0166-3615(99)00040-8
Öztürk N, Öztürk F (2001) Neural network based non-standard feature recognition to integrate CAD and CAM. Comput Ind 45:123–135. https://doi.org/10.1016/S0166-3615(01)00090-2
Lavoué G, Dupont F, Baskurt A (2005) A new CAD mesh segmentation method, based on curvature tensor analysis. CAD Computer Aided Design 37:975–987. https://doi.org/10.1016/j.cad.2004.09.001
Zhang X, Li G, Xiong Y, He F (2008) 3D Mesh Segmentation Using Mean-Shifted Curvature. In: Advances in Geometric Modeling and Processing. Springer, Berlin Heidelberg, pp 465–474
Nagargoje A, Kankar PK, Jain PK, Tandon P (2020) Performance Evaluation of the Data Clustering Techniques and Cluster Validity Indices for Efficient Toolpath Development for Incremental Sheet Forming. J Comput Inf Sci Eng 1–32. https://doi.org/10.1115/1.4048914
Ester M, Kriegel H-P, Sander J, Xu X (1996) A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In: Kdd, 34th ed. pp 226–231
Sander J, Ester M, Kriegel HP, Xu X (1998) Density-based clustering in spatial databases: The algorithm GDBSCAN and its applications. Data Min Knowl Disc 2:169–194. https://doi.org/10.1023/A:1009745219419
Schubert E, Sander J, Ester M et al (2017) DBSCAN Revisited, Revisited. ACM Transactions on Database Systems 42:1–21. https://doi.org/10.1145/3068335

Download PDF

Version 1

posted

You are reading this latest preprint version

Development of the geometrical feature extraction tool using DBSCAN clustering for toolpath generation in incremental forming

Status:

Version 1

Abstract

Figures

1. Introduction

2. Methodology

2.1. Development of datasets

2.2. Identification of the Parent Features

2.2.1. Contour Clustering by DBSCAN

2.2.2. Formation of groups

2.3. Identification of the Child Features

3. Results And Discussion

3.1. Dataset 1

3.1.1. Extraction of the parent features

3.1.2. Extraction of the child feature

3.2. Dataset 2

3.2.1. Formation of the parent features

3.2.2. Extraction of the child features

3.3. Dataset 3

3.3.1. Formation of the parent features

3.3.2. Extraction of child features

Conclusions

Declarations

References

Status:

Version 1