A framework from point clouds to workpieces – Visual Computing for Industry, Biomedicine, and Art

Design

In this study, to address high-precision machining from geometric data, a framework is implemented from the point clouds to the workpieces. The goals of the framework are as follows: (1) obtain the essential geometric information (such as sharp features) of the point clouds, (2) preserve the sharp features during machining, and (3) generate a machinable tool path.

To accomplish the above objectives, the proposed framework can be divided into three parts: mesh generation from geometric data, optimal surface segmentation for CNC, and tool-path planning with the certified scallop height. Further details of these objectives are provided in the following sections.

Mesh generation from geometric data

In this subsection, the methods used to generate a mesh model are briefly introduced. The point cloud is converted into a mesh using IGR [13], and the mesh is then denoised by applying MeshTGV [17]. The results show that IGR can produce a better mesh than the other mesh reconstruction methods, and MeshTGV can preserve sharp features without artifacts. To facilitate subsequent operations, a triangular mesh is converted into a quadrilateral mesh using Quadriflow [52]. An example of this is shown in Fig. 2.

From point cloud to mesh. a Point cloud; b Denoised mesh; c Final mesh

IGR

Given an input point cloud χ = {x_i}_i ∈ I ⊂ ℝ³, with or without normal data, (mathcal{N}={left{{n}_iright}}_{iin I}subset {mathbb{R}}^3). IGR learns a signed distance function (f:{R}^{mathbb{3}}times {R}^mto R) using a multilayer perceptron. The loss function is defined as follows:

where λ > 0, and ‖∙‖ is L₂ − norm.

The architecture is similar with DeepSDF and is easy to implement.

MeshTGV

Here, MeshTGV is used to refine a noisy mesh obtained from IGR by removing the noise [17]. With MeshTGV, some difference operators are constructed on the edges and facets of the mesh and a normal filter is applied to remove the noise while preserving the sharp features. The normal filter process is converted into a non-differentiable optimization problem. Variable splitting and ALM are introduced to solve this problem and find a smoothed normal field. Subsequently, the vertices are updated to generate the final mesh model using the scheme proposed by Zhang et al. [53].

Quadriflow

QuadriFlow is used to convert a triangular mesh into a quadrilateral mesh. QuadriFlow was developed from Instant Meshes [54] and has certain constraints added. Specifically, the regularity constraint is enforced by minimizing the cost network flow, and the consistent orientation constraint is then successively enforced. According to these constraints, one can re-optimize the position field and extract the quadrilateral mesh from the position field.

Optimal surface segmentation for CNC

To effectively preserve the sharp features of the workpiece during processing, the cutter should follow a path parallel to the sharp features rather than intersecting them. The mesh obtained in the last subsection is therefore segmented into several patches in such a way that the sharp features are located on the boundaries of each patch. A contour parallel tool path can then be generated on each patch to effectively preserve the sharp features. In this subsection, the proposed mesh segmentation method, which uses a MST, is introduced. Herein, the following new concept is also introduced:

Definition 1 A quadrilateral mesh patch E_i is called a sharp height field (SHF) if it satisfies the following conditions:

1. 1.

   E_i is quadrilateral.

2. 2.

   There are no extraordinary points in E_i.

3. 3.

   The sharp features are located on the boundaries of E_i.

Starting from the generated quadrilateral mesh F described in the previous subsection, the goal here is to segment the mesh into SHFs and control the number of SHFs using techniques applied in graph theory:

where E_i is the SHF segmented from the given mesh.

In Definition 1, conditions 1 and 2 ensure that the SHF can be fitted using a B-spline surface. After segmentation, a tool path that satisfies the scallop height constraint on each SHF must be generated. During this process, the first- and second-order differential information of the workpiece surface must be known; however, it is difficult to obtain accurate differential information for the surface represented by a mesh. A B-spline surface is therefore used to fit the SHF after segmentation, for which conditions 1 and 2 were considered. Condition 3 preserves the sharp features of the workpiece during the processing.

