## 3 Method
### The Delaunay Mesh Simplification Algorithm  
The complexity of a mesh will increase because of the newly inserted vertices according to the vertex inserting operation. An improved vertex collapsing operation is designed to conquer this drawback. The requirement for the improved vertex collapsing operation is that the local Delaunay property should be preserved in the non-connected domain. We assume that the original mesh is a Delaunay mesh, and the all edges in the set of hollow edges satisfied the local Delaunay property. As shown in Figure 5a, a hollow would be created if a vertex was deleted, and an improved vertex collapsing operation is designed to fill the hollow created by the vertex deletion, whose output is still a Delaunay mesh. The principle of the improved operation is shown in Figure 5b. The edge \(e_{ij}\) is in the set of hollow-edges, and the set of vertices \(V\) is all the vertices that are located in the hollow-edges. We assume that \(e_{ij}\) is a directed edge with the certain direction from vertex \(v_{i}\) to vertex \(v_{j}\). From the principle of the empty geodesic circumcircle property, for any triangle containing edge \(e_{ij}\), there are no other vertices in its circumcircle. Thus, the key of vertices collapsing operation is to find the minimum distance between the circumcenter \(O\) of a triangle t and the edge \(e_{ij}\). The specific situation is represented as shown in Figure 5b, where \(O_{1}\) is the circumcenter of \(t_{ijk}\), and the distance from \(O_{1}\) to \(e_{ij}\) is the shortest; then, the triangle \(t_{ijk}\) will satisfy the empty geodesic circumcircle property. Setting the direction of an edge and finding a vertex to the left of \(e_{ij}\) can avoid errors in the results because of the concave vertex just like \(v_{k}\). After all the edges in the set of hollow-edges rebuild the required vertices, the hollow would be patched. The local-Delaunay property of the interior edges, which are inserted after hollow-patching, could be preserved as well. It is obvious that the improved vertex collapsing operation could be able to simplify a Delaunay mesh. Even if there are NLD edges in the original mesh, this operation can still work on the vertex \(v_{i}\) as long as the edges \(e_{jk}\in D(v_{i})\) satisfy the local Delaunay property. Therefore, a simplification algorithm based on minimal volume destruction can be designed. The pseudo code is named as the pseudo-code Algorithm 2, where the iterative cost of \(v_{i}\) is set as the volume of \(\Omega(v_{i})\) (see Figure 6). Firstly, we classify vertex \(v_{i}\) as the non-collapsible and collapsible vertex according to the number of NLD edges in \(D(v_{i})\), respectively. If there are no NLD edges in \(D(v_{i})\), the vertex \(v_{i}\) is classified as the collapsible vertex. In this cases, all edges \(e_{jk}\in D(v_{i})\) satisfy the local Delaunay property, and the improved vertex collapsing operation is worked on \(v_{i}\), which will not destruct the local Delaunay property of all edges in \(D(v_{i})\). On the contrary, if there are NLD edges in \(D(v_{i})\), the improved vertex inserting operation would choose suitable locations on the NLD edge for newly inserted vertices. Then, a hybrid mechanism combined the improved vertex inserting operation and vertex collapsing operation will repeat until the number of vertices in the simplified mesh DM matches the user-defined value. Figure 5: (a) Schematic diagram of hole filling; (b) principle of vertex collapsing. ```
Input: Arbitrary closed triangle Mesh \(M=(V,E,F)\) Output: A simplified Delaunay Mesh \(DM=(V_{D},E_{D},F_{D})\) with \(N\) vertices
1 FunctioncalCost(vert):
2\(num\_of\_NLD\leftarrow\)is_NLD(e \(\in\Omega(vert)\)); triangles \(\leftarrow\) hollowPatching(vert);
3\(volume\gets 0\);
4 for\(t\):trianglesdo
5\(volume\gets get\_volume(t,vert)\) ;
6
7 end for
8 return\(volume\) - \(num\_of\_NLD\);
9
10 Initialize
11 the control factor \(\delta\);
12 the priority queue \(Q\) of the all NLD edges.