# Repair of Voids in Multi-Labeled Triangular Mesh
## 4 Method
### Search for Voids  
The void searching stage aims to search for all the connected triangle facet sets that satisfy the void characteristics from the generated multi-labeled mesh \(\mathbf{LM}\). From the point of view of graph theory, each set of connected triangular facets can be regarded as a maximum connected sub-graph organized by the topological relationship of mesh vertexes and triangular facets. Based on the idea of graph theory, a virtual graph \(\mathbf{G}(\mathbf{V},\mathbf{B})\) is defined by taking the mesh vertexes as the nodes \(\mathbf{V}\) of the graph and taking the triangular facets as the edges \(\mathbf{B}\) of the graph. To quickly search for quasi-voids, the topological adjacency relationship  
Figure 4: An example of a multi-labeled mesh combined by general meshes without labels: (**a**) two simple input meshes; (**b**) labels of mesh 1; (**c**) labels of mesh 2; (**d**) labels of the multi-labeled mesh. between nodes and edges in the virtual graph should be constructed in advance. For the virtual graph \(G(V,B)\), one node corresponds to multiple edges, and one edge corresponds to three nodes. Since the quasi-voids is a set of connected triangular facets in the multi-labeled mesh, the topological relationship of the triangular facets associated with each mesh vertex can be recorded directly by traversing the facet array. As mentioned above, to accurately search for the voids, the original multi-labeled mesh \(LM\) should be separated into connected multi-labeled sub-meshes \(LM_{j}(j=1,2,\ldots,m)\), which is similar to the process of separating an unconnected graph into multiple connected sub-graphs. Based on the virtual graph \(G(V,B)\), the BFS method of graph theory can be directly used to obtain the connected sub-graphs \(G_{j}(V_{j},B_{j})\left(j=1,2,\ldots,m\right)\). It is worth noting that as the vertex array of \(LM_{j}\) is different from the vertex array of \(LM\), the new vertex indices should be recorded in the process of separating the sub-graphs to correct the vertex indices of the triangular facets in the multi-labeled sub-meshes. As mentioned above, since the quasi-voids is a set of connected triangular facets with zero labels, the quasi-voids can be regarded as the connected sub-graphs in which the connectivity is judged based on the labels rather than the spatial positions in the virtual graph. Therefore, for each connected sub-graph \(G_{j}(V_{j},B_{j})\), the improved BFS method can also be used to search for the quasi-voids \(S_{T}\). Three mesh vertexes of a triangle facet are used as the initial nodes of BFS, and the vertexes of the mesh are breadth-first traversed according to the topological relationship of the virtual graph and the labels of the triangular facets. Finally, all sets of connected triangular facets \(S_{T}\) containing zero labels are obtained. The pseudo-code of the algorithm flow for searching for voids is shown in Algorithm 2 (Search for voids). ```
Input: Multi-labeled mesh \(LM\) Output: Voids \(VO_{j,k}(j=1,2,\ldots,m,\ k=1,2,\ldots,n)\)  Construct virtual graph \(G(V,B)\) and topological relationship for \(LM\). Divide \(LM\) into connected multi-labeled sub-meshes \(LM_{j}(j=1,2,\ldots,m)\) using the BFS method. foreach\(LM_{j}(j=1,2,\ldots,m)\)do  Construct virtual graph \(G_{j}\big{(}V_{j},B_{j}\big{)}\) and topological relationship for \(LM_{j}\). Initialize an array \(Mark_{k}\) to record the visited state of \(t\) in \(LM_{j}\). foreach\(t\in LM_{j}\)do \(Mark_{t}=0\) endfor  Initialize an array \(VO_{j}\) to store voids in \(LM_{j};k=0\). foreach\(t\in LM_{j}\)do if\(Mark_{t}=0\)then if\(t_{pos}=0\)then \(k\gets k+1\)  Initialize an empty void \(VO_{j,k}\). Initialize an empty triangular facet set \(S_{T}\). Push \(t\) to \(S_{T}\). Search for connected triangular facets \(T\) with zero label corresponding to \(t\) using the BFS method. foreach\(t^{\prime}\in T\)do  Push \(t^{\prime}\) to \(S_{T}\). \(Mark_{t^{\prime}}=1\) endfor if\(S_{T}\) is a true void then  Push \(S_{T}\) to \(VO_{j,k}\).