The segmentation method consists of three steps (Fig. 3): first, the K-means clustering algorithm is used to remove the workpiece setup base of the mesh; second, a weighted graph of the mesh is constructed based on the location of extraordinary points and sharp features. The MST of the graph is then obtained to determine the optimal connection of the extraordinary points; third, the mesh is divided into several SHFs by determining the clipping edges according to a specific priority.

Pipeline of the segmentation method

Removal of workpiece setup base

In real CNC machining, one can machine the base first and then use it for the machining setup to deal with the remaining parts. A setup base for the mesh must therefore first be chosen and removed. Meanwhile, removing the base can simplify the connection of extraordinary points (Eps, an interior vertex in a quadrilateral mesh which is shared by other than four faces), thus simplifying the subsequent segmentation process.

In general, the base should be as flat and large (in terms of area) as possible. Here, the K-means clustering algorithm is used to select a suitable base. First, the outer normal vector of each facet on the mesh is obtained, as shown in Fig. 4.

Outer normal vectors (red lines) on the mesh

Subsequently, each normal vector is treated as a three-dimensional data point, and the K-means clustering algorithm is used to classify such data points. The following objective function is then provided:

where S and Γ are the similarity and quantity of each dataset, respectively, and μ and γ are two weighting coefficients. Here, let μ = 0.7 and γ = 0.3. This objective function is used to obtain the optimal set of data points, as indicated by the black circle in Fig. 5. The optimal set of data points is mapped onto the workpiece, which is the setup base chosen in this study (with a one-to-one correspondence between faces and their normal vectors). As shown in Fig. 6, the green part represents the setup base, which is removed from the mesh.

Data points representing normal vectors. a Optimal dataset is shown in green; b Local enlarged portion of the optimal set

Setup base of Fandisk model

MST of extraordinary points

After removing the base, conditions 2 and 3 in Definition 1 are considered. For condition 3, which edges are sharp features must first be determined. Here, the angle between the normal vectors is used to determine whether the edge is a sharp feature: An edge with two adjacent quadrilateral facets is judged to be a sharp feature if the angle between the corresponding normal vectors of the two facets is greater than a given degree θ (in this study, let θ = 50^∘). In Fig. 7a, the blue lines represent sharp features of the Fandisk model.

Information on Fandisk model. a Sharp features; b Edges between EPs (red dots)

For condition 2, the EPs should be located at the boundaries of each SHF; therefore, all connection edges between extraordinary points are considered, as shown in Fig. 7b. In this way, the initial segmentation problem can be regarded as a paper-cut problem with EPs and sharp features on the clipping edges. Which mesh edges are clipping edges must be determined such that Eq. (3) is satisfied. Owing to condition 2, some connection edges of the EPs belong to the clipping edges. The connection relations of the EPs directly determine the number of SHFs; hence, the connections of the EPs must be controlled and connected together.

First, the connected weighted graphs of the EPs are established. In Fig. 7b, all connection edges naturally form a connected graph. According to condition 3, all sharp features belong to the clipping edges, and thus the sharp features that do not belong to the connection edge of the EPs (called priori sharp edges) are in a sense equivalent to the boundary of the mesh, as shown by the red lines in Fig. 8. Hence, the unnecessary connection edges of the EPs that intersect the priori sharp edges should be removed. Subsequently, the weighted graph on the mesh is defined.

Removing redundant connection edges of EPs

Two types of vertices are given in the weighted graph, i.e., an EP vertex (red dots in Fig. 9) and an auxiliary vertex (red stars in Fig. 9). The EP vertex corresponds to the extraordinary points, and the auxiliary vertex is formed by the intersection of the two connection edges of the EPs. The remaining connection edges between the EPs form the edges of the weighted graph.

Information of connected graph and its MST. a Weighted graph of the mesh; b MST of connected graph

