# Path Planning for Laser Cladding Robot on Artificial Joint Surface Based on Topology Reconstruction
## 4 Generation of Laser Cladding Paths  
### Topological Reconstruction of the Artificial Joint CAD Model  
A STL (Stereo Lithography) file, which is a CAD data exchange file with a simple format, is very suitable for simulating, designing and modifying artificial joint models [20]. 3D models of artificial hip joints were converted into STL files by the CAD module, as shown in Figure 4a. Figure 4b shows the triangular facets in the STL file, which were described using three sets of X, Y and Z coordinates for each vertex and a normal unit vector indicating the direction of the facet. The three vertices were arranged counterclockwise. It must be mentioned that the triangular facets in the STL file were isolated and had no relation to the surrounding triangles. In other words, the STL file contained only graphical location information, not topological information. Therefore, in order to extract geometric information more effectively in the CAD model for subsequent path planning, it was necessary to pre-process STL files and create the relations among points, edges and facets [21]. In order to create the overall topological information at one time, the topology access should meet the following basic rules:  
**Rule 1:** Given a triangular facet, get its three edges and three vertices. **Rule 2:** Given an edge, get its two adjacent triangular facets and two vertices. **Rule 3:** Given a vertex, get all triangular facets in which the vertex is located. Figure 3: The overall procedure. As shown in Figure 5, the respective data structures of vertices, edges and facets were designed according to the rules above. To store and read data more efficiently, three lists of vertices, edges and facets were created to store vertices, edges and facets respectively. The information of a vertex contained the index of the vertex, the coordinate of the vertex, the normal vector of the vertex and all indexes of the facet on which the vertex is located. The information of an edge contained the index of the edge, indexes of two end points of the edge and indexes of two facets on which the edge is located. The information of a facet contained the normal vector of the surface, the index of three vertices and the index of three edges. According to the characteristics of the format of an STL file, a topological relation reconstruction algorithm was designed to read and parse STL files. The information of each triangular facet was read one by one, including the vertex coordinates and normal vector. Each vertex, edge and facet was topologically related to the surrounding elements and stored in the corresponding lists, as in the following steps. Figure 4: **(a) Main components of an artificial hip joint. (b) The triangular facets in an STL file of an acetabular cup. **  
Figure 5: The data structure after topology reconstruction. **Step 1:** Read in the three vertices (\(V_{1}\), \(V_{2}\), \(V_{3}\)) of a triangular facet in turn, and judge whether the vertex already exists in the list of vertices. If it does not exist, add it to the list of vertices; if it does, skip it. **Step 2:** Read in the three edges (\(E_{1}\), \(E_{2}\), \(E_{3}\)) of the current triangular facet in turn, and judge whether the edge already exists in the list of edges. If it does not exist, the index of the two vertices that make up the edge will be written in this edge, and add this edge to the list of edges; if it does, skip it. **Step 3:** When all vertices and edges of a triangular facet (\(F\)) are added to the corresponding lists, the index of the three vertices and three edges that make up the facet will be written in this facet. Then, add this facet to the list of facets. **Step 4:** Repeat Step 1-3 until all triangular facets are read and recorded. To illustrate this procedure further, the pseudocode of this procedure is also given as the following Algorithm 1.