# Path Planning for Laser Cladding Robot on Artificial Joint Surface Based on Topology Reconstruction
## 4 Generation of Laser Cladding Paths
### Generation of the Laser Cladding Interpolation Points  
#### 4.2.1 The Slicing Algorithm Based on Topological Relation  
In this section, the initial cladding path was generated from the CAD model based on the topological relations. A series of intersection point sets were obtained using a series of equidistant parallel planes intersecting the CAD model, which was called the slicing process. It was obvious that the process of intersection between the slicing planes and the CAD model was actually to find the intersection between the edges of the triangular facets and the cross planes. After all the intersection points were calculated, they were connected in a certain order to obtain the transversal lines. In order to reduce the number of intersection calculations and avoid additional time consumption of sorting the intersection point sets, the slicing algorithm was designed based on topological relations of the edges. The core of the slicing algorithm was to constantly search the edge list for the edge that intersected with the current slicing plane and calculate the intersection point. The basic principle of the algorithm is, firstly, to traverse the list of edges to find an edge that intersects with the current slicing plane and, then, to search for next intersected edge in the adjacent edges of this edge according \begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Vertex** & **Edge** & **Facet** \\ \hline
**Before topological reconstruction** & 18 & 18 & 6 \\
**After topological reconstruction** & 7 & 12 & 6 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Quantity of the recorded data. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Edge Index** & **Relevant Vertex Index** & **Relevant Facet Index** \\ \hline \(E_{1}\) & \(V_{1}\), \(V_{2}\) & \(F_{1}\) \\ \(E_{2}\) & \(V_{1}\), \(V_{3}\) & \(F_{1}\), \(F_{2}\) \\ \(E_{3}\) & \(V_{2}\), \(V_{3}\  
to the topological relation and to keep searching along the given direction until there are no intersected edges or return to the initial edge. To distinguish the searched edge from the unsearched edge, a Boolean variable named _isSearched_ was declared as an identifier in the data structure of the edge. The value of the identifier for all the edges was initially set as FALSE, which indicates none of the edges have been searched, and then changed to TRUE after being searched. The identifier was greatly useful for ensuring that each edge was accessed only once, which can significantly improve the efficiency of the slicing algorithm. In addition, there were several important variables, namely the width, direction and range of the slicing process, which needed to be determined before the slicing algorithm was executed. The direction and width of the slicing process were specified by the user according to the specific laser cladding requirements. The range of the slicing process was determined by the maximum and minimum coordinates on the slicing direction in the list of vertices. When the slicing direction was determined, the slicing algorithm automatically calculated the range of the slicing process along the slicing direction. Take the \(Z\) direction for example, the procedure of laser cladding path generation based on topological slicing is shown in Figure 7, where \(d\) is the slicing width, \(Z\) is the slicing direction and \(S\) is the value of the slicing plane in \(Z\) direction. The value of the slicing plane was initially set as the minimum value in \(Z\) direction and incremented by the value of the slicing width \(d\). The slicing process started at the minimum coordinate and ended at the maximum coordinate. Each single transversal line was generated in the following steps:  
**Step 1:** Find an edge that intersects with the current slicing plane but _isSearched_ is FALSE. Figure out the intersection between this edge and the slicing plane and change _isSearched_ of this edge to TRUE. **Step 2:** Find all the adjacent edges of that edge according to the topological relationship between the points, edges and facets.