# A Fast Hole-Filling Method for Triangular Mesh in Additive Repair
## 5 Hole Filling Based on Hole Size
### Middle-Sized Hole Filling by Projection-Based Method  
Since the majority of the holes occurring in one incomplete triangular mesh are middle-sized ones, the missing regions not only need to be fully closed but also should assort with surrounding meshes well after filling. Considering these facts, we hope to get a balance between the efficiency and the ability to shape recovery in the process of hole-filling. Therefore, the minimum area triangulation [6] and Laplace-Beltrami techniques are combined to achieve the initial filling and the deformation on  
Figure 4: Small-sized hole filling by centroid-based method. (**a**) Original hole. (**b**) The computed centroid vertex in gray color. (**c**) Newly created triangles. Figure 3: Hole boundary cleaning. (**a**) Initially detected tooth faces in red color. (**b**) New tooth faces caused by the deletion of (**a**). (**c**) The final hole after boundary cleaning. the patching mesh respectively in this paper, specifically including three stages: initial triangulation, patch refinement, and patch fairing. The corresponding pseudocode is in the Algorithm 2. ```
0:\((v_{0},v_{1},...,v_{k})\)\(\{\mathit{Hole\ boundary\ vertices}\}\)
0:\(P_{f}\)\(\{\mathit{Faired\ filling\ patch}\}\)
1:Produce the initial filling patch \(P_{i}\) by using minimum area triangulation
2:Collect all the edges of \(P_{i}\) as well as the hole boundary edges as an edge set \(S\)
3:for each triangle \(f_{i,j,m}\) of \(P_{i}\)do
4: Split it into three sub-triangles \(f_{i,j,c}\), \(f_{j,m,c}\), and \(f_{m,j,c}\) at its barycenter \(v_{c}\)
5: Save the edges of these sub-triangles into \(S\)
6:endfor
7:for each edge \(e_{i,j}\) of \(S\)do
8:if Meet the edge swapping condition then
9: Swap edge \(e_{i,j}\)
10:endif
11:endfor
12:Generate the refined filling patch \(P_{r}\)
13:Search the two adjacent faces \(P_{a}\) of \((v_{0},v_{1},...,v_{k})\)
14:Combine \(P_{r}\) and \(P_{a}\) into a new patch \(P_{n}\)
15:Deform \(P_{n}\) by using the Laplace-Beltrami algorithm
16:Produce the final filling patch \(P_{f}\)
```  
**Algorithm 2** Middle-sized hole filling  
**Initial triangulation** The key idea of the minimum area triangulation is to create every single triangle by directly connecting three ones among all the hole boundary vertices. As shown in Figure 5, there is a hole with six boundary vertices \((v_{1},v_{2},...,v_{6})\), and it is obvious that six filling schemes are available after looping all the boundary vertices. For each scheme, the total area of all filling triangles needs to be computed, and then these areas will be compared to find the smallest one. We assume that the scheme shown in Figure 5e has the smallest area, so the patching mesh of this scheme is finally chosen as the initial filling patch by using the minimum area triangulation. It can be seen that the filling efficiency of the minimum area triangulation is closely related to the size of the hole boundary vertices. This is the main reason why the minimum area triangulation is not suitable for filling large-sized holes. \[\Omega(M_{p})=\sum_{i=1}^{4}\Omega(f_{l,m,k})_{i},\quad(l,m,k)\in\{1,2,...,6\} \tag{1}\]  
where \(M_{p}\) denotes the final filling patch, and \(\Omega\) denotes the area of a patch or triangle. **Patch refinement** Since the shapes of the newly created triangles by the minimum area triangulation are relatively large and incompatible with the surrounding mesh, a refinement step is necessary to make them assort with the density of all the vertices of the filling patch well, specifically including two stages: triangle splitting and edge swapping. Figure 5: Minimum are triangulation. (**a–f**) Six different filling schemes. 1. Triangle splitting. Triangle splitting is to partition the big triangle into three sub-triangles. As shown in Figure 6, blue dots and red lines represent the hole boundary vertices and edges respectively. Faces \(f_{3,4,5},f_{2,3,5},f_{1,2,5},f_{1,5,6}\) are the initial filling triangles.