# Triangular Mesh Surface Subdivision Based on Graph Neural Network
## 3 Mesh Subdivision Based on Graph Neural Network
### Graph Neural Network Subdivision Framework  
For each mesh vertex in M1', a corresponding mesh patch containing a fixed number of vertices is generated, and the mesh patches are further converted into graph data forms, including adjacency matrices and graph node features. The mesh vertices in the patch correspond to the graph nodes one to one in the conversion process. Here, the features of each graph node include the vertex coordinates, vertex normal vectors, average area of the one-ring adjacent faces, number of one-ring adjacent faces, and differential vector of vertices. Among them, the one-ring neighborhood information is used to characterize the mesh's local face density and local resolution. Meanwhile, the vertex differential vector is obtained by the difference between the vertex and the centroid of each vertex in the one-ring neighborhood.  
The study shows that the neural network has difficulty learning spatial transformation, so it is necessary to use algorithms to realize the spatial transformation of patches. First, the patch is moved to the position of the central vertex. Then, the tensor voting strategy [36] is used to generate the transformation matrix Ri corresponding to each patch:  
\[Ti=\sum_{t\in N_{t}(i)}\mu_{t}n^{\prime}_{t}n^{\prime T}_{t} \tag{1}\]  
where \(N_{t}(i)\) are all the adjacent triangles of the center vertex i in the patch, \(\mu_{t}=(A_{t}/A_{m})\exp(-||c_{t}-p_{i}||/\sigma)\), \(A_{t}\) is the area of the triangle t, \(A_{m}\) is the maximum value of the triangle area in \(N_{t}(i)\), \(c_{t}\) is the centroid coordinate of the triangle t, \(p_{i}\) is the coordinates of the vertex i at the center of the patch, and \(\sigma\) is one-third of the length of the cube's side. It defines the adjacent space of each vertex. \(n^{\prime}_{t}=2(n_{t}\cdot w_{t})w_{t}-n_{t}\), where \(w_{t}=normalize\{(c_{t}-p_{i})\times n_{t}\}\times(c_{t}-p_{i})\).  
Ti is a positive semidefinite matrix, which can be spectrally decomposed into  
\[T_{i}=\lambda_{1}e_{1}e_{1}^{T}+\lambda_{2}e_{2}e_{2}^{T}+\lambda_{3}e_{3}e_{3 }^{T} \tag{2}\]where \(\lambda_{1}\geq\lambda_{2}\geq\lambda_{3}\), the rotation matrix is constructed as \(R_{i}=[e_{1},e_{2},e_{3}]\), and the vertex coordinates of each patch are multiplied by \(R_{i}^{-1}\). Using tensor voting strategies transforms each patch into an aligned space, significantly reducing the complexity of the network learning.  
The vertex coordinates and the average area of the adjacent faces of the vertex's one-ring neighborhood are scaled according to the maximum radius of the patch. Finally, the features are converted from global to local space to ensure the algorithm's translation, rotation, and scale invariance. The graph neural network will finally output a displacement vector nf for each patch. The obtained nf needs to be transformed back into the global coordinate system to adjust the position of the mesh M1' to obtain a subdivided mesh M1. The above subdivision cycle is repeated until the termination condition is reached. Figure 4 shows the algorithm flow of the neural subdivision of a one-time graph.