Sensitivity Analysis for Simulated Annealing-Based Fitting of CAD Models to Point Clouds of Digitized Parts

Today, being able to reconstruct or update 3D representations of existing products and systems has become mainstream to support the creation and exploitation of digital twins in the context of Industry 4.0 [1]. Clearly, the relative ease of access to more or less sophisticated 3D acquisition devices has certainly accelerated the demand while extending the range of possible applications. However, the point cloud treatment and the reverse engineering of CAD models are not yet fully automatized. Most of the existing reverse engineering techniques follow a time-consuming patch-by-patch reverse engineering strategy that does not satisfy the Industry 4.0 requirements [2]. Indeed, in most applications, the structure of the products or systems does not change, and only the position and orientation of its constitutive parts is to be updated. Thus, the update problem can be transformed in a fitting problem for which the optimal parameter values of CAD models have to be found to minimize the deviation between the digitized point clouds and the digital twins.

To support the fitting of parts and assemblies through the reverse engineering process, a simulated annealing (SA) based fitting algorithm has been developed [3]. It considers as input the digitized point cloud, the CAD models to be fitted and the set of its parameters to be modified by the SA algorithm to minimize the deviation. This metaheuristic algorithm has a stochastic behavior [4], with few knowledge on how the CAD parameters’ values are to be changed throughout the optimization. A possible way to understand the influence between the output and parameters’ evolution is sensitivity analysis [5, 6]. It has been used in various contexts, as, for example, for the parameter choices of SA for continuous network design [7], and various indices have been specified [8‐10]. This paper studies the possibility of coupling a sensitivity analysis to the SA algorithm. The sensitivity analysis allows the evolution of the influence of the CAD model parameters to be monitored throughout the fitting process. Comparing the obtained sensitivity evolution curves to the changes of the parameters directly imposed by the SA algorithm provides hints to improve the fitting process.

The paper is organized as follows. Section 2 briefly reviews the previously developed fitting framework, and the new sensitivity analysis is introduced in Sect. 3. Section 4 discusses the results on a L-like shape and how such an analysis could be intelligently exploited throughout the fitting process. The last section concludes the paper and discusses the future works.

Recently, a breakthrough has been achieved in the definition of part-by-part reconstruction or update of editable CAD models fitting the point cloud of a digitized mechanical part or assembly avoiding the patch-by-patch reconstruction [3]. The idea is to work directly at the level of the part whose parameters are modified by a SA algorithm until a good-quality fitting is obtained. The inputs are the point cloud \({\text{PC}}\) to which a parameterized CAD model \({\mathcal{M}}_{0}\) is to be fitted. The point cloud is composed of N points \({\text{PC}}\left[ i \right]\), with \(i \in \left[ {1..N} \right]\), and the CAD model is parameterized by \(N_{p}\) control parameters \(p_{k}\), with \(k \in \left[ {1..N_{p} } \right]\). During the prearrangement step, the user locates in a coarse manner the part inside the point cloud, this initializes the parameters values \(p_{k,0}\) (Fig. 1a). At each iteration \(j\), the SA algorithm then tries to modify the parameters values \(p_{k,j}\) until the updated CAD model perfectly fits the point cloud (Figs. 1b and 1c). The quality of the fitting is assessed thanks to an energy function which characterizes the overall deviation between the point cloud and the CAD model. The process stops when the energy function no longer decreases with respect to a given accuracy \(\varepsilon_{s}\), or when a max number of iterations \(M_{iter}\) is reached.

At an iteration \(j\) of the SA algorithm, the energy function to be minimized is evaluated as follows:

wherein \({\mathcal{M}}_{j}^{ \triangleright }\) represents the tessellation of the CAD model \({\mathcal{M}}_{j}\) after its update by the CAD modeler at the jth iteration of the SA algorithm, and d(point, mesh) is the distance function that returns the closest distance between a point and a mesh.

