# Build Orientation Optimization Based on Weighted Analysis of Local Surface Region Curvature
## 3 Methodology
### Surface Region Analysis
#### 3.1.3 Curvature Shift
The equation is equivalent to the following form:  
\[k(x_{i})=\frac{1}{\sqrt{2\pi}}\cdot e^{-\frac{\left|x_{i}\right|^{2}}{2}} \tag{10}\]  
in order to get the weight distribution according to the distance, so the model is further revised as following:  
\[w(d_{i})=a\cdot e^{-\frac{d_{i}}{2}} \tag{11}\]  
where \(a\) is weight coefficient, \(d_{i}\) is the distance between the \(i\)-th point and the cluster center, let \(a=1\), the Gaussian weight is determined by the following equation:  
\[\sum_{i=1}^{n}w(d_{i})=1 \tag{12}\]  
In order to manage the topological structure and points query efficiently, we used the KD-tree proposed in [31]. The index not only offers quick distance query to get one cluster but topological query of neighbour points to reconstruct the NURBS surface. Based on the curvature estimation and Gaussian kernel, the process of curvature shift is shown in Algorithm 1. The clustering model using curvature shift is shown in Figure 4c. Different clusters of the model are represented by different colors, which represent different regions that have similar geometry features. Clustering through curvature shift is to better analyze the key regions of the surface curvature changes, which helps filter out key points and triangle facets to assign higher weights to these regions in order to participate in the construction of the volume error function in Section 4. Although clustering is not the focus of this article, it is necessary to present the comparative results of the program running. The K-means cluster results are unpredictable, and the effect is difficult to determine. When the same parameters are used for clustering, different results will appear, because the initial value of the clustering is randomly assigned. Figure 5b,c are different results when \(k=10\). No matter what parameters are used to filter key points, the result is always uncertain. Curvature shift cluster results are shown in Figure 6. When the cluster center moves along the direction of the largest curvature change, the clustering result is unique. When different thresholds \(\epsilon\) are given, the key points with large curvature changes in the edge of the model can be filtered out effectively. ```
0: the original model \(M\), convergence threshold \(\epsilon\), cluster number \(c_{num}\), initial point \(p_{init}\)
0: the clustered model \(M^{{}^{\prime}}\), cluster list \(clist\), cluster center \(c_{centroids}\)
1: Set Gaussian bandwidth \(b_{w}\gets 1\), \(Q_{query}\leftarrow\varnothing\), \(j\gets 0\)
2: Define \(L(X)\) as the element number in \(X\)
3: Build the spatial index \(S_{index}\) of \(M\)
4:while\(L(Q_{query})\leq c_{num}\)do
5: Query point set \(Q_{query}\) in \(S_{index}\) (\(p_{init}\), \(b_{w}\))
6:if\(L(Q_{query})\leq c_{num}\)then
7:\(b\gets b_{w}+0.1\)
8:else
9:\(b\gets b_{w}-0.1\)
10:endif
11:endwhile
12: Calculate curvatures by Equation (5)
13:for point \(p_{i}\) in \(S\)do
14: Calculate \(w(d_{i})\) by Equations (11) and (12)
15: Calculate \(w(c_{i})\) based on Section 3.1.2
16:\(w(c_{i})\gets w(c_{i})+w(d_{i})\)
17: Calculate \(C_{sv}\) by Equation (9)
18:if\(\sqrt{C}_{sv}\geq\epsilon\)then
19:\(clist_{j}\gets p_{i}\)
20:else
21:\(j\gets j+1\)
22:\(clist_{j}\gets p_{i}\)
23:\(c_{centroids}\gets p_{i}\)
24:endif
25:endfor
26:return\(M^{{}^{\prime}}\), \(clist\), \(c_{centroids}\)
```  
**Algorithm 1** Curvature Shift. When the number of clusters is given, the bandwidth \(b_{w}\) is determined. The calculation range of \(C_{sv}\) is determined according to the bandwidth. In step 5, \(b_{w}\) is adaptively adjusted according to the number of clusters, and the range of \(C_{sv}\) is limited in the spherical domain within the radius \(h\) and the cluster center of the sphere. \(C_{sv}\) always moves along the direction with the biggest curvature density. If it is less than the threshold, the new cluster is added, otherwise the number of points in current cluster continues to increase. This iterative process ends up with the number of clusters set by the user.