# A Fast Hole-Filling Method for Triangular Mesh in Additive Repair
## 5 Hole Filling Based on Hole Size
### Large-Sized Hole Filling by Improved Advancing Front Method  
Although the minimum area triangulation has been regarded as a popular hole-filling method, it is not always effective especially for large-sized holes since it is both time-intensive and memory-intensive. In addition, the sizes of the newly created triangles commonly tend to be big and incompatible with the surrounding mesh. Besides that, the traditional advancing front method [18] can not fully guarantee that the missing region of a divergent hole can be smoothly closed, as shown in Figure 9a. To address these problems, an improved advancing front method is presented to fill large-sized holes, especially for divergent cases. Of course, our algorithm also works well on convergent holes illustrated in Figure 9b. The pseudocode of this algorithm is in the Algorithm 3. Figure 8: Patch fairing. (**a**) Refined hole-filling patch, (**b**) Faired hole-filling patch. **Basic principle** Given a hole loop, the angle \(\theta_{i}\) between two adjacent boundary edges \((e_{i-1,i},e_{i+1,i})\) at each vertex \(v_{i}\) should be first calculated. Then, starting from the vertex \(v_{i}\) with the smallest angle \(\theta_{i}\), new triangles can be created on the plane determined by \((e_{i-1,i},e_{i,i+1})\) with three rules illustrated in Figure 10. If \(\theta_{i}\leq 75^{\circ}\), \((v_{i-1},v_{i},v_{i+1})\) can be directly connected to form a new triangle. If \(75^{\circ}<\theta_{i}\leq 135^{\circ}\), a new vertex \(v_{n}\) needs to added on the bisector with the average edge length of \(e_{i-1,i}\) and \(e_{i,i+1}\). For the last case, two new vertices need to inserted on the trisector also with the average edge length of \(e_{i-1,i}\) and \(e_{i,i+1}\). This is the basic principle of the traditional advancing front hole-filling method. Figure 10: Three rules for adding new triangles. (**a**) \(\theta_{i}\leq 75^{\circ}\). (**b**) \(75^{\circ}<\theta_{i}\leq 135^{\circ}\). (**c**) \(\theta_{i}>135^{\circ}\). Figure 9: Two typical large-sized holes. (**a**) Divergent hole. (**b**) Convergent hole. According to the basic principle, the quality of the final filling patch, as well as the hole-filling speed, heavily depend on the proper determination of the 3D coordinates and the directions for the newly added vertices. In this paper, by taking both the adjacent vertices and local curvature of the hole boundary vertices into account, the 3D coordinates and directions of the newly added vertices can be appropriately determined. Our algorithm consists of two stages: vertex normal correction and optimal position determination. **Vertex normal correction** To make the newly created triangles tend to the center of the hole as fast as possible, that is, reducing the hole-filling times, the normal of each hole boundary vertex \(v_{i}\) needs to be corrected. Especially for most of the divergent holes, the missing regions are unable to be closed by directly utilizing the traditional advancing front method. In addition, based on the corrected vertex normals, the convergent holes can also be closed quickly. After loading a triangle mesh such as in STL format, the vertex normals are usually known, and these built-in normals are sufficient for most mesh processing algorithms. However, the original normal of a vertex is simply determined by weighting the average of the normals of its 1-ring adjacent faces, which does not reflect the curve of the hole boundary. Therefore, in this work, other hole boundary vertices are taken into account. As shown in Figure 11, assuming that there are \(n\) continuous boundary vertices (\(v_{l},l=i-1,i-2,...,i-n\)) on the left-hand side of \(v_{i}\), \(n\) edge vectors (\(e_{i,l}\)) by directly connected with \(v_{i}\) one by one can be produced. In the same way, another \(n\) edge vectors (\(e_{i,r},r=i+1,i+2,...,i+n\)) can also be obtained on its right-hand side of \(v_{i}\). After obtaining these two edge vector sets, another two edge vectors \(e_{i}\) and \(e_{r}\) (see Figure 11b) can be calculated by using the formula below.