The previous section has introduced the newly developed fitting algorithm that exploits a SA algorithm to minimize the overall deviation between the point cloud and the CAD model to be fitted. Even though this process has proved to generate good-quality results when compared to the traditional patch-by-patch fitting strategy, the path followed to reach the minimum remains under the control of the SA algorithm, which works as a black box and that neither takes into account the semantics associated to the various parameters \(p_{k}\) nor the way their variations may influence the evolution of the energy function step after step. Indeed, while acting on the variables to be optimized, the SA algorithm does not distinguish for instance the lengths, widths, thicknesses and radius that parameterize the features, and all the variables are considered in the same way. It also does not take into account the fact that the influence of a parameter variation on the energy may vary a lot depending on whether the parameter is associated to a structural feature (e.g. the length L of the L-like shape in Fig. 1) or to a detail feature (e.g. the radius r in Fig. 1).

To better compare the influence of the parameters, a sensitivity estimator \(S_{k,j}\) is here introduced to compute at each step j of the optimization process the sensitivity of the energy function with respect to each parameter \(p_{k}\):

Since the energy function is computed using a nearest point algorithm, it cannot be differentiated. Thus, at the jth iteration, the sensitivities are approximated using a first-order finite difference scheme (either forward or backward) directly controlled by the step \(h_{k}\) chosen for the corresponding parameter \(p_{k}\):

The core of the fitting algorithm has been implemented in MATLAB®, which is able to call the built-in functions of SolidWorks® to perform the successive CAD model updates and ensure the consistency of the resulting B-Rep model during the optimization loops. All the steps \(h_{k}\) used to compute the sensitivities are equal and only depend on the type of parameter they are associated to. Thus, step \(h_{k} = 0.1\;{\text{mm}}\) in case \(p_{k}\) is a length, and \(h_{k} = 0.1^\circ\) in case it is an angle. Those values have been chosen in coherence with the accuracy of the adopted CAD modeler.

In order to compare the sensitivity of the parameters to the way the SA algorithm modifies the parameters values step after step, the evolution of the parameters can be tracked in an absolute or relative manner, as follows:

Thus, the value \(\delta p_{k,j}\) characterizes the absolute evolution of the parameter \(p_{k}\) between iterations \(j\) and \(j + 1\), whereas \(\Delta p_{k,j}\) refers to its relative evolution. At each iteration \(j\) of the SA algorithm, it is therefore possible to compare the sensitivity \(S_{k,j}\) of each parameter \(p_{k}\), to the decision taken by the SA algorithm on how to modify the parameter value for the next step \(j + 1\). This is illustrated in Fig. 2 for the fitting of the L-like shape introduced in Sect. 3. For this example, the initial temperature of the SA algorithm has been set up to \(T_{0} = 10\) following the initialization procedure suggested in [3]. For the sensitivities, the forward finite difference scheme \(S_{k,j}^{ + }\) has been used when the absolute evolution \(\delta p_{k,j} > 0\), and the backward scheme \(S_{k,j}^{ - }\) otherwise.

From this experimentation, one can clearly see that the sensitivities of the five parameters defining the L-like shape are relatively different at the beginning, and that they slightly evolve as the fitting process goes on (Fig. 2 right). On the contrary, the changes imposed by the SA for each parameter at each iteration \(j\) are very close. For sake of clarity, the sensitivity of the five parameters at the beginning and the average of first ten iterations are given in Table 1. This table also shows the desired values, \(p_{k,D}\), and the final values \(p_{k,F}\) for the object’s parameters.

One can also see that the successive changes imposed by the SA algorithm to the parameters’ values (Fig. 2 left) cannot be easily correlated to the evolution of the sensitivities. Thus, several ways of improvement can be sketched:

The first idea has been implemented, but due to space limitation results cannot be shown here. On the example of the L-like shape, two main categories of parameters can be distinguished when comparing their sensitivities at the beginning of the fitting process: \(\left\{ {L,\ell ,e} \right\}\) and \(\left\{ {R, r} \right\}\) gather together parameters having comparable sensitivities. Such a decomposition in two groups gives rise to two successive optimization loops. Overall, doing this way the accuracy of the fitting is improved compared to the use of a single optimization loop.

This paper has explored the possibility to integrate a sensitivity analysis within a SA algorithm used to fit a CAD model in the point cloud of a digitized part. Such an approach helps grouping the CAD model’s parameters so as to treat batches having comparable sensitivities. Other improvements have also been sketched to be more accurate and to reduce optimization times.