The weight of each edge is then obtained. There are three types of edges: auxiliary, non-full degree of freedom (NF), and standard. The connecting edge of the two auxiliary points is called the auxiliary edge (black line in Fig. 9a). Choosing this type of edge as the clipping edge often increases the number of SHFs in the segmentation problem. Thus, the weight of the auxiliary edge will be set to a large number. The definition of NF edge is as follows: When the two endpoints of edge α are EPs A and B, the four edges adjacent to edge α at the EPs have at least one edge that does not belong to the weighted graph (the black dotted line in Fig. 10a), and α is then called an NF edge. Choosing an NF edge as a clipping edge often decreases the number of SHFs in the segmentation problem. As shown in Fig. 10b, if an NF edge is chosen as a clipping edge, the number of SHFs can be reduced to two, unlike with other clipping edges. Thus, smaller weights are given to this type of edge. In addition to the two types of edges mentioned above, the remaining edges in the graph are called a standard edge. The weights of these edges are as follows:

where Ξ is the set of boundaries of the quadrilateral facets that belong to the edge of a connected graph, length_i is the length of the boundary of a quadrilateral facet, SC_i is the coefficient of the sharp features, NC is the NF edge coefficient (set to 0.1), and AC is the auxiliary edge coefficient (set to 1000).

Information on NF edge. a Definition of NF edges; b Comparison of various connections

Because some redundant connection edges of the EPs are removed, there may be multiple connected weighted graphs on the mesh (for example, a single extraordinary point can be regarded as a degenerate weighted graph). The MST for each graph is determined to obtain the optimal connection relation between the EPs. Herein, the Kruskal greedy algorithm [55] is adopted to obtain the MST, as shown in Fig. 9b.

Remaining clipping edges

After obtaining the MST, the clipping edges on the mesh must be determined to obtain the SHFs. The clipping edges are set sequentially according to the following priorities: (1) MST of each weighted graph, (2) sharp feature edges and mesh boundaries, (3) NF edges, (4) extended edges of the sharp features, and (5) redundant connected edges for EPs.

These edges are set as clipping edges in order. Priorities 1–3 have been defined. As for priority 4, when the first three items are set as clipping edges, the entire mesh is insufficient to divide into several patches, as shown in Fig. 11a. Therefore, sharp features that do not intersect other clipping edges must be selected and extended forward until they meet other clipping edges (black curves in Fig. 11b), which is priority 4. The mesh can therefore be segmented into several patches.

Information on clipping edges. a Priorities 1, 2, and 3; b Priority 4 (black curve); c Priority 5 (purple curve)

For priority 5, the redundant (non-clipping edge) connecting edges of the EPs must be set as clipping edges to satisfy condition 1 in Definition 1. A clipping edge is thus set for every other connecting edge of the EPs, as shown in Fig. 12a. They are extended forward until they meet the other clipping edges (purple curves in Fig. 11c). Subsequently, the entire optimal segmentation algorithm is completed. Figures 12b-d show the results of the Fandisk model.

Results of Fandisk model. a Clipping edges of Eps; b Front view; c Left view; d Right view

Tool path planning with certified scallop height

In this subsection, a tool path generation method for each SHF is presented. To ensure the machining quality and effectively preserve the sharp features, a contour parallel tool path that strictly satisfies the scallop height constraint is chosen. During this process, although the first- and second-order differential information of the workpiece surface must be known, it is difficult to obtain accurate differential information for surfaces represented by a mesh. Therefore, a B-spline surface is used to fit the SHFs after segmentation prior to the tool-path generation.

Given a set of initial control meshes (the SHFs are used as the initial control mesh) and a target triangle mesh (generated denoised mesh described in MeshTGV section), the surface should be fit using a B-spline surface. Simultaneously, the result must ensure that C⁰ is continuous at the boundary of the SHFs. In this study, uniform bi-cubic B-spline surfaces are used to fit the mesh because the topological structure of each SHF is simple.

Random points P are obtained from the triangle mesh during every iteration, and the error between the point cloud and the B-spline surface should be minimized. First, the as-rigid-as-possible method proposed in ref. [56] is used to parameterize the point cloud P. Instead of using the Cartesian distance, the feature-sensitive metric in ref. [57] is applied. This metric is defined in the position and normal spaces in R⁶, which is more sensitive to surface changes. A local quadratic approximation of the squared distance method (SDM), is then used, as proposed in ref. [58]. During each iteration, the following energy function is optimized:

where e_k is the SDM error term, and F₁ is the thin planar energy. Because each part term is quadratic, the optimization problem can be transformed into the solution of a system of linear equations. The optimization problem is then solved iteratively until the error between the triangle mesh and spline surface becomes less than the threshold. Finally, the fitted B-spline surfaces are obtained, as shown in Fig. 13.

Fitted spline surface of Fandisk model. a Fitted spline surface; b Fitted SHFs

Subsequently, a tool path is generated on each fitting surface. First, a grid that satisfies the scallop height constraint on the rectangular parameter plane is provided. Before generating a grid, the path interval must be calculated according to the scallop height constraint. Scallops are created on the machined surface when the cutter moves along the tool path. The distance between paths is the cutter contact (CC) path interval, as shown in Fig. 14. The calculation of the path interval is associated with the convexity of the surface. In this study, a ball-end cutter is used to machine the surface, and the CC path interval then depends on the local radius of normal curvature R of the surface, the feedrate direction, the radius r of the cutter, and the scallop height h remaining on the surface. In general, the scallop height h is much smaller than radius r of the cutter; hence, the calculation of the path interval can be simplified. Through machining using a ball-end cutter, the tool path interval for different surfaces can be estimated from the following equations [59]:

Path intervals on three different surfaces. a Path interval on flat plane; b Path interval on a convex surface; c Path interval on concave surface

When the path interval l_i is obtained, it can be mapped back to the parameter domain using the following two formulas, and the distance of adjacent CC points in the parameter plane can be obtained [37]:

Here, E, F, and G are the first fundamental parameters of the surface, and u is the parameter of the current tool-path curve.

Subsequently, with the scallop height constraint satisfied, Algorithm 1 is used to generate the grid, as shown below:

More specifically, k sample points are taken from the lowest boundary of the perimeter plane, that is, the parametric line t = 0. For each sample point, the offset interval ∆t is calculated in the t direction with a given upper limit of the scallop height hm, as shown in Fig. 15a. Subsequently, the minimum is selected and defined as ∆t₀ to obtain the parametric line t = ∆t₀, as shown in Fig. 15b. The same process is repeated on the parametric line s = 0, and the minimum interval ∆s₀ is obtained. Next, whether the scallop height between intersection point lc₁ of the two parametric lines and the origin point is less than h_m is considered. If the scallop height constraint is not satisfied, ∆s₀ is further reduced to make the scallop height between the two points equal to hm according to Eq. (5), as shown in Fig. 15c. Next, the above process is repeated on parametric lines t = 1 and s = 1, and the corresponding offset intervals are obtained with the scallop height constraint (Fig. 15d). Finally, the parametric lines are offset in the same order until the entire parameter plane is filled (Fig. 15e).

Pipeline of the tool path generation method. a The offset interval of each sample point; b The minimum interval is selected to obtain the parametric line; c, d Adjust the intersection point to satisfy the scallop height constraint; e Offset the parametric lines until the entire parameter plane is filled; f Generate the contour tool paths

In this manner, any two adjacent points on the grid satisfy the scallop height constraint. As a result, two series of iso-parametric lines are defined as follows:

After obtaining the grid, a cluster of contours can be naturally generated as the tool path of the surface (for example, the first contour is composed of four parametric lines: t = t₀, t = t_N, s = s₀, and s = s_M), as shown in Fig. 15f. Thus, a tool path for the surface is generated.

Finally, a grid with a scallop height constraint and corresponding contour parallel tool path for every SHF is generated, and the entire tool path planning algorithm is completed. Figure 16 shows the final results.

Whole contour parallel tool paths of Fandisk model. a Grids; b Contour tool paths